Gaußsche Elimination

In der Mathematik ist die Gaußsche Elimination , auch Zeilenreduktion genannt , ein Algorithmus zur Lösung linearer Gleichungssysteme . Sie besteht aus einer Folge zeilenweiser Operationen, die auf der entsprechenden Koeffizientenmatrix durchgeführt werden . Mit dieser Methode lassen sich auch der Rang einer Matrix, die Determinante einer quadratischen Matrix und die Inverse einer invertierbaren Matrix berechnen . Die Methode ist nach Carl Friedrich Gauß (1777–1855) benannt.

Um eine Zeilenreduktion an einer Matrix durchzuführen, verwendet man eine Folge elementarer Zeilenumformungen , um die Matrix so lange zu modifizieren, bis die linke untere Ecke der Matrix möglichst vollständig mit Nullen gefüllt ist. Es gibt drei Arten von elementaren Zeilenumformungen:

• zwei Reihen vertauschen,
• Multiplikation einer Zeile mit einer Zahl ungleich Null, und
• Eine Zeile zu einer anderen Zeile addieren.

Mithilfe dieser Operationen lässt sich eine Matrix stets in reduzierte Zeilenstufenform überführen : Jede von Null verschiedene Zeile steht über jeder Nullzeile, der erste Eintrag jeder von Null verschiedenen Zeile ist 1, die Spalten mit diesen führenden Einsen haben ansonsten alle Einträge 0, und die führende Eins jeder von Null verschiedenen Zeile steht rechts von der führenden Eins der vorherigen Zeile. Diese Form ist eindeutig; sie ist also unabhängig von der Reihenfolge der verwendeten Zeilenumformungen. Beispielsweise sind in der folgenden Abfolge von Zeilenumformungen (bei der im ersten und dritten Schritt jeweils zwei elementare Operationen auf unterschiedlichen Zeilen durchgeführt werden) die dritte und vierte Matrix diejenigen in Zeilenstufenform, und die letzte Matrix ist die eindeutige reduzierte Zeilenstufenform. $${\displaystyle {\begin{bmatrix}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{bmatrix}}\to {\begin{bmatrix}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{bmatrix}}}$$

