Householdertransformation

In der Mathematik beschreibt die Householdertransformation die Spiegelung eines Vektors an der Hyperebene durch Null in einem euklidischen Raum. Im dreidimensionalen Raum ist sie eine lineare Abbildung, die eine Spiegelung an einer Ebene (durch den Ursprung) beschreibt.

Die Householdertransformation wurde 1958 durch den amerikanischen Mathematiker Alston Scott Householder eingeführt.

Die Spiegel-Hyperebene kann durch einen Einheitsvektor $\bm{v}$ (einen Vektor mit der Länge 1), der orthogonal zur Hyperebene ist, definiert werden.

Wenn $\bm{v}$ als Spalteneinheitsvektor gegeben und $\bm{I}$ die Einheitsmatrix ist, dann ist die oben beschriebene lineare Abbildung durch die folgende Householder-Matrix gegeben ($\bm{v} ^{T}$ bezeichnet die Transponierte des Vektors $\bm{v}$):

Spiegelungsmatrizen gab es selbstverständlich schon lange vorher und in der reinen Mathematik ist der Begriff Householder-Matrix für eine Spiegelungsmatrix eher unbekannt.

Diese Householdermatrix ist nützlich, wenn man eine beliebige Matrix (auch mit linear abhängigen Spalten) mit Hilfe einer orthonormalen Matrix darstellen will. Hat die Matrix linear unabhängige Spalten, so ist sie in der Form $A=QR$ darstellbar (QR-Zerlegung), wobei $Q$ orthonormale Spalten hat. In $R$ ist gespeichert, wie sich die Spalten von $A$ durch die von $Q$ darstellen lassen. Hat $A$ nun linear abhängige Spalten, so kann man $A$ trotzdem Spalte für Spalte mit der Householdermatrix transformieren.

Die Householder-Matrix hat folgende Eigenschaften:

Des Weiteren spiegelt $Q$ wirklich einen Punkt $X$ (den wir mit seinem Ortsvektor $\bm{x}$ identifizieren) wie oben beschrieben, da: $Qx = x - 2 v v^Tx = x - 2 \langle v,x\rangle v$, wobei < · , · > das Skalarprodukt bezeichnet. Beachte, dass $\langle\bm{v},\bm{x}\rangle$ dem Abstand von $X$ zur Hyperebene entspricht.

Householder-Spiegelungen können zur stabilen Berechnung von QR-Zerlegungen verwendet werden, indem zuerst eine Spalte einer Matrix auf das Vielfache eines Standard-Basisvektors gespiegelt wird; die Transformationsmatrix berechnet und mit der Originalmatrix multipliziert wird. Anschließend bearbeitet man die $(i,i)$ Minoren dieses Produkts rekursiv auf die gleiche Art. Weiteres findet sich unter QR-Zerlegung.

Die Zahl der Operationen für die QR-Zerlegung einer Matrix $A=QR \in \R^{m\times n},{m \ge n}$ mit dem Householder-Verfahren beträgt:

$\begin{matrix} {m \gg n} &\qquad& {2n^2 \cdot m} \\ {m \approx n} &\qquad& {4 \cdot \over{1 }{ 3} n^3} \end{matrix}$