Householdertransformation


Householdertransformation

In der Mathematik beschreibt die Householdertransformation die Spiegelung eines Vektors an einer Hyperebene durch Null im euklidischen Raum. Im dreidimensionalen Raum ist sie somit eine Spiegelung an einer Ebene (durch den Ursprung). Die Darstellung dieser linearen Abbildung durch eine Matrix wird als Householder-Matrix bezeichnet. Verwendung findet sie vor allem in der numerischen Mathematik, wenn mittels orthogonaler Transformationen Matrizen so gezielt umgeformt werden, dass bestimmte Spaltenvektoren auf das Vielfache des ersten Einheitsvektors abgebildet werden, insbesondere beim QR-Verfahren und der QR-Zerlegung.

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

Inhaltsverzeichnis

Definition und Eigenschaften

Illustration der Householder-Transformation in 2D

Die Spiegel-Hyperebene kann durch einen Normalenvektor v, also einen Vektor, der orthogonal zur Hyperebene ist, definiert werden. Ist v als Spaltenvektor gegeben und I die Einheitsmatrix, dann wird die oben beschriebene lineare Abbildung durch die folgende Matrix dargestellt:

H = I - \frac {2} {v^T v} v v^T.

Dabei bezeichnet vT die Transponierte des Spaltenvektors v, also einen Zeilenvektor. Der Nenner vTv ist das Skalarprodukt von v mit sich selbst, vvT das dyadische Produkt, eine Matrix. Die Matrix \tfrac {1} {v^T v} v v^T beschreibt die Orthogonalprojektion auf die durch v gegebene Richtung. Ist v auf die Länge eins normiert, also vTv = 1, so vereinfacht sich die Formel zu

H = I − 2vvT.

Die Spiegelungseigenschaft ersieht man daraus, dass


Hx 
  = x - 2 v v^Tx 
  = x - 2 \langle v,\, x \rangle\, v
  = (x-\langle v,\, x \rangle\, v)-\langle v,\, x \rangle\, v
,

wobei \langle \cdot, \cdot \rangle das Skalarprodukt bezeichnet. Der Term \langle v,\, x \rangle entspricht dabei dem Abstand des Punktes x zur Hyperebene v^\perp. Der Vektor x wird also in zwei orthogonale Anteile zerlegt, wobei der erste Anteil in der Hyperebene liegt und der zweite ein Vielfaches des Vektors v ist. Unter der Spiegelung wird der Anteil in der Ebene invariant gelassen, der Anteil in Richtung v, also senkrecht zur Ebene, wird "umgeklappt", also nun abgezogen statt addiert.

Die Householder-Matrix hat folgende Eigenschaften:

  • Sie ist symmetrisch: H = HT
  • Sie ist orthogonal: H − 1 = HT
  • Sie ist involutorisch: H2 = I (Dies folgt aus der Symmetrie und der Orthogonalität.)
  • Sie hat die Eigenwerte -1 (mit Vielfachheit 1) und 1 (mit Vielfachheit n − 1).
  • Matrix-Vektor-Multplikationen mit H sind schnell berechenbar.

Konstruktion einer spezifischen Spiegelung

Es sei ein Vektor a gegeben, der auf ein Vielfaches des Vektors e gespiegelt werden soll, das heißt, gesucht ist ein Einheitsvektor v mit Sva = λe. Geometrisch ist der Vektor v die Richtung einer der zwei Winkelhalbierenden der Geraden in Richtung a und in Richtung e. Die Winkelhalbierende ergibt sich, indem man auf beiden Geraden Punkte mit demselben Abstand zum Nullpunkt wählt und auf der Verbindungsstrecke dieser zwei Punkte den Mittelpunkt konstruiert. Die Gerade durch Nullpunkt und Mittelpunkt hat dann die gesuchte Richtung v, der Vektor v selbst ergibt sich durch Normieren dieser Richtung. Die zweite Winkelhalbierende ergibt sich, indem die Konstruktion ausgehend von a und -e durchgeführt wird.

Der Einfachheit halber sei e normiert, \|e\|=1. Dann muss, wegen der Orthogonalität der Spiegelung, \lambda=\pm\|a\| gelten. Der gesuchte Spiegelungsvektor v ergibt sich nun durch Normieren des Mittelpunktes \tfrac12(a+\lambda\,e), also

v=\frac{a+\lambda\, e}{\|a+\lambda\, e\|}.

Beide Vorzeichenvarianten führen zum gewünschten Ergebnis (sofern der Nenner von Null verschieden ist). Aus Gründen numerischer Stabilität wird das Vorzeichen von λ so gewählt, dass der Nenner am größten ist, also \lambda\cdot\langle a,\,e\rangle\ge 0 gilt.

In der Probe ergibt sich

\begin{align}
S_va=&a-2v\langle v,a\rangle
 \\[0.5em]
=&a-2\,(a+\lambda e)\,\frac{
 \|a\|^2+\lambda\langle e,a\rangle
 }{
 \|a\|^2+2\lambda\langle a,e\rangle+\lambda^2\|e\|^2}
 \\[0.8em]
=&a-2\,(a+\lambda e)\,
 \frac{\|a\|^2+\lambda\langle e,a\rangle}{\|a\|^2+2\lambda\langle a,e\rangle+\|a\|^2}
 \\[0.5em]
=&-\lambda e\\[0.5em]
\end{align}

Beispiel

Am häufigsten wird der Fall betrachtet, in dem e = e1 der erste kanonische Basisvektor ist. Sei a=(a_1,\bar a) in erste Komponente und Restvektor zerlegt. Dann gilt für die Norm \|a\|=\sqrt{|a_1|^2+\|\bar a\|^2}. Als Vorzeichen von λ ist das Vorzeichen von a1 zu wählen, die Richtung der Spiegelung ist dann

