Wikipedia · einfach zusammengefasst · Stand
Householdertransformation
In der Mathematik beschreibt die Householdertransformation die Spiegelung eines Vektors an einer Hyperebene durch Null im euklidischen Raum.
Inhalt5 Abschnitte
Grundidee und Matrixform
Eine Householdertransformation ist die Spiegelung eines Vektors an einer Hyperebene durch den Nullpunkt im euklidischen Raum. Im dreidimensionalen Raum entspricht sie einer Spiegelung an einer Ebene durch den Ursprung. Ihre Matrixdarstellung heißt Householder-Matrix. Sie ist besonders wichtig für die numerische Mathematik: Durch orthogonale Transformationen können Spaltenvektoren gezielt auf ein Vielfaches des ersten Einheitsvektors abgebildet werden, etwa bei QR-Verfahren und QR-Zerlegungen.
Eine Spiegel-Hyperebene wird durch einen Normalenvektor v beschrieben, der senkrecht auf ihr steht. Für v als Spaltenvektor und die Einheitsmatrix I lautet die Householder-Matrix
H = I - (2/(v^T v)) vv^T.
Dabei ist v^T der transponierte Zeilenvektor, v^T v das Skalarprodukt von v mit sich selbst und vv^T das dyadische Produkt. Die Matrix (1/(v^T v))vv^T ist die Orthogonalprojektion auf die Richtung von v. Ist v normiert, also v^T v = 1, vereinfacht sich die Formel zu H = I - 2vv^T.
Wirkung und wichtige Eigenschaften
Für einen Vektor x gilt bei normiertem v:
Hx = x - 2⟨v,x⟩v = (x - ⟨v,x⟩v) - ⟨v,x⟩v.
Das Standardskalarprodukt ⟨v,x⟩ beschreibt den Abstand von x zur Hyperebene v^⊥, die orthogonal zu v ist. Zuerst wird x um ⟨v,x⟩v auf diese Ebene projiziert; danach wird es um denselben Betrag auf die andere Seite verschoben. Der Anteil des Vektors innerhalb der Ebene bleibt unverändert, während der senkrechte Anteil in Richtung v sein Vorzeichen wechselt.
Die Householder-Matrix ist symmetrisch, also H = H^T, und orthogonal, also H^T H = I. Außerdem ist sie involutorisch: H^2 = I; eine zweimalige Spiegelung liefert somit wieder den ursprünglichen Vektor. Sie besitzt den einfachen Eigenwert −1 mit Eigenvektor v. Der Eigenwert 1 hat die Vielfachheit n−1; sein Eigenraum ist die Spiegelebene. Matrix-Vektor-Multiplikationen mit H sind schnell berechenbar.
Eine Spiegelung gezielt konstruieren
Soll ein Vektor a auf ein Vielfaches eines Einheitsvektors e gespiegelt werden, wird ein normierter Spiegelungsvektor v gesucht, so dass H_v a = λe mit H_v = I - 2vv^T gilt. Geometrisch zeigt v in Richtung einer der beiden Winkelhalbierenden zwischen den Geraden in Richtung a und e.
Da die Spiegelung orthogonal ist und deshalb die Länge erhält, muss bei ||e|| = 1 gelten: λ = ±||a||. Der Spiegelungsvektor wird aus dem normierten Differenzvektor bestimmt:
v = (a - λe)/||a - λe||.
Beide Vorzeichen von λ führen zum gewünschten Ergebnis, sofern der Nenner nicht null ist. Für numerische Stabilität wird das Vorzeichen so gewählt, dass der Nenner möglichst groß wird. Dafür gilt λ · ⟨a,e⟩ ≤ 0. Dann ergibt die Rechnung H_v a = λe.
Der häufigste Sonderfall ist e = e_1, der erste kanonische Basisvektor. Für a = (a_1, ā) ist ||a|| = √(|a_1|^2 + ||ā||^2). λ erhält das Vorzeichen von −a_1. Die Spiegelrichtung lautet dann
a - λe_1 = a + sign(a_1)||a||e_1 = (sign(a_1)(|a_1| + ||a||), ā).
Dabei ist sign(a_1) = 1 für a_1 ≥ 0 und −1 für a_1 < 0. Die Norm dieser Richtung kann mit bereits berechneten Größen als √(2||a||(||a|| + |a_1|)) geschrieben werden.
QR-Zerlegung mit Spiegelungen
Householder-Spiegelungen ermöglichen die stabile Berechnung einer QR-Zerlegung A = QR für A ∈ ℝ^(m×n). Zuerst wird die erste Spalte von A durch H_1 auf ein Vielfaches des ersten Einheitsvektors gespiegelt. Danach wird H_2 so gewählt, dass die erste Zeile und erste Spalte unverändert bleiben; dazu ist die erste Komponente seines Spiegelungsvektors null. Entsprechend werden in den folgenden Schritten immer nur die noch verbleibenden Hauptuntermatrizen unterhalb der Diagonale bearbeitet.
Nach den Spiegelungen entsteht eine Matrix R mit Dreiecksgestalt:
H_n ··· H_2H_1A = R.
Mit Q^T = H_n ··· H_2H_1 folgt Q^T A = R und damit A = QR. Dabei ist
Q = H_1H_2···H_n ∈ ℝ^(m×m), R = (R_1; 0) ∈ ℝ^(m×n).
Q ist hier quadratisch. In der Praxis werden Q und Q^T meist nicht vollständig ausgerechnet. Stattdessen nutzt man die Produktform und speichert die Spiegelvektoren v_i der Matrizen H_i = H_{v_i} im frei gewordenen Platz von A.
Für m ≥ n beträgt der Rechenaufwand bei m ≫ n etwa 2n^2m Operationen, bei m ≈ n etwa (4/3)n^3. Für m = n reichen n−1 Schritte, weil die letzte Spalte nicht mehr transformiert werden muss.
Algorithmus und Implementierung
Zur Berechnung von R wird in jedem Schritt k die linke Spalte z der aktuellen Untermatrix verwendet. Aus z wird ein Vektor u_k gebildet, indem seine erste Komponente um sign(z(1))·norm(z) verändert wird. Nach der Normierung wird u_k an den Positionen k bis m in einen ansonsten nullen Vektor v_k eingesetzt. Die Matrix wird dann aktualisiert durch
A = A - (2v_k)(v_k^T A).
Nach allen Schritten enthält A die Matrix R. Soll zusätzlich Q berechnet werden, beginnt man mit Q = eye(m) und aktualisiert in jedem Schritt
Q = Q - Qv_k(2v_k^T).
Das C++-Beispiel setzt diese Idee um: Es erzeugt die Householder-Matrix I - 2vv^T, bestimmt nacheinander die Spiegelungen, berechnet daraus Q und R und prüft anschließend mit dem Produkt QR, ob es mit der ursprünglichen Matrix A übereinstimmt. Die Prüfung verwendet die L2-Norm ||A - ACheck||^2 und akzeptiert die Zerlegung bei einem Wert kleiner als 1e-12.