Householdermatrix

03.06.2008, 19:51

Corn

Householdermatrix

Hallo
Ich habe ein riesen Problem
Bestimmen Sie eine Householdermatrix H, sodaß $\begin{eqnarray*} H*a = (7,0,0,0,0,0)^t \end{eqnarray*}$ mit $\begin{eqnarray*} a = (-2,1,1,1,1,1)^t \end{eqnarray*}$

Kann mir hier jemand eine Anleitung geben, was ich genau machen muß?
Ich schaffe es wohl, eine Matrix H zu finden, die die Gleichung löst, aber das ist dann höchstwahrscheinlich keine Householdermatrix.
Hilfe

Corn

04.06.2008, 02:55

20_Cent

Auf diesen Beitrag antworten »

Da gibts ein Rezept.
Ich denke das findeste durch googlen...
Du brauchst einen bestimmten Vektor v, damit kannste H berechnen...
mfG 20

04.06.2008, 07:08

Corn

Auf diesen Beitrag antworten »

Hallo 20_Cent, das klingt jetzt blöd, aber ich finde zur Householdermatrix immer nur die Householdertransformation oder wie man Ausgleichsprobleme löst.
Kannst du mir nicht den Link geben oder ein paar Schlagwörter?

04.06.2008, 09:41

tigerbine

Auf diesen Beitrag antworten »

Theorie

Zitat:

Original von tigerbine
Nun soll eine volle QR-Zerlegung bestimmt werden. Wieder hat A den Rang n. Es ist dann

$\begin{eqnarray*} A = QR \Leftrightarrow Q^{-1}A = R \Leftrightarrow Q^{T}A = R \end{eqnarray*}$

Ähnlich dem Prinzip beim Gaußalgorithmus ist es nun das Ziel die Matrix $\begin{eqnarray*} Q^T \end{eqnarray*}$ zu konstruieren, so dass $\begin{eqnarray*} Q^TA \end{eqnarray*}$ eine obere Dreiecksmatrix ist. Man schreibt:

$\begin{eqnarray*} Q^T = Q_l \cdot .... \cdot Q_1,\quad l:=\min\{m-1,n\} \end{eqnarray*}$

Dabei annulliert $\begin{eqnarray*} Q_j \end{eqnarray*}$ die Eintrage der j-ten Spalte unterhalb der Diagonalen.

Zitat:

Original von tigerbine
Householder-Spiegelung (Definition)

$\begin{eqnarray*} H:=I_n - 2\cdot \underbrace{uu^T}_{Dyade}\quad \text{mit } u \in \mathbb R^n,~||u||_2=1 \end{eqnarray*}$

Konstruktion von u

x sei nun der Teil des Spaltenvektors von "A", den es zu annullieren gilt, zzgl. des Diagonalelements.

$\begin{eqnarray*} u:=x + \text{sign}(x_1)\cdot ||x||_2 \cdot e_1 \quad \text{(Bedingungen für die zu erzeugenden Nullen)} \end{eqnarray*}$

$\begin{eqnarray*} \beta:=\frac{2}{u^Tu} \quad \text{(Normierung)} \end{eqnarray*}$

$\begin{eqnarray*} H=I-\beta\cdot uu^T \end{eqnarray*}$

Eigenschaften der Matrix H

H ist symmetrisch, dies folgt direkt aus der Symmetrie von I und der Dyade.
H ist orthogonal, denn
$\begin{eqnarray*} H^TH = (I_n-2uu^T)^T(I_n-2uu^T) = I - 4uu^T + 4u\underbrace{(u^Tu)}_{1}u^T = I_n \end{eqnarray*}$
u ist ein Eigenvektor von H, denn
$\begin{eqnarray*} Hu = (I_n-2uu^T) u = u - 2u(u^Tu) = (-1) \cdot u \end{eqnarray*}$
Der Eigenraum von (-1) ist eindimensional.
H hat sonst nur noch den Eigenwert 1. Die Dimension seines Eigenraums ist (n-1). Da H symmetrisch und regulär ist, gibt es eine ONB aus Eigenvektoren von H, so dass H bzgl. dieser Diagonalagestalt hat .Sei v ein zu u orthogonaler Vektor. Dann gilt:
$\begin{eqnarray*} Hv = v - 2u\underbrace{u^Tv}_{0} = v \end{eqnarray*}$
H ist eine Spiegelung, denn
$\begin{eqnarray*} \det(H) = -1 \end{eqnarray*}$
Hx ist ein Vielfaches des ersten Einheitsvektors mit dem Faktor $\begin{eqnarray*} \alpha = - \text{sign}(x_1)||x||_2 \end{eqnarray*}$