Die Umwandlung einer Matrix in die reduzierte Zeilenstufenform mithilfe von Zeilenumformungen wird manchmal als bezeichnetGauß-Jordan-Elimination . In diesem Fall bezeichnet der BegriffGaußsche Eliminationden Prozess bis zum Erreichen deroberen Dreiecksform(unreduzierteZeilenstufenform. Aus Rechengründen ist es beim Lösen linearer Gleichungssysteme manchmal vorteilhaft, die Zeilenoperationen zu beenden, bevor die Matrix vollständig reduziert ist.

Die Zeilenreduktion nutzt elementare Zeilenumformungen und lässt sich in zwei Teile gliedern. Im ersten Teil (manchmal auch Vorwärtselimination genannt) wird ein gegebenes Gleichungssystem in Zeilenstufenform gebracht. Daraus lässt sich erkennen, ob es keine, eine eindeutige oder unendlich viele Lösungen gibt. Im zweiten Teil (manchmal auch Rückwärtssubstitution genannt ) werden so lange Zeilenumformungen angewendet, bis eine Lösung gefunden ist; mit anderen Worten, die Matrix wird in reduzierte Zeilenstufenform gebracht.

Ein weiterer Blickwinkel, der sich für die Analyse des Algorithmus als sehr nützlich erweist, ist, dass die Zeilenreduktion eine Matrixzerlegung der ursprünglichen Matrix erzeugt. Die elementaren Zeilenoperationen können als Multiplikation der ursprünglichen Matrix von links mit Elementarmatrizen betrachtet werden .

Alternativ kann eine Folge elementarer Operationen, die eine einzelne Zeile reduziert, als Multiplikation mit einer Frobenius-Matrix betrachtet werden . Der erste Teil des Algorithmus berechnet dann eine LU-Zerlegung , während der zweite Teil die ursprüngliche Matrix als Produkt einer eindeutig bestimmten invertierbaren Matrix und einer eindeutig bestimmten reduzierten Zeilenstufenmatrix schreibt.

Es gibt drei Arten von elementaren Zeilenoperationen, die auf die Zeilen einer Matrix angewendet werden können:

1. Zwei Reihen vertauschen.
2. Multiplikation einer Zeile mit einem Skalar ungleich Null .
3. Addition eines skalaren Vielfachen einer Zeile zu einer anderen.

Wenn die Matrix zu einem linearen Gleichungssystem gehört, verändern diese Operationen die Lösungsmenge nicht. Daher kann die Anwendung dieser Zeilenumformungen die Lösung eines linearen Gleichungssystems vereinfachen.

In jeder Zeile einer Matrix, die nicht nur aus Nullen besteht, wird der erste von Null verschiedene Eintrag als führendes Element (oder Pivotelement ) dieser Zeile bezeichnet. Befinden sich zwei führende Elemente in derselben Spalte, kann man eines dieser Elemente durch eine Zeilenumformung vom Typ 3 auf Null setzen. Durch Vertauschen der Zeilen lassen sich die Zeilen so anordnen, dass in jeder von Null verschiedenen Zeile das führende Element rechts vom führenden Element der darüberliegenden Zeile steht. In diesem Fall spricht man von Zeilenstufenform . In dieser Form enthält der linke untere Teil der Matrix nur Nullen, und alle Nullzeilen befinden sich unterhalb der Zeilen mit Nicht-Null-Einträgen. Der Begriff „Zeilenstufenform“ wird hier verwendet, da man sich die Zeilen grob nach ihrer Größe geordnet vorstellen kann, wobei die größte Zeile oben und die kleinste unten steht.

Die folgende Matrix ist beispielsweise in Zeilenstufenform, und ihre führenden Einträge sind rot dargestellt: $${\displaystyle {\begin{bmatrix}0&\color {red}{\mathbf {2} }&1&-1\\0&0&\color {red}{\mathbf {3} }&1\\0&0&0&0\end{bmatrix}}.}$$

Es handelt sich um eine Zeilenstufenform, da die nullte Zeile unten steht und der führende Eintrag der zweiten Zeile (in der dritten Spalte) rechts vom führenden Eintrag der ersten Zeile (in der zweiten Spalte) steht.

Eine Matrix heißt in reduzierter Zeilenstufenform, wenn außerdem alle führenden Einträge gleich 1 sind (was durch elementare Zeilenumformungen vom Typ 2 erreicht werden kann) und in jeder Spalte, die einen führenden Eintrag enthält, alle anderen Einträge in dieser Spalte gleich null sind (was durch elementare Zeilenumformungen vom Typ 3 erreicht werden kann).

Angenommen, das Ziel besteht darin, die Lösungsmenge des folgenden linearen Gleichungssystems zu finden und zu beschreiben: $${\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\qquad (L_{1})\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\qquad (L_{2})\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\qquad (L_{3})\end{alignedat}}}$$

Die folgende Tabelle zeigt das Zeilenreduktionsverfahren, das simultan auf das Gleichungssystem und die zugehörige erweiterte Matrix angewendet wird . In der Praxis werden Systeme üblicherweise nicht anhand von Gleichungen gelöst, sondern mithilfe der erweiterten Matrix, die sich besser für computergestützte Berechnungen eignet. Das Zeilenreduktionsverfahren lässt sich wie folgt zusammenfassen: Zunächst wird x aus allen Gleichungen unterhalb von _L₁ eliminiert , anschließend y aus allen Gleichungen unterhalb von _L₂ . Dadurch erhält das System eine Dreiecksform . Anschließend kann jede Unbekannte durch Rückwärtseinsetzen bestimmt werden.

