# 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 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:

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