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.
Motivation Bearbeiten
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 Unterraumiteration Bearbeiten
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-Algorithmus Bearbeiten
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.
Literatur Bearbeiten
- G. Golub, Ch. van Loan: Matrix Computations. Johns Hopkins, Baltimore and London 1989, ISBN 0-8018-3739-1.