Zum Inhalt springen
Startseite

Gaußsche Elimination: Verfahren zur Lösung linearer Gleichungssysteme

Gaußsche Elimination erklärt: Schritt-für-Schritt Verfahren zur Lösung linearer Gleichungssysteme, Zeilenoperationen & Beispiele zur effizienten Matrixreduktion.

Autor: Erstellt: Aktualisiert:

In der Mathematik ist die Gaußsche Elimination (auch Zeilenreduktion genannt) eine grundlegende Methode zur Lösung von linearen Gleichungssystemen. Sie ist nach Carl Friedrich Gauß benannt, einem berühmten deutschen Mathematiker, der über diese Methode schrieb, sie aber nicht als Erster erfand. Die Gaußsche Elimination wandelt das Gleichungssystem in eine Matrixdarstellung um und vereinfacht diese durch elementare Zeilenoperationen, bis die Lösungen abgelesen oder einfach bestimmt werden können.

Bildergalerie

3 Bilder
Gaussian elimination animated
en.wikipedia.org · CC BY-SA 4.0

Grundidee

Gegeben sei ein lineares Gleichungssystem. Man schreibt die Koeffizienten und die rechten Seiten in der sogenannten erweiterten Matrix und führt dann auf dieser Matrix Operationen durch, die das System äquivalent verändern, aber die Lösungsmenge nicht ändern. Ziel ist eine Treppenform (Zeilenstufenform) oder idealerweise die reduzierte Zeilenstufenform, aus der die Unbekannten direkt abgelesen werden können.

Elementare Zeilenoperationen

Es gibt drei erlaubte Operationen, die die Lösung nicht verändern:

  • Typ 1: Vertauschen zweier Zeilen.
  • Typ 2: Multiplikation einer Zeile mit einer von Null verschiedenen Zahl.
  • Typ 3: Addieren eines Vielfachen einer Zeile zu einer anderen Zeile (Zeilenaddition).

Stufenform und reduzierte Stufenform

Eine Matrix ist in Zeilenstufenform (Treppenform), wenn jede nichtverschwindende Zeile links von der nächsten beginnt — jede Zeile hat gegenüber der vorherigen mindestens einen zusätzlichen führenden Nullwert. In der reduzierten Zeilenstufenform gilt zusätzlich, dass in jeder nichtverschwindenden Zeile der erste Nicht-Null-Eintrag gleich 1 ist (ein sogenannter Pivot) und in der Spalte dieses Pivots alle anderen Einträge null sind. Die vollständige Reduktion bis zur reduzierten Stufenform nennt man häufig Gauß–Jordan-Elimination.

Algorithmus — Schritt für Schritt

  1. Stelle die erweiterte Matrix des Systems auf.
  2. Wähle eine Pivotspalte (beginnend links). Finde in oder unter der aktuellen Zeile eine Zeile mit einem von Null verschiedenen Eintrag in dieser Spalte (Pivot). Wenn nötig, vertausche Zeilen (Typ 1).
  3. Skaliere die Pivotzeile so, dass der Pivot 1 wird (Typ 2).
  4. Eliminiere alle anderen Einträge in der Pivotspalte durch Addition eines geeigneten Vielfachen der Pivotzeile zu den übrigen Zeilen (Typ 3).
  5. Gehe zur nächsten Zeile und nächsten Pivotspalte und wiederhole die Schritte, bis die Matrix in Stufenform (oder reduziert) vorliegt.

Beispiel (kurz)

Für das System

 x + 2y = 5 2x + y = 4

ergibt die erweiterte Matrix

 [1 2 | 5] [2 1 | 4]

Pivot in Zeile 1 belassen, Zeile 2 := Zeile 2 − 2·Zeile 1:

 [1 2 | 5] [0 −3 | −6]

Zeile 2 durch −3 teilen:

 [1 2 | 5] [0 1 | 2]

Eliminiere y aus Zeile 1: Zeile 1 := Zeile 1 − 2·Zeile 2:

 [1 0 | 1] [0 1 | 2]

Ergebnis: x = 1, y = 2.

Lösungsarten und Zusammenhang mit Rang

Die Gaußsche Elimination zeigt klar, ob ein System eindeutig lösbar, unendlich viele Lösungen hat oder widersprüchlich ist:

  • Eindeutige Lösung: Rang der Koeffizientenmatrix = Anzahl der Unbekannten. In der reduzierten Form erscheint für jede Unbekannte ein Pivot.
  • Unendlich viele Lösungen: Rang < Anzahl der Unbekannten. Es gibt freie Variablen, die Parameter tragen.
  • Keine Lösung: In der erweiterten Matrix erscheint eine Zeile der Form [0 0 … 0 | b] mit b ≠ 0, was einem Widerspruch entspricht.

