Lösen linearer Gleichungssysteme mit Gauß-Jordan-Algorithmus



In der Schule lernt man einige Verfahren zum Lösen eines linearen Gleichungssystems (LGS). Jeder hat schon mal von Einsetzungsverfahren gehört, aber nur wenige von Gauß-Jordan-Algorithmus.
Damit lässt sich ein LGS meistens schneller lösen als mit herkömmlichen Lösungsverfahren. Zudem spart man sich damit einiges an Schreibarbeit und macht folglich weniger Fehler, denn jeder weiß, dass je länger die Rechnung ist, um so mehr Fehler sich einschleichen.

Ich werde hier Anhand einiger Beispiele zeigen, wie Gauß-Jordan-Algorithmus funktioniert.

Matrixschreibweise

Ein typisches LGS:

-2a – 4b – 6c = 4
3a – b + 2c = 1
4a + 3c = 3

Zuerst schreibt man die Gleichungen in eine Matrixform um. Jede Zeile der Matrix enthält die Koeffizienten aller Unbekannten der jeweiligen Gleichung. Der Wert nach dem Trennstrich entspricht dem konstanten Term in einer Gleichung.

\left(\begin{array}{lll|r} -2 &  -4 &  -6 & 4 \\  3 & -1 &  2 & 1 \\ 4 &  0 & 3 & 3  \end{array}\right)

Durch diese Darstellung spart man sich etwas an Schreibarbeit und bekommt eine bessere Übersicht.

Elementare Zeilenumformungen

Die Matrixschreibweise ist erst mal nur eine andere Form des LGS, d.h. man kann darauf bereits aus der Schule bekannte Elementarumformungen anwenden. Konkret bedeutet es, dass man folgende Umformungen durchführen darf, ohne das sich dadurch die Lösung des LGS verändert:

  • Das Vertauschen zweier Zeilen
  • Das Multiplizieren einer Zeile mit einem Wert ungleich Null
  • Das Addieren des Vielfachen einer Zeile zu einer anderen Zeile

Gauß-Jordan-Algorithmus

Der Gauß-Jordan-Algorithmus sagt uns in welcher Reihenfolge wir die elementaren Zeilenumformungen anwenden müssen. Befolgt man diesen Anweisungen, so erhält man automatisch eine Lösung des LGS, vorausgesetzt das LGS ist lösbar.

Ablauf:

  1. Vertausche die Zeilen so, dass in der ersten Zeile an erster Stelle keine Null steht.
  2. Dividiere die erste Zeile durch die erste Zahl in dieser Zeile. Damit hat man an erster Stelle eine Eins stehen.
  3. Subtrahiere von der zweiten Zeile ein Vielfaches der ersten Zeile so, dass als Ergebnis in zweiten Zeile die erste Zahl zu Null wird. Wiederhole das Gleiche mit erster und dritter, erster und vierter, erster und n-ten Zeile.
    Nach diesem Schritt, steht in der ersten Spalte oben eine Eins und die restlichen Einträge sind Null.
  4. Denkt man sich die erste Spalte und die erste Zeile weg, so erhält man ein kleineres LGS. Wende jetzt den Algorithmus von vorne auf das kleinere LGS an.
    Ergebnis ist eine Treppenform der Matrix, insbesondere stehen unter der Diagonale nur Nullen.
  5. Wende die oberen Schritte von vorne an, mit der rechten unteren anstatt linken oberen Zahl als Startpunkt. Das Ergebnis ist eine Diagonalmatrix und die Zahlen rechts vom Trennstrich ist die Lösung des LGS.

Ein Beispiel Schritt für Schritt

Gegebenes LGS:

\left(\begin{array}{lll|r} -2 &  -4 &  -6 & 4 \\  3 & -1 &  2 & 1 \\ 4 &  0 & 3 & 3  \end{array}\right)

Schritt 1:
Nicht nötig.

Schritt 2:

Wir dividieren die erste Zeile durch -2.
Im Folgenden verwendete Kurzschreibweise: I = I /(-2)

