Householderverfahren

Beschreibung

Das Househoulderverfahren bezeichnet das Verfahren, eine QR-Zerlegung durch Householdermatrix zu Erhalten.

Die Idee ist hier, dass jede Rotation (Geometrie) aus $SO(3)$ als Verkettung von Spiegelungen an Hyperebenen geschrieben werden kann.

Definition

Sei $A$ eine positiv definite, Hermitesche Matrix. Wir wollen eine QR-Zerlegung $A=QR$ durchführen.

Seien $a_1,...,a_n$ die Spalten von $A$. Wir finden die eindeutige Householdermatrix $H_1$, die $a_1$ auf ein Vielfaches des ersten Einheitsvektor $e_1$ spiegelt.

Betrachte nun die Matrix $H_{1}A$. Die Matrix skaliert den ersten Einheitsvektor. Wir suchen nun eine eindeutige Householdermatrix $H_2$, die $a_2$ auf $e_2$ spiegelt, führen aber gleichzeitig eine Scherung ein, die $a_1$ unverändert lässt. Dies kann erreicht werden, indem man die erste Komponente des Spieglungsvektor $u$ auf $0$ setzt.

Wir wiederholen die Schritte. Die Matrix $H_n...H_{1}A$ bildet Einheitsvektoren auf gescherte Voktoren ab, hat also Dreiecksform. $H_1...H_n$ ist eine unitäre Matrix (hoffe ich zumindest. Es ist hier eine Folge von Spiegelungen. Ich weiß also nicht, warum die Determinante $1$ und nicht $-1$ ist.) $A=QR=(H_1...H_n)(H_n...H_{1}A)$ ist die gesuchte Zerlegung.

Eigenschaften

Erste Spiegelung

Wir wollen eine Householder-Transformation finden, die einen Vektor $x$ auf ein Vielfaches des ersten Standardvektors spiegelt. Dies machen wir folgendermaßen: $u=\frac{v}{\Vert v{\Vert }_2},v:=\{\begin{array}{ll}\frac{x}{\Vert x{\Vert }_2}+\frac{x_1}{|x_1|}{e}_1& \text{wenn }{x}_1\ne 0\\ \frac{x}{\Vert x\Vert }+e_1& \end{array}$ Wobei $x_1=e^1(x)$ die erste Komponente von $x$ ist.

Spiegelt man in Richtung des erhaltenen Vektors $u$, so wird $x$ auf ein Vielfaches von $e_1$ abgebildet. Das $\frac{x_1}{|x_1|}$ benötigt man, damit das Verfahren auch für komplexe Zahlen korrekt funktioniert.

Q: Sei $x$ ein Vektor. Was ist die Formel um das $u$ gemäß des Householderverfahrens zu erhalten? A: $u=\frac{v}{\Vert v{\Vert }_2},v:=\{\begin{array}{ll}\frac{x}{\Vert x{\Vert }_2}+\frac{x_1}{|x_1|}{e}_1& \text{wenn }{x}_1\ne 0\\ \frac{x}{\Vert x\Vert }+e_1& \end{array}$

Q: Was ist die Formel, um die Householdermatrix aus $u$ zu erhalten? A: $H=Id-2u{u}^{\ast }$.

Verfahren

Sei $A\in GL(\mathbb{R},n)$. Wie bereits beschrieben, werden wir jetzt induktiv Householdermatrizen erstellen. Wir definieren:

• $A^{(1)}:=A$
• $Q^{(1)}:=Id$

Berechne $A^k,Q^{(k)}$ durch:

• $A^{(k+1)}:=H^{(k)}{A}^{(k)}$
• $Q^{(k+1)}:=Q^{(k)}{H}^{(k)}$

Die Householdermatrix ist die Matrix $Id-2u^{(k)}(u^{(k)})$, die den Vektor $x^{(k)}:=\left(\begin{array}{c}{a}_{k,k}^{(k)}\\ ⋮\\ a_{m,k}^{(k)}\end{array}\right)\in {\text{K}}^{m-k+1}$ auf den Vektor $e_1\in {\text{K}}^{m-k+1}$ abbildet und alle anderen Vektoren gleich lässt. Also: $H^{(k)}:=\left(\begin{array}{cc}Id& 0\\ 0& Id-2u^{(k)}(u^{(k)}{)}^{\ast }\end{array}\right)$

Q: Induktive Definition von $A^{(k+1)}$ und $Q^{(k+1)}$ beim Householder-Verfahren: A: - $A^{(k+1)}:=H^{(k)}{A}^{(k)}$

• $Q^{(k+1)}:=Q^{(k)}{H}^{(k)}$

Q: Berechnung von $H^{(k)}$ im Householder-Verfahren A: $H^{(k)}:=\left(\begin{array}{cc}Id& 0\\ 0& Id-2u^{(k)}(u^{(k)}{)}^{\ast }\end{array}\right)$