Gaußscher Eliminationsalgorithmus

Beschreibung

Der Gaußsche Eliminationsalgorithmus ist ein Algorithmus, der verwendet wird, um ein Lineares Gleichungssystem zu lösen. Es zerlegt eine Matrix eines Gleichungssystem in eine Unitäre Matrix und eine Matrix in Stufenform.

Bei beiden Matrizen lässt sich das Gleichungssystem leicht lösen. Bei ersterem durch Adjunktion.

Definition

Siehe https://de.wikipedia.org/wiki/Gau%C3%9Fsches_Eliminationsverfahren Ich habe keine Lust, das Verfahren zu erklären.

LR-Zerlegung

Die LR-Zerlegung ist ein Spezialfall des Gaußschen Eliminiationsalgorithmus. Er ist besonders leicht von Computern umzusetzen. Die LR-Zerlegung zerlegt eine Invertierbare Matrix $A$ in ein Produkt einer linken unteren, normierten Dreiecksmatrix und eine rechten oberen Dreiecksmatrix. $A=L\cdot R$

LR-Zerlegung mit Permutation

In der Numerik wird die LR-Zerlegung selten verwendet. Grund ist, dass die Kondition eines linearen Gleichungssystems sehr schlecht ist. Die Relative Kondition kann sehr hoch sein. Eine Möglichkeit, die Kondition zu verringern, ist Pivotstrategien zu benutzen.

Hierfür vertauscht man zuerst mit einer Permutationsmatrix $P$ Zeilen von $A$. Man erhält $PA=LR$

Eigenschaften

Konstruktion der Zerlegung

Wir konstrieren die Zerlegung, indem wir durch das Abziehen von Zeilen $A$ in eine rechte Dreicksmatrix umformen. Die Umformungsschritte merken schreiben wir dann links unten in eine Identitätsmatrix ein.

Das Vorgehen ist folgendes: Bringen wir den Matrixwert $a_{ij}$ auf $0$, indem wir von der $i$-ten Zeile $x$-mal die $k$-te Zeile abziehen, so schreiben wir in $l_{ij}$ unserer “Speichermatrix” den Wert $x$.

Q: Beschreibe das Vorgehen der LR-Zerlegung: A: Bringen wir den Matrixwert $a_{ij}$ auf $0$, indem wir von der $i$-ten Zeile $x$-mal die $k$-te Zeile abziehen, so schreiben wir in $l_{ij}$ unserer “Speichermatrix” den Wert $x$.

Transformationsmatrix

Indem man sich die auf $A$ durchgeführten Transformationen merkt, erhält man eine Transformationsmatrix $L$