Singulärwert-Zerlegung Die Singulärwerte von A ∈ R mxn,m ≥ n

Singulärwert-Zerlegung
Die Singulärwerte von A ∈ Rmxn , m ≥ n sollen berechnet werden.
Zunächst wird A auf Bidiagonalgestalt transformiert:


dn1 sdn2
O


dn2 . . .


∈ Rnxn
B=

.
. . sdnn 

O
dnn
Idee des Algorithmus:
führe den QR-Algorithmus durch für B T B, ohne B T B explizit auszurechen.
1. Berechne den shift-Parameter µ gemäß Wilkinson, also EW von
2
dnn−1 + sdn2n−1 dnn−1sdnn−1
,
dnn−1sdnn−1
dn2n + sdn2n
der am nächsten zu dn2n + sdn2n liegt
2. Berechne (implizit) B T B − µId = QR, B̃ T B̃ := RQ + µId mit
Givensrotationen:
sei V1 Givensrotation mit (V1(B T B − µId))e1 = a e1 , berechne


∗ ∗
O

+ ∗ ∗




.
.
.
BV1 =  0 0 ∗


 . .
.
.. ∗ 
 .. ..
0 0
O ∗
eliminiere das Element + mit Givensrotation U1


∗ ∗ +
O


∗ ∗




.
∗ ..
U1BV1 = 



.
.. ∗ 

O
∗
etc. bis man wieder Bidiagonalgestalt hat.
Dabei soll blockweise in B T B vorgegangen werden: ein Superdiagonalelement wird durch Null ersetzt, falls |bi,i+1| < 10−11(|bii| + |bi+1,i+1|).
Dann wird ein Block gebildet, der nur Superdiagonalelemente ungleich
Null enthält. Falls Diagonalelemente in dem Block gleich Null sind,
kann man mit Givensrotationen folgende Gestalt erreichen:




∗ ∗
O
∗ ∗
O




∗ ∗
∗ ∗








0
∗
0
0
∗

 →





∗
∗
∗
∗








∗ ∗
∗ ∗
O
∗ ∗
O
∗ ∗




∗ ∗
O
∗ ∗
O




∗ ∗
∗ ∗








0
0
0
∗
0
 →

→




∗ ∗
∗ ∗








∗ ∗
∗ ∗
O
∗ ∗
O
∗ ∗
Andernfalls wird die (implizite) QR-Transformation in 2. angwendet.
Dies wird solange iteriert, bis die Superdiagonale keine von Null verschiedenen Einträge mehr enthält.
=⇒ Singulärwerte von A stehen (bis auf Vorzeichen) auf der Diagonalen von B

Download Report