Householdertransformation – Wikipedia

Posted on by

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.

Illustration der Householder-Transformation in 2D

Die Spiegel-Hyperebene kann durch einen Normalenvektor

v{displaystyle v}

, also einen Vektor, der orthogonal zur Hyperebene ist, definiert werden. Ist

v{displaystyle v}

als Spaltenvektor gegeben und

I{displaystyle I}

die Einheitsmatrix, dann wird die oben beschriebene lineare Abbildung durch die folgende Matrix dargestellt:

H=I−2vTvvvT.{displaystyle H=I-{frac {2}{v^{T}v}}vv^{T}.}

Dabei bezeichnet

vT{displaystyle v^{T}}

die Transponierte des Spaltenvektors

v{displaystyle v}

, also einen Zeilenvektor.
Der Nenner

vTv{displaystyle v^{T}v}

ist das Skalarprodukt von

v{displaystyle v}

mit sich selbst,

vvT{displaystyle vv^{T}}

das dyadische Produkt. Die Matrix

1vTvvvT{displaystyle {tfrac {1}{v^{T}v}}vv^{T}}

beschreibt die Orthogonalprojektion auf die durch

v{displaystyle v}

gegebene Richtung.
Ist

v{displaystyle v}

auf die Länge eins normiert, also

vTv=1{displaystyle v^{T}v=1}

, so vereinfacht sich die Formel zu

H=I−2vvT.{displaystyle H=I-2vv^{T}.}

Die Spiegelungseigenschaft ersieht man daraus, dass

Hx=x−2vvTx=x−2⟨v,x⟩v=(x−⟨v,x⟩v)−⟨v,x⟩v{displaystyle Hx=x-2vv^{T}x=x-2langle v,,xrangle ,v=(x-langle v,,xrangle ,v)-langle v,,xrangle ,v}

,

wobei

⟨⋅,⋅⟩{displaystyle langle cdot ,cdot rangle }

das Standardskalarprodukt bezeichnet. Der Term

⟨v,x⟩{displaystyle langle v,,xrangle }

entspricht dabei dem Abstand des Punktes

x{displaystyle x}

zur Hyperebene

v⊥{displaystyle v^{perp }}

. Der Vektor

x{displaystyle x}

wird also in zwei zueinander orthogonale Anteile zerlegt, wobei der erste Anteil in der Hyperebene liegt und der zweite ein Vielfaches des Vektors

v{displaystyle v}

ist. Unter der Spiegelung wird der Anteil in der Ebene invariant gelassen, der Anteil in Richtung

v{displaystyle v}

, also senkrecht zur Ebene, wird „umgeklappt“, also nun abgezogen statt addiert.

Die Householder-Matrix hat folgende Eigenschaften:

Es sei ein Vektor

a{displaystyle a}

gegeben, der auf ein Vielfaches des Vektors

e{displaystyle e}

gespiegelt werden soll, das heißt, gesucht ist ein Einheitsvektor

v{displaystyle v}

, so dass mit der zugehörigen Householder-Matrix

Hv=I−2vvT{displaystyle H_{v}=I-2vv^{T}}

gilt

Hva=λe{displaystyle H_{v}a=lambda e}

. Geometrisch ist der Vektor

v{displaystyle v}

die Richtung einer der zwei Winkelhalbierenden der Geraden in Richtung

a{displaystyle a}

und in Richtung

