Unterraumiteration

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.