Gaußsches Eliminationsverfahren

Bestimme in jeder Spalte die Pivotzeile und verfolge die Elimination. Bei der zweiten Voreinstellung entscheidet diese Wahl über die Lösung. Wählst du die winzige Zahl als Pivot, erhältst du für x eine 0 statt der 1.

Rechenbeispiel — Gaußsches Eliminationsverfahren

Determinante	-1
Residuum	8,8818 × 10⁻¹⁶

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Gaußsches Eliminationsverfahren262 Wörter

Die Elimination überführt ein System in ein äquivalentes Dreieckssystem. Daraus kannst du die Lösung dann von unten nach oben ablesen. Ihre Bedeutung liegt nicht darin, dass sie funktioniert. Das tun andere Verfahren auch. Entscheidend ist, was sie kostet. Denn das bestimmt, welche Methode eine Maschine tatsächlich ausführt.

Was die einzelnen Symbole bedeuten

n: die Anzahl der Unbekannten und die einzige Größe, von der die Kosten abhängen.
pivot: der Koeffizient, durch den du eine Zeile teilst. Die vom Algorithmus festgelegte Reihenfolge macht das Verfahren entscheidungsfrei. Welche Zahl dort landet, entscheidet darüber, ob das Verfahren die Gleitkommaarithmetik übersteht.

Setzt voraus: Ein vollbesetztes System ohne ausnutzbare Struktur. Dünnbesetzte, Band- oder symmetrische Systeme sind günstiger. Die Wahl des passenden Spezialverfahrens macht den Großteil der numerischen linearen Algebra aus.
Versagt, wenn: Der Aufwand ist kubisch, und kubisch ist eine Wand. Die Elimination bei n Unbekannten erfordert etwa n³/3 Multiplikationen und ebenso viele Additionen. Zählst du bei einer echten Elimination direkt mit, kommst du bei n = 100 auf 333.300 Multiplikationen. Die Schätzung liefert 333.333. Dieser Exponent bedeutet eine feste Strafe für jedes Wachstum. Verdoppelst du die Unbekannten, vervielfacht sich die Arbeit um genau 8. Für 100 Unbekannte brauchst du 333.300 Multiplikationen. Bei 200 sind es schon 2.666.600. Eine Maschine, die tausend Unbekannte in einer Sekunde abarbeitet, braucht für zweitausend folglich acht Sekunden. Bei zwanzigtausend vergehen etwa zweieinviertel Stunden. Das ist die Gestalt dieser Wand. Deshalb lautet die spannende Frage in der numerischen linearen Algebra fast nie, wie du ein vollbesetztes System löst. Die Frage ist vielmehr, wie du vermeidest, überhaupt eines vor dir zu haben.

Zwei Rechenschritte in einer Reihenfolge, die jede Entscheidung abnimmt 🖖

Zwei Gleichungen brauchten einen einzigen Schritt: das Vielfache einer Zeile von einer anderen abzuziehen. Drei Gleichungen erfordern diesen Schritt und noch einen weiteren. Die Liste benennt beide. Einen Zeilentausch, um eine taugliche Zahl ins Pivot zu setzen, und eine Elimination. Die Reihenfolge steht starr fest. Du räumst die erste Spalte frei, dann die zweite. Danach liest du die Lösung aus der untersten Zeile ab und arbeitest dich nach oben durch. Folge diesem Muster und du musst nie wieder clever abwägen, welche Gleichung du angreifst. Das ist der Unterschied zwischen einem Rätsel und einem Verfahren. Und genau darum skaliert es: Dieselbe Routine für tausend Unbekannte läuft noch heute in jedem Ingenieurprogramm der Welt ab, sechzig Jahre nachdem man ihr einen Namen gab.

Die Determinante ist das Produkt der Pivotelemente 🖖

