Gleichungssystem mit dem Gauß-Algorithmus lösen

Die Aufgabe

Lösen Sie das LGS streng nach dem in der Vorlesung angegebenen Algorithmus nach Gauß ohne Spaltenoperationen und mit Rückwärtseinsetzen.

A = \begin{bmatrix} 1 & 2 & 1 \\ 2 & 3 & 0 \\ -1 & -2 & 1 \end{bmatrix}, \quad b = \begin{pmatrix} 8 \\ 8 \\ 2 \end{pmatrix}.

Gegeben sind eine Matrix $A$ mit drei Zeilen und drei Spalten und ein Vektor $b$ mit drei Zahlen. Gesucht ist der Vektor $x$ mit drei Unbekannten $x_1$ , $x_2$ , $x_3$ , für den $A \cdot x = b$ gilt.

Das ist ein lineares Gleichungssystem (LGS): drei Gleichungen, drei Unbekannte. Zeile für Zeile ausgeschrieben lautet es:

\begin{aligned} x_1 + 2x_2 + x_3 &= 8 \\ 2x_1 + 3x_2 \phantom{{}+x_3} &= 8 \\ -x_1 - 2x_2 + x_3 &= 2 \end{aligned}

„Streng nach dem Algorithmus“ heißt: Wir halten uns an das Verfahren der Vorlesung (Skript Lineare Algebra und Geometrie, Kapitel 3.3). Es steht in Schritt 2 vollständig da. „Ohne Spaltenoperationen“ heißt: Wir verändern nur Zeilen, nie Spalten. „Mit Rückwärtseinsetzen“ heißt: Die Unbekannten werden am Ende von unten nach oben berechnet.

So gehen wir vor:

Das LGS als Tabelle $(A|b)$ aufschreiben.
Die Regeln des Algorithmus lesen und das erste Diagonalelement prüfen.
Nullen unter der Diagonale erzeugen: $\text{II} - 2 \cdot \text{I}$ , dann $\text{III} + \text{I}$ , dann prüfen, ob in der zweiten Spalte noch etwas zu tun ist.
Rückwärtseinsetzen: zuerst $x_3$ , dann $x_2$ , dann $x_1$ .
Probe in den drei ursprünglichen Gleichungen.

Merke: Der Algorithmus hat zwei Hälften. Erst Zeilen so umformen, dass links unten nur Nullen stehen (Dreiecksform). Dann von der letzten Zeile nach oben auflösen.

Das LGS als Tabelle (A|b) schreiben

Zeile I, II, III sind die drei Gleichungen

(A|b) = \left(\begin{array}{ccc|c} 1 & 2 & 1 & 8 \\ 2 & 3 & 0 & 8 \\ -1 & -2 & 1 & 2 \end{array}\right) \begin{array}{l} \text{I} \\ \text{II} \\ \text{III} \end{array}

Beim Rechnen stören die Buchstaben $x_1$ , $x_2$ , $x_3$ und die Plus- und Gleichheitszeichen. Wichtig sind nur die Zahlen davor. Darum schreibt man sie als Tabelle: links die Zahlen von $A$ , rechts hinter einem senkrechten Strich die Zahlen von $b$ . Diese Tabelle heißt erweiterte Matrix und wird $(A|b)$ geschrieben.

Jede Zeile ist eine Gleichung. Die erste Spalte gehört zu $x_1$ , die zweite zu $x_2$ , die dritte zu $x_3$ . In der zweiten Gleichung kommt kein $x_3$ vor, dort steht darum eine $0$ .

Die Zeilen bekommen die Namen I, II und III. Damit lässt sich später genau sagen, welche Zeile mit welcher verrechnet wird.

Die Regeln des Algorithmus und das erste Diagonalelement

Skript · Algorithmus nach Gauß, erste Hälfte

Für $i = 1$ bis $n - 1$ : Prüfe, ob $a_{ii} \neq 0$ ist; falls nicht, Zeilentausch. Für $j = i + 1$ bis $n$ :

(\text{neue Zeile})_j = (\text{alte Zeile})_j - \frac{a_{ji}}{a_{ii}} \cdot (\text{alte Zeile})_i

Hier ist $n = 3$ . Die Prüfung für $i = 1$ : $a_{11}$ ist die Zahl in Zeile I, Spalte 1.

Erstes Diagonalelement

a_{11} = 1 \neq 0

Das Skript erlaubt für $(A|b)$ drei elementare Umformungen: zwei Zeilen vertauschen, eine Zeile mit einer Zahl $k \neq 0$ malnehmen und ein Vielfaches einer Zeile zu einer anderen Zeile addieren. Das Skript zeigt auch: Solche Zeilenumformungen ändern die Lösung des Gleichungssystems nicht. Beim Vertauschen steht nur die Reihenfolge der Gleichungen anders. Wir benutzen hier nur das Abziehen eines Vielfachen einer Zeile von einer anderen und, falls nötig, das Vertauschen.

Spaltenumformungen verbietet die Aufgabe. Sie würden die Zuordnung der Spalten zu $x_1$ , $x_2$ , $x_3$ durcheinanderbringen.

Das Ziel ist die obere Dreiecksform: Unter der Diagonale (von links oben nach rechts unten) stehen nur Nullen. Der Algorithmus geht dafür die Diagonalelemente $a_{ii}$ von $i = 1$ bis $i = n - 1$ durch, hier also $i = 1$ und $i = 2$ . Mit $n$ ist die Zahl der Unbekannten gemeint, hier $n = 3$ .

Die Buchstaben der Formel unten: $i$ ist die Nummer der Spalte, die gerade bearbeitet wird. $j$ ist die Nummer der Zeile, die gerade verändert wird. Mit $a_{ji}$ ist die Zahl in Zeile $j$ und Spalte $i$ gemeint, mit $a_{ii}$ die Zahl in Zeile $i$ und Spalte $i$ . Der Bruch $a_{ji}/a_{ii}$ sagt, wie oft Zeile $i$ von Zeile $j$ abgezogen wird.

Wichtig: $a_{ij}$ ist immer die Zahl, wie sie in der Matrix gerade dasteht, also nach den bisherigen Umformungen und nicht in der ursprünglichen Matrix $A$ . Beim zweiten Durchlauf ist $a_{22}$ darum nicht mehr $3$ wie in $A$ , sondern $-1$ .

Bei jedem $i$ wird zuerst geprüft, ob $a_{ii}$ ungleich 0 ist. Es wird gleich als Nenner eines Bruchs gebraucht, und durch 0 darf man nicht teilen. Ist es 0, tauscht man die Zeile mit einer Zeile weiter unten.

Hier ist $a_{11} = 1$ , also gibt es nichts zu tauschen.

	x₁	x₂	x₃	rechts
I	1	2	1	8
II	2	3	0	8
III	−1	−2	1	2

	x₁	x₂	x₃	rechts
I	1	2	1	8
II	0	−1	−2	−8
III	−1	−2	1	2

	x₁	x₂	x₃	rechts
I	1	2	1	8
II	0	−1	−2	−8
III	0	0	2	10

Gleichungssystem mit dem Gauß-Algorithmus lösen

Die Aufgabe

Das LGS als Tabelle (A|b) schreiben

Die Regeln des Algorithmus und das erste Diagonalelement

Die Matrix in drei Zuständen

Abbildung 1Die Matrix in drei Zuständen

Schritt 0Die Aufgabe

Schritt 1Das LGS als Tabelle (A|b) schreiben

Schritt 2Die Regeln des Algorithmus und das erste Diagonalelement

Die Matrix in drei Zuständen

Abbildung 1Die Matrix in drei Zuständen

Die Aufgabe

Das LGS als Tabelle (A|b) schreiben

Die Regeln des Algorithmus und das erste Diagonalelement