\left(\begin{array}{lll|r} -2/(-2)  &  -4/(-2) &  -6/(-2) & 4/(-2) \\  3 & -1 &  2 & 1 \\ 4 &  0 & 3 & 3  \end{array}\right)

\left(\begin{array}{lll|r} 1  &  2 &  3 & -2 \\  3 & -1 &  2 & 1 \\ 4 &  0 & 3 & 3  \end{array}\right)

Schritt 3:

Damit die erste Zahl in der zweiten Zeile Null wird, müssen wir von der zweiten Zeile das dreifache der ersten Zeile abziehen.
II = II – 3*I

\left(\begin{array}{lll|r} 1  &  2 &  3 & -2 \\  3-3*1 & -1-3*2 &  2-3*3 & 1-3*(-2) \\ 4 &  0 & 3 & 3  \end{array}\right)

\left(\begin{array}{lll|r} 1  &  2 &  3 & -2 \\  0 & -7 &  -7 & 7 \\ 4 &  0 & 3 & 3  \end{array}\right)

Von der dritten Zeile muss das vierfache der ersten Zeile abgezogen werden.
III = III – 4*I

\left(\begin{array}{lll|r} 1  &  2 &  3 & -2 \\  0 & -7 &  -7 & 7 \\ 4-4*1 &  0-4*2 & 3-4*3 & 3-4*(-2)  \end{array}\right)

\left(\begin{array}{lll|r} 1  &  2 &  3 & -2 \\  0 & -7 &  -7 & 7 \\ 0 & -8 & -9 & 11  \end{array}\right)

Schritt 4:

Man denkt sich die erste Zeile und die erste Spalte weg und beginnt beim 1. Schritt.

Schritt 1:

Entfällt, weil in der zweiten Zeile an der zweiten Stelle bereits keine Null steht.

Schritt 2:

Wir müssten in der zweiten Zeile die zweite Zahl, also die -7 auf 1 bringen.
II = II / (-7)

\left(\begin{array}{lll|r} 1  &  2 &  3 & -2 \\  0 & 1 &  1 & -1 \\ 0 & -8 & -9 & 11  \end{array}\right)

Schritt 3:

Aus -8 muss 0 werden. Also: III = III -(-8)*II = III + 8*II

\left(\begin{array}{lll|r} 1  &  2 &  3 & -2 \\  0 & 1 &  1 & -1 \\ 0+8*0 & -8+8*1 & -9+8*2 & 11+8*(-1)  \end{array}\right)

\left(\begin{array}{lll|r} 1  &  2 &  3 & -2 \\  0 & 1 &  1 & -1 \\ 0 & 0 & -1 & 3  \end{array}\right)

An dieser Stelle sehen wir bereits, dass c=-3 ist. Man könnte jetzt a und b durch Einsetzen bekommen, aber das ist nicht der Sinn dieses Beispiels. Es geht weiter.

Schritt 5:

Die Matrix hat jetzt eine Treppenstufenform bzw. konkret sogar eine Dreiecksform. An dieser Stelle beginnt der Algorithmus von vorne mit unterer rechter Zahl (-1) als Ausgangspunkt.

Schritt 1:

Entfällt, da -1 ungleich Null ist.

Schritt 2:

III = III / (-1)

\left(\begin{array}{lll|r} 1  &  2 &  3 & -2 \\  0 & 1 &  1 & -1 \\ 0 & 0 & 1 & -3  \end{array}\right)

Schritt 3:

Wir wiederholen das Spiel in dem wir versuchen die Zahlen oberhalb der letzten unteren Zahl zu eliminieren.
I = I – 3*III
II = II – III

\left(\begin{array}{lll|r} 1-3*0  &  2-3*0 &  3-3*1 & -2-3*(-3) \\  0-0 & 1-0 &  1-0 & -1-(-3) \\ 0 & 0 & 1 & -3  \end{array}\right)

\left(\begin{array}{lll|r} 1  &  2 &  0 & 7 \\  0 & 1 & 0 & 2 \\ 0 & 0 & 1 & -3  \end{array}\right)