Behalte während der Elimination die Pivotelemente im Auge und multipliziere sie miteinander. Für jeden Zeilentausch drehst du dann einmal das Vorzeichen um. Das liefert dir die Determinante, und zwar direkt aus den ohnehin nötigen Rechenschritten. Die meisten lernen Determinanten stattdessen über die Kofaktorentwicklung kennen. Es lohnt sich zu wissen, warum in der Praxis niemand so rechnet. Kofaktoren erfordern grob n! Rechenoperationen, im Gegensatz zu n³ bei der Elimination. Bei einer 20 × 20-Matrix stehen damit 2 × 10¹⁸ Schritte gegen gerade einmal 8.000. Ein Faktor von 10¹⁴ entscheidet schlichtweg darüber, was man einem Rechner überhaupt zumuten kann. Die Formel, die im Unterricht überall als Erste gelehrt wird, hat in der Realität noch nie eine Maschine ernsthaft verwendet.

Eine einzige Wahl im Verfahren verändert das Ergebnis 🖖

Klick auf Pivotisierung aus. Der Leitkoeffizient ist 10⁻¹⁷, der Algorithmus dividiert pflichtbewusst dadurch, und x ergibt 0, obwohl die wahre Lösung 1 lautet. Weder ist etwas kaputt, noch wurde eine Regel verletzt. Die Division durch eine sehr kleine Zahl vervielfacht jeden bereits vorhandenen Rundungsfehler, und bis die Rechnung oben beim Rückwärtseinsetzen ankommt, hat dieser Fehler die eigentliche Lösung restlos verschluckt. Das ist eine Klippe, kein Gefälle. Lässt du diesen Koeffizienten sinken, liefert 10⁻¹² noch vier korrekte Stellen und 10⁻¹⁵ drei. Dann aber gibt 10⁻¹⁶ plötzlich 2,22 zurück und 10⁻¹⁷ ergibt 0. Die Abbruchkante liegt beim Maschinenepsilon, dem Abstand zwischen 1 und der nächsten darstellbaren Double-Zahl. Setze das Häkchen, und der Algorithmus dividiert stattdessen durch die größte verfügbare Zahl. Auf einmal lässt sich jeder dieser Fälle exakt lösen. Deshalb gibt es auf der Seite die Residuen-Karte. Sie setzt das Ergebnis zurück in die Ausgangsgleichungen ein, und nur so kannst du eine echte Lösung von einer scheinbar korrekten unterscheiden.

Aufgaben vollständig gelöst

Lösen von 2x + y − z = 8 und der Genauigkeitsverlust 7 Schritte
Löse 2x + y − z = 8, −3x − y + 2z = −11, −2x + y + 2z = −3 und berechne anschließend, was dich die Elimination an Genauigkeit gekostet hat.
1. Schreibe das System als erweiterte Koeffizientenmatrix auf. Die Buchstaben leisten hier keine echte Arbeit. Lass sie also weg und behalte nur die Spalten.
  
  $2 - 3 - 2 1 - 1 1 - 1 22 8 - 11 - 3$
2. Nutze den größten Eintrag der ersten Spalte als Pivot. Das ist die −3 in der zweiten Zeile. Tausche diese Zeile nach oben. Da jeder Zeilentausch das Vorzeichen der Determinante umdreht, solltest du hier mitzählen.
  
  $R_{1} \leftrightarrow R_{2} (∣ - 3∣ > ∣2∣)$
3. Räume den Rest der ersten Spalte leer, indem du Vielfache der Pivotzeile abziehst.
  
  $R_{2} \to R_{2} - \frac{2}{- 3} R_{1}, R_{3} \to R_{3} - \frac{- 2}{- 3} R_{1}$
4. Wiederhole das für die zweite Spalte. Lies dann die unterste Zeile ab: Sie enthält genau eine Unbekannte und ihren Wert.
  
  $R_{2} \leftrightarrow R_{3} (\frac{5}{3} > \frac{1}{3}) \Rightarrow \frac{1}{5} z = - \frac{1}{5}$