Zahlenmäßige Aspekte und Pivotstrategien

Bei praktischer numerischer Berechnung können Rundungsfehler auftreten. Deshalb verwendet man häufig Pivotstrategien, z. B.:

  • Partielles Pivotieren: Wähle in der Pivotspalte den Eintrag mit dem größten Betrag und vertausche die entsprechende Zeile nach oben.
  • Vollständiges Pivotieren: Suche den größten Betrag in der noch betrachteten Untermatrix und vertausche Zeilen und Spalten (teurer, aber manchmal stabiler).

Solche Strategien verbessern die Stabilität und Genauigkeit der Lösung bei Fließkommarechnungen.

Komplexität und Beziehungen zu anderen Verfahren

Die Rechenaufwand der Gaußschen Elimination für ein n×n-System liegt im Allgemeinen bei O(n³) Operationen. Die Methode steht in engem Zusammenhang mit anderen Matrixzerlegungen:

  • LU-Zerlegung: Durch Gauß-Elimination ohne Zeilentausch lässt sich die Matrix in das Produkt einer unteren Dreiecksmatrix L und einer oberen Dreiecksmatrix U zerlegen. Diese Zerlegung ist nützlich, wenn viele Gleichungssysteme mit derselben Koeffizientenmatrix, aber unterschiedlichen rechten Seiten gelöst werden sollen.
  • QR-Zerlegung, Cholesky etc.: Alternative Methoden, die für spezielle Matrizen oder bessere numerische Stabilität bevorzugt werden können.

Anwendungen

Die Gaußsche Elimination ist überall dort wichtig, wo lineare Gleichungssysteme auftreten, z. B. in:

  • Technik und Naturwissenschaften (z. B. Netzwerkanalyse, Strukturmechanik),
  • Computergrafik (Lösungen von Transformationsgleichungen),
  • Optimierung und numerischer Simulation,
  • Datenanalyse und maschinellem Lernen (lineare Regression in geschlossener Form).

Historischer Hinweis

Obwohl die Methode den Namen von Carl Friedrich Gauß trägt, sind ähnliche Eliminationsverfahren schon in älteren Kulturen und Texten bekannt. Gauß trug durch systematische Darstellung und Anwendung zur Bekanntheit und Verbreitung der Methode bei.

Die Gaußsche Elimination ist ein einfach zu verstehendes und zugleich sehr mächtiges Werkzeug der linearen Algebra. Mit Kenntnis der elementaren Zeilenoperationen, der Pivotstrategien und der Interpretation der resultierenden Matrix lassen sich praktisch alle Fragen zur Lösbarkeit linearer Systeme beantworten.

Beispiel

Angenommen, das Ziel ist es, die Antworten auf dieses System von linearen Gleichungen zu finden.

2 x + y - z = 8 ( R 1 ) - 3 x - y + 2 z = - 11 ( R 2 ) - 2 x + y + 2 z = - 3 ( R 3 ) {\Anzeigestil {\beginnt{ausgerichtet}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\qquad (R_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (R_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (R_{3})\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\qquad (R_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (R_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (R_{3})\end{alignedat}}}

Zunächst muss das System in eine erweiterte Matrix umgewandelt werden. In einer erweiterten Matrix wird jede lineare Gleichung zu einer Zeile. Auf einer Seite der erweiterten Matrix werden die Koeffizienten jedes Terms in der linearen Gleichung zu Zahlen in der Matrix. Auf der anderen Seite der erweiterten Matrix sind die konstanten Terme, denen jede lineare Gleichung gleich ist. Für dieses System ist die erweiterte Matrix:

[ 2 1 - 1 8 - 3 - 1 2 - 11 - 2 1 2 - 3 ] {\Anzeigestil \links[{\Beginn{Anordnung}{ccc|c}2&1&-1&-1&8\\\-3&-1&-1&2&-11\\\-2&1&2&-3\Ende{Anordnung}}}}rechts]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]}

Anschließend können Zeilenoperationen auf der erweiterten Matrix durchgeführt werden, um sie zu vereinfachen. Die folgende Tabelle zeigt den Prozess der Zeilenreduktion auf dem Gleichungssystem und auf der erweiterten Matrix.

System von Gleichungen

Reihen-Operationen

Erweiterte Matrix

2 x + y - z = 8 - 3 x - y + 2 z = - 11 - 2 x + y + 2 z = - 3 {\Anzeigestil {\beginnt{ausgerichtet}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\\-3x&&\;-\;&&y&&\;+\;&&2z&& \;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}}

[ 2 1 - 1 8 - 3 - 1 2 - 11 - 2 1 2 - 3 ] {\Anzeigestil \links[{\Beginn{Anordnung}{ccc|c}2&1&-1&-1&8\\\-3&-1&-1&2&-11\\\-2&1&2&-3\Ende{Anordnung}}}}rechts]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]}

