Unterraumiteration

Die Unterraumiteration dient in der numerischen Mathematik der Approximation von Eigenwerten einer quadratischen Matrix und der dazugehörigen Eigenvektoren. Sie ist eine Verallgemeinerung der einfachen Vektoriteration (Von-Mises-Iteration) und benötigt wie diese die Matrix nur in Form von Matrix-Vektor-Produkten , ist also besonders geeignet für dünnbesetzte Matrizen. Im Unterschied zur Vektoriteration kann man damit aber mehrere Eigenwerte mit den größten Beträgen bestimmen. Tatsächlich lässt sich über die Unterraum-Iteration auch das Standardverfahren zur Berechnung aller Eigenwerte herleiten, der QR-Algorithmus.

MotivationBearbeiten

Der Artikel Potenzmethode zeigt, dass sich ein genügend allgemeiner Startvektor   bei  -facher Anwendung der Matrix wie in   langsam in die Richtung eines Eigenvektors   zum betragsgrößten Eigenwert   dreht. Um ein zu großes Anwachsen der Werte zu verhindern, wird der Vektor dabei aber nach jedem Schritt in eine Richtungsinformation und eine Größeninformation aufgespaltet,

 

Die Unterraumiteration verallgemeinert dieses Vorgehen, indem man es gleichzeitig auf   (i. d. R.  ) Vektoren anwendet. Wenn diese genügend allgemein sind, bilden sie die Basis eines  -dimensionalen Untervektorraums, die man in einer Basismatrix   zusammenfassen kann. Der Basisschritt im Verfahren ist wieder die Multiplikation mit der Matrix, also  . Nach jeder Multiplikation macht man aber wie bei der Potenzmethode wieder eine Aufspaltung in Richtungs- und Größeninformation. Dabei gibt es verschiedene Möglichkeiten, eine numerisch besonders günstige Version ist die Verwendung von Orthonormalbasen (ONB), wobei dann   gilt mit der Einheitsmatrix   und  . Nach Multiplikation der Basismatrix   mit   erfolgt die Aufspaltung in Richtungsinformation (ONB) und Größeninformation mit Hilfe der QR-Zerlegung.

Ablauf der UnterraumiterationBearbeiten

Das Verfahren startet mit einer orthogonalen Matrix  , d. h.  . Im  -ten Schritt des Verfahrens berechnet man aus der Matrix   die Matrizen   über eine reduzierte QR-Zerlegung,

 

Dabei bildet   eine neue Orthonormalbasis und   ist eine quadratische obere Dreiecksmatrix. Das Verfahren konvergiert, wenn bei den Eigenwerten   von   eine Lücke bei den Beträgen hinter dem  -ten Eigenwert auftritt,  . Dann konvergieren die von den Basen aufgespannten Unterräume   gegen einen invarianten Unterraum   von   mit   (vgl. Untervektorraum). Wenn   eine Basismatrix von   ist, bedeutet das, dass es eine Matrix   gibt, so dass   gilt. Die   Eigenwerte von   sind dann genau die   betragsgrößten Eigenwerte   von oben. Bei der Unterraumiteration bekommt man die Grenzmatrix   einfach als Grenzwert der Matrizen  , wobei   im Verfahren sowieso berechnet wird. Die Eigenwerte von   sind daher natürlich auch für endliches   Approximationen der betragsgrößten Eigenwerte.

Querverbindung zum LR- und QR-AlgorithmusBearbeiten

Obwohl der eigentliche Einsatzbereich der Unterraumiteration die Berechnung weniger Eigenwerte ( ) dünnbesetzter Matrizen ist, kann man das Verfahren auch für die volle Dimension   betrachten. Die reduzierte QR-Zerlegung   stimmt dann mit der vollständigen QR-Zerlegung   überein, wo alle Matrizen quadratische  -Gestalt haben. Insbesondere sind die Matrizen   unitär,  . Entscheidend sind wieder die Matrizen  , denn sie enthalten die Eigenwert-Information. Überlegt man sich nun, wie   aus   hervorgeht, bekommt man aus der Unterraumiteration die Gleichung

 

Auch das eingeklammerte Produkt   ist wieder unitär. Es gilt aber auch direkt

 

Das bedeutet aber, dass man   ohne Rückgriff auf die Originalmatrix   direkt aus der QR-Zerlegung von   berechnen kann. Dies beschreibt genau die einfachste Variante des QR-Algorithmus. Der Zusammenhang mit dem älteren LR-Algorithmus ist analog, dort werden statt der unitären Transformationen untere Dreiecksmatrizen aus LR-Zerlegungen verwendet.

LiteraturBearbeiten

  • G. Golub, Ch. van Loan: Matrix Computations. Johns Hopkins, Baltimore and London 1989, ISBN 0-8018-3739-1.