5. Substituiere rückwärts nach oben. Die letzte Zeile liefert z, die mittlere liefert y, und aus der obersten erhältst du x.
  
  $z = - 1, y = 3, x = 2$
6. Multipliziere die Pivots und wende das Vorzeichen für zwei Vertauschungen an, um die Determinante zu erhalten. Prüfe dein Ergebnis, indem du es in die ursprünglichen Gleichungen einsetzt und nicht in die reduzierten.
  
  $det = (- 3) (\frac{5}{3}) (\frac{1}{5}) (- 1)^{2} = - 1$
7. Das Residuum liegt bei etwa 10⁻¹⁶. Das ist ungleich null. Es entspricht exakt der Größenordnung jener Rundungsfehler, die ein Computer schlichtweg nicht vermeiden kann. Und genau das sollte man ehrlicherweise berichten. Eine Lösung, die von sich behauptet, absolut exakt zu sein, stammt entweder aus der Ganzzahlarithmetik oder schaut einfach nicht genau hin. Ändere nun bei ausgeschalteter Pivotisierung den führenden Koeffizienten auf 10⁻¹⁷. Das Residuum springt auf 1. Das ist dieselbe Warnung, nur brüllt sie dich diesmal an.
  
  $i max ∣ A_{i} x - b_{i} ∣ \approx 9 \times 1 0^{- 16}$
Antwort

x = 2, y = 3, z = −1, Determinante −1. Ein Residuum von etwa 10⁻¹⁶ zeigt, dass die Arithmetik genau so exakt arbeitet, wie es mit Fließkommazahlen eben möglich ist. Wenn du die Pivotisierung bei einem schlecht skalierten System abschaltest, ist genau diese Zahl das Signal dafür, dass deine Lösung falsch ist.
Zweimal eine Determinante von 0, mit zwei verschiedenen Bedeutungen 7 Schritte
Diese Voreinstellung hat keine Lösung und die nächste unendlich viele, und beide geben eine Determinante von 0 aus. Rechne heraus, was die beiden tatsächlich trennt, und entscheide, was ein Ändern der rechten Seite jemals bringen könnte.
1. Die Spaltenpivotisierung sucht in der ersten Spalte den größten Koeffizienten. Dort steht die 3 in der untersten Zeile, der erste Zug ist also ein Tausch.
  
  $123121122375 R_{1} \leftrightarrow R_{3} 321121221573 (∣3∣ > ∣2∣ > ∣1∣)$
2. Räum die Spalte leer: Zieh ⅔ der neuen ersten Zeile von der zweiten ab und ⅓ davon von der dritten.
  
  $R_{2} \to R_{2} - \frac{2}{3} R_{1}, R_{3} \to R_{3} - \frac{1}{3} R_{1} : 300 1 \frac{4}{3} \frac{2}{3} 2 \frac{2}{3} \frac{1}{3} 5 \frac{11}{3} \frac{4}{3}$
3. In der zweiten Spalte steht 4/3 bereits über 2/3, es muss also nichts getauscht werden. Zieh die Hälfte von Zeile 2 von Zeile 3 ab.
  
  $R_{3} \to R_{3} - \frac{1}{2} R_{2} : 300 1 \frac{4}{3} 0 2 \frac{2}{3} 0 5 \frac{11}{3} - \frac{1}{2}$
4. Zeile 3 ist links nun leer und trägt rechts −½, was sich als 0 = −½ liest. Es wurden nur zwei Pivots gelegt, 3 und 4/3, wo drei Unbekannte drei brauchen, und ein fehlendes Pivot macht das Produkt null.
  
  $pivots 3, \frac{4}{3} — two, not three ⟹ det A = 0, last row: 0 = - \frac{1}{2}$
