LU-Zerlegung

Position in der SkillModul 2 von 4 · Thema 2 von 3

2.2 LU-Zerlegung

—Lab-Punkte— / 100XP gesamt—Serie—

Elimination zum Merken

Das Gauß-Verfahren löst $A\mathbf{x}=\mathbf{b}$ , indem Vielfache einer Zeile von den darunterliegenden Zeilen abgezogen werden, bis die Matrix oberes Dreieck $U$ hat. Die verwendeten Multiplikatoren lohnt es sich aufzuheben: unter die Diagonale einer unteren Dreiecksmatrix $L$ mit Einsen auf der Diagonale gesetzt, ergeben sie $A=LU$ . Die Zerlegung hält die gesamte Elimination fest, die Arbeit wird also einmal geleistet und wiederverwendet.

A=LU,\qquad L\mathbf{y}=\mathbf{b},\qquad U\mathbf{x}=\mathbf{y}

(1)

Zum Lösen berechnet man zuerst $L\mathbf{y}=\mathbf{b}$ durch Vorwärtseinsetzen (von oben nach unten), dann $U\mathbf{x}=\mathbf{y}$ durch Rückwärtseinsetzen (von unten nach oben). Jeder Schritt kostet etwa $n^2$ Operationen, die Zerlegung etwa $\tfrac{2}{3}n^3$ . Bei vielen rechten Seiten (viele Szenarien mit derselben Matrix) zerlegt man einmal und zahlt pro Szenario nur $n^2$ .

Eine LU von HandSei

A=\begin{pmatrix}2&1\\4&5\end{pmatrix}

. Der Multiplikator ist

4/2=2

: Ziehen Sie das Doppelte von Zeile 1 von Zeile 2 ab, so erhalten Sie

U=\begin{pmatrix}2&1\\0&3\end{pmatrix}

und

L=\begin{pmatrix}1&0\\2&1\end{pmatrix}

. Probe:

LU=\begin{pmatrix}2&1\\4&2+3\end{pmatrix}=A

. Lösung von

A\mathbf{x}=(3,9)

L\mathbf{y}=\mathbf{b}

gibt

y_1=3

y_2=9-2\cdot3=3

; dann gibt

U\mathbf{x}=\mathbf{y}

den Wert

x_2=1

2x_1+1=3

, also

\mathbf{x}=(1,1)

$L$ : untere Dreiecksmatrix, Einsen auf der Diagonale, die Eliminationsmultiplikatoren darunter.
$U$ : obere Dreiecksmatrix, Ergebnis der Elimination; ihre Diagonale enthält die Pivots.
Pivotisierung: Zeilen tauschen, damit das Pivot groß ist; das ergibt $PA=LU$ mit einer Permutationsmatrix $P$ .

Ein Null- oder winziges Pivot erfordert einen ZeilentauschBei

\begin{pmatrix}0&1\\1&1\end{pmatrix}

ist das erste Pivot 0, und einfache Elimination teilt durch null, obwohl die Matrix durchaus invertierbar ist. Ein Zeilentausch behebt das. Ein winziges statt null gewordenes Pivot führt nicht zum Absturz, erzeugt aber riesige Multiplikatoren und ruiniert die Genauigkeit; echte Bibliotheken pivotieren deshalb immer.

Lab: Was bewertet wird

Die Matrix L15 Pkt.
Die Matrix U15 Pkt.
Eine Determinante aus U15 Pkt.
Lösen mit L und U15 Pkt.
Warum pivotisieren15 Pkt.
Die Schritte einer LU-Lösung10 Pkt.
Warum einmal zerlegen15 Pkt.

0/ 7 beantwortet

1Matrix · Vektor15 Pkt.Nicht beantwortet

Sei $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Tragen Sie den unteren Dreiecksfaktor $L$ (Einsen auf der Diagonale) von $A=LU$ ohne Zeilentausch ein.

L =

2Matrix · Vektor15 Pkt.Nicht beantwortet

Sei $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Tragen Sie den oberen Dreiecksfaktor $U$ ein.

U =

3Numerische Antwort15 Pkt.Nicht beantwortet

Die Matrix $A=\begin{pmatrix}2&1&1\\4&3&3\\8&7&9\end{pmatrix}$ zerfällt ohne Tausch in $L=\begin{pmatrix}1&0&0\\2&1&0\\4&3&1\end{pmatrix}$ und $U=\begin{pmatrix}2&1&1\\0&1&1\\0&0&2\end{pmatrix}$ . Bestimmen Sie $\det A$ .

\det A =

akzeptiert: ± 0.001

4Numerische Antwort15 Pkt.Nicht beantwortet

Sei $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Lösen Sie mit $L=\begin{pmatrix}1&0\\2&1\end{pmatrix}$ und $U=\begin{pmatrix}2&1\\0&3\end{pmatrix}$ das System $A\mathbf{x}=(5,13)$ . Wie groß ist $x_1$ ?

x_1 =

akzeptiert: ± 0.001

5Auswahl15 Pkt.Nicht beantwortet

Was geht schief, wenn man auf $\begin{pmatrix}0&1\\1&1\end{pmatrix}$ die einfache Elimination ohne Zeilentausch anwendet?

6Schritte ordnen10 Pkt.Nicht beantwortet

Bringen Sie die Schritte zur Lösung von $A\mathbf{x}=\mathbf{b}$ mit pivotisierter LU in die richtige Reihenfolge.

Zum Umsortieren ziehen, oder ein Element fokussieren, mit Leertaste anheben, mit Pfeiltasten bewegen und mit Leertaste ablegen.

