Gaußsches Eliminationsverfahren

Das Gaußsche Eliminationsverfahren ist ein schematisches Verfahren zur Bestimmung der Lösung von linearen Gleichungssystemen. Es wurde um 1850 von Carl Friedrich Gauß aufgestellt. Der Algorithmus ist ein wichtiges Verfahren zum Lösen von Gleichungssystemen. Er eignet sich nicht zur numerischen Berechnung. Da er schlechte Stabilitätseigenschaften hat, werden in der Praxis häufig andere Verfahren verwendet.

Ein lineares Gleichungssystem mit drei Unbekannten hat die Form:

$a_{1}x+a_{2}y+a_{3}z=e_{1}$;

$b_{1}x+b_{2}y+b_{3}z=e_{2}$;

$c_{1}x+c_{2}y+c_{3}z=e_{3}$.

Der Algorithmus zur Berechnung der Variablen x, y und z lässt sich in zwei Etappen einteilen:

1. Vorwärtselimination,
2. Rückwärtseinsetzen.

Im ersten Schritt wird das Gleichungssystem in die Stufenform gebracht. Das heißt, dass pro Zeile mindestens eine Variable weniger auftritt, also mindestens eine Variable eliminert wird indem die Zeile so umgeformt wird, dass der Koeffizient der Variablen Null ist. Im obigen Beispiel würde man $b_{1},c_{1}$ und $c_{2}$ eliminieren, in der dritten Zeile ist dann nur noch die Unbekannte $x_{3}$. Zum Erreichen der Stufenform sind drei Umformungen zulässig: Es können (komplette) Zeilen vertauscht werden, eine Zeile kann mit einer von Null verschiedenen Zahl multipliziert werden oder es darf, wie beim Additionsverfahren, eine Zeile oder das vielfache einer Zeile zu einer Anderen addiert werden.

Im zweiten Schritt werden von der letzten Zeile, in der sich nur noch eine 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).

Algorithmus in Pseudocode

Der folgenden Algorithmus führt nur die Vorwärtselimination aus.

a: Matrix (nicht die erweiterte Matrix!)

gauss_elimination(a)
1  von spalte $\leftarrow$ 1 bis anzahl_spalten(a) - 1
2      führe aus von zeile $\leftarrow$ spalte + 1 bis anzahl_zeilen(a)
3          führe aus von i $\leftarrow$ spalte + 1 bis anzahl_spalten(a)
4              führe aus a[zeile][i] $\leftarrow$ a[zeile][i] - (a[zeile][spalte] / a[spalte][spalte]) * a[spalte][i]

Beispiel

1. x + 2y + 3z = 2, hier: $a_{1}=1$, $a_{2}=2$, $a_{3}=3$ und $e_{1}=2$
2. x + y + z = 2
3. 3x + 3y + z = 0

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

${\begin{pmatrix}1&2&3&|&2\\1&1&1&|&2\\3&3&1&|&0\end{pmatrix}}$

Jetzt wird so umgeformt, dass $b_{1}$ und $c_{1}$ Null werden, indem man geeignete Vielfache der ersten Gleichung zur zweiten und dritten Gleichung addiert.

Zu Zeile 2 wird das (-1)-fache und zu Zeile 3 das (-3)-fache von Zeile 1 addiert:

${\begin{pmatrix}1&\ 2&\ 3&|&\ 2\\0&-1&-2&|&\ 0\\0&-3&-8&|&-6\end{pmatrix}}$

Damit $c_{2}$ Null wird, wird ein Vielfaches von Zeile 2 zu Zeile 3 addiert, in diesem Fall das (-3)-fache:

${\begin{pmatrix}1&\ 2&\ 3&|&\ 2\\0&-1&-2&|&\ 0\\0&\ 0&-2&|&-6\end{pmatrix}}$

Falls dabei ein Diagonalelement Null ist und deshalb darunter liegende Elemente durch Addition von Vielfachen nicht geändert werden können, werden vorher, falls möglich, Zeilen vertauscht.

Am Ende kann durch Betrachten der letzten Zeile über die Lösbarkeit entschieden werden. Das Gleichungssystem ist:

1. eindeutig lösbar, wenn das Diagonalelement nicht Null ist,
2. mehrdeutig lösbar, wenn nur Nullen enthalten sind,
3. gar nicht lösbar, wenn das Diagonalelement Null und das letzte Element nicht Null ist.

(Diese Bedingungen beziehen sich nur auf den Fall, dass die Anzahl der Gleichungen mit der Anzahl der Veränderlichen übereinstimmt.)

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

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle 0x+0y+0z = 0} ,

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

Weiter im Beispiel:

Die letzte Zeile bedeutet

$-2z=-6$ .

Diese Gleichung ist einfach lösbar und $z=3$.

Damit ergibt sich für die zweite Zeile

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

und weiter

$x=5$ .

Damit sind alle "Unbekannten" (x, y, z) berechnet:

$x=5\quad y=-6\quad z=3$ .

Wird im ersten Schritt die Matrix weiter umgeformt, bis die Lösung direkt abgelesen werden kann, nennt man das Verfahren Gauß-Jordan-Algorithmus.

Ein weiteres Verfahren zur Lösung linearer Gleichungssysteme ist die Cramersche Regel.

Numerik

Die Laufzeit des Algorithmus ist kubisch, d.h. die Anzahl arithmetischer Operationen ist bei einer nxn-Matrix durch O(n³) beschränkt.

Der Algorithmus sollte auf einem Rechner nur für Gleichungssysteme mit wenigen Gleichungen und Unbekannten verwendet werden. Die algorithmische Umsetzung erfolgt mittels der LR-Zerlegung.