Verwendung der Singulärwertzerlegung zur Berechnung von Eigenwerten und Eigenvektoren symmetrischer Matrizen

Ich weiß, dass bei einer symmetrischen Matrix die Singulärwerte gleich den Absolutwerten der Eigenwerte sind. Wenn die Matrix auch positiv semidefinit ist, sind die Eigenzerlegung und die Singulärwertzerlegung identisch. Meine Frage betrifft symmetrische Matrizen, die nicht positiv semidefinit sind, also mindestens einen negativen Eigenwert haben.

Ich habe mit zufällig generierten symmetrischen Matrizen experimentiert und festgestellt, dass bei einem positiven Eigenwert der Eigenvektor nach geeigneter Vorzeichenwahl sowohl mit dem linken als auch mit dem rechten singulären Vektor identisch ist. Bei einem negativen Eigenwert ist der Eigenvektor entweder gleich dem linken oder rechten singulären Vektor und gleich dem verbleibenden singulären Vektor multipliziert mit -1. Ein Gegenbeispiel konnte ich nicht finden.

Wenn diese Beobachtung für alle symmetrischen Matrizen gilt, kann eine Eigenwertzerlegung für solche Matrizen leicht aus einer Singularvektorzerlegung abgeleitet werden, indem die Vorzeichen des Singularwerts und eines der Singularvektoren vertauscht werden, wenn sich die Singularvektoren in den Vorzeichen unterscheiden.

Ich ging zunächst davon aus, dass dies eine bekannte Tatsache sei. Ich habe es jedoch in den einschlägigen Wikipedia-Artikeln oder auf anderen Websites nicht klar angegeben gefunden. Außerdem habe ich die SVD nirgendwo als Eigenwertalgorithmus aufgeführt gesehen, während andere Algorithmen, die auf symmetrische Matrizen beschränkt sind, dies sind.

Ich gebe unten ein Beispiel, das von einem von mir geschriebenen Programm generiert wurde, das die zyklische Jacobi-Methode aus der GNU Scientific-Bibliothek zur Berechnung von Eigenwerten und Eigenvektoren und eine Funktion von mymathlib.com zur Berechnung der SVD verwendet. Eigenwerte und Singulärwerte wurden nach absteigendem Betrag sortiert. Vorzeichen wurden so gewählt, dass die erste Komponente der Eigenvektoren und linken singulären Vektoren positiv war.

Meine Fragen sind, ist mein vorgeschlagener Algorithmus zur Berechnung von Eigenwerten und Eigenvektoren für alle symmetrischen Matrizen gültig? Wenn ja, gibt es einen Grund, für solche Berechnungen andere Methoden, wie z. B. die zyklische Jacobi-Methode, der SVD vorzuziehen?

Matrix
------
69 47 -1 512
47 1 32 43
-1 32 27 40
512 43 40 88

Eigenvalues
-----------
599.067
-435.442
43.6227
-22.2481

Eigenvectors
------------
0.694513 0.711505 0.105479 0.0169263
0.10848 -0.0122921 -0.492832 -0.863248
0.0544405 0.0629158 -0.862857 0.498554
0.709169 -0.699751 0.0383271 0.0772006

Singular values
---------------
599.067
435.442
43.6227
22.2481

Left singular vectors
---------------------
0.694513 0.711505 0.105479 0.0169263
0.10848 -0.0122921 -0.492832 -0.863248
0.0544405 0.0629158 -0.862857 0.498554
0.709169 -0.699751 0.0383271 0.0772006

Right singular vectors
----------------------
0.694513 -0.711505 0.105479 -0.0169263
0.10848 0.0122921 -0.492832 0.863248
0.0544405 -0.0629158 -0.862857 -0.498554
0.709169 0.699751 0.0383271 -0.0772006

Aktualisieren

Qiaochu Yuan antwortete, dass meine Beobachtung für eine symmetrische Matrix mit unterschiedlichen Singulärwerten richtig sei, dh dass Eigenwerte und Eigenvektoren aus der Singulärwertzerlegung abgeleitet werden könnten. Im Fall einer symmetrischen Matrix mit singulären Werten, die sich wiederholen, würde ein SVD-Algorithmus jedoch nicht garantiert eine korrekte Lösung generieren, da die SVD Multiplizitäten aufweisen könnte, die unterschiedlichen Eigenwerten (mit unterschiedlichem Vorzeichen) entsprechen.

