Der Gauß-Algorithmus

• Der Gauß-Algorithmus ist der wohl bekannteste Universallöser für lineare Gleichungssysteme Ax=b mit quadratischen Matrizen A.
• Zu einer regulären Matrix A wird eine Zerlegung in zwei Dreiecksmatrizen L (untere Dreiecksmatrix) und R (obere Dreiecksmatrix) berechnet mit PAQ = LR. Dabei sind P und Q zwei Permutationsmatrizen. Man kann stets Q als Einheitsmatrix wählen, aber auf die Zeilenvertauschungen kann man nicht immer verzichten.
• Realisiert wird die Zerlegung mittels Linearkombination einzelner Zeilen der Matrix A. Eine Anwendung der gleichen Kombinationen auf den Vektor b liefert schließlich das gestaffelte Gleichungssystem Rx=b, mit oberer Dreiecksmatrix R, das dann die Lösung x durch die sogenannte Rücksubstitution liefert.
• Um den Einfluß von Rundungsfehlern zu reduzieren, kann durch Vertauschen einzelner Zeilen (Spalten-Pivotisierung) dafür gesorgt werden, daß der Betrag der Elemente der Matrix L kleiner oder gleich 1 ist. Die Zerlegung der Matrix A hat dann die Form PA=LR mit einer Permutationsmatrix P. Mit der sogenannten Restmatrix-Pivotsuche, die auch Spaltentausch beinhaltet, kann man das sogenannte ''Pivotwachstum'', also das Anwachsen der Elemente in R relativ zu denen in A noch weiter dämpfen. Diese Implementierung ist vor allem zur Demonstration des Rundungsfehlereinflusses gedacht.
• Der Rechenaufwand beim Gauß-Algorithmus ist O(n³) bei voll besetzter Matrix. Es gibt aber spezielle Varianten für große sogenannte dünnbesetzte Matrizen.

Die Eingaben

• n ist die Dimension der quadratischen Matrix A und darf den Wert 11 nicht überschreiten.
• Es kann angegeben werden, ob ohne Pivotisierung, mit Spalten-Pivotisierung oder mit Restmatrix-Pivotisierung gerechnet werden soll.
• Die Eingabe des Gleichungssystems erfolgt formatfrei und zeilenweise incl. rechte Seite. So steht z.B. 1,2,3,6  für die Gleichung 1*x₁+2*x₂+3*x₃ = 6. Eine Trennung der Zahlen kann durch Leerzeichen bzw. Kommata erfolgen. Erlaubt sind die Zahlendarstellungen der Programmiersprache FORTRAN.

Die Ausgaben

• Die berechete Lösung x_berechnet des Systems Ax=b.
• Das Residuum Ax_berechnet-b in der berechneten Lösung.
• Die berechnete L-R- Zerlegung.
• Eine mit einer rudimentären Form der ''inversen Iteration'' (siehe ''Eigenwertproblem'') berechnete Schätzung der Konditionszahl der Matrix, also ||A||||A^{-1}||, in der 1-Norm.

Fragen ?!

• Wie verhält sich das Residuum bei starken Unterschieden in den Größenordnungen der Matrixelemente bezüglich der Pivotisierung ?
• Vergleichen Sie bei einem System mit bekannter Lösung die Resultate mit und ohne Pivotisierung.
• Gibt es einen einfachen Zusammenhang zwischen der Größe des Residuums und der Genauigkeit in der Lösung ?

Das Eingabeformular

Zurück: Lineare Gleichungssysteme