Das Gaußsche Eliminationsverfahren
Der Gauß-Algorithmus (nach Carl Friedrich Gauß) ist das Standardverfahren zum Lösen linearer Gleichungssysteme. Die Idee ist einfach: Durch geschickte Zeilenumformungen wird die erweiterte Koeffizientenmatrix in Stufenform (auch Dreiecksform genannt) gebracht.
In Stufenform steht in jeder Zeile eine führende Variable, die in allen darunterliegenden Zeilen den Koeffizienten 0 hat. Von dieser Form aus kann die Lösung durch Rückwärtssubstitution berechnet werden: Man beginnt bei der letzten Gleichung und setzt die gefundenen Werte sukzessive in die darüberliegenden Gleichungen ein.
Erlaubte Zeilenumformungen
Beim Gauß-Algorithmus dürfen drei elementare Zeilenumformungenangewendet werden, die die Lösungsmenge nicht verändern:
1. Zeilentausch: Zwei Zeilen werden vertauscht. Dies ist nützlich, um ein Pivot-Element ≠ 0 in die gewünschte Position zu bringen.2. Skalierung: Eine Zeile wird mit einer Zahl ≠ 0 multipliziert.3. Addition: Ein Vielfaches einer Zeile wird zu einer anderen Zeile addiert. Dies ist die Hauptoperation zur Elimination von Variablen.
Pivotisierung für numerische Stabilität
In der Praxis verwendet man die Spaltenpivotisierung: Bevor eine Variable eliminiert wird, sucht man in der entsprechenden Spalte das betragsmäßig größte Element und tauscht die zugehörige Zeile nach oben.
Dies verhindert Division durch sehr kleine Zahlen und verbessert die numerische Stabilität des Verfahrens erheblich. Ohne Pivotisierung können Rundungsfehler bei schlecht konditionierten Systemen zu falschen Ergebnissen führen.
Sonderfälle: Keine oder unendlich viele Lösungen
Nicht jedes lineare Gleichungssystem hat genau eine Lösung. Wenn während der Elimination eine Zeile der Form (0 0 ... 0 | b) mit b ≠ 0 entsteht, ist das System widersprüchlich und hat keine Lösung.
Entsteht eine Nullzeile (0 0 ... 0 | 0), ist das System unterbestimmtund hat unendlich viele Lösungen. Die freien Variablen können dann beliebig gewählt werden, und die übrigen Variablen hängen von dieser Wahl ab.