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.
 
 

Definition und Eigenschaften

Die Spiegel-Hyperebene kann durch einen Einheitsvektor \(\displaystyle \bm{v}\) (einen Vektor mit der Länge 1), der orthogonal zur Hyperebene ist, definiert werden.
Wenn \(\displaystyle \bm{v}\) als Spalteneinheitsvektor gegeben und \(\displaystyle \bm{I}\) die Einheitsmatrix ist, dann ist die oben beschriebene lineare Abbildung durch die folgende Householder-Matrix gegeben (\(\displaystyle \bm{v} ^{T}\) bezeichnet die Transponierte des Vektors \(\displaystyle \bm{v}\)):
\(\displaystyle Q = I - 2 v v^T\)
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 \(\displaystyle A=QR\) darstellbar (QR-Zerlegung), wobei \(\displaystyle Q\) orthonormale Spalten hat. In \(\displaystyle R\) ist gespeichert, wie sich die Spalten von \(\displaystyle A\) durch die von \(\displaystyle Q\) darstellen lassen. Hat \(\displaystyle A\) nun linear abhängige Spalten, so kann man \(\displaystyle A\) trotzdem Spalte für Spalte mit der Householdermatrix transformieren.
Die Householder-Matrix hat folgende Eigenschaften:
  • sie ist symmetrisch: \(\displaystyle Q = Q^T\)
  • sie ist orthogonal: \(\displaystyle Q^{-1} = Q^T\)
  • sie ist involutorisch: \(\displaystyle Q^{2} = I\)
  • sie hat die Eigenwerte 1 und -1.
Des Weiteren spiegelt \(\displaystyle Q\) wirklich einen Punkt \(\displaystyle X\) (den wir mit seinem Ortsvektor \(\displaystyle \bm{x}\) identifizieren) wie oben beschrieben, da: \(\displaystyle Qx = x - 2 v v^Tx = x - 2 \langlev,x\rangle v\), wobei < · , · > das Skalarprodukt bezeichnet. Beachte, dass \(\displaystyle \langle\bm{v},\bm{x}\rangle\) dem Abstand von \(\displaystyle X\) zur Hyperebene entspricht.

Anwendung: QR-Zerlegung

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 \(\displaystyle (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 \(\displaystyle A=QR \in \R^{m\times n},{m \ge n}\) mit dem Householder-Verfahren beträgt:
\(\displaystyle \begin{matrix} {m \gg n} &\qquad& {2n^2 \cdot m} \\ {m \approx n} &\qquad& {4 \cdot \over{1 }{ 3} n^3} \end{matrix} \)

Seit die Mathematiker über die Relativitätstheorie hergefallen sind, verstehe ich sie selbst nicht mehr.

Albert Einstein

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Householdertransformation aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе