Eliminationsverfahren

Eliminationsverfahren bezeichnet eine Gruppe von Methoden zur Lösung linearer Gleichungssysteme durch Eliminieren von Variablen. Ziel ist es, das System in eine einfachere Form zu überführen, aus der die Lösung direkt abgeleitet werden kann. Die bekannteste Umsetzung ist die Gaussian-Elimination, es gibt jedoch mehrere Varianten wie Gauss-Jordan-Elimination und LU-Zerlegung, die das gleiche Grundprinzip mit unterschiedlichen Schwerpunkten nutzen.

Typischer Ablauf: Man beginnt mit der augmentierten Matrix [A|b] eines Systems Ax = b. Durch elementare Zeilenoperationen wird A schrittweise in eine obere Dreiecksmatrix (Row Echelon Form) oder sogar in eine Identitätsmatrix überführt. Danach erfolgt Rücksubstitution, das heißt man bestimmt von unten nach oben die Werte der Variablen. Häufig wird eine Vorwärtspivotisierung (Pivoting) eingesetzt, um numerische Stabilität zu gewährleisten, besonders bei schlecht konditionierten oder singulären Matrizen. Die Komplexität liegt grob bei O(n^3) für ein n × n-System.

Varianten: Die Gaussian-Elimination besteht aus Vorwärtselimination und Rücksubstitution. Die Gauss-Jordan-Elimination zielt darauf ab, die linke Seite der Matrix während der Elimination schrittweise zu einer Einheitsmatrix zu transformieren, wodurch die Lösung direkt sichtbar wird. Die LU-Zerlegung zerlegt A in ein Produkt aus einer unteren und einer oberen Dreiecksmatrix (A = LU), was besonders bei mehreren rechten Seiten (b) vorteilhaft ist.

Anwendungen: Lösung linearer Gleichungssysteme in Technik, Physik, Computergrafik und Ökonomie; Berechnung von Matrixinversen; Least-Squares-Lösungen über Normalgleichungen oder QR-Zerlegung.

Geschichte: Das Verfahren ist eng mit Carl Friedrich Gauss verbunden, dessen Arbeiten die Grundlage der Gauss-Elimination bilden. Heute sind Eliminationsverfahren fundamentale Bausteine der linearen Algebra.