home

LRP-Zerlegung

1. Lösung linearer Gleichungen mit LR-Zerlegung

2. Ein einfacher rekursiver Algorithmus mit einem Schönheitsfehler

3. Umformung in eine Iteration

4. Beseitigung des Schönheitsfehlers: LRP-Zerlegung

2. Ein einfacher rekursiver Algorithmus mit einem Schönheitsfehler

Wir gliedern die quadratische n·n-Matrix A = \begin{pmatrix} a_{11} & a_{12} & \ldots & a_{1n} \cr a_{21} & a_{22} & \ldots & a_{2n} \cr \vdots & \vdots & \ddots & \vdots \cr a_{n1} & a_{n2} & \ldots & a_{nn} \end{pmatrix} in vier Teilmatrizen:

A = \begin{pmatrix} \yellow{\begin{matrix}a_{11}\end{matrix}} & \blue{\begin{matrix}a_{12} & \ldots & a_{1n}\end{matrix}} \cr \blue{\begin{matrix}a_{21} \cr \vdots \cr a_{n1}\end{matrix}} & \yellow{\begin{matrix} a_{22} & \ldots & a_{2n} \cr \vdots & \ddots & \vdots \cr a_{n2} & \ldots & a_{nn} \end{matrix}} \end{pmatrix}

Die Elemente dieser Zerlegung (statt A' schreiben wir A1) können wir in mathGUIde so schreiben:

v = A.submatrix(1,0, n-1,1)
w = A.submatrix(0,1, 1,n-1)

A1 = A.submatrix(1,1, n-1,n-1)

Zum Verständnis: Die Matrizen-Indizes zählen in mathGUIde nicht ab 1 sondern ab Null (um mit den JavaScript-Arrays kompatibel zu bleiben). Der submatrix-Methode übergibt man in den ersten beiden Parametern die Zeile und Spalte des linken oberen Elements der Untermatrix, dann die Anzahl der zu übernehmenden Zeilen und Spalten.

Durch Ausmultiplizieren sieht man, dass diese Matrix in folgendes Produkt zerlegt werden kann, vorausgesetzt, dass a_{11} von Null verschieden ist: A = \begin{pmatrix}1 & \textbf 0 \cr \frac{1}{a_{11}} \textbf{v} & I_{n-1}\end{pmatrix} \begin{pmatrix}a_{11} & \textbf w \cr \textbf 0 & \yellow{A' - \frac{1}{a_{11}} \textbf{v w}}\end{pmatrix}

Wir ziehen uns jetzt an den eigenen Haaren aus dem Sumpf, indem wir das Problem auf eine kleinere Matrix abwälzen, nämlich auf die gelb unterlegte (n-1)·(n-1)-Matrix. Nehmen wir also einmal an, dass wir diese als Produkt einer linken (lower) und einer rechten (upper) Dreiecksmatrix darstellen können:

B = \yellow{A' - \frac{1}{a_{11}} \textbf{v w}} = L' R'

Damit erhalten wir

A = \begin{pmatrix} 1 & \textbf 0 \cr \frac{1}{a_{11}}\textbf v & I_{n-1} \end{pmatrix} \begin{pmatrix} a_{11} & \textbf w \cr \textbf 0 & \yellow{L'R'} \end{pmatrix} = \pink{ \begin{pmatrix} 1 & \textbf 0 \cr \frac{1}{a_{11}} \textbf v & L' \end{pmatrix} } \green{ \begin{pmatrix} a_{11} & \textbf w \cr \textbf 0 & R' \end{pmatrix} }

Man sieht leicht, dass die rötlich unterlegte Matrix eine untere Dreiecksmatrix ist und die grün unterlegte eine obere Dreiecksmatrix.

Vorausgesetzt, dass wir nicht auf eine Division durch Null stoßen (das ist der wunde Punkt, den wir noch klären müssen), können wir also durch rekursive Anwendung dieser Zerlegung eine n·n-Matrix in eine untere und eine obere Dreiecksmatrix zerlegen.
Wir müssen nur dafür sorgen, dass die Rekursion abbricht. Dazu behandeln wir die 1·1-Matrizen separat: Jede 1·1-Matrix ist ja immer gleichzeitig eine untere und auch eine obere Dreiecksmatrix, da sie nur aus der Hauptdiagonale besteht.
Wir können dann einfach schreiben:

\begin{pmatrix}a_{11}\end{pmatrix} = \pink{\begin{pmatrix}1\end{pmatrix}} \green{\begin{pmatrix}a_{11}\end{pmatrix}}

Diese Rekursion können wir jetzt in eine mathGUIde-Funktion übernehmen:

Ein weiterer Test mit einer 4·4-Matrix:

Fortsetzung: 3. Umformung in eine Iteration

home