5. Der Rang ist das, was die Determinante verbirgt. Die Koeffizientenmatrix hat zwei unabhängige Zeilen. Die erweiterte Matrix hat drei, weil jenes übrig gebliebene −½ eine Zeile ist, die nichts wegkürzen kann. Rang 2 gegen Rang 3 ist genau das, was „keine Lösung“ bedeutet.
  
  $rank A = 2 < rank [A ∣ b] = 3 ⟹ no solution$
6. Die Voreinstellung Eine Gleichung dreimal rechnet dieselbe Arithmetik und sagt etwas anderes. Jede Zeile ist ein Vielfaches der ersten, also sind beide Ränge 1 und die Determinante wieder 0. Die Lösungsmenge hat 3 − 1 = 2 freie Richtungen: die ganze Ebene x + y + z = 3. Das Werkzeug sagt „unendlich viele“, ohne zu sagen, in wie vielen Richtungen.
  
  $Infinitely many: rank A = rank [A ∣ b] = 1, det A = 0, dim = 3 - 1 = 2 (x + y + z = 3)$
7. Ändere eine Zahl und sieh, welche Größe sich bewegt. Setz eine 6 dorthin, wo rechts in Zeile 2 die 7 steht. Die Koeffizientenmatrix bleibt unberührt, die Determinante rührt sich also nicht, aber der Rang der erweiterten Matrix fällt auf 2, und aus keiner Lösung wird eine ganze Gerade von Lösungen.
  
  $b_{2} = 7 \to 6 : rank [A ∣ b] = 2 = rank A ⟹ dim = 3 - 2 = 1$
Antwort

Die Determinante meldet nur, ob die Koeffizientenmatrix einen vollständigen Satz Pivots hat. Die rechte Seite kommt darin nie vor, und deshalb kann sie die beiden Voreinstellungen nicht trennen, während die beiden Ränge es können: keine Lösung, wenn sie sich widersprechen, und eine Lösungsmenge der Dimension 3 − Rang, wenn sie übereinstimmen. Ist die Determinante erst einmal 0, kauft dir keine rechte Seite mehr eine einzelne Antwort; du bekommst keine oder eine ganze Familie, und die Wahl zwischen beiden ist alles, worüber b entscheidet. Die Residuumskarte bleibt aus demselben Grund dunkel, aus dem es sie gibt: Ein Residuum braucht eine Lösung, die man wieder in die Gleichungen einsetzen kann.

$dim = n - rank A when rank [A ∣ b] = rank A; det A = 0 ⟹ no b gives exactly one$

Lernpfad

Nach x auflösen, vom Minuszeichen aufwärts

Quellen (1)

Two centuries of the method being reinvented and misattributed, including how Gauss's name came to be on it: J. F. Grcar, "How ordinary elimination became Gaussian elimination." Historia Mathematica 38:2 (2011), 163–218.

Vom 42Math-Team · Aktualisiert 2026-08-26

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Mathematik →

Beispielaufgaben

Lösbares System - Zwei Vertauschungen und drei Eliminationen liefern x = 2, y = 3, z = −1. Das Residuum liegt bei etwa 10⁻¹⁶. Genauer kann ein Computer nicht rechnen.
Ohne Pivotisierung - Der erste Koeffizient ist 10⁻¹⁷ und die Pivotisierung ist deaktiviert, also teilt der Algorithmus durch ihn. Das Ergebnis ist x = 0, obwohl es 1 sein müsste, und das Residuum ist 1 statt 0. Setze das Häkchen, und dasselbe System wird exakt gelöst.
Eine Gleichung dreimal - Jede Zeile ist ein Vielfaches der ersten. Nach der Elimination bestehen zwei Zeilen komplett aus Nullen. Die Determinante ist 0. Das System legt keinen Punkt fest, sondern eine Ebene.
Widersprüchlich - Die zweite Zeile widerspricht der ersten: gleiche linke Seite, aber andere rechte Seite. Die Elimination führt zu 0 = 1. Keine noch so clevere Rechnung kann das retten.