Householder-Transformation
1958
Eine Matrix kann durch Multiplikation mit einer Matrix Q
in eine Dreiecksmatrix überführt werden.
d11 d12 d13
a11 a12 a13
0 d22 d23 = Q a21 a22 a23 = Q · A
0 0 d33
a31 a32 a33
Dies erfolgt durch wiederholte Spiegelungen.
Zunächst wird eine Spiegelmatrix Q1 ermittelt, die Folgendes leistet:
b11 b12 b13
a11 a12 a13
0 b22 b23 = Q1 a21 a22 a23
0 b32 b33
a31 a32 a33
Q1 spiegelt die 1. Spalte (als Ortsvektor oder Punkt) von A auf einen Punkt,
der auf der x-Achse liegt.
1
Spiegelung
Ein (beliebiger) Punkt P wird an einer Ursprungsebene E gespiegelt, deren Normalenvektor
gegeben ist. Für diese orthogonale Projektion ist die Abbildungsmatrix gesucht.
z
×P
y
S×
x
E:
~n ~x = 0
◦
−→
g : ~x = OP + λ ~n◦
×
P′
Schnitt:
−→
~n◦ (OP + λ ~n◦ ) = 0
−→
~n◦ OP + λ = 0
−→
λ = −~n◦ OP
−→
=⇒
−→
Abstand d(P, E) = λ wegen |~n◦ | = 1
−→
OP ′ = OP − 2(~n◦ OP ) ~n◦
Der Übergang zu Koordinaten ergibt für ~n (durch leichtes Nachrechnen):
−→
OP ′ =
(
1
0
0
0
1
0
−→
−→
kurz: OP ′ = Q OP
0
n1 n1
2
0 −
n2 n1
~n 2
1
n3 n1
|
n1 n2 n1 n3
−→
n2 n2 n2 n3
OP
n3 n2 n3 n3
{z
}
T
= ~n ~n dyadisches Produkt, sym.
)
y
P
Q heißt Householder-Matrix, wenn P in der
angegebenen Weise auf die x-Achse gespiegelt wird.
−→
−→
Mit | OP | = | OP ′ | ist die
Spiegelachse (-ebene) festgelegt.
P′
~n◦
x
2
Householder-Transformation
1
1
2
0
A = 2 −3
= [a1 , a2 , a3 ]
2
4 −4
A wird in eine Dreiecksmatrix (rechts oben) zerlegt. Wir beginnen mit der 1. Spalte.
1.
2.
n = a1 + α|a1 |e
1
0
Q1 =
0
(α Vorzeichen von a11 )
0
n1 n1 n1 n2 n1 n3
2
0
− n2 n2 n1 n2 n2 n2 n3
1
n3 n1 n3 n2 n3 n3
0
1
0
3.
1
0
Q1 =
0
0
1
0
"
#
2.
16
0
2
0 − 8
24
8
1
−3 −1
2
0
Q1 ·A = 0 −4
0
3 −4
Das Ganze noch einmal mit:
1.
n = a1 + α|a1 |e
Q∗ =
"
1
0
0
1
1
1
4
n = 2 + 1 · 3 · 0 = 2
2
0
2
#
−4
0
3 −4
"
n1 n1 n1 n2
n2 n1 n2 n2
−4
1
−9
n=
+ (−1) · 5 ·
=
3
0
3
#
Q∗ =
3.
4.
Q2 =
1
5
5
0
0 −4
0
3
0
3
4
5
0
1 0 −4
Q2 Q1 A = 5
0
3
8
−1 −2 −2
1
4
2 −1
= 3 −2
4
−2 −1
2
= [a1 , a2 ]
(α Vorzeichen von a11 )
2
− 2
n
8
4
4
"
1
0
0
1
#
"
#
"
9
−3
−4
− 15
= 15
−3
1
3
0 −3 −1
2
−15 −5 10
1
3
0
0 −4
= 5 0 25 −12 = R
4
0
3 −4
0
0 −16
3
3
4
#
QR-Zerlegung
Q2 Q1 A = R
=⇒
A = QT
QT R
| 1{z 2}
Q
T
beachte Q−1
i = Qi ,
wegen der Spiegelung gilt: Qi · Qi = I
Gleichungssystem lösen
Ax = b
QRx = b
Rx = QT b
Auf der linken Seite kann von unten nach oben gerechnet werden.
Alternativ für händische Rechnung:
Ax = b
| Q1
Q1 Ax = Q1 b
| Q2
Q2 Q1 Ax = Q2 Q1 b
···
Wenn auf der linken Seite eine Dreiecksmatrix entstanden ist,
kann von unten nach oben gerechnet werden.
Für verschiedene b′ s auf der rechten Seite (z. B. Einheitsvektoren für inverse Matrix)
können auf diese Weise mehrere Gleichungssysteme gleichzeitig bearbeitet werden.
c Roolfs
4
© Copyright 2024 ExpyDoc