a + \operatorname{sign}(a_1)\,\|a\| e_1 = \Bigl(\operatorname{sign}(a_1)\,(|a_1|+\|a\|),\;\bar a\Bigr).

Der Vektor v entsteht durch Normierung dieser Richtung. Nach Umformen stellt sich die Norm der Richtung als

\|a+\lambda e_1\|=\sqrt{2\,\|a\|\,(\|a\|+|a_1|)}

dar, wobei in dieser Form nur bereits berechnete Zwischenergebnisse benutzt werden. In der unnormierten Variante der Spiegelung ergeben sich weitere Einsparungen an Rechenschritten.

Anwendung: QR-Zerlegung

Householder-Spiegelungen können zur stabilen Berechnung von QR-Zerlegungen einer Matrix A=QR\in\R^{m\times n} verwendet werden, indem zunächst die erste Spalte der Matrix mit einer Spiegelung H1 auf das Vielfache des ersten Einheitsvektors gespiegelt wird, wie im letzten Abschnitt erläutert (jetzt bezeichnet der Index aber die Nummer der Spiegelung).

Danach behandelt man H1A mit einer Spiegelung H2 analog und im i-ten Schritt den (i,i) Minoren des Produkts H_{i-1}\cdots H_1A iterativ auf die gleiche Art, bis die Restmatrix Dreieckgestalt R besitzt. Am Ende bekommt man im Fall m\ge n die QR-Zerlegung

 A=QR,\quad Q=H_1H_2\cdots H_{m-1}\in\R^{m\times m},\ R=\begin{pmatrix}R_1\\0\end{pmatrix}\in\R^{m\times n}.

Man beachte, dass Q hier eine quadratische Matrix ist. Meist wird die Matrix Q nicht explizit berechnet, sondern man nutzt direkt die Produktform, auch bei Q^T=S_{m-1}\cdots S_2S_1. Dazu werden die Spiegelvektoren vi von S_i=S_{v_i} im frei gewordenen Platz der Matrix A gespeichert.

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 \over 3} n^3} \end{matrix}

Pseudocode

Da für die meisten Berechnungen das explizite Ausrechnen von Q nicht nötig ist, reicht es nur die Matrix R zu berechnen. z ist die linke Spalte der jeweiligen Untermatrix. Bei der unten angegebenen Funktion wir das Ergebnis direkt in A geschrieben, so dass nach Abarbeitung des Algorithmus das R in A steht. Die Zeile R=A könnte also auch weggelassen werden.

  function GetR(A)
     for k=1:n
         z=A(k:m,k);
   
         uk=z;
         uk(1)+=sign(z(1))*norm(z);
         uk=uk/norm(uk);
   
         vk=zeros(m);
         vk(k:m)= uk;
   
         A=A-(2*vk)*(vk'*A);
     end
     R=A;
     return R;

Literatur

  • Gene H. Golub, Charles F. van Loan: Matrix Computations. 2nd Edition. The Johns Hopkins University Press, 1989.
  • Gerhard Opfer: Numerische Mathematik für Anfänger. Eine Einführung für Mathematiker, Ingenieure und Informatiker, 5. Aufl., Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0413-6
  • Martin Hermann: Numerische Mathematik, 2., überarbeitete und erweiterte Auflage, Oldenbourg Verlag, München, Wien 2006, ISBN 3-486-57935-5, pp.159-161

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Householder — Alston Scott Householder (* 5. Mai 1904 in Rockford (Illinois), † 4. Juli 1993, Malibu (Kalifornien)) war ein US amerikanischer Mathematiker, der Pionierarbeit in der numerischen linearen Algebra geleistet hat. Er führte 1958 die nach ihm… …   Deutsch Wikipedia

  • Householder-Matrix — 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… …   Deutsch Wikipedia

  • Householder-Spiegelung — 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… …   Deutsch Wikipedia

  • Householder-Transformation — 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… …   Deutsch Wikipedia

  • Householdermatrix — 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… …   Deutsch Wikipedia

  • Alston Scott Householder — (* 5. Mai 1904 in Rockford (Illinois); † 4. Juli 1993, Malibu (Kalifornien)) war ein US amerikanischer Mathematiker, der Pionierarbeit in der numerischen linearen Algebra geleistet hat. Er führte 1958 die nach ihm benannte… …   Deutsch Wikipedia

  • Clifford-Algebra — Die Clifford Algebra (nach William Kingdon Clifford) ist ein mathematisches Konstrukt, das in der Differentialgeometrie sowie in der Quantenphysik Anwendung findet. Sie dient der Definition der Spin Gruppe und ihren Darstellungen, der… …   Deutsch Wikipedia

  • Deflation (Mathematik) — Deflation bezeichnet eine Technik aus der numerischen Mathematik, mit der eine Matrix in Blockdreiecksform gebracht wird, so dass das Spektrum von A gerade die Vereinigung der Spektren der Diagonalblöcke ist. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • GMRES — Das GMRES Verfahren (für Generalized minimal residual method) ist ein iteratives numerisches Verfahren zur Lösung großer, dünnbesetzter linearer Gleichungssysteme. Das Verfahren ist aus der Klasse der Krylow Unterraum Verfahren und insbesondere… …   Deutsch Wikipedia

  • Gram-Schmidt — Das Gram Schmidtsche Orthogonalisierungsverfahren ist ein Algorithmus aus dem mathematischen Teilgebiet der linearen Algebra. Er erzeugt zu jedem System linear unabhängiger Vektoren aus einem Prähilbertraum, d. h. einem Vektorraum mit… …   Deutsch Wikipedia