Beweis:

Die Vektoren x und u unterscheiden sich nur im ersten Eintrag, d.h. es gilt $\begin{eqnarray*} u_j=x_j,~j=2,...,n \end{eqnarray*}$ . So kann man Dyade wie folgt schreiben:

$\begin{eqnarray*} U = \begin{pmatrix}u_1u_1 &u_1x_2 & \hdots & u_1x_n \\ x_2u_1 &x_2x_2 & \hdots & x_2x_n \\ \vdots & \vdots & \ddots & \vdots \\ x_nu_1 & x_nx_2 & \hdots & x_nx_n \end{pmatrix} \end{eqnarray*}$

Nun ist

$\begin{eqnarray*} Hx = (I-\beta uu^T)x = x - \frac{2}{u^Tu}\cdot Ux \end{eqnarray*}$ .

Für den Nenner des Faktors ß gilt:

$\begin{eqnarray*} u^Tu &&= \sum_{k=1}^n~u_k^2 = u_1^2 + \sum_{k=2}^n~x_k^2 \\ &&=\Bigl(x_1+\text{sign}(x_1)||x||_2\Bigr)^2 + \sum_{k=2}^n~x_k^2 \\&&= x_1^2 + 2x_1\cdot \text{sign}(x_1)||x||_2 +(\text{sign}(x_1)||x||_2)^2 + \sum_{k=2}^n~x_k^2 \\&& = 2\cdot \Bigl( ||x||_2^2+x_1 \cdot \text{sign}(x_1)||x||_2 \Bigr) \end{eqnarray*}$

Für den j-ten Eintrag des Vektors Ux gilt:

$\begin{eqnarray*} (Ux)_j = \sum_{k=1}^{n}~(u_ju_k)x_k \end{eqnarray*}$

Für j=1 gilt:

$\begin{eqnarray*} (Ux)_1&& = \sum_{k=1}^n~(u_1u_k)x_k = u_1 \cdot \Bigl(u_1x_1 + \sum_{k=2}^n~x_kx_k \Bigr)\\ &&=u_1 \cdot \Bigl((x_1 + \text{sign}(x_1)\cdot ||x||_2)x_1 +\sum_{k=2}^n~x_kx_k \Bigr) \\&& =u_1\cdot \Bigl( ||x||_2^2 + x_1 \cdot \text{sign}(x_1)||x||_2\Bigr) \end{eqnarray*}$

$\begin{eqnarray*} (Hx)_1&&=[(I-\beta\cdot uu^T)x]_1 = x_1-\beta\cdot (Ux)_1 \\&& = x_1 - \beta\cdot u_1\cdot \Bigl( ||x||_2^2 + x_1 \cdot \text{sign}(x_1)||x||_2\Bigr) \\&& = x_1 - u_1\\&& = -\text{sign}(x_1)||x||_2 \end{eqnarray*}$

Für j =2,...,n gilt:

$\begin{eqnarray*} (Ux)_1&& = \sum_{k=1}^n~(x_ju_k)x_k = \\&&=x_ju_1x_1 + \sum_{k=2}^n~(x_jx_k)x_k \\&&=x_ju_1x_1 + x_j\cdot \sum_{k=2}^n~(x_k)^2 = x_j\cdot (u_1x_1 + \sum_{k=2}^n~(x_k)^2) \\&&= x_j\cdot (x_1^2+x_1\cdot \text{sign}(x_1)||x||_2 + \sum_{k=2}^n~(x_k)^2) \\&& = x_j\cdot (||x||_2^2 + x_1\cdot \text{sign}(x_1)||x||_2) \end{eqnarray*}$

$\begin{eqnarray*} (Hx)_j=x_j -x_j = 0 \end{eqnarray*}$

Somit ist Hx ein Vielfaches des ersten Einheitsvektors mit obigem Faktor.

Zitat:

Original von tigerbine
Wie hängen nun die eingangs erwähnten Matrizen $\begin{eqnarray*} Q_i \end{eqnarray*}$ und die Matrizen H zusammen? Mit entsprechenden Dimensionen gilt:

$\begin{eqnarray*} Q_i = \begin{pmatrix}\underbrace{I}_{(i-1) \times (i-1)} &\underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)}&\underbrace{H_i}_{(n+1-i)\times (n+1-i)} \end{pmatrix} \end{eqnarray*}$

Auch die Matrizen $\begin{eqnarray*} Q_i \end{eqnarray*}$ sind symmetrisch. Es gilt:

$\begin{eqnarray*} Q_i^T&&= \begin{pmatrix}\underbrace{I}_{(i-1) \times (i-1)} &\underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)}&\underbrace{H_i^T}_{(n+1-i)\times (n+1-i)} \end{pmatrix} \\&&=\begin{pmatrix}\underbrace{I}_{(i-1) \times (i-1)} &\underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)}&\underbrace{H_i}_{(n+1-i)\times (n+1-i)} \end{pmatrix} \\&&=Q_i \end{eqnarray*}$

Ebenso sind sie orthogonal:

$\begin{eqnarray*} Q_i^TQ_i &&= \begin{pmatrix}\underbrace{I^TI}_{(i-1) \times (i-1)} &\underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)}&\underbrace{H_i^TH_i}_{(n+1-i)\times (n+1-i)} \end{pmatrix} \\&&= I \end{eqnarray*}$

Und mit der Rechenregel für Blockdiagonalmatrizen folgt auch sofort:

$\begin{eqnarray*} \det(Q_i)=-1 \end{eqnarray*}$

Handelt es sich auch um eine Householder-Matrix? Dazu muss man nur einen Vektor $\begin{eqnarray*} \hat u_i \end{eqnarray*}$ finden mit:

$\begin{eqnarray*} Q_i = I - \frac{2}{\hat u_i^T \hat u_i} \cdot \hat u_i \hat u_i^T \end{eqnarray*}$

Wählt man nun:

$\begin{eqnarray*} (\hat u_i)^T = ( \underbrace{0}_{(i-1)},~\underbrace{u_i}_{(n+1-i)})^T \end{eqnarray*}$

Dann ist:

$\begin{eqnarray*} \frac{2}{\hat u_i^T \hat u_i} = \frac{2}{u_i^T u_i} \end{eqnarray*}$

$\begin{eqnarray*} \hat U_i = \begin{pmatrix} \underbrace{0}_{(i-1) \times (i-1)} & \underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)} &\underbrace{U_i}_{(n+1-i) \times (n+1-i)} \end{pmatrix} \end{eqnarray*}$

Damit ergibt:

$\begin{eqnarray*} I_n - \beta \cdot \hat U_i &&= \begin{pmatrix} \underbrace{I_{i-1}}_{(i-1) \times (i-1)} & \underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)} &\underbrace{I_{n+1-i}-\beta \cdot U_i}_{(n+1-i) \times (n+1-i)} \end{pmatrix} =\begin{pmatrix} \underbrace{I_{i-1}}_{(i-1) \times (i-1)} & \underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)} &\underbrace{H_i}_{(n+1-i) \times (n+1-i)} \end{pmatrix} \\ && = Q_i \end{eqnarray*}$

Somit sind die $\begin{eqnarray*} Q_i \end{eqnarray*}$ auch Householder-Matrizen.

04.06.2008, 09:41

tigerbine

Auf diesen Beitrag antworten »

Beispiel
$\begin{eqnarray*} A^{(1)}=\begin{pmatrix} 1&5&4 \\ -2&1&3 \\ 2&0&-2 \end{pmatrix}\Rightarrow x^{(1)} = \begin{pmatrix}1\\-2\\2 \end{pmatrix} \end{eqnarray*}$

Somit ergibt sich:

$\begin{eqnarray*} u^{(1)} &&= \begin{pmatrix}1\\-2\\2 \end{pmatrix} + (+1) \cdot \sqrt{1^2+2^2+2^2} \cdot \begin{pmatrix}1\\0\\0 \end{pmatrix} \\&&= \begin{pmatrix}1\\-2\\2 \end{pmatrix} + 3 \cdot \begin{pmatrix}1\\0\\0 \end{pmatrix} = \begin{pmatrix}4\\-2\\2 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \beta^{(1)} = \frac{2}{(u^{(1)})^Tu^{(1)}} = \frac{2}{4^2+2^2+^2} = \frac{1}{12} \end{eqnarray*}$

$\begin{eqnarray*} U_1= u^{(1)}(u^{(1)})^T = \begin{pmatrix} 16&-8&8\\-8&4&-4\\8&-4&4 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} H_1 = I_3- \beta^{(1)} \cdot U =\frac{1}{3}\cdot \begin{pmatrix} -1&2&-2\\2&2&1\\-2&1&2 \end{pmatrix} = Q_1 \end{eqnarray*}$

Und somit erhält man schließlich:

$\begin{eqnarray*} Q_1 \cdot A^{(1)}&& = \frac{1}{3}\cdot \begin{pmatrix} -1&2&-2\\2&2&1\\-2&1&2 \end{pmatrix} \begin{pmatrix} 1&5&4 \\ -2&1&3 \\ 2&0&-2 \end{pmatrix} \\&&= \begin{pmatrix} -3&-1&2 \\ 0&4&4 \\ 0&-3&-3 \end{pmatrix} \end{eqnarray*}$

**************************************************
Nun geht es in Runde 2.

$\begin{eqnarray*} A^{(2)} = \begin{pmatrix}4&4 \\ -3&-3 \end{pmatrix} \Rightarrow x^{(2)} = \begin{pmatrix} 4 \\-3 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} u^{(2)} = \begin{pmatrix} 4 \\-3 \end{pmatrix} + (+1)\cdot \sqrt{4^2+3^2} \cdot \begin{pmatrix}1 \\ 0\end{pmatrix} = \begin{pmatrix}9 \\-3 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \beta^{(2)} = \frac{2}{9^2+3^2} = \frac{1}{45} \end{eqnarray*}$

$\begin{eqnarray*} U_2 = \begin{pmatrix} 81&-27 \\ -27 & 9 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} H_2= I_2 - \beta^{(2)}\cdot U_2 = \begin{pmatrix} -0.8& 0.6 \\ 0.6 & 0.8 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} Q_2 = \begin{pmatrix}1&0&0\\0&-0.8&0.6 \\ 0&0.6 & 0.8 \end{pmatrix} \end{eqnarray*}$

Und damit:

$\begin{eqnarray*} Q_2Q_1A^{(1)} &&=\begin{pmatrix}1&0&0\\0&-0.8&0.6 \\ 0&0.6 & 0.8 \end{pmatrix}\begin{pmatrix} -3&-1&2 \\ 0&4&4 \\ 0&-3&-3 \end{pmatrix}\\&& = \begin{pmatrix} -3&-1&2 \\ 0&-5&-5 \\ 0&0&0 \end{pmatrix} \end{eqnarray*}$

**************************************************

Somit ist die volle QR-Zerlegung fertig. Wir erhalten:

$\begin{eqnarray*} R = \begin{pmatrix} -3&-1&2 \\ 0&-5&-5 \\ 0&0&0 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} Q^{-1} = Q_2Q_1 = \frac{1}{3} \cdot \begin{pmatrix}1&0&0\\0&-0.8&0.6 \\ 0&0.6 & 0.8 \end{pmatrix}\begin{pmatrix} -1&2&-2\\2&2&1\\-2&1&2 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} Q &&=\frac{1}{3} \cdot \begin{pmatrix} -1&2&-2\\2&2&1\\-2&1&2 \end{pmatrix}\begin{pmatrix}1&0&0\\0&-0.8&0.6 \\ 0&0.6 & 0.8 \end{pmatrix} \\&&= \begin{pmatrix} -\frac{1}{3} & -\frac{14}{15} & -\frac{2}{15} \\ \frac{2}{3} & -\frac{1}{3} & \frac{2}{3} \\ -\frac{2}{3} & \frac{2}{15} & \frac{11}{15} \end{pmatrix} \end{eqnarray*}$

Es ist also:

$\begin{eqnarray*} A=QR \Leftrightarrow \begin{pmatrix} 1&5&4 \\ -2&1&3 \\ 2&0&-2 \end{pmatrix} = \begin{pmatrix} -\frac{1}{3} & -\frac{14}{15} & -\frac{2}{15} \\ \frac{2}{3} & -\frac{1}{3} & \frac{2}{3} \\ -\frac{2}{3} & \frac{2}{15} & \frac{11}{15} \end{pmatrix}\begin{pmatrix} -3&-1&2 \\ 0&-5&-5 \\ 0&0&0 \end{pmatrix} \end{eqnarray*}$

04.06.2008, 10:24

20_Cent

Auf diesen Beitrag antworten »

Du brauchst natürlich nur eine Householderspiegelung, da du keine Matrix transformieren willst, sondern nur eine Spalte.
mfG 20

04.06.2008, 18:36

Corn

Auf diesen Beitrag antworten »

Hi tigerbine
vielen Dank, dass du all deine Beiträge zusammengesucht hast, um sie mir zur Verfügung zu stellen. Das hat mir sehr geholfen und all meine Unklarheiten beseitigt

04.06.2008, 20:13

tigerbine

Auf diesen Beitrag antworten »

Gerne. Mit dem Hinweis von 20_Cent sollte es dann ja auch geklappt haben. Stellst du dann noch deine Lösung ein? Wink

Neue Frage »

Antworten »

Householdermatrix

Verwandte Themen