L(D)U - Faktorisierung < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Man löse das folgende System, in dem man eine LU - Faktorisierung benutze:
Ax [mm] =\pmat{ 2 & 1 & 1 & 1 \\ 4 & 1 & 0 & 1 \\ -2 & 2 & 1 & 1 } \vektor{x_1 \\ x_2 \\ x_3 \\ x_4 } [/mm] = [mm] \vektor{1 \\ -2 \\ 7} [/mm] = b |
huhu,
Ich muss mir dieses Thema irgendwie selber beibringen. In unserem SKript ist nur diese eine Beispielaufgabe drin, also jeweils eine zur LU und dann eine mit Übergang zu LDU -Faktorisierung. Die Aufgabe ist arg lang, hoffe es gibt unter euch welche die sich das antun wollen ;)
Also:
erster Schritt nach Aufgabenstellung lautet:
"Man rechnet nach, dass die Elementarmatrizen wie folgt aussehen":
[mm] E_1: \pmat{ 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 } [/mm] , [mm] E_2: \pmat{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 } [/mm] , [mm] E_3: \pmat{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 3 & 1 }
[/mm]
, sodass sich ergibt:
[mm] E_3 [/mm] * [mm] E_2 [/mm] * [mm] E_1 [/mm] * A = [mm] \pmat{ 2 & 1 & 1 & 0 \\ 0 & -1 & -2 & 1 \\ 0 & 0 & -4 & 4 } [/mm] = U
---------------------
meine Frage, nach Abtippen eigentlich sogar dir einzig wirklich wichtige: Wie berechne ich diese Elementarmatrizen?
---------------------
Wenn wir nun setzen:
L = [mm] E_1^{-1} [/mm] * [mm] E_2^{-1} [/mm] * [mm] E_3^{-1} [/mm] = [mm] \pmat{ 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 } [/mm] ,was also eine untere Dreiecksmatrix darstellt mit Einsen auf der Haptdiagonalen, dann ist:
A = LU = [mm] \pmat{ 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 } [/mm] * [mm] \pmat{ 2 & 1 & 1 & 0 \\ 0 & -1 & -2 & 1 \\ 0 & 0 & -4 & 4 }
[/mm]
Nun kann das System Ly = b:
[mm] y_1 [/mm] = 1
[mm] 2y_1 +y_2 [/mm] =-2
[mm] -y_1 -3y_2 +y_3 [/mm] =7
gelöst werden und es ergibt sich:
y= (1,-4,-4) und das System
Ux = y:
[mm] 2x_1 [/mm] + [mm] x_2 [/mm] + x= 1
[mm] -x_2 -2x_3 [/mm] + [mm] x_4 [/mm] = -4
[mm] -4x_3 [/mm] + [mm] 4x_4 [/mm] = -4
und wir erhalten:
x = [mm] \vektor{x_1 \\ x_2 \\ x_3 \\ x_4} [/mm] = [mm] \vektor{-1 \\ 2 \\ 1 \\ 0 } [/mm] + t* [mm] \vektor{0 \\ -1 \\ 1 \\ 1 } [/mm] für t [mm] \in \IR [/mm] beliebig.
---------------------------------
ich finde es sehr abschreckend dieses Verfahren und lässt einem irgendwie heulend in die Arme von Herrn Gauß rennen. Der Sinn dieses komplizierten Verfahren statt einfach Gauß Elimination zu machen ist mir unbekannt.
---------------------------------
" Die Matrix U in der Zerlegung A = LU kann weiter zerlegt werden und zwar als Produkt U = D [mm] U_{~} [/mm] , wobei D eine Dreiecksmatrix ist, deren Diagonalelemente die Pivots von U oder Nullen sind."
-----------------
Was sind Pivots?
-----------------
"Anstelle von [mm] U^{~} [/mm] schreiben wir nun U, also insgesamt A = LDU . Vorheriges Beispiel lautete:
A = LU = [mm] \pmat{ 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 } [/mm] * [mm] \pmat{ 2 & 1 & 1 & 0 \\ 0 & -1 & -2 & 1 \\ 0 & 0 & -4 & 4 }
[/mm]
Diese entwickeln wir weiter zu einer Zerlegung A = LDU, nämlich
[mm] \pmat{ 2 & 1 & 1 & 0 \\ 0 & -1 & -2 & 1 \\ 0 & 0 & -4 & 4 } [/mm] = [mm] \pmat{ 2 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -4 } [/mm] * [mm] \pmat{ 1 & 0,5 & 0,5 & 0 \\ 0 & 1 & 2 & -1 \\ 0 & 0 & 1 & -1 } [/mm] = DU
--------------------------
Wie komme ich auf diese Weiterzerlegung?
---------------------------
" Die LDU - Zerlegung einer Matrix ist immer möglich, wenn kein Zeilentausch im Eliminationsprozess vorgenommen werden muss."
--------------------------
Heisst das, dass ich keine Zeilen tauschen darf, um möglichst an eine obere Dreiecksmatrix zu kommen?
Vielen Dank schonmal im Vorraus ! ;)
|
|
| |
|
Hi,
> Man löse das folgende System, in dem man eine LU -
> Faktorisierung benutze:
>
>
>
> Ax [mm]=\pmat{ 2 & 1 & 1 & 1 \\
4 & 1 & 0 & 1 \\
-2 & 2 & 1 & 1 } \vektor{x_1 \\
x_2 \\
x_3 \\
x_4 }[/mm]
> = [mm]\vektor{1 \\
-2 \\
7}[/mm] = b
> huhu,
>
> Ich muss mir dieses Thema irgendwie selber beibringen. In
> unserem SKript ist nur diese eine Beispielaufgabe drin,
> also jeweils eine zur LU und dann eine mit Übergang zu LDU
> -Faktorisierung. Die Aufgabe ist arg lang, hoffe es gibt
> unter euch welche die sich das antun wollen ;)
> Also:
> erster Schritt nach Aufgabenstellung lautet:
>
> "Man rechnet nach, dass die Elementarmatrizen wie folgt
> aussehen":
>
> [mm]E_1: \pmat{ 1 & 0 & 0 \\
-2 & 1 & 0 \\
0 & 0 & 1 }[/mm] , [mm]E_2: \pmat{ 1 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 1 }[/mm]
> , [mm]E_3: \pmat{ 1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 3 & 1 }[/mm]
> ,
> sodass sich ergibt:
>
> [mm]E_3[/mm] * [mm]E_2[/mm] * [mm]E_1[/mm] * A = [mm]\pmat{ 2 & 1 & 1 & \red{0} \\
0 & -1 & -2 & 1 \\
0 & 0 & -4 & \red{4 }}[/mm]
Die roten Einträge sind Rechenfehler.
> = U
>
> ---------------------
>
>
>
> meine Frage, nach Abtippen eigentlich sogar dir einzig
> wirklich wichtige: Wie berechne ich diese
> Elementarmatrizen?
In der Matrix
[mm]A=\pmat{ 2 & 1 & 1 & 1 \\
4 & 1 & 0 & 1 \\
-2 & 2 & 1 & 1 }[/mm]
werded analog zur Gaußelimination die Spalten so verändert, sodass man eine solche Dreickecksgestalt erhält.
Bei der Matrix A multipliziert man die erste Zeile mit -2 und addiert diese zur zweiten Zeile
[mm]\pmat{ 2 & 1 & 1 & 1 \\
4 & 1 & 0 & 1 \\
-2 & 2 & 1 & 1 }\rightsquigarrow \pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
-2 & 2 & 1 & 1 } [/mm]
Beschrieben werden kann dieser Umformungsschritt durch
[mm]\underbrace{\pmat{ 1 & 0 & 0 \\
\blue{-2} & 1 & 0 \\
0 & 0 & 1 }}_{E_1}\pmat{ 2 & 1 & 1 & 1 \\
4 & 1 & 0 & 1 \\
-2 & 2 & 1 & 1 } =\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
-2 & 2 & 1 & 1 } [/mm]
Als nächstes wird die erste Zeile mit "+1" multipliziert und zur dritten Zeile addiert:
[mm]\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
-2 & 2 & 1 & 1 } \rightsquigarrow\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
0 & 3 & 2 & 2 } [/mm]
Die Umformung erhält man durch
[mm]\underbrace{\pmat{ 1 & 0 & 0 \\
0& 1 & 0 \\
\blue{+1} & 0 & 1 }}_{E_2}\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
-2 & 2 & 1 & 1 } =\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
0 & 3 & 2 & 2 } [/mm]
Die erste Spalte ist abgearbeitet. Bisher haben wir folgendes gemacht:
[mm]\underbrace{\pmat{ 1 & 0 & 0 \\
0& 1 & 0 \\
\blue{+1} & 0 & 1 }}_{E_2}\green{\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
-2 & 2 & 1 & 1 } } =\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
0 & 3 & 2 & 2 } [/mm]
[mm]\underbrace{\pmat{ 1 & 0 & 0 \\
0& 1 & 0 \\
\blue{+1} & 0 & 1 }}_{E_2}\green{\underbrace{\pmat{ 1 & 0 & 0 \\
\blue{-2} & 1 & 0 \\
0 & 0 & 1 }}_{E_1}\pmat{ 2 & 1 & 1 & 1 \\
4 & 1 & 0 & 1 \\
-2 & 2 & 1 & 1 }} =\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
0 & 3 & 2 & 2 } [/mm]
Betrachten wir nun die zweite Spalte. Als nächstes wird die zweite Spalte so umgeformt, sodass unterhalb der zweiten Zeile nur 0 steht. Dafür müssen wir die zweite Zeile mit 3 multiplizieren und diese dann auf die dritte Zeile addieren:
[mm]\underbrace{\pmat{ 1 & 0 & 0 \\
0& 1 & 0 \\
0 & \blue{3} & 1 }}_{E_3}\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
0 & 3 & 2 & 2 } =\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
0 & 0 & -4 & -1 } [/mm]
Insgesamt haben wir in den Rechenschritt die Matrix A umgeformt zu
[mm]E_3\cdot E_2\cdot E_1\cdot A={\color{RedViolet}\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
0 & 0 & -4 & -1 } }=: {\color{RedViolet}U}[/mm]
> L = [mm]E_1^{-1}[/mm] * [mm]E_2^{-1}[/mm] * [mm]E_3^{-1}[/mm] = [mm]\pmat{ 1 & 0 & 0 \\
2 & 1 & 0 \\
-1 & -3 & 1 }[/mm]
> ,was also eine untere Dreiecksmatrix darstellt mit Einsen
> auf der Haptdiagonalen, dann ist:
>
> A = LU = [mm]\pmat{ 1 & 0 & 0 \\
2 & 1 & 0 \\
-1 & -3 & 1 }[/mm] *
> [mm]\pmat{ 2 & 1 & 1 & 0 \\
0 & -1 & -2 & 1 \\
0 & 0 & -4 & 4 }[/mm]
Genau:
[mm] A=\underbrace{\left( E_3\cdot E_2\cdot E_1 \right)^{-1}}_{L} U = L\cdot U[/mm]
Für [mm]Ax=b\;[/mm] löst man [mm]LUx=L(Ux)=b\;[/mm] also erst [mm]Ly=b\;[/mm] und dann [mm]Ux=y\;[/mm].
>
> Nun kann das System Ly = b:
>
> [mm]y_1[/mm] = 1
> [mm]2y_1 +y_2[/mm] =-2
> [mm]-y_1 -3y_2 +y_3[/mm] =7
>
> gelöst werden und es ergibt sich:
>
> y= (1,-4,-4) und das System
>
> Ux = y:
>
> [mm]2x_1[/mm] + [mm]x_2[/mm] + x= 1
> [mm]-x_2 -2x_3[/mm] + [mm]x_4[/mm] = -4
> [mm]-4x_3[/mm] + [mm]4x_4[/mm] = -4
>
>
> und wir erhalten:
>
>
> x = [mm]\vektor{x_1 \\
x_2 \\
x_3 \\
x_4}[/mm] = [mm]\vektor{-1 \\
2 \\
1 \\
0 }[/mm]
> + t* [mm]\vektor{0 \\
-1 \\
1 \\
1 }[/mm] für t [mm]\in \IR[/mm] beliebig.
>
>
> ---------------------------------
>
> ich finde es sehr abschreckend dieses Verfahren und lässt
> einem irgendwie heulend in die Arme von Herrn Gauß rennen.
> Der Sinn dieses komplizierten Verfahren statt einfach Gauß
> Elimination zu machen ist mir unbekannt.
Die LU-Zerlegung ist nur ein bisschen systematischer aufgeschrieben, als "Gauß".
Bei dem Gauß-Alog machst du doch komplett das Gleiche nur auf beiden Seiten der Gleichung:
Zeilenumformungen
[mm]\underbrace{E_n\cdots E_2E_1 }_{L^{-1}}Ax = \underbrace{E_n\cdots E_2E_1}_{L^{-1}} b[/mm]
Da steht also nichts anderes als
[mm]\underbrace{\underbrace{E_n\cdots E_2E_1 }_{L^{-1}}A}_{U}x = \underbrace{E_n\cdots E_2E_1}_{L^{-1}} b[/mm]
kurz:
[mm]Ux = L^{-1} b \Leftrightarrow LU x = L(Ux)=b[/mm]
Der Vorteil sich an den Algorithmus LU zu halten ist bei mehreren rechten Seiten [mm]b_i[/mm]. Hat man [mm]A=LU[/mm] einmal berechnet, so kann [mm]Ax=b_i[/mm] für verschiedene [mm]b_i[/mm] effizient gelöst werden. (Bei invertierbaren Matrizen [mm]A\;[/mm] kann so mittels Lösen von [mm]LUx_i=e_i[/mm] die inverse Matrix [mm]\pmat{|&|&| \\
x_1&x_2& \ldots x_n\\
|&|&|} = A^{-1}[/mm] effizient bestimmt werden.) Beim Gaußalgorithmus, den man per Hand durchführt schreibt man ja die rechte Seite b mit an die Matrix A dran und verändert diese simultan zu den Zeilenumformungen. Damit müsste man jedes Mal von vorne anfangen, wenn man verschiedene [mm] $b_i$'s [/mm] hat.
>
> ---------------------------------
>
>
> " Die Matrix U in der Zerlegung A = LU kann weiter zerlegt
> werden und zwar als Produkt U = D [mm]U_{~}[/mm] , wobei D eine
> Dreiecksmatrix ist, deren Diagonalelemente die Pivots von
> U oder Nullen sind."
>
>
> -----------------
>
> Was sind Pivots?
englisch pivot für Achse, Drehachse
Allerdings deine Einträge hier Pivotelemente zu nennen ist sehr sehr sehr unglücklich.
>
> -----------------
>
>
> "Anstelle von [mm]U^{~}[/mm] schreiben wir nun U, also insgesamt A =
> LDU . Vorheriges Beispiel lautete:
>
> A = LU = [mm]\pmat{ 1 & 0 & 0 \\
2 & 1 & 0 \\
-1 & -3 & 1 }[/mm] *
> [mm]\pmat{ 2 & 1 & 1 & 0 \\
0 & -1 & -2 & 1 \\
0 & 0 & -4 & 4 }[/mm]
>
> Diese entwickeln wir weiter zu einer Zerlegung A = LDU,
> nämlich
>
>
> [mm]\pmat{ 2 & 1 & 1 & 0 \\
0 & -1 & -2 & 1 \\
0 & 0 & -4 & 4 }[/mm]
> = [mm]\pmat{ 2 & 0 & 0 \\
0 & -1 & 0 \\
0 & 0 & -4 }[/mm] * [mm]\pmat{ 1 & 0,5 & 0,5 & 0 \\
0 & 1 & 2 & -1 \\
0 & 0 & 1 & -1 }[/mm]
> = DU
Im Prinzip normierst du nur die Einträge zu führenden Einsen.
>
>
> --------------------------
>
> Wie komme ich auf diese Weiterzerlegung?
>
> ---------------------------
[mm]\pmat{\frac{1}{2}&0&0\\
0&1&0\\
0&0&1}\cdot\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
0 & 0 & -4 & -1 }=\pmat{ 1 & 0.5 & 0.5 & 0.5 \\
0 & -1 & -2 & -1 \\
0 & 0 & -4 & -1 }[/mm]
Also auch
[mm]\underbrace{{H_1}^{-1}\underbrace{\pmat{\frac{1}{2}&0&0\\
0&1&0\\
0&0&1}}_{H_1}}_{\textrm{Einheitsmatrix}}\cdot\pmat{ 2 & 1 & 1 & 1 \\
0 & -1 & -2 & -1 \\
0 & 0 & -4 & -1 }={H_1}^{-1}\pmat{ 1 & 0.5 & 0.5 & 0.5 \\
0 & -1 & -2 & -1 \\
0 & 0 & -4 & -1 }[/mm]
und [mm]{H_1}^{-1} = \pmat{2&0&0\\
0&1&0\\
0&0&1},{H_2}^{-1} = \pmat{1&0&0\\
0&-1&0\\
0&0&1},{H_3}^{-1} = \pmat{1&0&0\\
0&1&0\\
0&0&-4}[/mm]
[mm] $D={H_1}^{-1}{H_2}^{-1}{H_3}^{-1}$
[/mm]
>
>
>
> " Die LDU - Zerlegung einer Matrix ist immer möglich,
> wenn kein Zeilentausch im Eliminationsprozess vorgenommen
> werden muss."
Es ist auch sonst möglich. Nur nicht so einfach.
>
>
> --------------------------
>
>
> Heisst das, dass ich keine Zeilen tauschen darf, um
> möglichst an eine obere Dreiecksmatrix zu kommen?
Bei dem LU-Algorithmus sind keine Zeilentausche vorgesehen. Zeilentausche sind beim LU-Algorithmus mit Permutation vorhanden und man erhält am Ende dann $PA=LU$.
Für diesen Fall habe ich eine Seite online gestellt:
http://werkzeuge.wieschoo.com/lupivot.php
>
>
>
> Vielen Dank schonmal im Vorraus ! ;)
Schöne Semesterferien...
|
|
|
| |
|
heey ;)
vielen, vielen, vielen, vielen Dank für alle die vielen, sehr ausführlichen Rechenschritte! Das ist klasse!
Ich wünsche dir ebenfalls eine schöne Zeit! ;)
ganz viele liebe Grüße,
Evelyn
|
|
|
|
