Householdermatrix

14.01.2009, 13:35

Bjoern1982

Householdermatrix

Hallo,

ich soll die Determinante, Eigenwerte und Eigenvektoren einer Householder-Matrix $\begin{eqnarray*} Q=I- 2vv^T \end{eqnarray*}$ für einen Vektor v aus R^n mit $\begin{eqnarray*} ||v||_2=1 \end{eqnarray*}$ bestimmen.

Wie bestimme ich eine solche Householdermatrix ?

Gruß Björn

14.01.2009, 13:37

tigerbine

Auf diesen Beitrag antworten »

RE: Householdermatrix

Zitat:

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*}$

Zitat:

$\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*}$

14.01.2009, 22:19

Bjoern1982

Auf diesen Beitrag antworten »

Wow, das passt ja echt hagenau zu meiner Aufgabe smile

Bin ich blind oder wo ist am Ende die gesuchte HH-Matrix H ?
Ich sehe nur H1 und H2...

Edit:

Oder ist das dann am Ende einfach H=Q ?

14.01.2009, 22:23

tigerbine

Auf diesen Beitrag antworten »

Nein, die HH Matrizen tauchen während des Algo auf, mit der Aufgabe jeweils eine Spalte unterhalb der Diagonale zu annulieren. Die tauchen als Blöche in den Qs auf.

14.01.2009, 22:44

Bjoern1982

Auf diesen Beitrag antworten »

Sprich explizit steht die gesucht HH Matrix hier noch gar nicht, ich muss sie mir als noch aus den Blöcken von Q1 und Q2 basteln ?
Wenn ja, wie genau ?

14.01.2009, 22:54

tigerbine

Auf diesen Beitrag antworten »

Du suchst doch eine Matrix Q und eine Matrix R. Und nicht EINE HH Matrix.

Die HH tauchen bei der Bestimmung von Q und R im Algo auf, so wie es da steht.

14.01.2009, 22:56

Bjoern1982

Auf diesen Beitrag antworten »

Inwiefern macht meine eingangs gestellte Frage bzw die AUfgabenstellung dann überhaupt Sinn ?

14.01.2009, 23:08

tigerbine

Auf diesen Beitrag antworten »

Lol, meinste ich stell dir den Beweis der Aussagen einfach ein?

Das Beispiel sollte dir nur mal zeigen, wie so eine H ausssieht.

Zitat:

$\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*}$

Nun musst du eben mal die Eigenschaften nachwweisen. Dabei ist die Definitionsschreibweise schon von Vorteil.

Zitat:

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

14.01.2009, 23:41

Bjoern1982

Auf diesen Beitrag antworten »

Ok ich probiere das nachher nochmal, das scheint wohl die aufwändigste Aufgabe zu sein, ich poste jetzt eben noch die letzte Aufgabe und widme mich dann am Schluss nochmal den HH-Matrizen.

14.01.2009, 23:47

tigerbine

Auf diesen Beitrag antworten »

RE: Householdermatrix

Zitat:

Original von Bjoern1982
Hallo,

ich soll die Determinante, Eigenwerte und Eigenvektoren einer Householder-Matrix $\begin{eqnarray*} Q=I- 2vv^T \end{eqnarray*}$ für einen Vektor v aus R^n mit $\begin{eqnarray*} ||v||_2=1 \end{eqnarray*}$ bestimmen.
Gruß Björn

Die Fetten sind Einzeiler. Augenzwinkern

Und das letzte, eigenltlich auch. Du kennst den EV schon per Definition von H. Nun hab ich schon viel verraten. Augenzwinkern

15.01.2009, 00:41

Bjoern1982

Auf diesen Beitrag antworten »

Naja einen Versuch starte ich nochmal, mir fallen auch gleich die Augen zu Augenzwinkern

Wenn du mir das mit dem Eigenvektor schon so unter die Nase reibst hab ich eben mal getestet mit v:

$\begin{eqnarray*} Qv=(I-2vv^T)v=v-2vv^Tv=v-2v \cdot ||v||_2^2=-1 \cdot v \end{eqnarray*}$

Daraus würde folgen, dass c=-1 der Eigenwert zum Eigenvektor v ist.

Laut wiki soll es aber auch noch den Eigenwert 1 geben.
Die Determinante muss aufgrund der Orthogonalität wohl auch 1 oder -1 sein, das hab ich noch so im Hinterkopf aus der linearen Algebra.

Viel mehr fällt mir derzeit leider nicht ein...ich werde nun aber auch gleich ins Bett gehen, keine Power mehr unglücklich

15.01.2009, 00:47

tigerbine

Auf diesen Beitrag antworten »

V ist korrekt. Die Determinate im Betrag auch. Nun überlege mal, nur von Namen her, was wohl wahrscheinlicher ist. Wenn es schon Spiegelung heißt Big Laugh

Dass sie orthognal ist, naja prüfe doch einfach, ob die transponierte die Inverse ist.

Was passiert, wenn u ein zu v orthogonaler Vektor ist mit Hv?

15.01.2009, 13:31

Bjoern1982

Auf diesen Beitrag antworten »

Hallo bine Wink

Kurze Rückmeldung:

Von der Argumentation zu den Eigenvektoren und Eigenwerten war das alles genauso wie du es schon beschrieben hattest.
Für die Determinante reichte es tatsächlich schon zu sagen, dass Q eine Spiegelung beschreibt.
Alternativ - und das habe ich so gemacht - konnte man noch wie hier mit dem Basiswechsel wir hier begründen

Determinante der Householder Spiegelung

Die Orthogonalitäs und Symmetrieeigenschaften musste man sogar gar nicht mehr zeigen, weil es in der Vorlesung schon bewiesen wurde - insofern wirklich eine sehr kurze Aufgabe...wenn man denn drauf kommt Augenzwinkern

Vielen Dank für die Hilfe smile

15.01.2009, 16:34

tigerbine

Auf diesen Beitrag antworten »

RE: Householdermatrix
Hier nun meine Fortsetzung. Augenzwinkern

Zitat:

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.

Neue Frage »

Antworten »

Householdermatrix

Verwandte Themen