Gauß-Jordan-Algorithmus

Author: Hans Lohninger

Der Gauß-Jordan-Algorithmus kann dazu verwendet werden, lineare Gleichungen zu lösen und/oder die Inverse einer Matrix zu berechnen. Der Gauß-Jordan-Algorithmus basiert auf Äquivalenzoperationen. Obwohl dieser Algorithmus leicht zu verstehen ist, ist er nicht der beste Weg, um lineare Gleichungen zu lösen, denn er dauert bis zu dreimal so lange wie der beste verfügbare Algorithmus und benötigt zusätzlichen Speicherplatz.

Das Prinzip des Algorithmus ist einfach: Das System von zu lösenden linearen Gleichungen wird als rechteckige Matrix aufgeschrieben (die Koeffizienten und die Konstanten des Gleichungssystems), möglicherweise durch eine Einheitsmatrix vergrößert, wenn die invertierte Matrix auch gewünscht ist. Diese rechteckige Matrix wird nun durch Äquivalenzoperationen so verändert und neu arrangiert, dass die originale Submatrix von den Koeffizienten der Gleichungen zu einer Einheitsmatrix wird.

Stellen wir uns zum Beispiel vor, das folgende Gleichungssystem wäre zu lösen:

Als Erstes müssen wir die unbekannten Variablen in eine gerade Linie bringen. Variablen, die in einer bestimmten Gleichung nicht verwendet werden, werden mit einem Koeffizienten von null eingetragen:

Von diesem Gleichungssystem extrahieren wir die Koeffizienten auf der linken Seite und die Konstanten auf der rechten Seite (blau), um eine rechteckige Matrix zu formen:

Benötigen wir die Inverse der Koeffizientenmatrix, müssen wir auch die Einheitsmatrix (rot) addieren, so dass wir letztlich mit der folgenden Matrix starten:

Um dieses System zu lösen, müssen wir Äquivalenzoperationen so anwenden, dass die schwarze quadratische Submatrix eine Einheitsmatrix wird. So erhalten wir folgende Matrix:

Nun enthält der blaue Vektor die Lösungen und die rote vorherige Einheitsmatrix beinhaltet die Inverse der originalen (schwarzen) Koeffizientenmatrix. Daraus ergibt sich die Lösung des linearen Gleichungssystems mit: