LUP-Zerlegung
1. Lösung linearer Gleichungen mit LU-Zerlegung
Ein erstes Beispiel
Betrachten wir das folgende lineare Gleichungssystem:
\pmatrix{1 & 2 & 3 \cr
2 & 9 & 10 \cr
3 & 26 & 24 } \pmatrix{x_1 \cr x_2 \cr x_3} = \pmatrix{3 \cr 7 \cr 15}
Die Koeffizientenmatrix lässt sich folgendermaßen als Produkt aus einer unteren (linken)
und einer oberen (rechten) Dreiecksmatrix schreiben:
\pmatrix{1 & 2 & 3 \cr
2 & 9 & 10 \cr
3 & 26 & 24 }
= \pmatrix{1 & 0 & 0 \cr
2 & 1 & 0 \cr
3 & 4 & 1 }
\pmatrix{1 & 2 & 3 \cr
0 & 5 & 4 \cr
0 & 0 & -1 }
Hilft uns dies bei der Lösung des Gleichungssystems?
Das Gleichungssystem lässt sich damit so schreiben:
\def\pink{\bbox[#ffe0e0,2pt]}
\def\green{\bbox[#c0ffc0,2pt]}
\pink{
\pmatrix{1 & 0 & 0 \cr
2 & 1 & 0 \cr
3 & 4 & 1 }}
\cdot
\green{
\pmatrix{1 & 2 & 3 \cr
0 & 5 & 4 \cr
0 & 0 & -1 }
\pmatrix{x_1 \cr x_2 \cr x_3}}
= \pmatrix{3 \cr 7 \cr 15}
Wenn wir das grüne Produkt y nennen,
haben wir die Gleichung
\def\pink{\bbox[#ffe0e0,2pt]}
\def\green{\bbox[#c0ffc0,2pt]}
\pink{
\pmatrix{1 & 0 & 0 \cr
2 & 1 & 0 \cr
3 & 4 & 1 }
}
\cdot
\green{\textbf y}
= \pmatrix{3 \cr 7 \cr 15}
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
unteren Dreiecksmatrix L und einer oberen Dreiecksmatrix
U schreiben lässt, dann wird das Gleichungssystem
A \textbf x = \textbf b zu
L U \textbf x = \textbf b
und mit dem Ansatz
U \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 b
nach \textbf y auflösen,
- Das Gleichungssystem U \textbf x = \textbf y
nach \textbf y auflösen.
Aber wie kann man eine Matrix in die beiden Faktoren L und U 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:
\def\yellow{\bbox[#ffffa0,2pt]}
\def\pink{\bbox[#ffe0e0,2pt]}
\def\green{\bbox[#c0ffc0,2pt]}
\yellow{
\pmatrix{a_{11} & a_{12} \cr
a_{21} & a_{22}}}
=
\pink{
\pmatrix{1 & 0 \cr
x & 1}}
\cdot
\green{
\pmatrix{u & v \cr
0 & w}}
=
\yellow{
\pmatrix{u & v \cr
ux & xv+w}}
Der Vergleich beider Varianten der gelben Matrix ergibt:
\def\pink{\bbox[#ffe0e0,2pt]}
\def\green{\bbox[#c0ffc0,2pt]}
\eqalign{
\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}
}
und damit
\def\yellow{\bbox[#ffffa0,2pt]}
\def\pink{\bbox[#ffe0e0,2pt]}
\def\green{\bbox[#c0ffc0,2pt]}
\yellow{
\pmatrix{a_{11} & a_{12} \cr
a_{21} & a_{22}}}
=
\pink{
\pmatrix{1 & 0 \cr
\frac{a_{21}}{a_{11}} & 1}}
\cdot
\green{
\pmatrix{a_{11} & a_{12} \cr
0 & a_{22} - \frac{a_{21}}{a_{11}} a_{12}}}
Leider funktioniert das nicht für alle invertierbaren Matrizen,
denn die beiden Divisionen durch Null verlangen, dass a11
von Null verschieden ist, was z.B. bei der invertierbaren Matrix
\pmatrix{0 & 1 \cr 1 & 0}
nicht der Fall ist. Die Umgehung dieses Problems verschieben wir und
erweitern zunächst unsere Methode auf beliebige n·n-Matrizen.
Fortsetzung: 2. Ein einfacher rekursiver Algorithmus mit einem Schönheitsfehler