Gleichungssystem	Zeilenoperationen	Erweiterte Matrix
${\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\end{alignedat}}}$		${\displaystyle \left[{\begin{array}{rrr|r}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]}$
${\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&2y&{}+{}&z&{}={}&5&\end{alignedat}}}$	${\displaystyle {\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2}\\L_{3}+L_{1}&\to L_{3}\end{aligned}}}$	${\displaystyle \left[{\begin{array}{rrr|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&2&1&5\end{array}}\right]}$
${\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&&&-z&{}={}&1&\end{alignedat}}}$	${\displaystyle L_{3}+-4L_{2}\to L_{3}}$	${\displaystyle \left[{\begin{array}{rrr|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right]}$
Die Matrix befindet sich nun in Zeilenstufenform (auch Dreiecksform genannt).
${\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&&&{}={}7&\\&&{\tfrac {1}{2}}y&&&{}={}{\tfrac {3}{2}}&\\&&&{}-{}&z&{}={}1&\end{alignedat}}}$	${\displaystyle {\begin{aligned}L_{1}-L_{3}&\to L_{1}\\L_{2}+{\tfrac {1}{2}}L_{3}&\to L_{2}\end{aligned}}}$	${\displaystyle \left[{\begin{array}{rrr|r}2&1&0&7\\0&{\frac {1}{2}}&0&{\frac {3}{2}}\\0&0&-1&1\end{array}}\right]}$
${\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&\quad &&{}={}&7&\\&&y&\quad &&{}={}&3&\\&&&\quad &z&{}={}&-1&\end{alignedat}}}$	${\displaystyle {\begin{aligned}2L_{2}&\to L_{2}\\-L_{3}&\to L_{3}\end{aligned}}}$	${\displaystyle \left[{\begin{array}{rrr|r}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]}$
${\displaystyle {\begin{alignedat}{4}x&\quad &&\quad &&{}={}&2&\\&\quad &y&\quad &&{}={}&3&\\&\quad &&\quad &z&{}={}&-1&\end{alignedat}}}$	${\displaystyle {\begin{aligned}L_{1}-L_{2}&\to L_{1}\\{\tfrac {1}{2}}L_{1}&\to L_{1}\end{aligned}}}$	${\displaystyle \left[{\begin{array}{rrr|r}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]}$
Die Matrix befindet sich nun in reduzierter Zeilenstufenform.

_{Die zweite Spalte beschreibt ,} welche Zeilenoperationen gerade durchgeführt wurden. Im ersten Schritt wird x aus L2 durch Addition entfernt .3/2L1 bis L2 _. Anschließendwird x aus L3 eliminiert , indem L1 zu L3 addiert _wird . Diese Zeilenoperationen sind in der Tabelle wie _{folgt gekennzeichnet :}$${\displaystyle {\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2},\\L_{3}+L_{1}&\to L_{3}.\end{aligned}}}$$

Sobald y auch aus der dritten Zeile eliminiert wurde, ergibt sich ein lineares Gleichungssystem in Dreiecksform, womit der erste Teil des Algorithmus abgeschlossen ist. Aus rechentechnischer Sicht ist es schneller, die Variablen in umgekehrter Reihenfolge zu lösen, ein Verfahren, das als Rückwärtssubstitution bekannt ist. Die Lösung lautet z = −1 , y = 3 und x = 2. Insbesondere existiert in diesem Fall eine eindeutige Lösung des ursprünglichen Gleichungssystems.

Anstatt die Matrix nach Erreichen der Zeilenstufenform zu reduzieren, kann man, wie in der Tabelle dargestellt, bis zur reduzierten Zeilenstufenform fortfahren. Dieses Verfahren der Zeilenreduktion bis zur vollständigen Reduzierung der Matrix wird manchmal als Gauß-Jordan-Elimination bezeichnet, um es vom Abbruch nach Erreichen der Zeilenstufenform zu unterscheiden.

Die Methode der Gaußschen Elimination erscheint – wenn auch ohne Beweis – im chinesischen Mathematikbuch „ Kapitel Acht: Rechteckige Anordnungen“ der „Neun Kapitel über die mathematische Kunst“ . Ihre Anwendung wird in achtzehn Aufgaben mit zwei bis fünf Gleichungen veranschaulicht. Die erste Erwähnung des Buches unter diesem Titel stammt aus dem Jahr 179 n. Chr., Teile davon wurden jedoch bereits um 150 v. Chr. verfasst. ^{[ 1 ] [ 2 ] [ 3 ]} Liu Hui kommentierte das Verfahren im 3. Jahrhundert.

Laut Grcar ^{[ 4 ]} wurde die Lösung linearer Gleichungen durch Elimination in verschiedenen eurasischen Kulturen unabhängig voneinander seit der Antike entwickelt, und in Europa wurden bereits in der Spätrenaissance (um 1550) konkrete Beispiele des Verfahrens veröffentlicht. Es ist durchaus möglich, dass das Verfahren damals schon von Mathematikern als elementar und für Fachleute nicht erklärungsbedürftig angesehen wurde, sodass wir seine detaillierte Geschichte wohl nie vollständig erfahren werden, außer dass es zu dieser Zeit zumindest an mehreren Orten in Europa praktiziert wurde.

Die Methode in Europa geht auf die Aufzeichnungen Isaac Newtons zurück . ^{[ 4 ] [ 5 ]} In den Jahren 1669/70 schrieb Newton, dass allen ihm bekannten Algebra-Lehrbüchern eine Lektion zur Lösung simultaner Gleichungen fehlte, die er daraufhin ergänzte. Die Universität Cambridge veröffentlichte die Aufzeichnungen schließlich 1707 unter dem Titel „ Arithmetica Universalis“, lange nachdem Newton seine akademische Laufbahn beendet hatte. Die Aufzeichnungen fanden weite Verbreitung, wodurch die (heute so genannte) Gaußsche Elimination Ende des 18. Jahrhunderts zum Standardlehrplan in Algebra-Lehrbüchern wurde. Carl Friedrich Gauß entwickelte 1810 eine Notation für die symmetrische Elimination, die im 19. Jahrhundert von professionellen Rechnern zur Lösung der Normalgleichungen von Ausgleichsproblemen übernommen wurde. ^{[ 6 ]} Der in der Oberstufe gelehrte Algorithmus wurde erst in den 1950er Jahren aufgrund von Verwirrung bezüglich der Geschichte des Themas nach Gauß benannt. ^{[ 7 ]}

Manche Autoren verwenden den Begriff Gaußsche Elimination nur für das Verfahren bis zur Stufenform der Matrix und den Begriff Gauß-Jordan-Elimination für das Verfahren, das zur reduzierten Stufenform führt. Die Bezeichnung rührt daher, dass es sich um eine Variante der Gaußschen Elimination handelt, wie sie Wilhelm Jordan 1888 beschrieb. Die Methode wird jedoch auch in einem im selben Jahr veröffentlichten Artikel von Clasen erwähnt. Jordan und Clasen haben die Gauß-Jordan-Elimination vermutlich unabhängig voneinander entdeckt. ^{[ 8 ]}

Historisch gesehen wurde die Zeilenreduktionsmethode erstmals zur Lösung linearer Gleichungssysteme eingesetzt. Im Folgenden werden einige weitere wichtige Anwendungsgebiete des Algorithmus aufgeführt.

Um zu erklären, wie die Gaußsche Elimination die Berechnung der Determinante einer quadratischen Matrix ermöglicht, müssen wir uns daran erinnern, wie die elementaren Zeilenumformungen die Determinante verändern:

• Durch Vertauschen zweier Zeilen wird die Determinante mit −1 multipliziert.
• Die Multiplikation einer Zeile mit einem von Null verschiedenen Skalar multipliziert die Determinante mit demselben Skalar.
• Das Hinzufügen eines skalaren Vielfachen einer anderen Zeile zu einer anderen Zeile ändert die Determinante nicht.

Wenn die Gaußsche Elimination einer quadratischen Matrix A eine Zeilenstufenmatrix B erzeugt , sei d das Produkt der Skalare, mit denen die Determinante gemäß den obigen Regeln multipliziert wurde. Dann ist die Determinante von A der Quotient aus dem Produkt der Elemente der Diagonalen von B und d . $${\displaystyle \det(A)={\frac {\prod \operatorname {diag} (B)}{d}}.}$$

Für eine n × n- Matrix benötigt diese Methode rechentechnisch nur O( n³ ) arithmetische Operationen. Die Verwendung der Leibniz-Formel für Determinanten erfordert hingegen O( ^{n² )} Operationen (Anzahl der Summanden in der Formel multipliziert mit der Anzahl der Multiplikationen in jedem Summanden) . Die rekursive Laplace-Entwicklung benötigt O( n²n ) Operationen , wenn die Teildeterminanten nur einmal berechnet werden müssen (Anzahl der Operationen in einer Linearkombination multipliziert mit der Anzahl der zu berechnenden Teildeterminanten, die durch ihre Spalten bestimmt werden) . Selbst auf den schnellsten Rechnern sind diese beiden Methoden für n größer als 20 unpraktisch oder nahezu unpraktisch. ${\displaystyle (n\,n!)}$

Eine Variante des Gaußschen Eliminationsverfahrens, die sogenannte Gauß-Jordan-Elimination, kann zur Bestimmung der Inversen einer Matrix verwendet werden, sofern diese existiert. Ist A eine n × n -Matrix, so kann man ihre Inverse durch Zeilenumformung berechnen , falls sie existiert. Zunächst wird die n × n- Einheitsmatrix rechts von A erweitert , wodurch eine n × 2n - Blockmatrix [ A | I ] entsteht . Durch Anwendung elementarer Zeilenumformungen wird nun die reduzierte Zeilenstufenform dieser n × 2n - Matrix ermittelt. Die Matrix A ist genau dann invertierbar ^, wenn sie auf die Einheitsmatrix I reduziert werden kann ; in diesem Fall ist der rechte Block der resultierenden Matrix A⁻¹ . Kann der Algorithmus den linken Block nicht auf I reduzieren , so ist A nicht invertierbar.

Betrachten wir beispielsweise die folgende Matrix: $${\displaystyle A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}.}$$

