Zusammenfassung – Gauß-Verfahren
Das Ziel – ein LGS systematisch lösen
Wenn man ein LGS mit vielen Gleichungen und vielen Variablen lösen möchte, sollte man dabei systematisch vorgehen, um den Überblick nicht zu verlieren.
Das Gauß-Verfahren bzw. Gaußsche-Eliminationsverfahren ist ein Verfahren, mit dem man beliebige lineare Gleichungssysteme systematisch lösen kann.
Das Gaußsche Eliminationsverfahren ist ein algorithmisches Verfahren. D.h., es kann von einem Computer durchgeführt werden. Jedes Computeralgebrasystem benutzt ein solches Verfahren beim Lösen von linearen Gleichungssystemen.
Ein Beispiel
Beispiel
Gegeben: ein LGS
$\begin{array}{lrcrcrcr} [1] &\quad 4x_1 & - & 8x_2 & - & 8x_3 & = & 4 \\ [2] &\quad 2x_1 & + & x_2 & + & 3x_3 & = & 3 \\ [3] &\quad -3x_1 & + & 3x_2 & - & x_3 & = & 2 \end{array}$
Gesucht: die Lösung(en) des LGS
Schritt A: Umwandlung des LGS in Stufenform:
$\begin{array}{lrcrcrcr} [1] &\quad 4x_1 & - & 8x_2 & - & 8x_3 & = & 4 \\ [2] &\quad 2x_1 & + & x_2 & + & 3x_3 & = & 3 \\ [3] &\quad -3x_1 & + & 3x_2 & - & x_3 & = & 2 \end{array}$
$[1] \leftarrow [1] \cdot (1/4)$
$\begin{array}{lrcrcrcr} [1] &\quad x_1 & - & 2x_2 & - & 2x_3 & = & 1 \\ [2] &\quad 2x_1 & + & x_2 & + & 3x_3 & = & 3 \\ [3] &\quad -3x_1 & + & 3x_2 & - & x_3 & = & 2 \end{array}$
$[2] \leftarrow [2] + [1] \cdot (-2)$
$\begin{array}{lrcrcrcr} [1] &\quad x_1 & - & 2x_2 & - & 2x_3 & = & 1 \\ [2] &\quad & & 5x_2 & + & 7x_3 & = & 1 \\ [3] &\quad -3x_1 & + & 3x_2 & - & x_3 & = & 2 \end{array}$
$[3] \leftarrow [3] + [1] \cdot 3$
$\begin{array}{lrcrcrcr} [1] &\quad x_1 & - & 2x_2 & - & 2x_3 & = & 1 \\ [2] &\quad & & 5x_2 & + & 7x_3 & = & 1 \\ [3] &\quad & &-3x_2 & - & 7x_3 & = & 5 \end{array}$
$[3] \leftarrow [3] + [2]$
$\begin{array}{lrcrcrcr} [1] &\quad x_1 & - & 2x_2 & - & 2x_3 & = & 1 \\ [2] &\quad & & 5x_2 & + & 7x_3 & = & 1 \\ [3] &\quad & & 2x_2 & & & = & 6 \end{array}$
Schritt B: Bestimmung der Lösung(en) des LGS in Stufenform:
Auflösen von [3] nach $x_2$ liefert $x_2 = 3$.
Einsetzen von $x_2 = 3$ in [2] und Auflösen nach $x_3$ liefert $x_3 = -2$.
Einsetzen von $x_2 = 3$ und $x_3 = -2$ in [1] und Auflösen nach $x_1$ liefert $x_1 = -3$.
Ergebnis: Die Lösung des vorgegebenen LGS lautet: $x_1 = -3$, $x_2 = 3$; $x_3 = -2$ bzw. $(x_1, x_2, x_3) = (-3, 3, -2)$.
Die Grundidee – ein LGS äquivalent umwandeln
Die Grundidee besteht darin, ein vorgegebenes LGS in Rechteckform mit Hilfe von Äquivalenzumformungen in ein LGS in Stufenform umzuwandeln.
Start: LGS in Rechteckform:
$\begin{array}{lrcrcrcr} [1] &\quad ...x_1 & + & ...x_2 & + & ...x_3 & = & ... \\ [2] &\quad ...x_1 & + & ...x_2 & + & ...x_3 & = & ... \\ [3] &\quad ...x_1 & + & ...x_2 & + & ...x_3 & = & ... \end{array}$
Ziel: LGS in Stufenform:
$\begin{array}{lrcrcrcr} [1] &\quad ...x_1 & + & ...x_2 & + & ...x_3 & = & ... \\ [2] &\quad 0x_1 & + & ...x_2 & + & ...x_3 & = & ... \\ [3] &\quad 0x_1 & + & 0x_2 & + & ...x_3 & = & ... \end{array}$
oder eine Variante wie z.B.:
$\begin{array}{lrcrcrcr} [1] &\quad ...x_1 & + & ...x_2 & + & ...x_3 & = & ... \\ [2] &\quad 0x_1 & + & ...x_2 & + & ...x_3 & = & ... \\ [3] &\quad 0x_1 & + & ...x_2 & + & 0x_3 & = & ... \end{array}$
Die Lösungen des LGS in Stufenform lassen sich direkt Schritt für Schritt bestimmen. Diese Lösungen sind dann auch die Lösungen des vorgegebenen LGS, da die Lösungsmenge bei den durchgeführten Äquivalenzumformungen nicht verändert wird.
Die Umformungen – Gleichungen multiplizieren und addieren
Beim Umwandeln eines vorgegebenen LGS sind folgende Äquivalenzumformungen erlaubt:
- eine Gleichung mit einer beliebigen reellen Zahl ungleich 0 multiplizieren (Beispiel: $[1] \leftarrow [1] \cdot 2$)
- eine Gleichung zu einer anderen hinzuaddieren (Beispiel: $[2] \leftarrow [1] + [2]$)
- eine Gleichung mit einer anderen vertauschen (Beispiel: $[3] \leftrightarrow [2]$)
- ... sowie Kombinationen dieser Operationen wie ...
- ein Vielfaches (ungleich 0) einer Gleichung zu einer anderen hinzuaddieren (Beispiel: $[3] \leftarrow [2] \cdot 4 + [3]$)
- ein Vielfaches (ungleich 0) einer Gleichung zu einem Vielfachen (ungleich 0) einer anderen Gleichung hinzuaddieren (Beispiel: $[3] \leftarrow [2] \cdot 4 + [3] \cdot (-1)$)
Diese Umformungen setzt man so ein, dass Variablen nach und nach eliminiert werden, bis man die gewünschte Stufenform erhält.
Anzahl der Lösungen
Es gibt drei Fälle zur Anzahl der Lösungen eines LGS:
- Wenn das LGS in Dreiecksform mindestens eine Widerspruchszeile aufweist (z.B. $3 = 7$), dann hat das LGS keine Lösung.
- Wenn das LS in Dreiecksform keine Widerspruchszeilen aufweist und die Anzahl der Variablen der Anzahl nichttrivialer Zeilen entspricht, dann ist das LGS eindeutig lösbar. Als triviale Zeilen gelten dabei solche, die immer erfüllt sind (z.B. $0=0$).
- Wenn das LS in Dreiecksform keine Widerspruchszeilen aufweist und die Anzahl der Variablen größer ist als die Anzahl nichttrivialer Zeilen, dann hat das LGS unendlich viele Lösungen.
Ein LGS mit weniger Gleichungen als Variablen heißt unterbestimmt.
Ein LGS mit mehr Gleichungen als Variablen heißt überbestimmt.
Beachte: Ein unterbestimmtes LGS hat immer unendlich viele oder keine Lösungen, da es nicht in eine widerspruchsfreie Dreiecksform mit der passenden Anzahl Gleichungen überführt werden kann. Ein überbestimmtes LGS kann alle drei Fälle bezüglich der Anzahl an Lösungen aufweisen.