Schritt 4:

Man beginnt den Algorithmus von vorne mit 1 in der Mitte als Ausgangspunkt.

Schritt 1 und 2:

Entfallen.

Schritt 3:

I = I – 2*II

\left(\begin{array}{lll|r} 1-2*0  &  2-2*1 &  0-2*0 & 7-2*2 \\  0 & 1 & 0 & 2 \\ 0 & 0 & 1 & -3  \end{array}\right)

\left(\begin{array}{lll|r} 1  &  0 &  0 & 3 \\  0 & 1 & 0 & 2 \\ 0 & 0 & 1 & -3  \end{array}\right)

Damit hat die Matrix eine Diagonalform. Wir könnten auch schreiben:

1a + 0b + 0c = 3
0a + 1b + 0c = 2
0a + 0b + 1c = -3

Was direkt der Lösung a=3; b=2; c=-3 entspricht.

Wenn man die Zwischenschritte weg lässt, dann wird deutlich, wie wenig Schreibarbeit so ein Lösungsweg braucht.

Ein weiteres Beispiel

\left(\begin{array}{lll|r} -1  &  -5 &  0 & 12 \\  -1 & -4 & 0 & 8 \\ 0 & 2 & -1 & -13  \end{array}\right)

II = II – I

\left(\begin{array}{lll|r} -1  &  -5 &  0 & 12 \\  0 & 1 & 0 & -4 \\ 0 & 2 & -1 & -13  \end{array}\right)

III = III – 2*II

\left(\begin{array}{lll|r} -1  &  -5 &  0 & 12 \\  0 & 1 & 0 & -4 \\ 0 & 0 & -1 & -5  \end{array}\right)

I = I + 5*II

\left(\begin{array}{lll|r} -1  &  0 &  0 & -8 \\  0 & 1 & 0 & -4 \\ 0 & 0 & -1 & -5  \end{array}\right)

Somit ist die Lösung a=8; b=-4; c=5. Wie man sieht muss die erste Zahl nicht unbedingt auf Eins gebracht werden um weiter zu rechnen. Genauso wenig muss man im dritten Schritt immer subtrahieren. Man nutzt es so, wie es gerade am besten erscheint, Hauptsache man schafft stufenweise viele Nullen in der Matrix.

Wie man sieht ist die praktische Anwendung nicht besonders schwierig und vor allem zeitsparender als andere Verfahren, was besonders in einer Klausur von Bedeutung ist.




3 Kommentare zu “Lösen linearer Gleichungssysteme mit Gauß-Jordan-Algorithmus”

  1. Patrickam 25. Mai 2010 um 18:36 Uhr

    Achja sowas war noch ein Spaß in der Schule. Allerdings haben wir es unter dem Namen „Gaußsches Verfahren“ gelernt. Aber sehr richtig, das ist schon leicht anwendbar :)

  2. Maximam 25. Mai 2010 um 19:48 Uhr

    Was du wohl meinst ist Gaußsches Eliminationsverfahren.
    Gauß-Jordan-Algorithmus ist eine Erweiterung davon. Man kann damit nicht nur wie in diesem Beitrag gezeigt einfache LGS lösen, sondern auch anderen Operationen, wie zum Beispiel eine Basistransformation durchführen.

  3. Ibotsuam 31. Mai 2010 um 18:27 Uhr

    Ich dachte in erster Linie auch an das Gaußsches Eliminationsverfahren.
    Man merkt, dass dieser Algorithmus etwas mhr drauf hat. :D

Trackback URI | Kommentare als RSS

Einen Kommentar schreiben

XHTML: Du kannst folgende Tags verwenden: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <sub> <sup>

Hinweis: Ich behalte mir das Recht vor solche Kommentare, die Beleidigungen oder rechtswidrige Inhalte beinhalten erst nach einer Editierung freizugeben oder kommentarlos zu löschen. Ähnliches gilt auch für Kommentare die offensichtlich nur der Suchmaschinenoptimierung dienen.