12. Lineare Gleichungssysteme

Lösbarkeit von LGS

Um eine eindeutige Lösung zu erhalten, muss man auf jeden Fall $n$ Gleichungen für $n$ Unbekannte stellen. (Dadurch ist die eindeutige Lösbarkeit aber leider noch nicht garantiert!)

Graphisch suchen wir den Schnittpunkt zweier Geraden:

Recht einfach lässt sich das folgende LGS lösen

$\def\arraystretch{1.25} \begin{array}{rrcc}2x_1& -x_2 & = &-2\\& \frac{3}{2}x_2 & = &2\end{array}$

Wir können sofort $x_2=\frac{4}{3}$ ablesen und das in die erste Gleichung einsetzen

was $x_1=-\frac{1}{3}$ gibt.

Gauß'sches Eliminationsverfahren

Schön wäre es natürlich, wenn alle unsere LGS in einer solchen Dreiecksform vorliegen würden. Glücklicherweise können wir ein allgemeines LGS leicht in eine solche Form bringen. Diesen Zustand des zweiten Systems können wir aus dem ersten System leicht herstellen, indem wir die erste Gleichung mit $\frac{1}{2}$ multiplizieren und das von der zweiten Gleichung abziehen - wir eliminieren mittels der ersten Gleichung $x_1$ aus der zweiten Gleichung.

Wir wollen ein LGS äquivalent umformen (ohne Änderung der Lösungsmenge) durch folgende Strategie:

• Mittels der ersten Zeile $x_1$ aus Zeilen $2\ldots n$ eliminieren

• Mittels der zweiten Zeile $x_2$ aus Zeilen $3\ldots n$ eliminieren

• …

• Mittels der $n-1$-ten Zeile $x_{n-1}$ aus Zeile $n$ eliminieren

• Aus dem so entstandenen gestaffelten Dreieckssystem kann man nacheinander $x_n$, $x_{n-1}$,… $x_2$ und $x_1$ ausrechnen.

Eine Komplikation kann auftreten: wenn im Schritt "$x_i$ eliminieren" der (derzeitige) Koeffizient $a_{i,i}$ Null ist, gelingt die Elimination nicht.

In diesem Fall Zeile $i$ mit einer darunter liegenden Zeile vertauschen, bei der in Spalte $i$ keine Null steht (gibt es keine solche Zeile, gibt es keine eindeutige Lösung des LGS).

Um Schreibarbeit zu sparen und zur Implementierung auf dem Computer, lässt man die $x_i$ und das $=$ weg. Speichere nur Koeffizienten $a_{i,j}$ und $b_i$.

Beispiel

Bei dem linearen Gleichungssystem

$\def\arraystretch{1.25} \begin{array}{rrrcc}x_1& -x_2 & & = &2\\-x_1 & +x_2 & +x_3 & = &1\\2x_1 & & -x_3 & = & 3\end{array}$

sieht der Algorithmus so aus:

$\def\arraystretch{1.25} \left(\begin{array}{ccc} 1 & -1 & 0\\ -1 & 1 & 1 \\ 2 & 0 & -1 \end{array}\left|\begin{array}{c} 2\\ 1\\ 3\end{array}\right.\right) \leadsto$$\def\arraystretch{1.25} \left(\begin{array}{ccc} 1 & -1 & 0\\ 0 & 0 & 1 \\ 2 & 0 & -1 \end{array}\left|\begin{array}{c} 2\\ 3\\ 3\end{array}\right.\right)$

$\def\arraystretch{1.25} \leadsto \left(\begin{array}{ccc} 1 & -1 & 0\\ 0 & 0 & 1 \\ 0 & 2 & -1 \end{array}\left|\begin{array}{c} 2\\ 3\\ -1\end{array}\right.\right)$$\def\arraystretch{1.25} \leadsto \left(\begin{array}{ccc} 1 & -1 & 0\\ 0 & 2 & -1 \\ 0 & 0 & 1 \end{array}\left|\begin{array}{c} 2\\ -1\\ 3\end{array}\right.\right)$

Wer an dieser Stelle Probleme hat, die Lösung abzulesen, kann sich das einfach wieder als Gleichungssystem hinschreiben:

$\def\arraystretch{1.25} \begin{array}{rrrcc}x_1& -x_2 & & = &2\\& +2x_2 & -x_3 & = &-1\\& & +x_3 & = & 3\end{array}$

gibt $x_3=3$, $x_2 = (-1 + 3)/2 = 1$ und $x_1 = 2 + 1 = 3$.