Gaußsches Eliminationsverfahren

Gaußsches Eliminationsverfahren

Das Gaußsche Eliminationsverfahren ist ein schematisches Verfahren zur Bestimmung der Lösungsmenge von linearen Gleichungssystemenen. Es wurde um 1850 von Carl Friedrich Gauß aufgestellt. Der Algorithmus gehört zu den wichtigsten numerischen Verfahren der Mathematik. Für diesen Algorithmus spricht heute unter anderem die einfache Implementierbarkeit in Computern.

Ein Lineares Gleichungssystem hat die Form:

Der Algorithmus wird in zwei Etappen gegliedert.

Vorwärtselimination
Rückwärtseinsetzen

Im ersten Schritt wird das Gleichungssystem in die Dreiecksform gebracht. Das heißt, dass die Elemente unter der Hauptdiagonalen, das sind im obigen Beispiel und , Null sein müssen. Die Umformung erfolgt wie beim Additionsverfahren.

Im zweiten Schritt werden von der letzten Zeile ausgehend die Variablen ausgerechnet und in die darüberliegende Zeile eingesetzt.

Ein lineares Gleichungssystemen kann eindeutig, mehrdeutig oder gar nicht lösbar sein. Die Unterscheidung in diese Fälle ist nach der ersten Etappe des Verfahrens möglich. Dazu wird die letzte Zeile betrachtet (siehe weiter unten).

Beispiel:

 x + 2y + 3z = 2  hier: , ,  und 
 x +  y +  z = 2
3x + 3y +  z = 0

Es werden schematisch nur die Koeffizienten (a, b, c, e) geschrieben:

1 2 3 2 1 1 1 2 3 3 1 0

Jetzt muss man so umformen, dass und Null werden. Man muss dafür Vielfache der ersten Gleichung zur zweiten und dritten Gleichung addieren. Das heißt für die 2. Zeile:

die 1. Zeile mit (-1) multiplizieren

1*(-1)= -1 und dann zur zweiten Zeile addieren

--> 1+(-1)=0 =

2*(-1)= -2 und dann zur zweiten Zeile addieren --> 1+(-2)= -1 =

3*(-1)= -3 und dann zur zweiten Zeile addieren --> 1+(-3)= -2 =

2*(-1)= -2 und dann zur zweiten Zeile addieren --> 2+(-2)=0 =

Damit Null wird muss man die erste Zeile mit (-3) multiplizieren, dann geht es wie in der 2. Zeile weiter.

1 2 3 2 0 -1 -2 0 0 -3 -8 -6

Um Null werden zu lassen muss man ein vielfaches der zweiten Zeile zur 3. Zeile addieren. Das heißt in diesem Fall:
-3+(-3)*(-1)= 0 (Man muss mit -3 multiplizieren)
-8+(-3)*(-2)= -2
-6+(-3)* 0 = -6

1 2 3 2 0 -1 -2 0 0 0 -2 -6

Nach dieser Zeile kann (siehe oben) über die Lösbarkeit entschieden werden.

Das Gleichungssystem ist:

eindeutig lösbar, wenn dort steht: 0 .. 0 x y | x,y ungleich 0
mehrdeutig lösbar, wenn dort steht: 0 .. 0 0 0 | nur mehr Nullen in einer Zeile (muß nicht die letzte sein)
gar nicht lösbar, wenn dort steht: 0 .. 0 0 y | y ungleich 0

Wenn Mehrdeutigkeit auftritt, so gibt die Position der Zeile mit lauter Nullen (von unten gezählt) an, wieviele Parameter für die Lösungen frei wählbar sind. Ist – im Extremfall – bereits die erste Zeile nur mit Nullen gefüllt, wie hier:

0x + 0y + 0z  = 0

so können für alle 3 Werte beliebige Zahlen eingesetzt werden.

Weiter im Beispiel:

Die letzte Zeile bedeutet

-2z = -6, also z = 3,

damit ergibt sich für die zweite Zeile

-1y -2z = 0, also y = -6

und weiter

x = 5,

also als Lösungsmenge die Menge mit dem Element

(5; -6; 3).