2 x + y - z = 8 1 2 y + 1 2 z = 1 2 y + z = 1 2 y + z = 5 {\Anzeigestil {\begin{alignedat}{7}2x&&\;+&&y&&\;-&&\;z&&\\;=\;&&8&\\&&&&{\frac {1}{2}}y&&\;+&&\;{\frac {1}{2}}z&&\;=\;&&1&\\&&&& 2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y&&\;-&&\;z&&\;=\;&&8&\\&&&&{\frac {1}{2}}y&&\;+&&\;{\frac {1}{2}}z&&\;=\;&&1&\\&&&&2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}}

R 2 + 3 2 R 1 → R 2 {\Anzeigestil R_{2}+{\frac {3}{2}}}R_{1}\Rechtspfeil R_{2}} {\displaystyle R_{2}+{\frac {3}{2}}R_{1}\rightarrow R_{2}}
R 3 + R 1 → R 3 {\Anzeigestil R_{3}+R_{1}\rechter Pfeil R_{3}} {\displaystyle R_{3}+R_{1}\rightarrow R_{3}}

[ 2 1 - 1 8 0 1 / 2 1 / 2 1 0 2 1 5 ] {\Anzeigestil \links[{\Beginn{Anordnung}{ccc|c}2&1&-1&-1&8\\\\0&1/2&1/2&1\\\0&2&1&1&5\Ende{Anordnung}}}}rechts]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\0&1/2&1/2&1\\0&2&1&5\end{array}}\right]}

2 x + y - z = 8 1 2 y + 1 2 z = 1 - z = 1 {\Anzeigestil {\begin{alignedat}{7}2x&&\;+&&y\;&&-&&\;z\;&&=\;&&8&\\\&&&&{\frac {1}{2}}y\;&&+&&\;{\frac {1}{2}}z\;&&=\;&&1&\\&&&&&&&&\;-z\;& &\;=\;&&1&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y\;&&-&&\;z\;&&=\;&&8&\\&&&&{\frac {1}{2}}y\;&&+&&\;{\frac {1}{2}}z\;&&=\;&&1&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}}

R 3 + - 4 R 2 → R 3 {\Anzeigestil R_{3}+-4R_{2}\rechter Pfeil R_{3}}} {\displaystyle R_{3}+-4R_{2}\rightarrow R_{3}}

[ 2 1 - 1 8 0 1 / 2 1 / 2 1 0 0 0 - 1 1 1 ] {\Anzeigestil \links[{\Beginn{Anordnung}{ccc|c}2&1&-1&-1&8\\\0&1/2&1/2&1\\\0&0&0&-1&1\Ende{Anordnung}}}}rechts]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&-1&8\\0&1/2&1/2&1\\0&0&-1&1\end{array}}\right]}

Die Matrix ist jetzt in Zeilenform. Diese Form wird auch als Dreiecksform bezeichnet.

System von Gleichungen

Reihen-Operationen

Erweiterte Matrix

2 x + y = 7 1 2 y = 3 / 2 - z = 1 {\Anzeigestil {\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;\;&&=\;&&7&\\\&&&&&{\frac {1}{2}}y\;&&&&\;\;&&=\;&&3/2&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&{\frac {1}{2}}y\;&&&&\;\;&&=\;&&3/2&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}}

R 2 + 1 2 R 3 → R 2 {\Anzeigestil R_{2}+{\frac {1}{2}}}R_{3}\Rechtspfeil R_{2}} {\displaystyle R_{2}+{\frac {1}{2}}R_{3}\rightarrow R_{2}}
R 1 - R 3 → R 1 {\Anzeigestil R_{1}-R_{3}\Pfeil rechts R_{1}} {\displaystyle R_{1}-R_{3}\rightarrow R_{1}}

[ 2 1 0 7 0 0 1 / 2 0 0 3 / 2 0 0 0 - 1 1 1 ] {\Anzeigestil \links[{\Beginn{Anordnung}{ccc|c}2&1&0&0&7\\\0&1/2&0&3/2\\\0&0&0&-1&1\Ende{Anordnung}}}}rechts]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&0&7\\0&1/2&0&3/2\\0&0&-1&1\end{array}}\right]}

