LU-Zerlegung

Studium

A = L \cdot U

Voraussetzung: $A \in \mathbb{R}^{n \times n},$ $Gauß-Elimination ohne Zeilentausch durchführbar$

$A$: quadratische Koeffizientenmatrix
$L$: untere Dreiecksmatrix mit Einsen auf der Diagonalen; enthält die Eliminationsfaktoren
$U$: obere Dreiecksmatrix, das Ergebnis der Gauß-Elimination

Die LU-Zerlegung schreibt eine Matrix als Produkt einer unteren und einer oberen Dreiecksmatrix, wie sie die Gauß-Elimination liefert.

Erklärung

Die LU-Zerlegung (auch LR-Zerlegung) ist die Gauß-Elimination in Matrixform. Man formt $A$ durch Abziehen von Vielfachen oberer Zeilen in eine obere Dreiecksmatrix $U$ um und merkt sich jeden Faktor $l_{ij}$ , mit dem Zeile $j$ von Zeile $i$ abgezogen wurde. Diese Faktoren bilden, mit Einsen auf der Diagonalen, die untere Dreiecksmatrix $L$ .

Damit löst man $Ax = b$ in zwei einfachen Schritten:

Vorwärtseinsetzen: $L\,y = b$ von oben nach unten lösen.
Rückwärtseinsetzen: $U\,x = y$ von unten nach oben lösen.

Die Zerlegung kostet etwa $\frac{2}{3}n^3$ Rechenoperationen, jedes weitere Einsetzen nur etwa $2n^2$ . Bei vielen Systemen mit derselben Matrix und verschiedenen rechten Seiten zerlegt man daher einmal und setzt mehrfach ein. Nebenbei ergibt sich $\det A = u_{11} \cdot u_{22} \cdots u_{nn}$ .

Ohne Zeilentausch existiert die Zerlegung nur, wenn bei der Elimination kein Pivotelement null wird. Im Allgemeinen und aus Stabilitätsgründen tauscht man Zeilen (Spaltenpivotisierung) und erhält $PA = LU$ mit einer Permutationsmatrix $P$ . Diese Zerlegung existiert für jede invertierbare Matrix.

Beispiele

A = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{pmatrix}

Erste Spalte: Zeile 2 minus $2 \cdot$ Zeile 1, Zeile 3 minus $4 \cdot$ Zeile 1. Das ergibt die Zeilen $(0, 1, 1)$ und $(0, 3, 5)$ . Zweite Spalte: neue Zeile 3 minus $3 \cdot$ neue Zeile 2 ergibt $(0, 0, 2)$ . Also

L = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 4 & 3 & 1 \end{pmatrix}, \qquad U = \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{pmatrix}

und $\det A = 2 \cdot 1 \cdot 2 = 4$ .

Für $b = (4, 10, 24)$ liefert Vorwärtseinsetzen $y_1 = 4$ , $y_2 = 10 - 2 \cdot 4 = 2$ , $y_3 = 24 - 4 \cdot 4 - 3 \cdot 2 = 2$ . Rückwärtseinsetzen ergibt $x_3 = 1$ , $x_2 = 2 - 1 = 1$ , $x_1 = \frac{4 - 1 - 1}{2} = 1$ , also $x = (1, 1, 1)$ .

Typische Fehler

Die Faktoren mit falschem Vorzeichen in $L$ eintragen. Wird das $2$ -Fache abgezogen, steht in $L$ eine $+2$ .
Für die Faktoren der zweiten Spalte die ursprünglichen statt der bereits umgeformten Zeilen verwenden.
Die Zerlegung erzwingen, obwohl ein Pivot null ist. $\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$ hat keine LU-Zerlegung ohne Zeilentausch.
Bei $PA = LU$ vergessen, auch $b$ zu permutieren: Man löst $Ly = Pb$ .

LU-Zerlegung

LU-Zerlegung

Erklärung

Beispiele

Typische Fehler

Verwandte Formeln