QR Zerlegung < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
Hallo Zusammen,
Ich habe leider immer noch Probleme mit dieser Zerlegung. Ich versteh' immer noch nicht den letzten Schritt:
[mm]\begin{array}{l@{\;}l}
Q&=Q\cdot{}\left(\begin{array}{c|c}E_{i-1}&0\\\hline 0&\tilde{Q}_i\end{array}\right)\\
A^{i+1}&=\left(\begin{array}{c|c}E_{i-1}&0\\\hline 0&\tilde{Q}_i\end{array}\right)\cdot{}A^{(i)}
\end{array}[/mm]
Soweit bin ich da im Moment gekommen:
Sei [m]A: = \left( {\begin{array}{*{20}c}
{ - 6} & 3 & { - 2} \\
4 & 9 & 4 \\
2 & 5 & 8 \\
\end{array} } \right)[/m]. Und jetzt wende ich den Algo. an:
1. l = 2
i = 1, 2
zu 3.1)
[m]\begin{gathered}
\left| L \right|: = \sqrt {\frac{{\sqrt {56} \left( {\sqrt {56} + 6} \right)}}
{2}} = \sqrt {\frac{{56 + 6\sqrt {56} }}
{2}} = \sqrt {28 + 3\sqrt {56} } \hfill \\
k: = - {\text{sign}}\left( { - 6} \right)\sqrt {56} = \sqrt {56} \hfill \\
w: = \frac{1}
{{2\sqrt {28 + 3\sqrt {56} } }}\left( {\left( {\begin{array}{*{20}c}
{ - 6} \\
4 \\
2 \\
\end{array} } \right) - \sqrt {56} \left( {\begin{array}{*{20}c}
1 \\
0 \\
0 \\
\end{array} } \right)} \right) = \frac{1}
{{2\sqrt {28 + 3\sqrt {56} } }}\left( {\begin{array}{*{20}c}
{ - 6 - \sqrt {56} } \\
4 \\
2 \\
\end{array} } \right) \hfill \\
\tilde Q_1 : = \left( {\begin{array}{*{20}c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array} } \right) - 2\left( {\frac{1}
{{2\sqrt {28 + 3\sqrt {56} } }}} \right)^2 \left( {\begin{array}{*{20}c}
{ - 6 - \sqrt {56} } \\
4 \\
2 \\
\end{array} } \right)\left( { - 6 - \sqrt {56} ,\;4,\;2} \right) \hfill \\
= \left( {\begin{array}{*{20}c}
{ - \frac{{3\sqrt {14} }}
{{14}}} & {\frac{{\sqrt {14} }}
{7}} & {\frac{{\sqrt {14} }}
{{14}}} \\
{\frac{{\sqrt {14} }}
{7}} & {\frac{{6\sqrt {14} }}
{{35}} + \frac{1}
{5}} & {\frac{{3\sqrt {14} }}
{{35}} - \frac{2}
{5}} \\
{\frac{{\sqrt {14} }}
{{14}}} & {\frac{{3\sqrt {14} }}
{{35}} - \frac{2}
{5}} & {\frac{{3\sqrt {14} }}
{{70}} + \frac{4}
{5}} \\
\end{array} } \right) \hfill \\
\end{gathered}[/m]
Und was jetzt? Ich habe diesen letzten Schritt irgendwie immer noch nicht verstanden. Vielleicht könnte mir jemand Schritt für Schritt diesen letzten Teil des Algorithmus erklären. Ich weiß auch nicht, vielleicht durch einfache wörtliche Anweisungen wie (Streiche Spalte sowieso; Streiche Zeile sowieso; Füge dies und das ein; ...). So daß ich den Algo. wenigstens anwenden kann (vom Verständnis der zugrundeliegenden Idee des Algorithmus kann wohl schon keine Rede mehr sein. :-( ).
Vielen Dank!
Schöne Grüße
Karl
edit:
>>>>>>>>>>
Multipliziert man die letzte so erhaltene Matrix mit A so erhält man etwas Bemerkenswertes:
[Dateianhang nicht öffentlich]
Ich scheine also schon auf dem richtigen Weg zu sein. Den beim letzten Schritt aus dem Algorithmus sind ja auch Nullen unten links aufgezeichnet. Es ist außerdem auffällig, daß die vorherige Matrix symmetrisch ist. Und dann gilt: $Q = [mm] Q^{-1}$ [/mm] oder wie?
Grüße
Karl
<<<<<<<<
Dateianhänge:
Anhang Nr. 2 (Typ: gif) [nicht öffentlich]
|
|
| |
|
Hallo Karl,
> Multipliziert man die letzte so erhaltene Matrix mit A so
> erhält man etwas Bemerkenswertes:
>
> [Dateianhang nicht öffentlich]
Genau in der ersten Spalte wurden Nullen unterhalb des ersten Elements erzeugt.
> Ich scheine also schon auf dem richtigen Weg zu sein.
Genau und dieses [mm] E_{i-1} [/mm] in der Matrix ist eine (Mathematiker-)Formulierung dafür das du den Algorithmus jetzt auf die Matrix anwendest in der erste Spalte erste Zeile gestrichen worden sind bzw. nicht mehr mit transformiert werden. Am besten b (von Ax=b) gleich mit transformieren. Analog die erste Zeile danach unverändert lassen.
> Es ist außerdem
> auffällig, daß die vorherige Matrix symmetrisch ist. Und
> dann gilt: [mm]Q = Q^{-1}[/mm] oder wie?
![[ok]](/images/smileys/ok.gif "[ok]")
Bei der Householder Spiegelung gilt:
[mm] Q_{i}^T=Q_{i}=Q_{i}^{-1}
[/mm]
Also Schrittweise:
1.Start:
Ax=b
2.Householderspiegelungen:
QAx=Qb
Dabei ist QA eine obere Dreiecksmatrix. Wie beim Gaußschen Algorithmus ohne Pivotisierung werden sukzessive Nullen unterhalb des Diagonalelements erzeugt.
3. Rx=c
Dreieckssystem lösen wie bei Gauß
Alles klar?
gruß
mathemaduenn
|
|
|
| |
|
Hallo mathemaduenn,
Ich habe versucht deine Erklärungen nachzuvollziehen und bin jetzt mit dem Verfahren etwas weitergekommen. Diesmal benutze ich aber ein anderes Beispiel. Das erste war einfach zu kompliziert (Deine Erklärungen zu dem [mm] $b\!$ [/mm] habe ich leider auch nicht verstanden):
Sei
[m]A: = \left( {\begin{array}{*{20}c}
2 & 1 & 0 \\
1 & 3 & 1 \\
0 & 1 & 2 \\
\end{array} } \right)[/m]
Jetzt die QR-Zerlegung:
[Dateianhang nicht öffentlich]
Wie Du siehst habe ich das [mm] $R\!$ [/mm] wohl nun richtig berechnet. Aber wie berechne ich das [mm] $Q\!$?
[/mm]
Danke!
Viele Grüße
Karl
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
|
| |
|
Hallo Karl,
Du hast [mm] Q_1=\pmat{-\bruch{2\wurzel{5}}{5} & -\bruch{\wurzel{5}}{5} & 0 \\ -\bruch{\wurzel{5}}{5} & \bruch{2\wurzel{5}}{5}& 0 \\ 0 & 0 & 1}
[/mm]
[mm] Q_2 [/mm] würde sich ergeben wenn Du die in Schritt 22 von Dir berechnete Matrix wie in Deiner Beschreibung mit [mm] E_1 [/mm] ergänzt also
[mm] Q_2=\pmat{1 & 0 & 0 \\ 0 & -\bruch{\wurzel{30}}{6} & -\bruch{\wurzel{6}}{6} \\ 0 & -\bruch{\wurzel{6}}{6} & \bruch{\wurzel{30}}{6}}
[/mm]
Q kannst Du dann berechnen mittels [mm] Q=Q_1Q_2
[/mm]
Nun kannst Du Ax=b lösen in dem Du
1. R=Q^TA
2. c=Q^Tb
berechnest und dann das übriggebliebene Dreieckssystem(Rx=c) durch sukzessives einsetzen (von unten nach oben die [mm] x_i [/mm] ausrechnen) löst.
Nun wird dir aufgefallen sein das Du R ausgerechnet hast ohne das Q zu kennen. ![[schock]](/images/smileys/schock.gif "[schock]") Man braucht Q gar nicht auszurechnen um Ax=b zu lösen.
c kannst du analog zu R gleich mitberechnen.
[mm] b_1=Q_1b
[/mm]
[mm] b_2=Q_2b_1
[/mm]
[mm] c=b_2
[/mm]
Ich hoffe ich hab deine Fragen damit beantwortet. ansonsten ![[user]](/images/smileys/user.gif "[user]") frag einfach nochmal.
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:41 Mo 07.02.2005 | | Autor: | Karl_Pech |
Hallo mathemaduenn,
Ich denke, ich habe das Prinzip dank deiner Erklärungen jetzt verstanden. Vielen Dank!
Für Matrizen mit Dimension [mm] $\ne [/mm] 3$ rechne ich also einfach so, wie in meinem Beispiel und verringere dabei in jedem Schritt die Dimension meines [mm] $Q\!$. [/mm] Am Schluß stelle ich die Dimensionen aller [mm] $Q\!$ [/mm] wieder her, indem ich sie in dieses 1er-Schema packe:
[m]Q_{{\text{entgültig}}} = \left( {Q_{{\text{erstes}}} } \right)*\left( {\begin{array}{*{20}c}
{\text{1}} & {\text{0}} \\
{\text{0}} & {Q_{{\text{zweites}}} } \\
\end{array} } \right)* \ldots *\left( {\begin{array}{*{20}c}
1 & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots & \vdots & \ddots & 0 \\
0 & 0 & 0 & {Q_{{\text{letztes}}} } \\
\end{array} } \right)[/m]
(Wobei alle Matrizen in diesem Schema die gleiche Dimension haben sollen. Ist in der Zeichnung etwas unglücklich.)
Viele Grüße
Karl
|
|
|
|
