Unterraumiteration

Die Unterraumiteration dient in der numerischen Mathematik der Approximation von Eigenwerten einer quadratischen Matrix $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 $A$ nur in Form von Matrix-Vektor-Produkten $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.

Motivation

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

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

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

Ablauf der Unterraumiteration

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

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

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

Querverbindung zum LR- und QR-Algorithmus

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

$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 $Q_{k}:=U_{k-1}^{\ast }U_{k}$ ist wieder unitär. Es gilt aber auch direkt

$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 $S_{k}=R_{k}Q_{k}$ ohne Rückgriff auf die Originalmatrix $A$ direkt aus der QR-Zerlegung von $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.

Literatur

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