e{displaystyle 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{displaystyle v}

, der Vektor

v{displaystyle v}

selbst ergibt sich durch Normieren dieser Richtung. Die zweite Winkelhalbierende ergibt sich, indem die Konstruktion ausgehend von

a{displaystyle a}

und

−e{displaystyle -e}

durchgeführt wird.

Der Einfachheit halber sei

e{displaystyle e}

normiert,

‖e‖=1{displaystyle |e|=1}

. Dann muss, wegen der Orthogonalität der Spiegelung,

λ=±‖a‖{displaystyle lambda =pm |a|}

gelten. Der gesuchte Spiegelungsvektor

v{displaystyle v}

ergibt sich nun durch Normieren des Differenzvektors

12(a−λe){displaystyle {tfrac {1}{2}}(a-lambda ,e)}

, also

v=a−λe‖a−λe‖{displaystyle 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

λ{displaystyle lambda }

so gewählt, dass der Nenner am größten ist, also

λ⋅⟨a,e⟩≤0{displaystyle lambda cdot langle a,,erangle leq 0}

gilt.

In der Probe ergibt sich

Hva=a−2v⟨v,a⟩=a−2(a−λe)‖a‖2−λ⟨e,a⟩‖a‖2−2λ⟨a,e⟩+λ2‖e‖2=a−2(a−λe)‖a‖2−λ⟨e,a⟩‖a‖2−2λ⟨a,e⟩+‖a‖2=λe{displaystyle {begin{aligned}H_{v}a=&a-2vlangle v,arangle \[0.5em]=&a-2,(a-lambda e),{frac {|a|^{2}-lambda langle e,arangle }{|a|^{2}-2lambda langle a,erangle +lambda ^{2}|e|^{2}}}\[0.8em]=&a-2,(a-lambda e),{frac {|a|^{2}-lambda langle e,arangle }{|a|^{2}-2lambda langle a,erangle +|a|^{2}}}\[0.5em]=&lambda e\[0.5em]end{aligned}}}

Beispiel[Bearbeiten | Quelltext bearbeiten]

Am häufigsten wird der Fall betrachtet, in dem

e=e1{displaystyle e=e_{1}}

der erste kanonische Basisvektor ist. Sei

a=(a1,a¯){displaystyle a=(a_{1},{bar {a}})}

in erste Komponente und Restvektor zerlegt. Dann gilt für die Norm

‖a‖=|a1|2+‖a¯‖2{displaystyle |a|={sqrt {|a_{1}|^{2}+|{bar {a}}|^{2}}}}

. Als Vorzeichen von

λ{displaystyle lambda }

ist das Vorzeichen von

−a1{displaystyle -a_{1}}

zu wählen, die Richtung der Spiegelung ist dann

v−λe1=a+sign⁡(a1)‖a‖e1=(sign⁡(a1)(|a1|+‖a‖),a¯){displaystyle v-lambda e_{1}=a+operatorname {sign} (a_{1}),|a|e_{1}={Bigl (}operatorname {sign} (a_{1}),(|a_{1}|+|a|),;{bar {a}}{Bigr )}}

.

Dabei ist

sign⁡(a1):={1füra1≥0,−1füra1<0.{displaystyle operatorname {sign} (a_{1}):={begin{cases}1&quad {text{für}}quad a_{1}geq 0,\-1&quad {text{für}}quad a_{1}<0.end{cases}}}

Der Vektor

v{displaystyle v}

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

‖a−λe1‖=2‖a‖(‖a‖+|a1|){displaystyle |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.

Householder-Spiegelungen können zur stabilen Berechnung von QR-Zerlegungen einer Matrix

A=QR∈Rm×n{displaystyle A=QRin mathbb {R} ^{mtimes n}}

verwendet werden, indem zunächst die erste Spalte der Matrix mit einer Spiegelung

H1{displaystyle H_{1}}

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{displaystyle H_{1}A}

mit einer Spiegelung

H2{displaystyle H_{2}}

analog, wobei die Spiegelung so konstruiert wird, dass erste Zeile und Spalte von der Transformation unberührt bleiben. Dies wird erreicht, indem die erste Komponente des Spiegelungsvektors zu Null gesetzt wird. Zur Bestimmung des dritten Schrittes geht analog nur die Hauptuntermatrix unter dem dritten Diagonalelement ein, der Spiegelungsvektor ist Null in den ersten zwei Komponenten etc. Im

i{displaystyle i}

-ten Schritt wird also die Untermatrix unter der Position

(i,i){displaystyle (i,i)}

des Produkts

Ai=Hi−1⋯H1A{displaystyle A_{i}=H_{i-1}cdots H_{1}A}

auf die gleiche Art reduziert, bis die Restmatrix

Hn⋯H2H1A=R{displaystyle H_{n}cdots H_{2}H_{1}A=R}

Dreiecksgestalt besitzt. (Im Fall

m=n{displaystyle m=n}

genügen

n−1{displaystyle n-1}

Schritte, da die letzte Spalte nicht mehr transformiert werden muss.)

Mit

QT=Hn⋯H2H1{displaystyle Q^{T}=H_{n}cdots H_{2}H_{1}}

gilt

QTA=R{displaystyle Q^{T}A=R}

, also ergibt sich die QR-Zerlegung

A=QR{displaystyle A=QR}

mit

Q=(Hn⋯H2H1)T=H1H2⋯Hn∈Rm×m,R=(R10)∈Rm×n.{displaystyle Q=(H_{n}cdots H_{2}H_{1})^{T}=H_{1}H_{2}cdots H_{n}in mathbb {R} ^{mtimes m},quad quad R={begin{pmatrix}R_{1}\0end{pmatrix}}in mathbb {R} ^{mtimes n}.}

Man beachte, dass

Q{displaystyle Q}

hier eine quadratische Matrix ist. Meist werden die Matrizen

Q{displaystyle Q}

bzw.

QT{displaystyle Q^{T}}

nicht explizit berechnet, sondern man nutzt direkt die Produktform. Dazu werden die Spiegelvektoren

vi{displaystyle v_{i}}

von

Hi=Hvi{displaystyle H_{i}=H_{v_{i}}}

im frei gewordenen Platz der Matrix

A{displaystyle A}

gespeichert.

Die Zahl der Operationen für die QR-Zerlegung einer Matrix

A=QR∈Rm×n,m≥n{displaystyle A=QRin mathbb {R} ^{mtimes n},{mgeq n}}

mit dem Householder-Verfahren beträgt:

m≫n2n2⋅mm≈n43n3{displaystyle {begin{matrix}{mgg n}&qquad &{2n^{2}cdot m}\{mapprox n}&qquad &{{4 over 3}n^{3}}end{matrix}}}

Pseudocode[Bearbeiten | Quelltext bearbeiten]

Da für die meisten Berechnungen das explizite Ausrechnen von

Q{displaystyle Q}

nicht nötig ist, reicht es, nur die Matrix

R{displaystyle R}

zu berechnen.

z{displaystyle z}

ist die linke Spalte der jeweiligen Untermatrix. Bei der unten angegebenen Funktion wird das Ergebnis direkt in

A{displaystyle A}

geschrieben, so dass nach Abarbeitung des Algorithmus das

R{displaystyle R}

in

A{displaystyle A}

steht. Die Zeile

R=A{displaystyle 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)

     R=A
     return R

Sollte

Q{displaystyle Q}

dennoch benötigt werden, lässt sich das obere Beispiel einfach erweitern: 

  function GetR(A)
    Q=eye(m) 
    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)
         Q=Q-Q*vk*(2*vk')

     R=A
     return R
  • 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, Band 1: Algebraische Probleme. 4., überarbeitete und erweiterte Auflage, Walter de Gruyter Verlag, Berlin und Boston 2020, ISBN 978-3-11-065665-7.