Motivation

Einleitung

Viele Probleme in der Mathematik lassen sich auf lineare Gleichungssysteme zurückführen. Im Folgenden wollen wir uns daher damit beschäftigen, wie man entsprechende LGS mithilfe eines Eliminationsverfahrens mit Spaltenpivotierung lösen kann und wollen insbesondere auf die Implementierung in Java eingehen. Diese Anwendung soll hierbei nur die Möglichkeiten von Java verdeutlichen und nicht auf eine Optimierung der Laufzeit oder Ausnutzung spezieller Besetzungsstrukturen von Matrizen beruhen.

Wir wollen letztlich eine Implementierung einer direkten Lösungsmethode für (reguläre, reelle) quadratische lineare Gleichungssysteme erstellen und diese anwenden. Die Implementierung basiert im Wesentlichen auf dem Gaußschen Eliminationsverfahren, welches durch diverse Veranstaltungen bekannt ist.

Gestaffelte Systeme

Wenn wir eine obere Dreiecksmatrix A als Koeffizientmatrix unseres regulären LGS haben, lässt sich dies leicht durch rückwärts einsetzen lösen: In der letzten Zeile ist nur eine unbekannte Komponente des Vektors in einer linearen Gleichung, in der vorletzten Zeile gibt es nur zwei Unbekannte, wobei wir eine der Unbekannten schon durch vorherige bestimmen können und damit diese Gleichung uns durch Umstellen noch eine Unbekannte bestimmen lässt. So erhalten wir für Systeme der Form

a_11*x_1 + a_12*x_2 + ... + a_1n*x_n = b_1
           a_22*x_2 + ... + a_2n*x_n = b_2
                                    ...
                            a_nn*x_n = b_n

folgenden Algorithmus:

Sukzessives Rückwärtseinsetzen

Da wir nur reguläre Systeme betrachten, müssen die Diagonaleinträge der oberen Dreiecksmatrix stets ungleich 0 nach Grundkenntnissen der Linearen Algebra sein. somit können wir durch Umstellen und Dividieren eine Lösung erhalten:

x_n = b_n / a_nn
x_j = (b_j- (a_j(j+1)*x_j+1 ... a_jn*x_n) )/a_jj

Anwendung bei allgemeiner Koeffizientenmatrix

Nach Grundkenntnissen der Linearen Algebra wissen wir, dass wir bei einem LGS folgende Rechenschritte vornehmen können, ohne die Lösung zu verändern:

(1) Wir können Zeilen vertauschen. Hierbei wird stets eine ganze Zeile der Matrix und der rechte entsprechende Vektoreintrag mit einer anderen Zeile und einem Vektoreintrag getauscht.
(2) Wir können alle Einträge der Matrix und des Vektors mit einer reellen Zahl ungleich 0 multiplizieren.
(3) Wir können zu einer Zeile eine andere hinzuaddieren.

Mit diesen Umformungen ist es stets möglich, ein reguläres LGS in die Form zu bringen, dass die Koeefizientenmatrix eine obere Dreiecksmatrix ist. Dieses Umformen bezeichnet man als Eliminationsverfahren, da wir so unter der Hauptdiagonalen die Elemente "eliminieren". Anschließend können wir das LGS dann durch Rückwärtseinsetzen lösen.