1Vorwärtseinsetzen: $L\mathbf{y}=P\mathbf{b}$ lösen
2 $PA=LU$ zerlegen
3Rückwärtseinsetzen: $U\mathbf{x}=\mathbf{y}$ lösen
4Zeilentausch auf die rechte Seite anwenden: $P\mathbf{b}$

7In Worten erklären15 Pkt.Nicht beantwortet

Sie müssen $A\mathbf{x}=\mathbf{b}$ für 1000 verschiedene Vektoren $\mathbf{b}$ mit derselben Matrix $A$ lösen. Sagen Sie in zwei Sätzen, wie die LU-Zerlegung hilft.

Bewertet nach:Die Matrix wird nur einmal zerlegt und die Faktoren werden wiederverwendetJede weitere rechte Seite kostet nur zwei günstige Dreieckslösungen, etwa n zum Quadrat0 / 400 Zeichen

Mathe-ModusEingabe per Tastatur oder LaTeXAufgabe 1 von 7 · Strg ⏎ zum Prüfen

LU-Zerlegung

Position in der SkillModul 2 von 4 · Thema 2 von 3

2.2 LU-Zerlegung

—Lab-Punkte— / 100XP gesamt—Serie—

Elimination zum Merken

A=LU,\qquad L\mathbf{y}=\mathbf{b},\qquad U\mathbf{x}=\mathbf{y}

(1)

Eine LU von HandSei

A=\begin{pmatrix}2&1\\4&5\end{pmatrix}

. Der Multiplikator ist

4/2=2

: Ziehen Sie das Doppelte von Zeile 1 von Zeile 2 ab, so erhalten Sie

U=\begin{pmatrix}2&1\\0&3\end{pmatrix}

und

L=\begin{pmatrix}1&0\\2&1\end{pmatrix}

. Probe:

LU=\begin{pmatrix}2&1\\4&2+3\end{pmatrix}=A

. Lösung von

A\mathbf{x}=(3,9)

L\mathbf{y}=\mathbf{b}

gibt

y_1=3

y_2=9-2\cdot3=3

; dann gibt

U\mathbf{x}=\mathbf{y}

den Wert

x_2=1

2x_1+1=3

, also

\mathbf{x}=(1,1)

$L$ : untere Dreiecksmatrix, Einsen auf der Diagonale, die Eliminationsmultiplikatoren darunter.
$U$ : obere Dreiecksmatrix, Ergebnis der Elimination; ihre Diagonale enthält die Pivots.
Pivotisierung: Zeilen tauschen, damit das Pivot groß ist; das ergibt $PA=LU$ mit einer Permutationsmatrix $P$ .

Ein Null- oder winziges Pivot erfordert einen ZeilentauschBei

\begin{pmatrix}0&1\\1&1\end{pmatrix}

Lab: Was bewertet wird

Die Matrix L15 Pkt.
Die Matrix U15 Pkt.
Eine Determinante aus U15 Pkt.
Lösen mit L und U15 Pkt.
Warum pivotisieren15 Pkt.
Die Schritte einer LU-Lösung10 Pkt.
Warum einmal zerlegen15 Pkt.

0/ 7 beantwortet

1Matrix · Vektor15 Pkt.Nicht beantwortet

Sei $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Tragen Sie den unteren Dreiecksfaktor $L$ (Einsen auf der Diagonale) von $A=LU$ ohne Zeilentausch ein.

L =

2Matrix · Vektor15 Pkt.Nicht beantwortet

Sei $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Tragen Sie den oberen Dreiecksfaktor $U$ ein.

U =

3Numerische Antwort15 Pkt.Nicht beantwortet

\det A =

akzeptiert: ± 0.001

4Numerische Antwort15 Pkt.Nicht beantwortet

x_1 =

akzeptiert: ± 0.001

5Auswahl15 Pkt.Nicht beantwortet

Was geht schief, wenn man auf $\begin{pmatrix}0&1\\1&1\end{pmatrix}$ die einfache Elimination ohne Zeilentausch anwendet?

6Schritte ordnen10 Pkt.Nicht beantwortet

Bringen Sie die Schritte zur Lösung von $A\mathbf{x}=\mathbf{b}$ mit pivotisierter LU in die richtige Reihenfolge.

Zum Umsortieren ziehen, oder ein Element fokussieren, mit Leertaste anheben, mit Pfeiltasten bewegen und mit Leertaste ablegen.

1Vorwärtseinsetzen: $L\mathbf{y}=P\mathbf{b}$ lösen
2 $PA=LU$ zerlegen
3Rückwärtseinsetzen: $U\mathbf{x}=\mathbf{y}$ lösen
4Zeilentausch auf die rechte Seite anwenden: $P\mathbf{b}$

7In Worten erklären15 Pkt.Nicht beantwortet

Sie müssen $A\mathbf{x}=\mathbf{b}$ für 1000 verschiedene Vektoren $\mathbf{b}$ mit derselben Matrix $A$ lösen. Sagen Sie in zwei Sätzen, wie die LU-Zerlegung hilft.

Bewertet nach:Die Matrix wird nur einmal zerlegt und die Faktoren werden wiederverwendetJede weitere rechte Seite kostet nur zwei günstige Dreieckslösungen, etwa n zum Quadrat0 / 400 Zeichen

Mathe-ModusEingabe per Tastatur oder LaTeXAufgabe 1 von 7 · Strg ⏎ zum Prüfen

LU-Zerlegung

Elimination zum Merken

Lab: Was bewertet wird

Melde dich an, um deinen Code auszuführen.

LU-Zerlegung

Elimination zum Merken

Lab: Was bewertet wird

Melde dich an, um deinen Code auszuführen.