Unterraumiteration

Die Unterraumiteration dient in der numerischen Mathematik der Approximation von Eigenwerten einer quadratischen Matrix <math>A\in\Complex^{n\times n}</math> und der dazugehörigen Eigenvektoren. Sie ist eine Verallgemeinerung der einfachen Vektoriteration (Von-Mises-Iteration) und benötigt wie diese die Matrix <math>A</math> nur in Form von Matrix-Vektor-Produkten <math>A\cdot v</math>, 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 <math>u_0\in\Complex^n</math> bei <math>k</math>-facher Anwendung der Matrix wie in <math>A^ku_0</math> langsam in die Richtung eines Eigenvektors <math>v_1</math> zum betragsgrößten Eigenwert <math>\lambda_1</math> 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,

<math>u_k\|Au_{k-1}\|:=Au_{k-1}.</math>

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

Ablauf der Unterraumiteration

Das Verfahren startet mit einer orthogonalen Matrix <math>\hat U_0\in\Complex^{n\times m},\ m\le n,</math>, d. h. <math>\hat U_0^\ast\hat U_0=I_m\in\R^{m\times m}</math>. Im <math>k</math>-ten Schritt des Verfahrens berechnet man aus der Matrix <math>\hat U_{k-1}\in\Complex^{n\times m},\ m\le n,</math> die Matrizen <Math>\hat U_k,\hat R_k</math> über eine reduzierte QR-Zerlegung,

<math> \hat U_k\cdot\hat R_k=A\hat U_{k-1}.</math>

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

Querverbindung zum LR- und QR-Algorithmus

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

<math>S_k=U_k^\ast A U_k=(U_k^\ast AU_{k-1})U_{k-1}^\ast U_k= R_k(U_{k-1}^\ast U_k).</math>

Auch das eingeklammerte Produkt <math>Q_k:=U_{k-1}^\ast U_k</math> ist wieder unitär. Es gilt aber auch direkt

<math>S_{k-1}=U_{k-1}^\ast(AU_{k-1})=(U_{k-1}^\ast U_k)R_k=Q_kR_k.</math>

Das bedeutet aber, dass man <math>S_k=R_kQ_k</math> ohne Rückgriff auf die Originalmatrix <math>A</math> direkt aus der QR-Zerlegung von <math>S_{k-1}=Q_kR_k</math> 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.