QR-Zerlegung: How to? < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:18 Do 17.03.2005 | | Autor: | Xenon__ |
hi there!
hab heute schon 2 stunde auf dieses verfahren verwendet, mit musterlösungen gerechnet, bei denen die interessanten teile leider immer fehlen und bei mir hakts immer an derselben stelle.
sei A := [mm] \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 4 \\ 1 & 2 & 3 \end{bmatrix} [/mm] und b := [mm] \vektor{1 \\ 2 \\ 3}
[/mm]
gelöst werden soll das LGS Ax=b mit QR-Zerlegung.
jetzt habe ich hier die folgende formel zur lösung:
1.)
a) [mm] w_{i} [/mm] := [mm] v_{i} [/mm] + [mm] \parallel v_{i} \parallel_{2} [/mm] * [mm] e_{i}
[/mm]
b) [mm] M_{i} [/mm] := I - 2 * [mm] \bruch {w_{i} * w_{i}^{T}} {w_{i}^{T} * w_{i}}
[/mm]
c) [mm] A_{i} [/mm] := [mm] M_{i} [/mm] * [mm] A_{i-1} [/mm] (mit [mm] A_{0} [/mm] := A)
2.) letzten endes bekomme ich für eine n [mm] \times [/mm] n-Matrix [mm] A_{1} [/mm] bis [mm] A_{n} [/mm] raus und bilde dann mit [mm] Q^{T} [/mm] := [mm] M_{n} [/mm] * [mm] \ldots [/mm] * [mm] M_{1} [/mm] und R := [mm] A_{n} [/mm] := [mm] M_{n} [/mm] * [mm] A_{n-1}
[/mm]
(wobei [mm] v_{i} [/mm] := spalte i der Matrix A (abzüglich der zeileneinträge [mm] a_{j} [/mm] mit j < i) und [mm] \parallel v_{i} \parallel_{2} [/mm] die euklidische Norm beschreibt. I ist die Einheitsmarix der Dimension n-(n-1))
das problem ist folgendes:
im ersten schritt bilde ich den vektor [mm] w_{1}. [/mm] schön. im zweiten schritt rechne ich [mm] \bruch {w_{1} * w_{1}^{T}} {w_{1}^{T} * w_{1}} [/mm] aus und erhalte einen vektor der form [mm] \vektor{ a_{1} \\ \vdots \\ a_{n}}. [/mm] den soll ich nun von der einheitsmatrix abziehen??????? geht doch gar nicht, da I [mm] \in [/mm] n [mm] \times [/mm] n ist und der abzuziehende wert [mm] \in [/mm] n [mm] \times [/mm] 1 ist...
ich habe noch ein anderes verfahren, das aber quasi das gleiche macht - und am selben problem scheitert :(
falls jemand zeit und geduld aufbringen könnte, mal eine (kleine) aufgabe (ein schritt der rechnung reicht ja theoritisch schon aus) ***AUSFÜHRLICH*** vorzurechnen, wäre ich über alle massen dankbar!!!!!!!!!!! Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt. meine musterlösungen und scripte helfen mir leider auch nicht weiter :(
|
|
| |
|
Hallo Xenon__,
> sei A := [mm]\pmat{1 & 2 & 3 \\ 2 & 3 & 4 \\ 1 & 2 & 3}[/mm]
> und b := [mm]\vektor{1 \\ 2 \\ 3}
[/mm]
>
> gelöst werden soll das LGS Ax=b mit QR-Zerlegung.
Sei [mm]\textstyle Q=E,\ A^{(i)}:=\left(a^{(i)}_{jk}\right),\ y^{(i)}:=\left(a_{ii}^{(i)},\dotsc,a_{mi}^{(i)}\right)^T[/mm]. Dann lautet der Algorithmus, den ich im Folgenden benutzen werde:
1: [mm]\ell := \min\{m-1,n\}[/mm]
2: Berechne für [mm]i=1,2,\dotsc,\ell[/mm]:
[mm]\begin{array}{l@{\;}l}
\left|L\right|&:=\sqrt{\frac{\left\|y^{(i)}\right\|_2\left(\left\|y^{(i)}\right\|_2+\left|y_1^{(i)}\right|\right)}{2}}\\
k&:=\begin{cases}-\operatorname{sign}\left(y_1^{(i)}\right)\left\|y^{(i)}\right\|_2&\texttt{für }y_1^{(i)}\ne 0\\
-\left\|y^{(i)}\right\|_2&\texttt{für }y_1^{(i)}=0
\end{cases}\\
w&:=\frac{1}{2L}\left(y^{(i)}-ke_1\right)\\
\tilde{Q}_i&:=E-2ww^H\\
{}&=E-\frac{1}{2\left|L\right|^2}\left(y^{(i)}-ke_1^{(i)}\right)\left(y^{(i)}-ke_1^{(i)}\right)^H\\
Q&=Q\cdot{}\left(\begin{array}{c|c}
E_{i-1}&0\\\hline0&\tilde{Q}_i
\end{array}\right)\\
A^{(i+1)}&=\left(\begin{array}{c|c}
E_{i-1}&0\\\hline0&\tilde{Q}_i
\end{array}\right)\cdot{}A^{(i)}
\end{array}[/mm]
Er funktioniert mit Householder-Spiegelungen. [ Es gibt aber auch noch die Möglichkeit über Givens-Rotationen zur Lösung zu kommen. Da kenne ich mich jedoch nicht aus. ]
Anwendung für deinen konkreten Fall:
Wir berechnen zuerst die Anzahl der nötigen Iterationen:
[mm]l: = \min \left\{ {m - 1,n} \right\} = \min \left\{ {2,3} \right\} = 2[/mm]
Wir müssen den Algorithmus also zweimal anwenden, um zur Zerlegung zu kommen:
erste Iteration:
[mm]\left| L \right|: = \sqrt {\frac{{\left\| {y^{\left( 1 \right)} } \right\|_2 \left( {\left\| {y^{\left( 1 \right)} } \right\|_2 + \left| {y_1^{\left( 1 \right)} } \right|} \right)}}
{2}} = \sqrt {\frac{{\sqrt 6 \left( {\sqrt 6 + 1} \right)}}
{2}} = \sqrt {\frac{{6 + \sqrt 6 }}
{2}} = \sqrt {3 + \frac{{\sqrt 6 }}
{2}}[/mm]
(Frag' mich nicht, wie man gerade auf diese Form fürs [mm]L\![/mm] kommt. Dafür verstehe ich den Algorithmus nicht gut genug.)
[mm]k:=\begin{cases}
-\operatorname{sign}\left(y_1^{(1)}\right)\left\|y^{(1)}\right\|_2,&\texttt{falls }y_1^{(1)}\ne 0\\
-\left\|y^{(1)}\right\|_2,&\texttt{falls }y_1^{(1)}=0
\end{cases}\quad\Rightarrow k = - \sqrt 6[/mm]
Wir entscheiden uns hier für den ersten Fall, da [mm]1 \ne 0[/mm].
Jetzt kommen wir, denke ich, zum Kern des [mm]QR\texttt{-Algorithmus}[/mm]. Wir bestimmen einen speziellen Vektor, der uns dann eine symmetrische Matrix liefert, welche uns zu unserem ersten [mm]Q\![/mm] führt. Was jetzt kommt, ist, denke ich, gerade diese Householder-Spiegelung:
[mm]w: = \frac{1}
{{2\left| L \right|}}\left( {y^{\left( 1 \right)} - ke_1 } \right) = \frac{1}
{{2\left| L \right|}}\left( {\left( {\begin{array}{*{20}c}
1 \\
2 \\
1 \\
\end{array} } \right) - \left( { - \sqrt 6 } \right)\left( {\begin{array}{*{20}c}
1 \\
0 \\
0 \\
\end{array} } \right)} \right) = \frac{1}
{{2\sqrt {3 + \frac{{\sqrt 6 }}
{2}} }}\left( {\begin{array}{*{20}c}
{1 + \sqrt 6 } \\
2 \\
1 \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
{\frac{{1 + \sqrt 6 }}
{{2\sqrt {3 + \frac{{\sqrt 6 }}
{2}} }}} \\
{\frac{1}
{{\sqrt {3 + \frac{{\sqrt 6 }}
{2}} }}} \\
{\frac{1}
{{2\sqrt {3 + \frac{{\sqrt 6 }}
{2}} }}} \\
\end{array} } \right)[/mm]
Als nächstes bestimmen wir also das erste [mm]Q\![/mm]:
[mm]\tilde Q_1 : = \left( {\begin{array}{*{20}c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array} } \right) - 2ww^H = E - 2\left( {\begin{array}{*{20}c}
{\frac{{\sqrt 6 }}
{{12}} + \frac{1}
{2}} & {\frac{{\sqrt 6 }}
{6}} & {\frac{{\sqrt 6 }}
{{12}}} \\
{\frac{{\sqrt 6 }}
{6}} & {\frac{2}
{5} - \frac{{\sqrt 6 }}
{{15}}} & {\frac{1}
{5} - \frac{{\sqrt 6 }}
{{30}}} \\
{\frac{{\sqrt 6 }}
{{12}}} & {\frac{1}
{5} - \frac{{\sqrt 6 }}
{{30}}} & {\frac{1}
{{10}} - \frac{{\sqrt 6 }}
{{60}}} \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
{ - \frac{{\sqrt 6 }}
{6}} & { - \frac{{\sqrt 6 }}
{3}} & { - \frac{{\sqrt 6 }}
{6}} \\
{ - \frac{{\sqrt 6 }}
{3}} & {\frac{{2\sqrt 6 }}
{{15}} + \frac{1}
{5}} & {\frac{{\sqrt 6 }}
{{15}} - \frac{2}
{5}} \\
{ - \frac{{\sqrt 6 }}
{6}} & {\frac{{\sqrt 6 }}
{{15}} - \frac{2}
{5}} & {\frac{{\sqrt 6 }}
{{30}} + \frac{4}
{5}} \\
\end{array} } \right)[/mm]
[ Vielleicht möchtest Du an dieser Stelle wissen, was dieses ominöse [mm]w^H[/mm] (lies: "w hermitesch") bedeutet. Du weißt, daß man Vektoren normalerweise in eine Spalte schreibt. Allerdings kann man Vektoren auch in eine Zeile schreiben (Stell' dir z.B. einen Stab vor. Du hälst diesen Stab vertikal zum Boden. Wenn Du ihn jetzt kippst und horizontal zum Boden hälst, ist es ja trotzdem noch der selbe Stab nicht wahr?  Oder mathematisch ausgedrückt: Sei [mm]v: = \left(\begin{smallmatrix}
a \\
b \\
c \\
\end{smallmatrix}\right)[/mm]. Dann [mm]v^H : = \left( {a,b,c} \right)[/mm]. ]
Und da wir ja immer Zeile mal Spalte multiplizieren, erhalten wir hier:
[mm]vv^H : = \left( {\begin{array}{*{20}c}
{\red{a}} \\
{\red{b}} \\
{\red{c}} \\
\end{array} } \right)\left( {\blue{a},\blue{b},\blue{c}} \right) = \left( {\begin{array}{*{20}c}
{\red{a}*\blue{a}} & {\red{a}*\blue{b}} & {\red{a}*\blue{c}} \\
{\red{b}*\blue{a}} & {\red{b}*\blue{b}} & {\red{b}*\blue{c}} \\
{\red{c}*\blue{a}} & {\red{c}*\blue{b}} & {\red{c}*\blue{c}} \\
\end{array} } \right)[/mm]
[ "Hermitesch" ist sozusagen eine "erweiterte Form" von "transponiert". Diese "Erweiterung" tritt aber erst bei komplexen Zahlen in Erscheinung(, meine ich). Man muß also nicht nur wie beim Transponieren die Koordinaten jedes einzelnen Eintrags in der Matrix vertauschen, sondern müßte bei jedem komplexen Eintrag wohl noch den konjugiert-komplexen Eintrag dazu bilden. Da wir uns aber im Reellen befinden, ist das für uns irrelevant. ]
Ok, weiter im Algorithmus. Jetzt berechnen wir die 1te Spalte und 1te Zeile von [mm]R\![/mm]:
[mm]\tilde Q_1 A_1 = \left( {\begin{array}{*{20}c}
{ - \sqrt 6 } & { - \frac{{5\sqrt 6 }}
{3}} & { - \frac{{7\sqrt 6 }}
{3}} \\
0 & { - \frac{{2\sqrt 6 }}
{{15}} - \frac{1}
{5}} & { - \frac{{4\sqrt 6 }}
{{15}} - \frac{2}
{5}} \\
0 & {\frac{2}
{5} - \frac{{\sqrt 6 }}
{{15}}} & {\frac{4}
{5} - \frac{{2\sqrt 6 }}
{{15}}} \\
\end{array} } \right) = :R_1[/mm]
zweite Iteration:
Als nächstes streichen wir die erste Zeile und erste Spalte von [mm]R_1[/mm] und betrachten damit nur noch folgende Matrix:
[mm]A_2 : = \left( {\begin{array}{*{20}c}
{ - \frac{{2\sqrt 6 }}
{{15}} - \frac{1}
{5}} & { - \frac{{4\sqrt 6 }}
{{15}} - \frac{2}
{5}} \\
{\frac{2}
{5} - \frac{{\sqrt 6 }}
{{15}}} & {\frac{4}
{5} - \frac{{2\sqrt 6 }}
{{15}}} \\
\end{array} } \right)[/mm]
Und jetzt geht alles wieder von vorne los:
[mm]\left| L \right|: = \sqrt {\frac{{\left\| {y^{\left( 2 \right)} } \right\|_2 \left( {\left\| {y^{\left( 2 \right)} } \right\|_2 + \left| {y_1^{\left( 2 \right)} } \right|} \right)}}
{2}} = \sqrt {\frac{{\frac{{\sqrt 3 }}
{3}\left( {\frac{{\sqrt 3 }}
{3} + \frac{{2\sqrt 6 }}
{{15}} + \frac{1}
{5}} \right)}}
{2}} = \sqrt {\frac{{\sqrt 3 }}
{{30}} + \frac{{\sqrt 2 }}
{{15}} + \frac{1}
{6}}[/mm]
[mm]k:=\begin{cases}
-\operatorname{sign}\left(y_1^{(2)}\right)\left\|y^{(2)}\right\|_2,&\texttt{falls }y_1^{(2)}\ne 0\\
-\left\|y^{(2)}\right\|_2,&\texttt{falls }y_1^{(2)}=0
\end{cases}\quad\Rightarrow k = - \left( { - 1} \right)\frac{{\sqrt 3 }}
{3} = \frac{{\sqrt 3 }}
{3}[/mm]
[mm] \Rightarrow w: = \frac{1}
{{2\left| L \right|}}\left( {y^{\left( 2 \right)} - ke_1 } \right) = \left( {\begin{array}{*{20}c}
{ - \sqrt {\frac{{\sqrt 3 }}
{{10}} + \frac{{\sqrt 2 }}
{5} + \frac{1}
{2}} } \\
{\sqrt { - \frac{{\sqrt 3 }}
{{10}} - \frac{{\sqrt 2 }}
{5} + \frac{1}
{2}} } \\
\end{array} } \right)[/mm]
[mm]\tilde Q_2 : = E - 2ww^H = \left( {\begin{array}{*{20}c}
{ - \frac{{2\sqrt 2 }}
{5} - \frac{{\sqrt 3 }}
{5}} & {\frac{{2\sqrt 3 }}
{5} - \frac{{\sqrt 2 }}
{5}} \\
{\frac{{2\sqrt 3 }}
{5} - \frac{{\sqrt 2 }}
{5}} & {\frac{{2\sqrt 2 }}
{5} + \frac{{\sqrt 3 }}
{5}} \\
\end{array} } \right)[/mm]
[mm]\tilde Q_2 A_2 = \left( {\begin{array}{*{20}c}
{\frac{{\sqrt 3 }}
{3}} & {\frac{{2\sqrt 3 }}
{3}} \\
0 & 0 \\
\end{array} } \right)[/mm]
Beachte, es ist zwingend, daß der linke Eintrag ganz unten [mm]0\![/mm] ist (klar, wir wollen ja schließlich eine rechte obere Dreiecksmatrix aufbauen.) Ich sag' das nur nochmal extra, weil hier in der letzten Zeile noch eine Null steht. Diese wurde aber nur durch die Rechnung begünstigt und ist natürlich nicht zwingend!
Was jetzt kommt ist wiederum entscheidend! Wir haben jetzt [mm]R\![/mm] schrittweise durch die Multiplikation der [mm]\texttt{Teil-}Q\texttt{'s}[/mm] mit den [mm]\texttt{Teil-}A\texttt{'s}[/mm] erzeugt (Ich hoffe, es ist jetzt etwas klarer geworden wie das hier gemeint ist, sonst frag' nochmal nach). Jetzt haben wir folgende Matrix-"Bausteine":
[mm]\left( {\begin{array}{*{20}c}
{ - \sqrt 6 } & { - \frac{{5\sqrt 6 }}
{3}} & { - \frac{{7\sqrt 6 }}
{3}} \\
0 & {} & {} \\
0 & {} & {} \\
\end{array} } \right)[/mm] und [mm]\left( {\begin{array}{*{20}c}
{\frac{{\sqrt 3 }}
{3}} & {\frac{{2\sqrt 3 }}
{3}} \\
0 & 0 \\
\end{array} } \right)[/mm]
Jetzt setzen wir den "kleineren Baustein" in den "Größeren" ein und erhalten die [mm]R\texttt{-Matrix}[/mm]:
[mm]R: = \left( {\begin{array}{*{20}c}
{ - \sqrt 6 } & { - \frac{{5\sqrt 6 }}
{3}} & { - \frac{{7\sqrt 6 }}
{3}} \\
0 & {\frac{{\sqrt 3 }}
{3}} & {\frac{{2\sqrt 3 }}
{3}} \\
0 & 0 & 0 \\
\end{array} } \right)[/mm]
Bei [mm]Q\![/mm] geht es genauso:
[mm]Q = \tilde Q_1 \left( {\begin{array}{*{20}c}
1 & {0\;0} \\
\begin{gathered}
0 \hfill \\
0 \hfill \\
\end{gathered} & {\tilde Q_2 } \\
\end{array} } \right) = \tilde Q_1 \left( {\begin{array}{*{20}c}
1 & 0 & 0 \\
0 & { - \frac{{2\sqrt 5 }}
{5} - \frac{{\sqrt 3 }}
{5}} & {\frac{{2\sqrt 3 }}
{5} - \frac{{\sqrt 2 }}
{5}} \\
0 & {\frac{{2\sqrt 3 }}
{5} - \frac{{\sqrt 2 }}
{5}} & {\frac{{2\sqrt 2 }}
{5} + \frac{{\sqrt 3 }}
{5}} \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
{ - \frac{{\sqrt 6 }}
{6}} & {\frac{{\sqrt 3 }}
{3}} & { - \frac{{\sqrt 2 }}
{2}} \\
{ - \frac{{\sqrt 6 }}
{3}} & { - \frac{{\sqrt 3 }}
{3}} & 0 \\
{ - \frac{{\sqrt 6 }}
{6}} & {\frac{{\sqrt 3 }}
{3}} & {\frac{{\sqrt 2 }}
{2}} \\
\end{array} } \right)[/mm]
Zum Schluss nutzen wir aus, daß [mm]Q^{-1} = Q^T[/mm] ist, weil Q orthogonal ist:
[mm] \Rightarrow Ax = b \Leftrightarrow QRx = b \Leftrightarrow Rx = Q^{ - 1} b = Q^T b = \left( {\begin{array}{*{20}c}
{ - \frac{{4\sqrt 6 }}
{3}} \\
{\frac{{2\sqrt 3 }}
{3}} \\
{\sqrt 2 } \\
\end{array} } \right) = :b'[/mm]
Zu berechnen ist also jetzt das äquivalente System [mm]Rx = b'\![/mm], das aber bereits in der richtigen Treppenform ist. Wir sehen, daß dieses System offenbar nicht lösbar ist.
Ok, soviel jetzt erstmal von mir. Frag' bei Unklarheiten nach!
Viele Grüße
Karl
[P.S. Such' mal im Numerik-Sub-Forum nach [mm]QR\texttt{-Zerlegung}[/mm]. Du solltest dann auf einige frühere Stränge von mir und mathemaduenn treffen. Er hat mir mit dem Thema sehr geholfen.]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:13 Di 29.03.2005 | | Autor: | Kix |
Hallo!
Könnte vielleicht jemand mir kurz die QR-Zerlegung (Householder-Transformation) einer einfachen Matrix erklären. Also wie man da genau vorgeht?
Ich hab in meiner Unterlagen nur Lösungen (als nur die zerlegte Matrix), aber keine Beschreibung des "Weges" und mit meinem Skript komm ich nicht weiter... :(
Als Beispiel wäre die Matrix:
[mm] \pmat{ 4 & 3 \\ 3 & 4 }
[/mm]
Vielen Dank!!!
-AA-
|
|
|
| |
|
Hallo Kix,
Ich hab deinen Artikel mal in einen anderen Disskussionsstrang verschoben. Hier hat Karl_Pech schonmal sehr ausführlich ein 3x3 Beispiel vorgerechnet. 2x2 geht vom Prinzip her ähnlich nur das Du nach der ersten "Iteration" fertig bist. Falls das nicht reicht meld Dich nochmal.
gruß
mathemaduenn
|
|
|
|
