Diagonalisierung/Eigenvektoren bestimmen, eine experimentelle Methode

28/10/2010 - 18:26 von Gottfried Helms | Report spam
Hi -

ich habe gerade ein altes, vergessenes Modell für die
Eigenwerte/Eigenvektor-Berechnung wiedergefunden und
würde gerne wissen, ob und wenn unter welchem Namen das
bekannt ist, um die nette Idee eventuell aufzubohren und
vielleicht ein bißchen allgemeiner zu machen.

1) -

Der erste Schritt ist, zunàchst die Eigenwerte zu finden.
Das kann man natürlich durch das charakteristische Polynom und
dessen Wurzeln lösen - aber hier will ich das einmal iterativ
machen.

Die Idee ist eine gegebene Matrix M, deren Eigensystem-Dar-
stellung gesucht ist, in die Schur-normalform zu bringen, also
eine Dreiecksform und zwar durch "orthogonale Ähnlichkeitstransformation".
Gut - letzteres ist der Terminus technikus, man kann sich
das besser so vorstellen, daß man die Matrix M mit einer
Rotationsmatrix T spaltenweise rotiert damit man auf
Dreiecksgestalt kommt. Das ist eine simple Aufgabe, z.B.
kann man eine Prozedur schreiben, die einem diese erforder-
liche Rotationsmatrix ausspuckt:

T = getrotation(M,"dreieck")

und dann ist M1 = M * T dreieckig.

"Ähnlichkeitstransformation" heißt allerdings, daß eine
Matrix rechts UND links multipliziert werden muß und zwar
unter Benutzung der inversen, z.B.

M1 = X^-1 * M * X

dann sind M1 und M àhnlich und haben dieselben Eigenwerte.
Wenn ich meine Matrix t von oben nehme, und sie entsprechend
anmultipliziere

M1 = M * T
M2 = T^-1 * M1

dann ist zwar M1 dreieckig, aber in M2 wird die Dreiecksgestalt
wieder zerstört.
Aber - M2 ist ein "bißchen mehr" dreieckig, und wenn ich das
iteriere

M1 = M
repeat
T = getrotation(M1,"dreieck")
M1 = T^-1 * M1 * T
until <pràzisions-kriterium=OK>

dann bekomme ich in M1 die Schur-Normalform als dreieckige
Ähnlichkeitsmatrix zu M.

Die Sache hat 3 Vorteile:

- die Eigenwerte tauchen in der Diagonalen auf und ich brauche
sie nur auzulesen

- T^-1 kann ich einfach "berechnen": ist einfach die transponierte
von T (weil "orthogonal")

- sie ist numerisch ziemlich gut rechenbar auch bei vielen Iterationen,
da nur sin/cos-Funktionen verwendet werden.


Sie hat zwei Eigenschaften, die man als Vorteil, aber auch als
Problem ansehen kann:

- es ist unproblematisch wenn es gleiche Eigenwerte gibt (nicht
alle Verfahren können damit umgehen, z.B. die berühmte Matrix-
power-methode, die wir hier kürzlich diskutiert haben)

- es ist auch unproblematisch, wenn es negative Eigenwerte gibt,
allerdings bekommen wir dann keine exakte Diagonale sondern
die entsprechenden Jordan-Blocks in dem eigentlich leeren
Bereich, und die entsprechenen Eintràge sind *nicht* die
Eigenwerte.

Unbekannt ist mir das generelle Konvergenzverhalten - wieviel womöglich
tausende Iterationen brauche ich, wenn ich nur 20x20-Matrizen behandeln
will?

Gut, nehmen wir einmal an, wir haben die Schurnormalform erreicht
und die Eigenwerte stehen in der Diagonale.



2) Danach sind die Eigenvektoren zu bestimmen. Hier hatte ich mir in
meiner jugendlichen Frische damals eine abenteuerliche Methode
ausgedacht, aber -u.a.- anscheinend nicht bemerkt, daß die Eigenwerte dann
unterschiedlich sein müssen (möglicherweise gibt's weitere Probleme,
die ich im Moment noch nicht sehe)

Ich erzeuge eine quadratische Vandermondematrix VD, die die Eigenwerte
und deren Potenzen enthàlt. Also, sind d,e,f die ersten drei Eigenwerte,
h der letzte und deren Anzahl n, sieht VD so aus:

[ 1 ,d, d^2, d^3, ..., d^(n-1)]
[ 1 ,e, e^2, e^3, ..., e^(n-1)]
VD = [ 1 ,f, f^2, f^3, ..., f^(n-1)]
...
[ 1, h, h^2, h^3, h^(n-1)]

Dann verwende ich die entsprechenden Potenzen von M und zwar
trage ich deren 1. Spalten in eine entsprechende quadratische
Listenmatrix L ein:

(M^0) [*,1] -> L[*,1] // von Spalte 1 in M^0 nach Spalte 1 in L
(M^1) [*,1] -> L[*,2] // von Spalte 1 in M^1 nach Spalte 2 in L
...
(M^(n-1)) [*,1] -> L[*,n] // usw.

Dann kann gemàß

W = L * VD^-1

in W die komplette Matrix der Eigenvektoren auf einen Schlag
berechnet werden und wir haben die gesuchte Eigenwertzerlegung:

M = W * diag(d,e,f,...,h)*W^-1

Man sieht sofort, daß VD invertierbar sein muß, also müssen
alle Eigenwerte unterschiedlich sein.



Um dies jetzt auf mögliche weitere, nicht ganz offensichtliche,
Probleme hin abzuklopfen (z.B. ist Konvergenz garantiert?) würde ich
mich gerne schlauer machen falls diese Methode irgend einen
bekannten Namen hat unter dem ich suchen/nachlesen kann
(oder falls nicht, vielleicht hier in der NG ein paar geeignete
Kommentare zu erhaschen... :-) )

Weiß jemand was?
Gruß -

Gottfried
 

Lesen sie die antworten

#1 Ulrich Lange
28/10/2010 - 18:42 | Warnen spam
Gottfried Helms schrieb:
Hi -

ich habe gerade ein altes, vergessenes Modell für die
Eigenwerte/Eigenvektor-Berechnung wiedergefunden und
würde gerne wissen, ob und wenn unter welchem Namen das
bekannt ist, um die nette Idee eventuell aufzubohren und
vielleicht ein bißchen allgemeiner zu machen.

[...]

Um dies jetzt auf mögliche weitere, nicht ganz offensichtliche,
Probleme hin abzuklopfen (z.B. ist Konvergenz garantiert?) würde ich
mich gerne schlauer machen falls diese Methode irgend einen
bekannten Namen hat unter dem ich suchen/nachlesen kann
(oder falls nicht, vielleicht hier in der NG ein paar geeignete
Kommentare zu erhaschen... :-) )



Hallo Gottfried,

wenn ich nicht irgendwas komplett falsch verstehe, entspricht Dein
Verfahren doch der klassischen QR-Iteration, oder?

http://de.wikipedia.org/wiki/QR-Algorithmus

Gruß, Ulrich Lange

(ulrich punkt lange bindestrich mainz at t-online punkt de)

Ähnliche fragen