Singulärwertzerlegung mit QR-Algorithmus

Question

kann mir jemand erklären, wie genau man die Rechenschritte macht, bei der Singulärwertzerlegung.

Also ich habe das "Prinzip" verstanden, aber hab Schwierigkeiten beim rechnen.

Man macht ja folgendes:

Man reduziert die zu zerlegende Matrix A mit den Orthogonalmatrizen P,Q auf eine obere Bidiagonalgestalt.

Also: PAQ = ( B 0)^T

Jetzt wendet man auf diese Biadiagonalgestalt abwechselnd Givensrotationen von links und rechts an.

Mit den benutzen Givensrotationen erhalte ich dann:

GBG^T= ∑

Meine Fragen nun:

Wie bestimme ich P und Q, also wie wähle ich den Vektor v der Householder Matrix?

Wenn ich die Givensrotation von rechts nehme, um ein Element über der Diagonalen auszulöschen, funktioniert das dann ganz normal wie bei den Elementen unter der diagonalen?

Sind P^T und Q^T dann meine Matrizen für die gilt:

P∑Q^T = A ?

Wäre am hilfreichsten,wenn das vielleicht mal an einem Beispiel  vorgerechnet wird:

A =

1 1

√2 0

0 √2

Hierzu habe ich bereits die Zerlegung auf eine andere Weise berechnet.

Comments

Schau mal hier

https://www.youtube.com/watch?v=WsQZJy6orug

vielleicht hilft das.

---

Danke.  Das hilft mir leider nicht.  Wie man die qr Zerlegung einer Matrix bestimmt weiß ich Und kann ich auch anwenden.  Aber in wiefern ist mit diesem Verfahren die singulärwerte berechne weiß ich leider nicht und ist in dem Video ja auch nicht beschrieben

Answer 1

Hi,
zuerst wird die Matrix \( A = \left( a^{(1)}, a^{(2)} \right) \) auf Bidiagonalgestalt mittels Householder Transformationen gebracht. \( a^{(i)} \) ist der \(i-te \) Spaltenvektor von \( A \) Die Transformation sieht so aus
$$ w^{(1)} =  a^{(1)} + \text{sgn} \left(a^{(i)} \right) \left| a^{(1)} \right| e_1  $$ Daraus ergibt sich dann
$$ v^{(1)} = \frac{w^{(1)}}{w^{(1)}_1}  $$ Die Householdertransformation lautet dann
$$ H_1 = I - 2 \frac{v_1 v_1^t}{v_1^t v_1}  $$ Daraus folgt dann
$$ H_1 A = \begin{pmatrix}  -\sqrt{3} & -\frac{\sqrt{3}}{3} \\ 0 & -\frac{\sqrt{6}}{3} \\ 0 & \sqrt{2} \end{pmatrix} $$
Jetzt die gleiche Prozedur auf den Vektor \(  \begin{pmatrix} -\frac{\sqrt{6}}{3} \\ \sqrt{2} \end{pmatrix} \) anwenden ergibt dann eine zweite Transformationsmatrix \( H_2' \)
Diese Matrix ergibt dann die zweite Householdertransformationsmatrix \( H_2 = \begin{pmatrix}  1 & 0 \\ 0 & H_2' \end{pmatrix} \)
Daraus folgt jetzt \( H_2 H_1 A = \begin{pmatrix}  B \\ 0 \end{pmatrix}  \) mit \( B = \begin{pmatrix}  -\sqrt{3} & \frac{\sqrt{3}}{3} \\ 0 & \frac{2}{3}\sqrt{6} \end{pmatrix}  \)

Für die Matrix \( B^t B \) werden die Eigenwerte \( \lambda \) und Eigenvektoren ausgerechnet. Sei \( V \) die Matrix die die Eigenvektoren als Spalten enthält. Zusätzlich werden noch die Vektoren \( u^{(i)} = \frac{1}{\sqrt{\lambda_i}} A v^{(i)} \) ausgerechnet.
Damit ergibt sich dann
$$ U^t B V = \Sigma = \begin{pmatrix}  2 & 0 \\ 0 & \sqrt{2} \end{pmatrix}  $$

Zum Schluss ergibt sich
$$ H_1^t H_2^t \begin{pmatrix} U \Sigma V^t \\ 0 \end{pmatrix} = A $$oder

$$  \begin{pmatrix} U^t & 0 \end{pmatrix} H_2 H_1 A V = \Sigma $$

Comments

Hab zum Schluss noch ein paar Korrekturen eingefügt.

---

Danke erstmal.

Habe noch einige Fragen:

Daraus ergibt sich dann

v(1)=w(1)w(1)1
"ddasdasdgfa






sdasdasd

WD

Was meinst du damit?

Wir haben v direkt so definiert,wie du w definiert hast und damit dann die jeweilig Householdermatrix berechnet.

(1. ) Du bestimmst sigma durch die Eigenwerte von B^TB also über die Singulärwerte, so hätte ich das auch gemacht, nur dass ich die Singulärwerte von A^TB bestimmt hätte und dann mit Matrix der EV die Matrix und selbigen Formel für u_i die Matrix U bestimmt.

Außerdem in der Beschreibung,die ich dem Skript entnommen habe(siehe Frage) steht, dass man von beiden Seiten mit Househouldermatrizen multipliziert.

Sigma soll sich laut beschreibung durch Verwenden von Givensrotationen von beiden Seiten berechnen lassen. Das ist ja das,was ich unter anderem nicht verstehe.

Die "normale" Art die Singulärzerlegung zu bestimmen kenne ich bereits wie in (1.) geschildert.

---

Hi, den Schritt $$ v^{(1)} = \frac{w^{(1)}}{w^{(1)}_1}  $$ muss man nicht machen kann man aber. Ich habe ihn hierher

www3.math.tu-berlin.de/Vorlesungen/WS11/NumMath1/uebung/householder.pdf

Das beidseitige multiplizieren mit den Householder Matrizen ist nur nötig, wenn man in den Spalten und den Zeilen Nullen erzeugen will. Bei dem einfachen Beispiel hier muss man nur Nullen in den Spalten erzeugen, also nur von links multiplizieren.

Durch eine Givensrotation kann man die Matrix \( B \) nicht auf Diagonalform bringen, weil dann folgende Gleichungen erfüllt sein müssten:

$$ \begin{pmatrix}  x & y \\ 0 & z \end{pmatrix}\begin{pmatrix}  c & s \\ -s & c \end{pmatrix} =  \begin{pmatrix}  xc-ys & xs+yc \\ -zs & zc \end{pmatrix}  $$ und das müsste eine Diagonalmatrix sein. \( c \) und \( s \) bedeuten dabei jeweils \( \sin(\varphi) \) und \( \cos(\varphi) \)
Das würde aber bedeuten \( \sin(\varphi) = 0 \) was zur Folge hätte, da ja auch \( c^2 + s^2 =1 \) gilt, dass \( \cos(\varphi) = 1 \) gelten muss. Also ist das Element oben rechts in der Matrix \( y \ne 0 \) was ja eigentlich nicht sein darf, wenn man eine Diagonalmatrix erzeugen möchte.