Arnoldi-Verfahren

In der numerischen Mathematik ist das Arnoldi-Verfahren wie das Lanczos-Verfahren ein iteratives Verfahren zur Bestimmung einiger Eigenwerte und zugehöriger Eigenvektoren. Es ist nach Walter Edwin Arnoldi benannt. Im Arnoldi-Verfahren wird zu einer gegebenen Matrix ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ und einem gegebenen Startvektor ${\displaystyle q\in \mathbb {C} ^{n}}$ eine orthonormale Basis des zugeordneten Krylowraumes

${\displaystyle {\mathcal {K}}_{m}(A,q)={\mbox{span}}\{q,Aq,A^{2}q,\ldots \,A^{m-1}q\}}$

berechnet. Da die Spalten ${\displaystyle A^{i}q}$ bis auf eine etwaige Skalierung genau den in der Potenzmethode berechneten Vektoren entsprechen, ist es klar, dass der Algorithmus instabil wird, wenn zuerst diese Basis berechnet würde und anschließend, zum Beispiel nach Gram-Schmidt, orthonormalisiert würde.

Der Algorithmus kommt allerdings ohne die vorherige Aufstellung der sogenannten Krylowmatrix ${\displaystyle K_{m}(A,q)=\left(q,Aq,A^{2}q,\ldots ,A^{m-1}q\right)}$ aus.

Der Algorithmus (MGS-Variante)

Gegeben sei eine quadratische Matrix ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ und ein (nicht notwendig normierter) Startvektor ${\displaystyle r_{0}\in \mathbb {C} ^{n}}$.

for ${\displaystyle k\in \mathbb {N} }$ and ${\displaystyle r_{k-1}\not =0}$ do

${\displaystyle h_{k,k-1}\leftarrow \|r_{k-1}\|}$

${\displaystyle q_{k}\leftarrow r_{k-1}/h_{k,k-1}}$

${\displaystyle r_{k}\leftarrow Aq_{k}}$

for ${\displaystyle j=1,\ldots ,k}$ do

${\displaystyle h_{jk}\leftarrow \langle q_{j},r_{k}\rangle }$

${\displaystyle r_{k}\leftarrow r_{k}-q_{j}h_{jk}}$

end for

end for

Einsatz beim Eigenwertproblem

Nach ${\displaystyle m}$ Schritten hat das Arnoldi-Verfahren im Wesentlichen eine Orthonormalbasis in der Matrix ${\displaystyle Q_{m}=(q_{1},\ldots ,q_{m})}$ bestimmt und eine Hessenbergmatrix

${\displaystyle H_{m}={\begin{pmatrix}h_{11}&h_{12}&\ldots &h_{1m}\\h_{21}&h_{22}&\ldots &h_{2m}\\0&\ddots &\ddots &\vdots \\&&h_{m,m-1}&h_{mm}\end{pmatrix}}.}$

Für d​iese im Arnoldi-Verfahren berechneten Größen g​ilt der Zusammenhang

${\displaystyle AQ_{m}=Q_{m}H_{m}+h_{m+1,m}q_{m+1}e_{m}^{T}}$

wo ${\displaystyle e_{m}}$ der ${\displaystyle m}$-te Einheitsvektor ist. Daraus folgt:

• Für ${\displaystyle h_{m+1,m}=0}$ definiert die Gleichung ${\displaystyle AQ_{m}=Q_{m}H_{m}}$ einen invarianten Unterraum der Matrix ${\displaystyle A}$ und alle ${\displaystyle m}$ Eigenwerte der Matrix ${\displaystyle H_{m}}$ sind auch Eigenwerte von ${\displaystyle A}$. In diesem Fall bricht das Arnoldi-Verfahren vorzeitig ab aufgrund der zweiten Bedingung ${\displaystyle r_{k-1}\not =0}$.
• Wenn ${\displaystyle h_{m+1,m}}$ klein ist, sind die Eigenwerte von ${\displaystyle H_{m}}$ gute Approximationen an einzelne Eigenwerte von ${\displaystyle A}$. Insbesondere Eigenwerte am Rand des Spektrums werden gut approximiert ähnlich wie beim Lanczos-Verfahren.

Anwendung auf Lineare Systeme, FOM und GMRES

Das Arnoldi-Verfahren ist außerdem der Kern-Algorithmus des GMRES-Verfahrens zur Lösung Linearer Gleichungssysteme und der Full Orthogonalization Method (FOM). In der FOM baut man den Krylow-Unterraum und die Basen ${\displaystyle Q_{m}}$ mit dem Startvektor ${\displaystyle r_{0}=b}$ auf und ersetzt beim linearen System ${\displaystyle Ax=b}$ die Matrix ${\displaystyle A}$ durch die Approximation ${\displaystyle Q_{m}H_{m}Q_{m}^{T}}$. Die rechte Seite ist also Element des Krylowraums, ${\displaystyle b=\beta q_{1}}$. Die Näherungslösung ${\displaystyle x_{m}\in K_{m}(A,b)}$ im Krylow-Raum wird in der Basisdarstellung ${\displaystyle x_{m}=Q_{m}y_{m}}$ bestimmt anhand des Systems

${\displaystyle H_{m}y_{m}=\beta e_{1}.}$

Dies entspricht der Bedingung ${\displaystyle Q_{m}^{T}(b-Ax_{m})=0}$ und definiert die Lösung ${\displaystyle x_{m}}$ durch die Orthogonalitätsbedingung ${\displaystyle b-Ax_{m}\perp K_{m}(A,q)}$. Daher ist die FOM ein Galerkin-Verfahren. Löst man das kleine System ${\displaystyle H_{m}y_{m}=\beta e_{1}}$ mit einer QR-Zerlegung von ${\displaystyle H_{m}}$, so unterscheidet sich die Methode nur minimal vom Pseudocode im Artikel GMRES-Verfahren.

Literatur

• W.E. Arnoldi: The Principle of Minimized Iterations in the Solution of the Matrix Eigenvalue Problem. In: Quarterly of Applied Mathematics. 9, 1951, S. 17–29.
• Gene H. Golub, Charles F. Van Loan: Matrix Computations. 3. Auflage. The Johns Hopkins University Press, 1996, ISBN 0-8018-5414-8.