| |
- Um einen Teil der Eigenwerte einer grossen symmetrischen Matrix A zu bestimmen, kann
man das Lanczos-Verfahren verwenden.
- Die Idee des Verfahrens ist einfach: Man bildet wie beim von-Mises-Verfahren eine Folge
Akx0, k=0,...,i, definiert hier aber einen Unterraum des Rn
als ihre lineare Hülle, bildet dort eine Orthogonalbasis Qi und benutzt die Eigenwerte der
Matrix QiTAQi, also die der Projektion von A
auf den Unterraum, als Eigenwertnäherungen für A.
- Dies kann man geschickt so organisieren, dass Iteration und Orthogonalisierung simultan laufen:
x0 sei geeignet gewählt mit Länge 1.
Q(.,1) = x0
d1 = Q(.,1)T *A* Q(.,1)
r1 = A*Q(.,1)- d1 * Q(,.1)
Iteriere i=2,3,... solange ||ri-1|| > 0 :
ei-1 = ||ri-1||
Q(.,i)= ri-1/ ||ri-1||
v = A*Q(.,i)
di = Q(,.1)T * v
ri = v - di* Q(.,i) -ei-1 * Q(.,i-1)
- Die Matrix QiT * A * Qi ergibt sich als
die Tridiagonalmatrix Ti mit den Einträgen ej-1, dj, ej
mit j=1,...,i
- Das Eigenwertproblem dieser Tridiagonalmatrix ist effizient und genau lösbar.
- Gewisse der Eigenwerte der Tridiagonalmatrix konvergieren rasch gegen solche von A
und die zugehörigen Eigenvektoren sind die entsprechenden Spalten der Matrix
Y(.,j=1,...,i) = Q(.,j=1,...,i)*Vi
wo Vi die Eigenvektormatrix der Tridiagonalmatrix ist.
- Welche Eigenwerte das sind, kann man auf verschiedene Weise erkennen. Wir benutzen hier
den Test von B.Parlett: akzeptiere lambdaj, wenn
|ei*V(i,j)| <= epsaccept*Frobeniusnorm(Ti)
- Eine Fehlerabschätzung erhält man aus der Aussage
||A*Y(.,j)-lambdaj*Y(.,j)||/||A*Y(.,j)|| >= |lambdaj - mu|/|mu|
für einen exakten Eigenwert mu von A.
- Das Verfahren bricht ab, sobald ein ej null wird. Dies hängt
von der Eigenwertverteilung von A und vom Startvektor ab.
z.B. darf A keine mehrfachen Eigenwerte besitzen und x0
sollte Komponenten in allen Eigenrichtungen haben.
- Leider verliert die unter Rundungsfehlereinfluss berechnete Matrix Q
schnell ihre Spaltenorthonormiertheit. Wenn man nichts dagegen unternimmt,
hat das zwar nicht den Zusammenbruch des Verfahrens zur Folge, aber es
können merkwürdige Effekte auftreten, z.B. tritt ein einfacher
Eigenwert von A als (fast) mehrfacher in Ti auf.
Deshalb ergänzt man das Verfahren durch Reorthogonalisierungstechniken:
Bei der vollständigen Reorthogonalisierung wird im Schritt i die i-te Spalte von
Q bezüglich aller vorherigen nach Gram-Schmidt orthogonalisiert,
bei der sogenannten selektiven Reorthogonalisierung werden dazu nur die
alten Spalten benutzt, die zu akzeptierten Eigenwerten gehören.
|