Unterraumiteration

Die Unterraumiteration dient in der numerischen Mathematik der Approximation von Eigenwerten einer quadratischen Matrix $A\in {ℂ}^{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 {ℂ}^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\Vert A{u}_{k-1}\Vert :=A{u}_{k-1}.$

Die Unterraumiteration verallgemeinert dieses Vorgehen, indem man es gleichzeitig auf $m\le 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 {ℂ}^{n\times m}$ zusammenfassen kann. Der Basisschritt im Verfahren ist wieder die Multiplikation mit der Matrix, also $A{U}_0,A(A{U}_0),\dots$. 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 {ℝ}^{m\times m}$ gilt mit der Einheitsmatrix $I_m$ und $U_0^{\ast }={\overline{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 {ℂ}^{n\times m},m\le n,$, d. h. ${\hat{U}}_0^{\ast }{\hat{U}}_0=I_m\in {ℝ}^{m\times m}$. Im $k$-ten Schritt des Verfahrens berechnet man aus der Matrix ${\hat{U}}_{k-1}\in {ℂ}^{n\times m},m\le 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 {ℂ}^{n\times m}$ eine neue Orthonormalbasis und ${\hat{R}}_k\in {ℂ}^{m\times m}$ ist eine quadratische obere Dreiecksmatrix. Das Verfahren konvergiert, wenn bei den Eigenwerten ${\lambda }_1,\dots ,{\lambda }_n$ von $A$ eine Lücke bei den Beträgen hinter dem $m$-ten Eigenwert auftritt, $|{\lambda }_1|\ge \dots \ge |{\lambda }_m|>|{\lambda }_{m+1}|\ge \dots$. Dann konvergieren die von den Basen aufgespannten Unterräume $V_k:={\hat{U}}_k{ℂ}^m$ gegen einen invarianten Unterraum $V$ von $A$ mit $AV\subseteq V$ (vgl. Untervektorraum). Wenn $U\in {ℂ}^{n\times m}$ eine Basismatrix von $V$ ist, bedeutet das, dass es eine Matrix $S\in {ℂ}^{m\times m}$ gibt, so dass $AU=US$ gilt. Die $m$ Eigenwerte von $S$ sind dann genau die $m$ betragsgrößten Eigenwerte ${\lambda }_1,\dots ,{\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=A{U}_{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{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 }A{U}_k=(U_k^{\ast }A{U}_{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 }(A{U}_{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.