Arnoldi-Verfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 A\in\mathbb{C}^{n\times n} und einem gegebenen Startvektor q\in\mathbb{C}^n eine orthonormale Basis des zugeordneten Krylowraumes

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

berechnet. Da die Spalten A^iq 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 K_m(A,q)=\left(q,Aq,A^2q,\ldots,A^{m-1}q \right) aus.

Der Algorithmus (MGS-Variante)[Bearbeiten]

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

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

h_{k,k-1}\leftarrow \|r_{k-1}\|
q_k\leftarrow r_{k-1}/h_{k,k-1}
r_k\leftarrow Aq_k
for j=1,\ldots,k do
h_{jk}\leftarrow \langle q_j,r_k\rangle
r_k\leftarrow r_k-q_jh_{jk}
end for

end for

Einsatz beim Eigenwertproblem[Bearbeiten]

Nach m Schritten hat das Arnoldi-Verfahren im Wesentlichen eine Orthonormalbasis in der Matrix Q_m=(q_1,\ldots,q_m) bestimmt und eine Hessenbergmatrix

 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 diese im Arnoldi-Verfahren berechneten Größen gilt der Zusammenhang

 AQ_m=Q_mH_m+h_{m+1,m}q_{m+1}e_m^T

wo e_m der m-te Einheitsvektor ist. Daraus folgt:

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

Anwendung auf Lineare Systeme, FOM und GMRES[Bearbeiten]

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 Q_m mit dem Startvektor r_0=b auf und ersetzt beim linearen System Ax=b die Matrix A durch die Approximation Q_mH_mQ_m^T. Die rechte Seite ist also Element des Krylowraums, b=\beta q_1. Die Näherungslösung x_m\in K_m(A,b) im Krylow-Raum wird in der Basisdarstellung x_m=Q_my_m bestimmt anhand des Systems

 H_my_m =\beta e_1.

Dies entspricht der Bedingung Q_m^T(b-Ax_m)=0 und definiert die Lösung x_m durch die Orthogonalitätsbedingung b-Ax_m\perp K_m(A,q). Daher ist die FOM ein Galerkin-Verfahren. Löst man das kleine System  H_my_m =\beta e_1 mit einer QR-Zerlegung von H_m, so unterscheidet sich die Methode nur minimal vom Pseudocode im Artikel GMRES-Verfahren.

Literatur[Bearbeiten]

  • 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.