Matheseiten-Überblick
Rechner für lineare Gleichungssysteme
interaktive Beispiele zum Gaußschen Verfahren
zurück
Auf dieser Seite wird an einem Beispiel das Gaußsche Verfahren zum Lösen von linearen Gleichungssystemen erläutert, das sich insbesondere für programmierte Abläufe und für Gleichungssysteme mit vielen Unbekannten eignet.
Gesucht sei die Lösung für das lineare Gleichungssystem
6 = -12z - 10x -5x = -17 - 4w + 8z + 2y 23 = 4z + 5x -10x - 16z = 2 - 4w
Zuerst werden die Gleichungen so umgeformt, daß alle Variablen links vom Gleichheitszeichen stehen und das absolute Glied (also die Zahl ohne Variable) rechts:
I: 6 = -12z - 10x | +10x +12z -6
10x + 12z = -6
II: -5x = -17 - 4w + 8z + 2y | +4w -2y -8z
4w - 5x - 2y - 8z = -17
III: 23 = 4z + 5x | -5x -4z -23
-5x - 4z = -23
IV: -10x - 16z = 2 - 4w | +4w
4w - 10x - 16z = 2
Die so umgeformten Gleichungen werden nun so untereinander geschrieben, daß entsprechende Variablen untereinander stehen:
10x + 12z = -6
4w - 5x - 2y - 8z = -17
-5x - 4z = -23
4w - 10x - 16z = 2
Man vereinfacht sich die Schreibarbeit, indem man nur die Zahlen erfaßt, also die Koeffizienten (Faktoren vor den Variablen) aus der linken Seite und die absoluten Zahlen aus der rechten Seite der Gleichungen. Dabei müssen die Vorzeichen beachtet und übernommen werden. Für alle fehlenden Variablen wird eine Null geschrieben:
0 10 0 12 -6
4 -5 -2 -8 -17
0 -5 0 -4 -23
4 -10 0 -16 2
Eine derartige Zahlentabelle nennt man Matrix; und da es sich um die Koeffizienten eines linearen Gleichungssystems handel, heißt diese hier Koeffizientenmatrix.
Durch geeignete Umformungen versucht man, diese Matrix in die Form
1 0 0 0 a
0 1 0 0 b
0 0 1 0 c
0 0 0 1 d
zu überführen, wobei a, b, c und d für irgendwelche Zahlen stehen, die sich an diesen Stellen ergeben. Es sind allerdings keine Zahlen, die uns nicht interessieren, sondern es handelt sich bei ihnen um nichts geringeres als die Lösungen, nach denen wir eigentlich suchen. Denn die erste Zeile steht ja für w = a, die zweite für x = b, usw.
Man darf zu diesem Zwecke folgende Umformungtypen verwenden:
Ein Beispiel für den dritten Typus: Von der 4. Zeile
In der ersten Spalte muß von 4 das Vierfache von 0 abgezogen werden, d.h. die 4 bleibt.
in der zweiten Spalte muß von -10 das Vierfache von -5 abgezogen werden: -10 - 4·(-5) ergibt 10.
in der dritten Spalte: 0 - 4·0 = 0
in der vierten Spalte: -16 - 4·(-4) = 0
in der fünften Spalte: 2 - 4·(-23) = 94
Warum sind diese Umformungen möglich?
Das Vertauschen von Zeilen entspricht dem Umnumerieren der Gleichungen. Das verändert
die Lösungsmenge sicher nicht.
Das Multiplizieren von Gleichungen mit einer Zahl verändert bekanntlicherweise
auch die Lösungsmenge nicht.
Der dritte Typus bedarf einiger Überlegung: Bei Gleichungen sind die Terme links und rechts
des Gleichheitszeichens wertgleich. Wenn man nun auf beiden Seiten Gleiches addiert,
bleibt die Waage ausgewogen; d.h. man kann auf beiden Seiten der Gleichung die jeweiligen
Seiten einer anderen Gleichung (oder entsprechende Vielfache davon) addieren, ohne die
Aussage zu verändern, denn man addiert auf beiden Seiten denselben Wert.
Um nun das Ziel zu erreichen, geht man schrittweise und systematisch vor. Das Verfahren folgt einem schematischen Ablaufplan (Algorithmus), der nach Carl Friedrich Gauß auch Gaußscher Algorithmus oder Gaußsches Eliminationsverfahren genannt wird. Eliminieren heißt auslöschen; und tatsächlich werden nacheinander, d.h. zeilenweise, alle Zahlen zu Null gemacht (also ausgelöscht), die in unserer Ergebnismatrix Null sein sollen.
Im Ablaufplan verwenden wir für die Anzahl der Zeilen (d.h. der Gleichungen bzw. Unbekannten)
den Buchstaben n, damit der Algorithmus allgemeingültig ist (n nimmt Bezug auf die Tatsache,
daß diese Anzahl immer eine Natürliche Zahl ist). In unserem Beispiel ist n=4.
Für die jeweilige Zeile verwenden wir den Buchstaben i (von Index). Das
i durchläuft in diesem Verfahren systematisch nacheinander alle Zahlen von 1 bis 4.
Man nennt eine solche Variable auch „Laufvariable”.
Ich führe das Verfahren nun anhand dieses Ablaufplanes für das Beispiel durch.
Schritt A: i=1
0 10 0 12 -6
4 -5 -2 -8 -17
0 -5 0 -4 -23
4 -10 0 -16 2
Schritt B: Da in der 1. Zeile in der 1. Spalte eine 0 steht, vertausche die erste und die
zweite Zeile.
4 -5 -2 -8 -17
0 10 0 12 -6
0 -5 0 -4 -23
4 -10 0 -16 2
Schritt C: Nun dividiere jede Zahl in der 1. Zeile durch 4 (die Zahl in der 1. Spalte der
ersten Zeile):
1 -1,25 -0,5 -2 -4,25
0 10 0 12 -6
0 -5 0 -4 -23
4 -10 0 -16 2
Nun steht in der ersten Zeile in der ersten Spalte eine 1. Im folgenden
Schritt D müssen alle anderen Zahlen in dieser Spalte zu 0 gemacht werden. Dies
geschieht durch Addition (Subtraktion) geeigneter Vielfacher der ersten
Zeile.
Nur in der vierten Zeile steht keine 0, sondern eine 4.
Man bekommt die Null, wenn man das 4fache der ersten Zeile subtrahiert:
Rechne: 4-4·1=0 -10-4·(-1,25)=-10+5=-5 0-4·(-0,5)=2
-16-4·(-2)=-16+8=-8 2-4·(-4,25)=2+17=19
1 -1,25 -0,5 -2 -4,25
0 10 0 12 -6
0 -5 0 -4 -23
0 -5 2 -8 19
Schritt E: Da i=1<n=4, erhöhe i um 1: i=2 und fahre fort bei...
Schritt B: In der zweiten Zeile steht in der zweiten Spalte keine 0. Also ist kein Tausch nötig.
Schritt C: Dividiere die zweite Zeile durch 10, so daß dort eine 1 steht:
1 -1,25 -0,5 -2 -4,25
0 1 0 1,2 -0,6
0 -5 0 -4 -23
0 -5 2 -8 19
Schritt D: Addiere/subtrahiere geeignete Vielfache der zweiten Zeile zu den anderen, so daß
dort in der zweiten Spalte überall 0 steht:
addiere zur ersten Zeile das 1,25fache der zweiten Zeile,
addiere zur dritte Zeile das 5fache der zweiten Zeile,
addiere zur vierten Zeile das 5fache der zweiten Zeile:
1 0 -0,5 -0,5 -5
0 1 0 1,2 -0,6
0 0 0 2 -26
0 0 2 -2 16
Schritt E: Erhöhe i um 1 (i=3<4) und gehe zu B.
Schritt B: Weil in der 3. Zeile in der 3. Spalte 0 steht, vertausche die vierte mit der dritten
Zeile:
1 0 -0,5 -0,5 -5
0 1 0 1,2 -0,6
0 0 2 -2 16
0 0 0 2 -26
Schritt C: Dividiere die 3. Zeile durch 2:
1 0 -0,5 -0,5 -5
0 1 0 1,2 -0,6
0 0 1 -1 8
0 0 0 2 -26
Schritt D: Addiere zur ersten Zeile das 0,5fache der dritten, damit die -0,5
in der dritten Spalte der ersten Zeile verschwindet.
Rechne: -0,5+0,5·1=0 -0,5+0,5·(-1)=-0,5-0,5=-1 -5+0,5·(8)=-1
1 0 0 -1 -1
0 1 0 1,2 -0,6
0 0 1 -1 8
0 0 0 2 -26
Schritt E: i=4 und zurück zu
Schritt B: vierte Spalte in vierter Zeile OK. (Tauschen wäre auch nicht mehr möglich,
weil unterhalb keine Zeile mehr existiert.)
Schritt C: Dividiere die vierte Zeile durch 2:
1 0 0 -1 -1
0 1 0 1,2 -0,6
0 0 1 -1 8
0 0 0 1 -13
Schritt D: Addiere die vierte zur ersten Zeile,
subtrahiere das 1,2fache der vierten von der zweiten Zeile,
addiere die vierte zur dritten Zeile:
1 0 0 0 -14
0 1 0 0 15
0 0 1 0 -5
0 0 0 1 -13
Schritt E: i=4=n, daher weiter bei...
Schritt F: Lies die Lösungen in der letzten Spalte ab:
w = -14
x = 15
y = -5
z = -13
Zur Erinnerung: Die Zahlen 1 0 0 0 -14 in der ersten Zeile stehen für die
Gleichung 1w + 0x + 0y + 0z = -14. Das ist vereinfacht: w = -14.
In dieser schematischen Form läßt sich dieser Algorithmus sehr gut in Computerprogramme übersetzen. Das Skript des Rechners für lineare Gleichungssysteme auf diesen Seiten (→hier klicken) funktioniert exakt nach diesem Algorithmus. Dort kann man sich auch die einzelnen Lösungsschritte für beliebig eingebbare lineare Gleichungssysteme anschauen.
Man kann das Verfahren allerdings auch intelligent an passenden Stellen abkürzen
oder vereinfachen. Zum Beispiel bietet
sich oftmals an, eine bestimmte Variable bereits vor ihrer Zeit im Algorithmus
zu eliminieren, wenn sie nämlich bereits in einer Gleichung alleine steht.
Es taucht beispielsweise relativ früh die Zeile
Das Dividieren der Zeilen durch ihr Diagonalelement läßt sich unter Umständen gewinnbringend bis zum Schluß verzögern, um nämlich Brüche oder „Kommazahlen” zu vermeiden. Wenn man im Beispiel die vertauschte erste Zeile erst ganz zuletzt durch 4 teilt und die zweite zunächst durch 2 und am Ende durch 5, kann man vollständig mit ganzen Zahlen rechnen und hat zudem einfachere Subtraktionen, was erheblich übersichtlicher ist:
0 10 0 12 -6 Zeilen I und II vertauschen 4 -5 -2 -8 -17 0 -5 0 -4 -23 4 -10 0 -16 2 4 -5 -2 -8 -17 0 10 0 12 -6 0 -5 0 -4 -23 4 -10 0 -16 2 | -I 4 -5 -2 -8 -17 0 10 0 12 -6 | :2 0 -5 0 -4 -23 0 -5 2 -8 19 4 -5 -2 -8 -17 | +II 0 5 0 6 -3 0 -5 0 -4 -23 | +II 0 -5 2 -8 19 | +II 4 0 -2 -2 -20 0 5 0 6 -3 0 0 0 2 -26 Zeilen III und IV vertauschen 0 0 2 -2 16 4 0 -2 -2 -20 | +IV 0 5 0 6 -3 | -3·IV 0 0 2 -2 16 | +IV 0 0 0 2 -26 4 0 -2 0 -46 | +III 0 5 0 0 75 0 0 2 0 -10 0 0 0 2 -26 4 0 0 0 -56 | :4 0 5 0 0 75 | :5 0 0 2 0 -10 | :2 0 0 0 2 -26 | :2 1 0 0 0 -14 0 1 0 0 15 0 0 1 0 -5 0 0 0 1 -13
© Arndt Brünner, 12. 11. 2003 — Version: 17. 11. 2003
eMail
→ lineare Gleichungssysteme berechnen
→ Additionsverfahren
→ Einsetzungs-, Gleichsetzungsverfahren