Gauß-Algorithmus

Gauß-Algorithmus Definition

Mit dem Gauß-Algorithmus können lineare Gleichungssysteme (LGS) mit mehr als 2 Variablen und Gleichungen gelöst werden (es geht auch bei 2 Variablen, aber dafür gibt es andere Verfahren wie z. B. das Additionsverfahren).

Dabei werden Mehrfache einer Gleichung zu einer anderen Gleichung addiert, von dieser abgezogen oder es werden Gleichungen vertauscht. Das funktioniert, da alle Operationen immer auf beiden Seiten der Gleichung vorgenommen werden.

Der Gauß-Algorithmus überführt ein LGS durch die genannten Operationen in ein äquivalentes LGS in Zeilenstufenform bzw. Dreiecksform, das sich dann leicht lösen lässt.

Alternative Begriffe: Gauß-Elimination, Gauß-Eliminationsverfahren, Gauß-Verfahren, Gaußscher Algorithmus, Gaußsches Eliminationsverfahren, Gaußsches Verfahren.

Beispiel

Beispiel: Lineares Gleichungssystem mit Gauß-Algorithmus lösen

Gleichungssystem (3 Gleichungen mit 3 Variablen x, y und z):

x + y = 3

2x - 2y = -2

2x + z = 5

Die Koeffizienten (die Zahlen vor den x, y und z) überträgt man zunächst in eine (erweiterte) Koeffizientenmatrix (dabei kann man die linke und die rechte Seite der Gleichungen durch einen senkrechten Strich hervorheben):

$$\left[ \begin{array}{ccc|c} 1&1&0&3 \\ 2&-2&0&-2 \\ 2&0&1&5 \end{array} \right]$$

Anschließend werden die Zahlen unter der von links oben nach rechts unten laufenden Hauptdiagonalen der linken Seite (hier mit den Zahlen 1, -2 und 1) nach und nach durch Umformungen auf Null gebracht.

1. Schritt: Zu der 2. Zeile wird das -2-fache der ersten Zeile addiert (bzw. das 2-fache subtrahiert). Ergebnis:

$$\left[ \begin{array}{ccc|c} 1&1&0&3 \\ 0&-4&0&-8 \\ 2&0&1&5 \end{array} \right]$$

In der 2. Zeile steht jetzt bereits "schön" der Koeffizient für y in Höhe von -4 alleine auf der linken Seite; -4y = - 8, d. h. y = 2.

2. Schritt: Zu der 3. Zeile wird das -2-fache der ersten Zeile addiert (bzw. das 2-fache subtrahiert). Ergebnis:

$$\left[ \begin{array}{ccc|c} 1&1&0&3 \\ 0&-4&0&-8 \\ 0&-2&1&-1 \end{array} \right]$$

3. Schritt: Zu der 3. Zeile wird das -1/2-fache der zweiten Zeile addiert (bzw. das 1/2-fache subtrahiert). Ergebnis:

$$\left[ \begin{array}{ccc|c} 1&1&0&3 \\ 0&-4&0&-8 \\ 0&0&1&3 \end{array} \right]$$

Man hat jetzt die Zeilenstufenform bzw. Dreiecksform erreicht: die Zahlen unter der Hauptdiagonalen (hier mit den Zahlen 1, -4 und 1; durch die Umformungen hat sich die Hauptdiagonale gegenüber der Ausgangsmatrix geändert) sind 0.

Aus der letzten Zeile kann man direkt ablesen, dass z = 3 ist (die letzte Zeile ausgeschrieben lautet: 0x + 0y + 1z = 3).

Da 2x + z = 5 ist (3. Gleichung), gilt: 2x + 3 = 5; 2x = 2; x = 1.

Die Lösung des Gleichungssystems ist x = 1, y= 2, z = 3.

Kontrolle:

1 + 2 = 3

2 × 1 - 2 × 2 = 2 - 4 = -2

2 × 1 + 3 = 2 + 3 = 5.

Die hier gezeigten Zeilenumformungen sind nicht die einzigen möglichen; es gibt viele Wege zum Ziel (und eventuell auch kürzere).