Motivation: Unterschied zwischen den Versionen
Elias (Diskussion | Beiträge) |
Elias (Diskussion | Beiträge) |
||
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
Zeile 22: | Zeile 22: | ||
x_n = b_n / a_nn | 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. |
Aktuelle Version vom 9. März 2020, 20:07 Uhr
Inhaltsverzeichnis
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.