# LUP-Zerlegung

1. Lösung linearer Gleichungen mit LU-Zerlegung
2. Ein einfacher rekursiver Algorithmus mit einem Schönheitsfehler
3. Umformung in eine Iteration
4. Beseitigung des Schönheitsfehlers: 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 y1 = 3 ablesen.
Dies in die zweite Zeile eingesetzt, ergibt y2 = 7 - 2 y1 = 1.
Entsprechend ergibt sich y3 = 15 - 3 y1 - 4 y2 = 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 x = 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:

1. Das Gleichungssystem L y = b nach y auflösen,
2. Das Gleichungssystem U x = y nach x 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