Ich brauchte einige Zeit, um die Antwort vollständig zu verstehen (zuerst musste ich lernen, dass Eigenvektoren – und singuläre Vektoren – in Matrizen mit wiederholten Eigenwerten nicht eindeutig sind). Ich habe dann numerische Experimente durchgeführt und herausgefunden, dass Gegenbeispiele zu meiner Beobachtung leicht als QDQ T erzeugt werden können , wobei Q eine orthogonale Matrix ist, die durch QR-Zerlegung einer zufälligen Matrix erzeugt wird, und D eine geeignete Diagonalmatrix mit einem Paar von Einträgen ist die sich nur im Vorzeichen unterscheiden.

Antworten (1)

Wenn alle singulären Werte verschieden sind (was für Zufallsmatrizen mit hoher Wahrscheinlichkeit gilt), ist dies wahr und leicht zu beweisen. Schreiben A = U D v T . Dann A T = v D U T = A = U D v T . Bei unterschiedlichen singulären Werten sind die singulären Vektoren bis zur Skalierung eindeutig; daraus folgt, dass wenn eine Matrix A symmetrisch ist, dann sind es sein linker und sein rechter singulärer Vektor ± 1 Mal miteinander. Im + 1 Fall sind sie Eigenvektoren mit Eigenwert der Singularwert, und im − 1 Fall sind sie Eigenvektoren mit Eigenwert das Negative des Singulärwerts.

Wenn die Singularwerte nicht eindeutig sind, gibt es mehr Mehrdeutigkeit bei der Auswahl einer SVD. Was in diesem Fall zutrifft, ist, dass es immer möglich ist, eine SVD zu finden, bei der die singulären Vektoren Eigenvektoren sind, aber es gibt keinen Grund, warum ein SVD-Algorithmus garantiert eine solche SVD ausspuckt. Das Problem ist, dass die singulären Werte höhere Multiplizitäten haben können als die Eigenwerte, zB könnten die Eigenwerte sein ± 1 und dann sind die Singularwerte alle 1 .

Danke schön! Ich konstruierte neue Matrizen ED E' aus den Eigenvektoren E aus meinem obigen Beispiel und neue Diagonalmatrizen D mit entweder vier verschiedenen oder zwei verschiedenen und zwei gleichen Elementen. Bei 4 unterschiedlichen Elementen konvergierten die Algorithmen zum gleichen Ergebnis. Mit 2 eindeutigen und 2 gleichen Elementen fanden beide Algorithmen alle 4 Eigenwerte und konvergierten zu den gleichen e/s-Vektoren für eindeutige Elemente, ergaben jedoch leicht unterschiedliche e/s-Vektoren für wiederholte Elemente. Können diese leicht unterschiedlichen Diagonalisierungen unterschiedliche Darstellungen derselben Matrix sein? Oder schwierigere Konvergenz bei wiederholten e-Werten?
Ergänzung zum vorherigen Kommentar: Auch für wiederholte Eigenwerte waren linke und rechte singuläre Vektoren innerhalb der Maschinengenauigkeit gleich, wenn die Eigenwerte positiv waren, und unterschieden sich nur durch das Vorzeichen für negative Eigenwerte.
@vibo: Ich weiß nichts über die rechnerischen Aspekte bestimmter Algorithmen (insbesondere weiß ich nicht, wie sie Bindungen lösen, wenn es eine Vielzahl gibt), aber was passiert, wenn Sie einstecken A = [ − 1 0 0 1 ] zu einem SVD-Algorithmus?
Es gibt S= zurück [ 1 1 ] U= [ 1 0 0 − 1 ] V= [ − 1 0 0 − 1 ] wobei U die linken und V die rechten singulären Vektoren sind. Soweit ich den Code untersuchen kann, kümmert sich der Algorithmus nicht um Bindungen. Elemente außerhalb der Diagonale werden in einem zweistufigen Prozess entfernt, während sichergestellt wird, dass die Elemente auf der Diagonale nicht negativ sind. Warum sollte sich der Algorithmus um Bindungen kümmern müssen?
Verwendung der Singulärwertzerlegung zur Berechnung von Eigenwerten und Eigenvektoren symmetrischer Matrizen
AntwortenHierDatenschutz-Bestimmungen1y, 1v