Um die Inverse dieser Matrix zu finden, nimmt man die folgende Matrix, erweitert um die Einheitsmatrix, und reduziert sie zeilenweise auf eine 3 × 6 Matrix: $${\displaystyle [A|I]=\left[{\begin{array}{ccc|ccc}2&-1&0&1&0&0\\-1&2&-1&0&1&0\\0&-1&2&0&0&1\end{array}}\right].}$$

Durch Zeilenumformungen kann man überprüfen, ob die reduzierte Zeilenstufenform dieser erweiterten Matrix gegeben ist durch $${\displaystyle \left[{\begin{array}{rrr|rrr}1&0&0&{\frac {3}{4}}&{\frac {1}{2}}&{\frac {1}{4}}\\0&1&0&{\frac {1}{2}}&1&{\frac {1}{2}}\\0&0&1&{\frac {1}{4}}&{\frac {1}{2}}&{\frac {3}{4}}\end{array}}\right]=:[I|B].}$$

Man kann sich jede Zeilenoperation als Linksprodukt einer Elementarmatrix vorstellen . Rechts sehen wir, dass das Produkt dieser Elementarmatrizen B ist (da B = BI ). Links sehen wir, dass die Linksmultiplikation des Produkts dieser Matrizen mit A die Einheitsmatrix ergibt. Anders ausgedrückt: BA = I. Daher ist ^B = A⁻¹ , die gesuchte Inverse. Dieses Verfahren zur Bestimmung der Inversen funktioniert für quadratische Matrizen beliebiger Größe.

