Gaußsches Eliminationsverfahren

Jede Koeffizientenmatrix lässt sich durch Anwendung von elementaren Zeilenumformungen vom Typ A und B auf Zeilenstufenform und durch zusätzliche Verwendung von Typ C auf reduzierte Zeilenstufenform bringen. Die Zeilenstufenform ist i.a. nicht eindeutig, die reduzierte Zeilenstufenform hingegen ist stets eindeutig.

Erzeugung einer Zeilenstufenform

1. Starte mit der Koeffizientenmatrix mit Zeilen und reellen Einträgen .
2. Setze Spaltenindex auf die erste Nichtnullspalte. Falls keine solche existiert, beende Algorithmus und gib aktuelle Koeffizientenmatrix zurück.
3. Setze Zeilenindex auf eine Zeile, in der der EIntrag in der Spalte nicht ist.
4. Vertausche Zeile mit der ersten Zeile durch eine Elementare Zeilenumformungen > Typ B. Die resultierende Koeffizientenmatrix hat hiernach einen Eintrag .
5. Durchlaufe mit die Zeilen ab Index und addiere jeweils zur -ten Zeile das -fache der ersten Zeile durch eine Elementare Zeilenumformungen > Typ A. Die resultierende Koeffizientenmatrix hat hiernach die Einträge für und Nullspalten links der -ten Spalte.
6. Wiederhole die Schritte (2) bis (5) rekursiv mit der Teilmatrix, die duch Weglassen der ersten Zeile aus der Koeffizientenmatrix entsteht.

Das Verfahren bricht ab, wenn es keine Nichtnullspalte in der iterativ stets um eine Zeile kleiner werdenden Teilmatrix mehr gibt, spätestens, wenn die Teilmatrix keine Zeilen mehr besitzt.

Als Ergebnis liebt die Koeffizientenmatrix in einer Zeilenstufenform vor.

Erzeugung der reduzierten Zeilenstufenform

1. Starte mit einer Zeilenstufenform mit Zeilen und reellen Einträgen .
2. Setze Zeilenindex auf die letzte Nichtnullzeile. Falls keine solche existiert, beende Algorithmus und gib aktuelle Koeffizientenmatrix zurück.
3. Setze Spaltenindex auf den ersten Nichtnulleintrag , d.h. auf die Stufe der Zeile .
4. Multipliziere die Zeile mit dem Inversen durch eine Elementare Zeilenumformungen > Typ C. Die resultierende Koeffizientenmatrix hat hiernach den Eintrag bei der Stufe der Zeile .
5. Durchlaufe mit die Zeilen bis Index und addiere jeweils zur -ten Zeile das -fache der -ten Zeile durch eine Elementare Zeilenumformungen > Typ A. Die resultierende Koeffizientenmatrix hat hiernach die Einträge für in der -ten Spalte oberhalb der Stufe der -ten Zeile.
6. Wiederhole die Schritte (2) bis (5) rekursiv mit der Teilmatrix, die durch Weglassen der Zeilen ab Index aus der Koeffizientenmatrix entsteht.

Das Verfahren bricht ab, wenn es keine Nichtnullzeile in der interativ stets um mindestens eine Zeile kleiner werdenden Teilmatrix mehr gibt, spätestens wenn die Teilmatrix keine Zeilen mehr besitzt.

Als Ergebnis liegt die Koeffizientenmatrix in der eindeutig bestimmten reduzierten Zeilenstufenform vor.

Der selbe Algorithmus kann verwendet werden, um die (reduzierte) Zeilenstufenform der erweiterten Koeffizientenmatrix zu bestimmen: Die letzte Spalte mit den Einträgen ist dann wie die ersten Spaöten mit den Koeffizienten zu behandeln.