Unterraumiteration

Die Unterraumiteration dient in der numerischen Mathematik der Approximation von Eigenwerten einer quadratischen Matrix ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ und der dazugehörigen Eigenvektoren. Sie ist eine Verallgemeinerung der einfachen Vektoriteration (Von-Mises-Iteration) und benötigt wie diese die Matrix ${\displaystyle A}$ nur in Form von Matrix-Vektor-Produkten ${\displaystyle A\cdot v}$, 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.

Der Artikel Potenzmethode zeigt, dass sich ein genügend allgemeiner Startvektor ${\displaystyle u_{0}\in \mathbb {C} ^{n}}$ bei ${\displaystyle k}$-facher Anwendung der Matrix wie in ${\displaystyle A^{k}u_{0}}$ langsam in die Richtung eines Eigenvektors ${\displaystyle v_{1}}$ zum betragsgrößten Eigenwert ${\displaystyle \lambda _{1}}$ 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,

${\displaystyle u_{k}\|Au_{k-1}\|:=Au_{k-1}.}$

Die Unterraumiteration verallgemeinert dieses Vorgehen, indem man es gleichzeitig auf ${\displaystyle m\leq n}$ (i. d. R. ${\displaystyle m\ll n}$) Vektoren anwendet. Wenn diese genügend allgemein sind, bilden sie die Basis eines ${\displaystyle m}$-dimensionalen Untervektorraums, die man in einer Basismatrix ${\displaystyle U_{0}\in \mathbb {C} ^{n\times m}}$ zusammenfassen kann. Der Basisschritt im Verfahren ist wieder die Multiplikation mit der Matrix, also ${\displaystyle AU_{0},A(AU_{0}),\ldots }$. 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 ${\displaystyle U_{0}^{\ast }U_{0}=I_{m}\in \mathbb {R} ^{m\times m}}$ gilt mit der Einheitsmatrix ${\displaystyle I_{m}}$ und ${\displaystyle U_{0}^{\ast }={\bar {U}}_{0}^{T}}$. Nach Multiplikation der Basismatrix ${\displaystyle U}$ mit ${\displaystyle A}$ erfolgt die Aufspaltung in Richtungsinformation (ONB) und Größeninformation mit Hilfe der QR-Zerlegung.

Das Verfahren startet mit einer orthogonalen Matrix ${\displaystyle {\hat {U}}_{0}\in \mathbb {C} ^{n\times m},\ m\leq n,}$, d. h. ${\displaystyle {\hat {U}}_{0}^{\ast }{\hat {U}}_{0}=I_{m}\in \mathbb {R} ^{m\times m}}$. Im ${\displaystyle k}$-ten Schritt des Verfahrens berechnet man aus der Matrix ${\displaystyle {\hat {U}}_{k-1}\in \mathbb {C} ^{n\times m},\ m\leq n,}$ die Matrizen ${\displaystyle {\hat {U}}_{k},{\hat {R}}_{k}}$ über eine reduzierte QR-Zerlegung,

${\displaystyle {\hat {U}}_{k}\cdot {\hat {R}}_{k}=A{\hat {U}}_{k-1}.}$

Dabei bildet ${\displaystyle {\hat {U}}_{k}\in \mathbb {C} ^{n\times m}}$ eine neue Orthonormalbasis und ${\displaystyle {\hat {R}}_{k}\in \mathbb {C} ^{m\times m}}$ ist eine quadratische obere Dreiecksmatrix. Das Verfahren konvergiert, wenn bei den Eigenwerten ${\displaystyle \lambda _{1},\ldots ,\lambda _{n}}$ von ${\displaystyle A}$ eine Lücke bei den Beträgen hinter dem ${\displaystyle m}$-ten Eigenwert auftritt, ${\displaystyle |\lambda _{1}|\geq \ldots \geq |\lambda _{m}|>|\lambda _{m+1}|\geq \ldots }$. Dann konvergieren die von den Basen aufgespannten Unterräume ${\displaystyle V_{k}:={\hat {U}}_{k}\mathbb {C} ^{m}}$ gegen einen invarianten Unterraum ${\displaystyle V}$ von ${\displaystyle A}$ mit ${\displaystyle AV\subseteq V}$ (vgl. Untervektorraum). Wenn ${\displaystyle U\in \mathbb {C} ^{n\times m}}$ eine Basismatrix von ${\displaystyle V}$ ist, bedeutet das, dass es eine Matrix ${\displaystyle S\in \mathbb {C} ^{m\times m}}$ gibt, so dass ${\displaystyle AU=US}$ gilt. Die ${\displaystyle m}$ Eigenwerte von ${\displaystyle S}$ sind dann genau die ${\displaystyle m}$ betragsgrößten Eigenwerte ${\displaystyle \lambda _{1},\ldots ,\lambda _{m}}$ von oben. Bei der Unterraumiteration bekommt man die Grenzmatrix ${\displaystyle S}$ einfach als Grenzwert der Matrizen ${\displaystyle S_{k}:={\hat {U}}_{k}^{\ast }(A{\hat {U}}_{k})}$, wobei ${\displaystyle A{\hat {U}}_{k}}$ im Verfahren sowieso berechnet wird. Die Eigenwerte von ${\displaystyle S_{k}}$ sind daher natürlich auch für endliches ${\displaystyle k}$ Approximationen der betragsgrößten Eigenwerte.

Obwohl der eigentliche Einsatzbereich der Unterraumiteration die Berechnung weniger Eigenwerte (${\displaystyle m\ll n}$) dünnbesetzter Matrizen ist, kann man das Verfahren auch für die volle Dimension ${\displaystyle m=n}$ betrachten. Die reduzierte QR-Zerlegung ${\displaystyle {\hat {U}}_{k}\cdot {\hat {R}}_{k}=A{\hat {U}}_{k-1}.}$ stimmt dann mit der vollständigen QR-Zerlegung ${\displaystyle U_{k}\cdot R_{k}=AU_{k-1}}$ überein, wo alle Matrizen quadratische ${\displaystyle n\times n}$-Gestalt haben. Insbesondere sind die Matrizen ${\displaystyle U_{k}}$ unitär, ${\displaystyle U_{k}^{\ast }=U_{k}^{-1}}$. Entscheidend sind wieder die Matrizen ${\displaystyle S_{k}:=U_{k}^{\ast }A{\hat {U}}_{k}}$, denn sie enthalten die Eigenwert-Information. Überlegt man sich nun, wie ${\displaystyle S_{k}}$ aus ${\displaystyle S_{k-1}}$ hervorgeht, bekommt man aus der Unterraumiteration die Gleichung

${\displaystyle S_{k}=U_{k}^{\ast }AU_{k}=(U_{k}^{\ast }AU_{k-1})U_{k-1}^{\ast }U_{k}=R_{k}(U_{k-1}^{\ast }U_{k}).}$

Auch das eingeklammerte Produkt ${\displaystyle Q_{k}:=U_{k-1}^{\ast }U_{k}}$ ist wieder unitär. Es gilt aber auch direkt

${\displaystyle S_{k-1}=U_{k-1}^{\ast }(AU_{k-1})=(U_{k-1}^{\ast }U_{k})R_{k}=Q_{k}R_{k}.}$

Das bedeutet aber, dass man ${\displaystyle S_{k}=R_{k}Q_{k}}$ ohne Rückgriff auf die Originalmatrix ${\displaystyle A}$ direkt aus der QR-Zerlegung von ${\displaystyle S_{k-1}=Q_{k}R_{k}}$ 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.

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