Das Gaußsche Eliminationsverfahren lässt sich auf jede m × n- Matrix A anwenden . So können beispielsweise einige 6 × 9-Matrizen in eine Zeilenstufenmatrix T transformiert werden, wobei die Sterne beliebige Einträge und a , b , c , d , e Einträge ungleich null sind. Diese Zeilenstufenmatrix T enthält viele Informationen über A : Der Rang von A ist 5, da T 5 Zeilen ungleich null besitzt ; der von den Spalten von A aufgespannte Vektorraum bildet eine Basis aus den Spalten 1, 3, 4, 7 und 9 (den Spalten mit a , b , c , d , e in T ), und die Sterne zeigen, wie die übrigen Spalten von A als Linearkombinationen der Basisspalten dargestellt werden können. $${\displaystyle T={\begin{bmatrix}a&*&*&*&*&*&*&*&*\\0&0&b&*&*&*&*&*&*\\0&0&0&c&*&*&*&*&*\\0&0&0&0&0&0&d&*&*\\0&0&0&0&0&0&0&0&e\\0&0&0&0&0&0&0&0&0\end{bmatrix}},}$$

All dies gilt auch für die reduzierte Zeilenstufenform, die ein spezielles Zeilenstufenformat darstellt.

Die Anzahl der für die Zeilenreduktion benötigten arithmetischen Operationen ist ein Maß für die Recheneffizienz des Algorithmus. Beispielsweise benötigt man zum Lösen eines Systems von n Gleichungen mit n Unbekannten durch Zeilenumformungen der Matrix bis zur Stufenform und anschließendes Lösen nach jeder Unbekannten in umgekehrter Reihenfolge n(n+1)/2 Divisionen, (2n³ + 3n² − 5n ) / 6 Multiplikationen und ( ^2n³ + ^3n² − 5n ) / 6 Subtraktionen [ 9 ^{] ,} insgesamt also ^{etwa 2n³ /} 3 Operationen . ^Die arithmetische Komplexität ( Zeitkomplexität , wobei jede arithmetische Operation unabhängig von der Größe der Eingaben eine Zeiteinheit benötigt) beträgt somit O ( n³ ⁾ .

Diese Komplexität ist ein gutes Maß für die benötigte Rechenzeit, wenn die Zeit für jede arithmetische Operation annähernd konstant ist. Dies ist der Fall, wenn die Koeffizienten als Gleitkommazahlen dargestellt werden oder einem endlichen Körper angehören . Sind die Koeffizienten ganze Zahlen oder exakt dargestellte rationale Zahlen , können die Zwischenwerte exponentiell anwachsen, wodurch die Bitkomplexität exponentiell wird. ^{[ 10 ]} Der Bareiss-Algorithmus ist jedoch eine Variante der Gaußschen Elimination , die dieses exponentielle Wachstum der Zwischenwerte vermeidet. Bei gleicher arithmetischer Komplexität von O( n³ ⁾ weist er eine Bitkomplexität von O( n⁵ ⁾ auf und besitzt daher eine stark polynomielle Zeitkomplexität .

Das Gaußsche Eliminationsverfahren und seine Varianten können für Systeme mit Tausenden von Gleichungen und Unbekannten auf Computern angewendet werden. Bei Systemen mit Millionen von Gleichungen wird der Rechenaufwand jedoch prohibitiv. Solche großen Systeme werden im Allgemeinen iterativ gelöst . Spezielle Verfahren existieren für Systeme, deren Koeffizienten einem regelmäßigen Muster folgen (siehe Lineare Gleichungssysteme ).

Der erste stark polynomiale Algorithmus für die Gaußsche Elimination wurde 1967 von Jack Edmonds veröffentlicht. ^{[ 11 ] : 37} Unabhängig davon und fast gleichzeitig entdeckte Erwin Bareiss einen weiteren Algorithmus, der auf der folgenden Bemerkung basiert und auf eine divisionsfreie Variante der Gaußschen Elimination anwendbar ist.

Bei der Standard-Gauß-Elimination subtrahiert man von jeder Zeile unterhalb der Pivotzeile ein Vielfaches von , wobei und die Einträge in der Pivotspalte von bzw. sind . ${\displaystyle R_{i}}$${\displaystyle R_{k}}$${\displaystyle R_{k}}$${\displaystyle r_{i,k}/r_{k,k},}$${\displaystyle r_{i,k}}$${\displaystyle r_{k,k}}$${\displaystyle R_{i}}$${\displaystyle R_{k},}$

Die Bareiss-Variante besteht stattdessen darin, durch zu ersetzen. Dies führt zu einer Zeilenstufenform, die die gleichen Nulleinträge wie bei der Standard-Gauß-Elimination aufweist. ${\displaystyle R_{i}}$${\textstyle {\frac {r_{k,k}R_{i}-r_{i,k}R_{k}}{r_{k-1,k-1}}}.}$

Bareiss' wichtigste Bemerkung ist, dass jeder durch diese Variante erzeugte Matrixeintrag die Determinante einer Untermatrix der ursprünglichen Matrix ist.

Insbesondere wenn man mit ganzzahligen Einträgen beginnt, sind die im Algorithmus vorkommenden Divisionen exakte Divisionen, die zu ganzen Zahlen führen. Daher sind alle Zwischen- und Endeinträge ganze Zahlen. Darüber hinaus liefert die Hadamard-Ungleichung eine obere Schranke für die Absolutbeträge der Zwischen- und Endeinträge und ermöglicht so eine etwas geringere Komplexität als die Verwendung der Soft-O-Notation . ${\displaystyle {\tilde {O}}(n^{5}),}$

Da zudem eine obere Schranke für die Größe der finalen Einträge bekannt ist, kann eine Komplexität durch modulare Berechnung, gefolgt von chinesischem Restverfahren oder Hensel-Lifting, ermittelt werden . ${\displaystyle {\tilde {O}}(n^{4})}$

Als Folgerung können die folgenden Probleme in stark polynomieller Zeit mit derselben Bitkomplexität gelöst werden: ^{[ 11 ] : 40}

• Prüfung, ob m gegebene rationale Vektoren linear unabhängig sind
• Berechnung der Determinante einer rationalen Matrix
• Berechnung einer Lösung eines rationalen Gleichungssystems Ax = b
• Berechnung der inversen Matrix einer nichtsingulären rationalen Matrix
• Berechnung des Rangs einer rationalen Matrix

Ein mögliches Problem ist die numerische Instabilität , die durch die Möglichkeit der Division durch sehr kleine Zahlen verursacht wird. Wenn beispielsweise der Leitkoeffizient einer Zeile sehr nahe bei null liegt, müsste man zur Zeilenreduktion der Matrix durch diese Zahl dividieren. Dies bedeutet, dass jeder Fehler, der bei der Zahl nahe null vorliegt, verstärkt wird. Die Gaußsche Elimination ist für diagonaldominante oder positiv definite Matrizen numerisch stabil. Für allgemeine Matrizen gilt die Gaußsche Elimination im Allgemeinen als stabil, wenn partielle Pivotisierung verwendet wird , obwohl es Beispiele für stabile Matrizen gibt, für die sie instabil ist. ^{[ 12 ] [ 13 ]}

Die Gaußsche Elimination kann über jeden beliebigen Körper durchgeführt werden , nicht nur über die reellen Zahlen.

Der Buchberger-Algorithmus ist eine Verallgemeinerung des Gaußschen Eliminationsverfahrens auf Systeme von Polynomgleichungen . Diese Verallgemeinerung hängt maßgeblich von der Monomordnung ab . Die Wahl einer Variablenordnung ist bereits implizit im Gaußschen Eliminationsverfahren enthalten, da bei der Auswahl der Pivotpositionen von links nach rechts vorgegangen wird.

Die Berechnung des Rangs eines Tensors höherer Ordnung als 2 ist NP-schwer . ^{[ 14 ]} Daher kann es, falls P ≠ NP , kein Analogon zur Gaußschen Elimination in Polynomialzeit für Tensoren höherer Ordnung geben (Matrizen sind Array- Darstellungen von Tensoren zweiter Ordnung).

Wie oben erläutert, transformiert die Gaußsche Elimination eine gegebene m × n Matrix A in eine Matrix in Zeilenstufenform .

Im folgenden Pseudocode bezeichnet A[i, j]den Eintrag der Matrix A in Zeile i und Spalte j, wobei die Indizes bei 1 beginnen. Die Transformation wird direkt in der Matrix durchgeführt , d. h. die ursprüngliche Matrix geht verloren, da sie schließlich durch ihre Zeilenstufenform ersetzt wird.

h := 1 /* Initialisierung der Pivotzeile */ k := 1 /* Initialisierung der Pivotspalte */ solange h ≤ m und k ≤ n: /* Finde den k-ten Drehpunkt: */ i_max := argmax (i = h ... m, abs(A[i, k])) if A[i_max, k] = 0: /* In dieser Spalte befindet sich kein Pivotpunkt, gehe zur nächsten Spalte */ k := k + 1 sonst : Zeilen (h, i_max) vertauschen /* Für alle Zeilen unterhalb des Pivot-Elements: */ für i = h + 1 ... m: f := A[i, k] / A[h, k] /* Füllen Sie den unteren Teil der Pivotspalte mit Nullen: */ A[i, k] := 0 /* Wiederhole dies für alle verbleibenden Elemente in der aktuellen Zeile: */ für j = k + 1 ... n: A[i, j] := A[i, j] - A[h, j] * f /* Pivot-Zeile und -Spalte vergrößern */ h := h + 1 k := k + 1 

Dieser Algorithmus unterscheidet sich geringfügig von dem zuvor beschriebenen, indem er ein Pivotelement mit dem größten Absolutwert auswählt . Eine solche partielle Pivotisierung kann erforderlich sein, wenn an der Pivotstelle der Eintrag der Matrix null ist. In jedem Fall verbessert die Wahl des größtmöglichen Absolutwerts des Pivotelements die numerische Stabilität des Algorithmus, wenn Gleitkommazahlen zur Darstellung verwendet werden. ^{[ 15 ]}

Nach Abschluss dieses Verfahrens befindet sich die Matrix in Zeilenstufenform und das entsprechende Gleichungssystem kann durch Rückwärtseinsetzen gelöst werden.

• Fangcheng (Mathematik)
• Gram-Schmidt-Verfahren – ein weiteres Verfahren zur Überführung einer Matrix in eine kanonische Form.
• Fourier-Motzkin-Elimination – ein Algorithmus zur Eliminierung von Variablen in einem System linearer Ungleichungen, nicht in linearen Gleichungen.

• Interaktives didaktisches Werkzeug