2 x + y = 7 y = 3 z = - 1 {\Anzeigestil {\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;\;&&=\;&&7&\\\&&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}}

2 R 2 → R 2 {\Anzeigestil 2R_{2}\rechter Pfeil R_{2}} {\displaystyle 2R_{2}\rightarrow R_{2}}
R 3 → R 3 {\Anzeigestil -R_{3}\rechter Pfeil R_{3}} {\displaystyle -R_{3}\rightarrow R_{3}}

[ 2 1 0 7 0 1 0 1 0 3 0 0 0 1 - 1 ] {\Anzeigestil \links[{\Beginn{Anordnung}{ccc|c}2&1&1&0&7\\\\0&1&0&3\\\0&0&0&1&-1\Ende{Anordnung}}}rechts]} {\displaystyle \left[{\begin{array}{ccc|c}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]}

x = 2 y = 3 z = - 1 {\Anzeigestil {\Beginn{Ausrichtung}{7}x&&\;&&\;&&&&\\;\;&&=\;&&2&\\\&&&& y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}} {\displaystyle {\begin{alignedat}{7}x&&\;&&\;&&&&\;\;&&=\;&&2&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}}

R 1 - R 2 → R 1 {\Anzeigestil R_{1}-R_{2}\Rechter Pfeil R_{1}} {\displaystyle R_{1}-R_{2}\rightarrow R_{1}}
1 2 R 1 1 → R 1 {\Anzeigestil {\frac {1}{2}}}R_{1}\rechter Pfeil R_{1}} {\displaystyle {\frac {1}{2}}R_{1}\rightarrow R_{1}}

[ 1 0 0 0 2 0 1 0 1 0 3 0 0 0 1 - 1 ] {\Anzeigestil \links[{\Beginn{Anordnung}{ccc|c}1&0&0&0&2\\\\0&1&0&3\\\0&0&0&1&-1\Ende{Anordnung}}}rechts]} {\displaystyle \left[{\begin{array}{ccc|c}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]}

Die Matrix liegt nun in reduzierter Zeilenstaffelform vor. Das Lesen dieser Matrix sagt uns, dass die Lösungen für dieses Gleichungssystem auftreten, wenn x = 2, y = 3 und z = -1.

Fragen und Antworten

F: Was ist die Gaußsche Eliminierung?

A: Die Gaußsche Eliminierung ist eine Methode, die in der Mathematik verwendet wird, um Systeme linearer Gleichungen zu lösen.

F: Nach wem ist sie benannt?

A: Sie ist nach Carl Friedrich Gauß benannt, einem berühmten deutschen Mathematiker, der über diese Methode geschrieben, sie aber nicht erfunden hat.

F: Wie wird die Gaußsche Eliminierung durchgeführt?

A: Die Gaußsche Eliminierung wird durchgeführt, indem die Koeffizienten der Terme im System der linearen Gleichungen verwendet werden, um eine erweiterte Matrix zu erstellen. Anschließend wird die Matrix mit elementaren Zeilenoperationen vereinfacht.

F: Welche drei Arten von Zeilenoperationen werden bei der Gaußschen Eliminierung verwendet?

A: Die drei Arten von Zeilenoperationen, die bei der Gaußschen Eliminierung verwendet werden, sind: Vertauschen einer Zeile mit einer anderen Zeile, Multiplizieren einer Zeile mit einer Zahl ungleich Null und Addieren oder Subtrahieren einer Zeile von einer anderen Zeile.

F: Was ist das Ziel der Gaußschen Eliminierung?

A: Das Ziel der Gaußschen Eliminierung ist es, die Matrix in Zeilen-Echelon-Form zu erhalten.

F: Was ist die Zeilen-Echelon-Form?

A: Wenn eine Matrix in Zeilen-Echelon-Form vorliegt, bedeutet dies, dass jede Zeile von links nach rechts gelesen mit mindestens einem Nullterm mehr beginnt als die Zeile darüber.

F: Was ist die reduzierte Zeilen-Echelon-Form?

A: Reduzierte Zeilen-Echelon-Form bedeutet, dass die Matrix in Zeilen-Echelon-Form vorliegt und der einzige Nicht-Null-Term in jeder Zeile 1 ist. Die Gaußsche Eliminierung, die eine reduzierte Zeilen-Echelon-Matrix ergibt, wird manchmal auch als Gauß-Jordan-Elimination bezeichnet.

Autor

AlegsaOnline.com Gaußsche Elimination: Verfahren zur Lösung linearer Gleichungssysteme

URL: https://de.alegsaonline.com/art/37750

Teilen