<<

. 14
( 31 .)



>>


H = {z ∈ IRn |wT z = 0} :
x = y + z mit wT z = 0, (y aus dem orthogonalen Koplement)
= ±w + z
’ wT x = ±wT w + wT z = ±
’ Qx = x ’ 2(wT x)w = x ’ 2±w = ±w + z ’ 2±w = ’±w + z = ’y + z




wx
T
wx
’T
Qx x



w
w =1
H
Abbildung 3.3: Spiegelung an Hyperebene.

Problem: Sei x = (x1 , . . . , xn )T = 0 vorgegeben. Bestimme w ∈ IRn , wT w = 1,
mit
Qx = ke1 , k ∈ IR.
In diesem Fall ist Q eine spezielle Spiegelung an einer Hyperebene, vgl. die nach-
folgende Abbildung:


H
x w




Qx e1

Abbildung 3.4: Spiegelung.
QR“Zerlegung 59




Analytische Berechnung von Q: (Fur Qx = ke1 )
¨

’ |k| = Qx = x , k=± x .
Qx = (I ’ 2wwT )x = x ’ 2w(wT x) = ke1
x’ke1
’ w= = c(x ’ ke1 ) (w ist Vielfaches vom Vektor x ’ ke1 )
2(wT x)
w =1 x’ke1
’ w= x’ke1


An dieser Stelle ist lediglich das Vorzeichen von k = ± x noch unbekannt. Aus
Stabilit¨tsgrunden (Vermeidung von Ausl¨schung) w¨hlen wir k in geeigneter
a o a
¨
Weise. Es ist
1/2
x ’ ke1 = (x1 ’ k)2 + x2 + . . . + x2 .
2 n


Keine Ausl¨schung tritt auf fur
o ¨

(x1 ’ k)2 = (|x1 | + x )2 .
k = ’sign(x1 ) x ,
2 2 2
’ x ’ ke1 =x + 2 x |x1 | + x = 2 x ( x + |x1 |)

Insgesamt erhalten wir

T
Q = I ’ 2wwT = I ’ 2 (x’ke1 )(x’ke1 )
x’ke1 2
= I ’ βuuT
1
k = ’sign(x1 ) x , β = x (|x1 |+ x )
« 
sign(x1 )(|x1 | + x )
(3.32)
¬ ·
x2
¬ ·
¬ ·
u := x ’ ke1 = ¬ ·
.
.
¬ ·
.
 
xn


Householder-Transformation


3.5.3 QR“Zerlegung/Verfahren von Householder
Zur Zerlegung der Matrix A bilden wir die Sequenz

A = A(1) ’ A(2) ’ . . . ’ A(n) = R,
A(j+1) = Qj A(j) , Qj orthogonal.
60 Lineare Gleichungssysteme




j-ter Schritt (j ≥ 1): Sei
« 
— ··· — — ··· — 

¬ · 
. . .
..
¬ ·
. . .
. . . .
¬ · j’1
¬ · 

¬0 ·
— — ··· —
¬ ·
(j)

A =¬ ·
(j) (j)
¬ ·
ajj · · · ajn 

¬ ·
¬ ·
. . n’j+1
. .
¬ ·
0 . . 
  
(j) (j)
anj · · · ann

(j) (j)
x := (ajj , . . . , anj )T ∈ IRn’j+1 .

1. Fall: x = 0 : A ist singular (Beweis!), setzt Qj = I
¨
2. Fall: x = 0 : Bestimme nach (3.32) die orthogonale (n ’ j + 1, n ’ j + 1)’
˜
Matrix Qj mit
« 
« (j)  1
ajj ¬·
¬0·
¬.· ¬·
˜
Qj ¬ . · = k ¬ . · ∈ IRn+1’j .
.
 ¬.·
.
(j)
anj
0
Setzen wir nun jeweils

Ij’1 0
∈ IRn—n ,
Qj = orthogonal, symmetrisch
˜
0 Qj

so erhalten wir nach n Schritten

R := A(n) = Qn’1 Qn’2 . . . Q1 A.
(3.33)

De¬nieren wir die orthogonale Matrix

Q := (Qn’1 · · · Q1 )’1 = Q1 · · · Qn’1 , (da Qj orthogonal, symmetrisch)
’ A = QR

Satz 3.40 (QR“Zerlegung). Zu jeder (n, n)-Matrix A existiert eine orthogonale
(n, n)-Matrix Q und eine rechte Dreiecksmatrix R mit

A = QR.

Ist A regul¨r, so ist R regul¨r.
a a
QR“Zerlegung 61




Bei einer regularen Matrix A bildet man zur Losung des LGS Ax = b analog zu
¨ ¨
(3.33) den Ausdruck
c := b(n) = Qn’1 · · · Q1 b

und l¨st dann das gesta¬elte LGS Rx = c.
o
≈ 2 n3 Jedoch sind keine zus¨tzlichen Permutations-
Anzahl der Operationen: a
3
matrizen notwendig.


3.5.4 Erweiterungen
Die QR-Zerlegung kann unmittelbar auf nichtquadratische (m, n)-Matrizen A
(m > n) erweitert werden. Hier bildet man eine Sequenz

A(j+1) = Qj A(j) (j ≥ 1), A(1) = A
Qj orthogonale (m, m)-Matrix.

Wegen m > n erhalt man nach n Schritten
¨

n
R
˜
A(n+1) = QA =
0 m’n
n
˜
Q = Qn . . . Q1 orthogonal,
(3.34) .
« 
r11 · · · r1n
¬ . · obere Dreiecksmatrix
..
=¬ . .·
R .

0 rnn

Praktische Durchfuhrung mit (3.32)
¨

— — }j ’ 1
A(j) = A(1) = A
,
˜
0 A(j) }m ’ j + 1
n



Ij’1 0 }j ’ 1
Qj =
˜ }m ’ j + 1
0 Qj
m

˜
Qj = I ’ βj uj uT , j = 1, . . . , n,
j
62 Lineare Gleichungssysteme




wobei nach (3.32) gilt:
(j) (j)
xj = (ajj , . . . , amj )T ∈ IRm’j+1 ,
kj = ’sign((xj )1 ) xj ,
1
βj = ,
xj (|xj1 |+ xj )
uj = xj ’ kj ej .

<<

. 14
( 31 .)



>>