Matheseiten-Überblick
Rechner für lineare Gleichungssysteme
interaktive Beispiele zum Gaußschen Verfahren
zurück

Kommentiertes Beispiel für das Gaußsche Eliminationsverfahren

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:

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”.

Der Gaußsche Algorithmus
  1. Bringe die Gleichungen in Standarform (siehe oben) und stelle die Koeffizientenmatrix auf.
    Setze i=1.
  2. Falls in der i. Zeile die Zahl in der i. Spalte 0 ist, tausche diese Zeile mit einer Zeile unterhalb aus, bei der in der i. Spalte eine Zahl steht. Falls keine solche Zeile existiert, ist das Gleichungssystem nicht eindeutig oder auch gar nicht lösbar.
  3. Dividiere die i. Zeile durch die Zahl, in ihrer i. Spalte. Das Diagonalelement (i. Zeile, i. Spalte) wird dadurch 1.
  4. Subtrahiere zu allen anderen Zeilen j (j≠i) nun ein geeignetes Vielfaches der Zeile i, so daß die Zahl in der i. Spalte der j. Zeile 0 wird. (Siehe dazu das Beispiel oben.) Danach darf in der i. Spalte nur noch in der i. Zeile eine 1 stehen, sonst stehen nur noch Nullen in dieser Spalte.
  5. Falls i<n, erhöhe i um eins und gehe zurück zu B, sonst weiter bei F.
  6. Lies in der letzten Spalte die Lösungen ab.

 

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  0  0  0  2  -26   auf, mit der man da schon in allen anderen Gleichungen die letzte Spalte zu Null machen kann. (Das entspricht dem sofortigen Einsetzen des Zahlenwertes für die Variable in allen Gleichungen, sobald man den Wert kennt!)

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