(schon wieder) QR-Zerlegung < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo Zusammen,
Ich habe nun schon seit längerer Zeit vergeblich versucht diese "QR-Geschichte" nachzuvollziehen (Tut mir Leid mathemaduenn aber deine Erklärung hat mir leider nicht weitergeholfen. Und wegen Zeitnot konnte ich keine Rückfragen mehr stellen.). Jedenfalls habe ich es nun mit folgendem Algorithmus ((immer noch) Householder) probiert. Sei [mm]Q:=E,\ A^{(i)}:=\left(a_{jk}^{(i)}\right),\ y^{(i)}:=\left(a_{ii}^{(i)},\dotsc,a_{mi}^{(i)}\right)^T[/mm]:
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\\
\textcolor{red}{Q}&\textcolor{red}{=Q\cdot{}\left(\begin{array}{c|c}
E_{i-1}&0\\\hline0&\tilde{Q}_i
\end{array}\right)}\\
\textcolor{red}{A^{(i+1)}}&\textcolor{red}{=\left(\begin{array}{c|c}
E_{i-1}&0\\\hline0&\tilde{Q}_i
\end{array}\right)\cdot{}A^{(i)}}
\end{array}[/mm]
Die rot markierten Stellen des Algorithmus sind mir unklar. Ich vermute, daß es sich dabei um eine iterative Definition handelt.
Ansonsten habe ich es an der Matrix [mm]\left(\begin{smallmatrix}4 & 4&0 \\3 & 3&5\\0&4&1 \end{smallmatrix}\right)[/mm] ausprobiert:
1. [mm]l := \min\{2,3\} = 2[/mm]
2. [mm]i=1,2\![/mm]
3. [mm]\left|L\right| := \sqrt{\frac{\sqrt{4^2+3^2}\left(\sqrt{4^2+3^2}+4\right)}{2}} = 3\sqrt{\frac{5}{2}}[/mm]
4. [mm]k := -4\cdot{5} = -20[/mm], da [mm]4\ne 0[/mm]
5. [mm]w:=\frac{1}{6\sqrt{\frac{5}{2}}}\left(\begin{pmatrix}4\\3\\0\end{pmatrix}+\begin{pmatrix}20\\0\\0\end{pmatrix}\right)=\frac{1}{6\sqrt{\frac{5}{2}}}\begin{pmatrix}24\\3\\0\end{pmatrix}[/mm]
6. [mm]\tilde{Q}_i := \begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}-2ww^H=\begin{pmatrix}-11.8&-1.6&0\\-1.6&0.8&0\\0&0&1\end{pmatrix}[/mm]
Weiß jemand wie ich jetzt weitermachen soll?
Danke im Vorraus!
Viele Grüße
Karl
|
|
| |
|
Hallo Karl,
Zunächst sign(-4)=-1(in der Berechnung des K) weil sign(x) das Vorzeichen von x ist. Bis auf diesen kleinen Fehler hast du jetzt dein Start Q berechnet.
Dieses multiplizierst Du mit A und erhälst normalerweise eine Matrix [mm] A^{(2)} [/mm] die in der ersten Spalte in der ersten Zeile ein Element hat und sonst nur Nullen. Dann lässt man bei der Matrix [mm] A^{(2)} [/mm] die erste Zeile erste Spalte weg und führt so den Algorithmus sukzessive fort. So erhält man eine obere Dreiecksmatrix. Die rot markierten Stellen bedeuten quasi nur das man formal die vollständige Matrix erhält. (E ist die einheitsmatrix in entsprechender Dimension)
So erhälst Du für dein Beispiel:
[mm]Q=Q_1 \pmat{ 1 & 0 & 0 \\ 0 \\ 0 & & Q_2 } \pmat{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & Q_3 }[/mm]
[mm]R=\pmat{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & Q_3 } \pmat{ 1 & 0 & 0 \\ 0 \\ 0 & & Q_2 } Q_1[/mm]
[mm] (Q_2 [/mm] ist nat eine 2x2 Matrix)
gruß
mathemaduenn
P.S.: eine Reaktion ist immer schön auch wenn die heißt : "Hab leider keine Zeit um mich weiter damit auseinanderzusetzen."
|
|
|
| |
|
Hallo mathemaduenn,
> Zunächst sign(-4)=-1(in der Berechnung des K) weil sign(x)
> das Vorzeichen von x ist.
Bist du sicher, daß da ein Fehler vorliegt? sign(4) = +1 = 1. Also -sign(4) = -1. In der Matrix A ist doch das Element [mm] $a_{1,1} [/mm] = 4$.
Ich habe es jetzt jedenfalls auch mit deinem Tipp probiert, wobei die Stellen, die dann geändert werden müßten, rot sind:
1. [mm]l := \min\{2,3\} = 2[/mm]
2. [mm]i=1,2\![/mm]
3. [mm]\left|L\right| := \sqrt{\frac{\sqrt{4^2+3^2}\left(\sqrt{4^2+3^2}+4\right)}{2}} = 3\sqrt{\frac{5}{2}}[/mm]
4. [mm]k\ :=\ \stackrel{\textcolor{red}{?}}{-}\!4\cdot{5} = -20\textcolor{red}{\{20\}}[/mm], da [mm]4\ne 0[/mm]
5. [mm]w:=\frac{1}{6\sqrt{\frac{5}{2}}}\left(\begin{pmatrix}4\\3\\0\end{pmatrix}\stackrel{\textcolor{red}{-}}{+}\begin{pmatrix}20\\0\\0\end{pmatrix}\right)=\frac{1}{6\sqrt{\frac{5}{2}}}\begin{pmatrix}24\textcolor{red}{\{-16\}}\\3\\0\end{pmatrix}[/mm]
6. [mm]\tilde{Q}_i := \begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}-2ww^H=\begin{pmatrix}-11.8\textcolor{red}{\{-\frac{211}{45}\}}&-1.6\textcolor{red}{\{\frac{16}{15}\}}&0\\-1.6&0.8&0\\0&0&1\end{pmatrix}[/mm]
> Bis auf diesen kleinen Fehler hast du jetzt dein Start Q berechnet.
> Dieses multiplizierst Du mit A und erhälst normalerweise
> eine Matrix [mm]A^{(2)}[/mm] die in der ersten Spalte in der ersten
> Zeile ein Element hat und sonst nur Nullen.
Offenbar habe ich mich dann beide Male verrechnet, denn nach meiner ursprünglichen Rechnung erhalte ich:
[m]\begin{pmatrix}-11.8 & -1.6 & 0\\ -1.6 & 0.8 & 0\\ 0 & 0 & 1\end{pmatrix}*\begin{pmatrix}4 & 4 & 0\\ 3 & 3 & 5\\ 0 & 4 & 1\end{pmatrix} = \begin{pmatrix}-52 & -52 & -8\\ -4 & -4 & 4\\ 0 & 4 & 1\end{pmatrix}[/m]
und wenn ich deinen Tipp befolge, ergibt sich:
[m]\begin{pmatrix}-\bruch{211}{45} & \bruch{16}{15} & 0 \\ - 1.6 & 0.8 & 0 \\ 0 & 0 & 1\end{pmatrix} * \begin{pmatrix}4 & 4 & 0 \\ 3 & 3 & 5 \\ 0 & 4 & 1\end{pmatrix} = \begin{pmatrix}-\bruch{140}{9} & -\bruch{140}{9} & \bruch{16}{3}\\ -4 & -4 & 4\\ 0 & 4 & 1\end{pmatrix}[/m]
Keine dieser Ergebnis-Matrizen hat nur Nullen außer dem obersten Element ganz links.
> Dann lässt man
> bei der Matrix [mm]A^{(2)}[/mm] die erste Zeile erste Spalte weg und
> führt so den Algorithmus sukzessive fort. So erhält man
> eine obere Dreiecksmatrix. Die rot markierten Stellen
> bedeuten quasi nur das man formal die vollständige Matrix
> erhält. (E ist die einheitsmatrix in entsprechender
> Dimension)
> So erhälst Du für dein Beispiel:
> [mm]Q=Q_1 \pmat{ 1 & 0 & 0 \\ 0 \\ 0 & & Q_2 } \pmat{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & Q_3 }[/mm]
>
> [mm]R=\pmat{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & Q_3 } \pmat{ 1 & 0 & 0 \\ 0 \\ 0 & & Q_2 } Q_1[/mm]
>
> [mm](Q_2[/mm] ist nat eine 2x2 Matrix)
Im Moment fällt es mir schwer das zu verstehen. Aber hoffentlich verstehe ich mehr, wenn sich das mit dem oberen Tipp geklärt hat.
Viele Grüße
Karl
|
|
|
| |
|
Hallo Karl,
Da hab ich bei Dir wohl Verwirrung gestiftet weil ich sign(-4) geschrieben habe? Es bleibt das sign(x) Das Vorzeichen von x ist.
In der Aufgabe wäre K=sign(4) [mm] \wurzel{4^2+3^2} [/mm] = 1 *5
gruß
mathemaduenn
|
|
|
|
