Das gaußsche Eliminationsverfahren oder einfach Gauß-Verfahren (nach Carl Friedrich Gauß) ist ein Algorithmus aus den mathematischen Teilgebieten der linearen Algebra und der Numerik. Es ist ein wichtiges Verfahren zum Lösen von linearen Gleichungssystemen und beruht darauf, dass Äquivalenzumformungen zwar das Gleichungssystem ändern, aber die Lösung erhalten. Dies erlaubt es, jedes eindeutig lösbare Gleichungssystem auf Stufenform zu bringen, an der die Lösung durch sukzessive Elimination der Unbekannten leicht ermittelt oder die Lösungsmenge abgelesen werden kann.
Die Anzahl der benötigten Operationen ist bei einer -Matrix von der Größenordnung . In seiner Grundform ist der Algorithmus aus numerischer Sicht anfällig für Rundungsfehler. Durch eine Umstellung der Gleichungen, die Pivotisierung, wird das Verfahren stabil. Damit stellt das gaußsche Eliminationsverfahren das Standardlösungsverfahren für allgemeine lineare Gleichungssysteme dar und ist Teil aller wesentlichen Programmbibliotheken für numerische lineare Algebra wie NAG, IMSL und LAPACK.
Erklärung Ein lineares Gleichungssystem mit drei Gleichungen und drei Unbekannten und rechter Seite hat die Form:
Der Algorithmus zur Berechnung der Variablen , und lässt sich in zwei Etappen einteilen: Vorwärtselimination, Rückwärtseinsetzen (Rücksubstitution).
Im ersten Schritt wird das Gleichungssystem auf Stufenform gebracht. Stufenform heißt, dass pro Zeile mindestens eine Variable weniger auftritt, also mindestens eine Variable eliminiert wird. Im obigen Gleichungssystem würde man , und eliminieren, in der dritten Zeile ist dann nur noch die Variable :
Zum Erreichen der Stufenform werden elementare Zeilenumformungen benutzt, mit Hilfe derer das Gleichungssystem in ein neues transformiert wird, welches aber dieselbe Lösungsmenge besitzt. Ausreichend sind zwei Arten von elementaren Zeilenumformungen: Eine Zeile oder das Vielfache einer Zeile zu einer anderen Zeile addieren. Zwei Zeilen vertauschen. Das Verfahren besteht dann darin, angefangen in der ersten Spalte mit Umformungen der ersten Art durch geschicktes Addieren von Vielfachen der ersten Zeile alle Einträge bis auf den ersten zu null zu machen. Dies wird dann in der so modifizierten zweiten Spalte fortgesetzt, wobei diesmal Vielfache der zweiten Zeile zu den folgenden Zeilen addiert werden und so weiter. Dieser Schritt funktioniert nur, wenn das Diagonalelement der aktuellen Spalte nicht null ist. In so einem Fall ist die zweite Art der Zeilenumformung nötig, da durch eine Zeilenvertauschung ein Nichtnulleintrag auf der Diagonale erzeugt werden kann. Mit Hilfe dieser beiden Arten von Umformungen ist es möglich, jedes lineare Gleichungssystem auf Stufenform zu bringen.
Eine weitere Art der elementaren Umformung ist das Vertauschen von Spalten. Diese wird zur Durchführung des Algorithmus nicht benötigt, aber manchmal in Computerprogrammen aus Stabilitätsgründen eingesetzt. Dabei wird die Position der Variablen im Gleichungssystem geändert. Beim Rechnen per Kopf ist manchmal noch die Multiplikation einer Zeile mit einer Zahl nützlich, etwa um komplizierte Brüche zu vermeiden. Dies verursacht zusätzlichen Rechenaufwand und ist deswegen in Computerprogrammen keine Option und ändert ferner die Determinante der Koeffizientenmatrix, was theoretische Nachteile mit sich bringt.
Im zweiten Schritt des Verfahrens, dem Rückwärtseinsetzen, werden ausgehend von der letzten Zeile, in der nur noch eine Variable auftaucht, die Variablen ausgerechnet und in die darüberliegende Zeile eingesetzt.
Eine Alternative hierzu ist der Gauß-Jordan-Algorithmus, bei dem nicht nur die unteren Teile eliminiert werden, sondern auch die oberen, so dass eine Diagonalform entsteht, bei der das Rückwärtseinsetzen entfällt.
Eine weitere Möglichkeit ist die Benutzung einer erweiterten Matrix mit drei Untermatrizen, in denen mit fortschreitender Rechnung die Permutationsmatrix für die Zeilenvertauschungen zwecks Pivotisierung und die Dreiecksmatrizen für die LR-Zerlegung entstehen, siehe Äquivalenztransformation / Gauß’sches Eliminationsverfahren.
Beispiel , hier: , , und
Zur besseren Übersichtlichkeit werden die Koeffizienten des linearen Gleichungssystems in die mit erweiterte Koeffizientenmatrix geschrieben:
Jetzt wird so umgeformt, dass und null werden, indem man geeignete Vielfache der ersten Gleichung zur zweiten und dritten Gleichung addiert. Den entsprechenden Multiplikator erhält man, indem man das zu eliminierende Element (als erstes ) durch das Pivotelement teilt (für also und für dann ). Da die beiden Elemente und null werden sollen, werden die beiden Multiplikatoren jeweils mit multipliziert.
Zur zweiten Zeile wird also das -fache und zur dritten Zeile das -fache der ersten Zeile addiert. Damit null wird, wird im nächsten Schritt ein Vielfaches der neuen zweiten Zeile zur neuen dritten Zeile addiert, in diesem Fall das -fache:
Datei:Gauss Eliminierung.svg
Falls die Zahl, durch die zur Berechnung des Multiplikators dividiert wird (hier für die ersten beiden Zeilen die Zahl , beim dritten Mal die Zahl ), null ist, wird diese Zeile mit einer weiter unten liegenden vertauscht. Die letzte Zeile bedeutet . Diese Gleichung ist einfach lösbar und liefert . Damit ergibt sich für die zweite Zeile , mit also und weiter . Damit sind alle Variablen berechnet: , und .
Kontrolle durch Zeilensumme Die Umformungen können durch das Berechnen der Zeilensumme kontrolliert werden.
Datei:Gauss Zeilensumme.svg
Hier wurde in der letzten Spalte die Summe aller Elemente der jeweiligen Zeile angeschrieben. Für die erste Zeile ist die Zeilensumme . Da an der ersten Zeile keine Umformungen durchgeführt werden, ändert sich ihre Zeilensumme nicht. Bei der ersten Umformung dieses Gleichungssystems wird zur zweiten Zeile das -fache der ersten addiert. Macht man das auch für die Zeilensumme, so gilt . Dieses Ergebnis ist die Zeilensumme der umgeformten zweiten Zeile . Zur Überprüfung der Rechnungen kann man also die Umformungen an der Zeilensumme durchführen. Sind alle Rechnungen korrekt, muss sich die Zeilensumme der umgeformten Zeile ergeben.
Pivotisierung Das gaußsche Eliminationsverfahren ist im Allgemeinen nicht ohne Zeilenvertauschungen durchführbar. Ersetzt man im obigen Beispiel durch , so kann der Algorithmus ohne Zeilenvertauschung gar nicht starten. Zur Abhilfe wählt man ein Element der ersten Spalte der Koeffizientenmatrix, das sogenannte Pivotelement, welches ungleich 0 ist. +Wahl des Pivot 0 2 3 4 1 1 1 2 3 3 1 0
Danach vertauscht man die erste Zeile mit der Pivotzeile: +Zeilenvertauschung 1 1 1 2 0 2 3 4 3 3 1 0
Für die Rechnung per Hand ist es hilfreich, eine 1 oder minus 1 als Pivotelement zu wählen, damit im weiteren Verlauf des Verfahrens keine Brüche entstehen. Für die Berechnung mit Hilfe eines Computers ist es sinnvoll, das betragsgrößte Element zu wählen, um einen möglichst stabilen Algorithmus zu erhalten. Wählt man das Pivotelement in der aktuellen Spalte, spricht man von Spaltenpivotisierung. Alternativ kann man das Pivot auch in der aktuellen Zeile wählen. +Wahl des Pivot 0 2 3 4 1 1 1 2 3 3 1 0
In diesem Fall werden entsprechend die Spalten getauscht. +Spaltenvertauschung 2 0 3 4 1 1 1 2 3 3 1 0
Beim Rückwärtseinsetzen ist dabei zu beachten, dass die Variablen ihre Position im Gleichungssystem geändert haben. Wählt man als Pivot das betragsgrößte Element der gesamten Restmatrix, so spricht man von vollständiger Pivotisierung beziehungsweise Totalpivotisierung. Dafür sind im Allgemeinen sowohl Zeilen- als auch Spaltenvertauschungen notwendig.
Pivotisierung ist ohne nennenswerten Zusatzaufwand durchführbar, wenn nicht die Einträge der Matrix und der rechten Seite vertauscht, sondern die Vertauschungen in einem Indexvektor gespeichert werden.
LR-Zerlegung Einführendes Beispiel Will man das Lösen eines quadratischen eindeutig lösbaren Gleichungssystems als Computerprogramm umsetzen, bietet es sich an, den Gaußalgorithmus als LR-Zerlegung (auch LU-Zerlegung oder Dreieckszerlegung genannt) zu interpretieren. Dies ist eine Zerlegung der regulären Matrix in das Produkt einer linken unteren, normierten Dreiecksmatrix (links, beziehungsweise Englisch „left“, oder auch „lower“) und einer rechten oberen Dreiecksmatrix (rechts, bzw. Englisch „right“, oder auch „upper“, und dann mit bezeichnet). Das folgende Beispiel zeigt dies:
Dabei dient die Matrix dem Speichern der benötigten Umformungsschritte, die Multiplikationen mit Frobeniusmatrizen entsprechen, und hat die oben erwähnte Stufenform. Das zeigt die Existenz der Zerlegung. Um Eindeutigkeit zu erreichen, werden die Diagonalelemente der Matrix als 1 festgelegt. Die Umformungsschritte zu speichern hat den Vorteil, dass für verschiedene „rechte Seiten“ das Gleichungssystem effizient durch Vorwärts- und Rückwärtseinsetzen gelöst werden kann.
Die im Allgemeinen benötigten Zeilenvertauschungen können durch eine Permutationsmatrix beschrieben werden:
Eine Permutationsmatrix ist eine Matrix, die aus der Einheitsmatrix durch eine beliebige Anzahl an Zeilenvertauschungen entsteht und somit weiterhin nur aus Nullen und Einsen besteht.
Existenzsatz Für jede reguläre Matrix existiert eine Permutationsmatrix , eine untere, normierte Dreiecksmatrix und eine obere Dreiecksmatrix , sodass gilt: . Algorithmus Der Algorithmus zur Berechnung der Matrizen für ein vorgegebenes lautet wie folgt.
Es werden Matrixumformungen vollzogen (). Dabei führt man die Umformungsmatrizen ein:
Dabei wurden neue Hilfsmatrizen eingeführt:
Beachte: stellt den -ten Basisvektor dar in wurde nur eine Zeile der Einheitsmatrix mit einer anderen vertauscht muss so gewählt werden, dass den betragsmäßig größten Wert für alle Elemente aus der Teilspalte hat
Man benötigt noch weitere Hilfsmatrizen :
Nun können die gewünschten Matrizen angegeben werden:
Algorithmus in Pseudocode Ohne Pivotisierung, L, R out-of-place Der folgende Algorithmus führt eine LR-Zerlegung der Matrix A ohne Pivotisierung aus, indem er simultan L und R außerhalb (out-of-place) von A erzeugt:
Eingabe: Matrix A
// Initialisierung R := A L := E_n
// n-1 Iterationsschritte for i := 1 to n-1 // Zeilen der Restmatrix werden durchlaufen for k := i+1 to n // Berechnung von L L(k,i) := R(k,i) / R(i,i) // Achtung: vorher Prüfung auf Nullwerte notwendig // Spalten der Restmatrix werden durchlaufen for j := i to n // Berechnung von R R(k,j) := R(k,j) - L(k,i) * R(i,j)
Ausgabe: Matrix L, Matrix R
Ohne Pivotisierung, L, R in-place Alternativ ist (aus möglichem Interesse an Speichereffizienz) eine simultane Entwicklung von L und R direkt in A möglich (in-place), welcher durch folgenden Algorithmus beschrieben wird:
Eingabe: Matrix A
// n-1 Iterationsschritte for i := 1 to n-1 // Zeilen der Restmatrix werden durchlaufen for k := i+1 to n // Berechnung von L A(k,i) := A(k,i) / A(i,i) // Achtung: vorher Prüfung auf Nullwerte notwendig // Spalten der Restmatrix werden durchlaufen for j := i+1 to n // Berechnung von R A(k,j) := A(k,j) - A(k,i) * A(i,j)
Ausgabe: Matrix A (in modifizierter Form)
Mit Pivotisierung Der folgende Algorithmus führt eine LR-Zerlegung der Matrix mit Pivotisierung aus. Er unterscheidet sich von den Algorithmen ohne Pivotisierung nur durch mögliche Zeilenvertauschung:
Eingabe: Matrix
// n-1 Iterationsschritte for k := 1 to n-1 // Pivotisierung // finde betragsmäßig größtes Element in k-ter Spalte = k
for i := k+1 to n if < > = i
// vertausche Zeilen <Erstelle > <Vertausche Zeilen k,> // Rest analog zu obigen Algorithmen <Rest >
Ausgabe: Matrix L, Matrix R, Matrix P
Lösen eines linearen Gleichungssystems Das ursprüngliche LGS wird mittels der LR-Zerlegung nun wie folgt vereinfacht:
Nun definiert man die folgenden Hilfsvariablen
Folglich hat sich das LGS in eine vereinfachte Struktur gewandelt:
Diese können leicht durch Vorwärts- beziehungsweise Rückwärtseinsetzen gelöst werden.
Vorwärtseinsetzen