Wer in deutschen Bibliotheken stöbert, hat den Kopf dabei meist nach links geneigt, weil die Rückenbeschriftung der Bücher gewöhnlich von unten nach oben geht. In dieser Haltung würde man das nebenstehende Verkehrszeichen in eine linke und eine rechte Hälfte geteilt sehen. Im englischen Sprachraum laufen dagegen die Rückentexte von oben nach unten, was zu einer Rechtsneigung des Kopfes führt. Das Schild erscheint dann in eine untere (lower) und eine obere (upper) Hälfte geteilt. Dies erklärt, warum die im Folgenden eingeführte „LR-Zerlegung“ auf englisch „LU-Zerlegung“ heißt.
1. Lösung linearer Gleichungen mit LR-Zerlegung
Ein erstes Beispiel
Betrachten wir das folgende lineare Gleichungssystem:
\begin{pmatrix} 1 & 2 & 3 \\ 2 & 9 & 10 \\ 3 & 26 & 24 \end{pmatrix}
\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}
= \begin{pmatrix} 3 \\ 7 \\ 15 \end{pmatrix}
Die Koeffizientenmatrix lässt sich folgendermaßen als Produkt aus einer linken (unteren) und einer rechten (oberen) Dreiecksmatrix schreiben:
\begin{pmatrix} 1 & 2 & 3 \\ 2 & 9 & 10 \\ 3 & 26 & 24 \end{pmatrix}
= \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 4 & 1 \end{pmatrix}
\begin{pmatrix} 1 & 2 & 3 \\ 0 & 5 & 4 \\ 0 & 0 & -1 \end{pmatrix}
Hilft uns dies bei der Lösung des Gleichungssystems?
Das Gleichungssystem lässt sich damit so schreiben:
{\pink{
\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 4 & 1 \end{pmatrix}}}
\cdot {\green{\begin{pmatrix} 1 & 2 & 3 \\ 2 & 9 & 10 \\ 3 & 26 & 24 \end{pmatrix}
\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}}}
= \begin{pmatrix} 3 \\ 7 \\ 15 \end{pmatrix}
Wenn wir das grüne Produkt y nennen, haben wir die Gleichung
\pink{\begin{pmatrix}1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 4 & 1 \end{pmatrix}}
\cdot \green{\textbf y} = \begin{pmatrix}3 \\ 7 \\ 15 \end{pmatrix}
zu lösen: Aus der ersten Zeile können wir direkt y_1 = 3 ablesen.
Dies in die zweite Zeile eingesetzt, ergibt y_2 = 7 - 2y_1 = 1.
Entsprechend ergibt sich y_3 = 15 - 3y_1 - 4y_2 = 2.
Das Prinzip
Wir halten fest: Wenn sich die Matrix A als Produkt aus einer
linken Dreiecksmatrix L und einer rechten Dreiecksmatrix
R schreiben lässt, dann wird das Gleichungssystem
A \textbf x = \textbf b zu
L R \textbf x = \textbf b
und mit dem Ansatz
R \textbf x = \textbf y
wird daraus
L \textbf y = \textbf b
Das Gleichungssystem lässt sich besonders einfach in zwei Schritten lösen:
- Das Gleichungssystem
L \textbf y = \textbf bnach\textbf yauflösen, - Das Gleichungssystem
R \textbf x = \textbf ynach\textbf yauflösen.
Aber wie kann man eine Matrix in die beiden Faktoren L und R zerlegen?
LR-Zerlegung für 2·2-Matrizen
Wir versuchen es zunächst für den einfachen Fall einer 2·2-Matrix.
In unserem Beispiel hatte die untere Dreiecksmatrix auf der Hauptdiagonalen nur Einsen.
Das wollen wir hier wieder erreichen.
Damit bleiben nur noch vier unbekannte Elemente:
\yellow{\begin{pmatrix}a_{11} & a_{12} \cr a_{21} & a_{22}\end{pmatrix}}
=
\pink{\begin{pmatrix}1 & 0 \cr x & 1\end{pmatrix}}
\cdot
\green{\begin{pmatrix}u & v \cr 0 & w\end{pmatrix}}
= \yellow{\begin{pmatrix}u & v \cr ux & xv+w\end{pmatrix}}
Der Vergleich beider Varianten der gelben Matrix ergibt:
\begin{aligned}
\green u & = a_{11} \cr
\green v & = a_{12} \cr
ux=a_{21} \Rightarrow \pink x & = \frac{a_{21}}{a_{11}} \cr
xv+w=a_{22} \Rightarrow \green w & = a_{22} - \frac{a_{21}}{a_{11}} a_{12}
\end{aligned}
und damit
\yellow{\begin{pmatrix}a_{11} & a_{12} \cr a_{21} & a_{22}\end{pmatrix}}
= \pink{\begin{pmatrix}1 & 0 \cr \frac{a_{21}}{a_{11}} &a 1\end{pmatrix}}
\cdot
\green{
\begin{pmatrix}
a_{11} & a_{12} \cr
0 & a_{22} - \frac{a_{21}}{a_{11}} a_{12}
\end{pmatrix}}
Leider funktioniert das nicht für alle invertierbaren Matrizen,
denn die beiden Divisionen verlangen, dass a_{11}
von Null verschieden ist, was z.B. bei der invertierbaren Matrix
\begin{pmatrix}0 & 1 \cr 1 & 0 \end{pmatrix}
nicht der Fall ist. Die Umgehung dieses Problems verschieben wir und
erweitern zunächst unsere Methode auf beliebige n\cdot n-Matrizen.
Fortsetzung: 2. Ein einfacher rekursiver Algorithmus mit einem Schönheitsfehler
