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

Inhaltsverzeichnis

Der Algorithmus (MGS-Variante)

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

Nach m Schritten hat das Arnoldi-Verfahren i.w. 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 em der m-te Einheitsvektor ist. Daraus folgt:

  • Für hm + 1,m = 0 definiert die Gleichung AQm = QmHm einen invarianten Unterraum der Matrix A und alle m Eigenwerte der Matrix Hm sind auch Eigenwerte von A. In diesem Fall bricht das Arnoldi-Verfahren vorzeitig ab aufgrund der zweiten Bedingung r_{k-1}\not=0.
  • Wenn hm + 1,m klein ist, sind die Eigenwerte von Hm 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

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 Qm mit dem Startvektor r0 = 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 = βq1. Die Näherungslösung x_m\in K_m(A,b) im Krylow-Raum wird in der Basisdarstellung xm = Qmym bestimmt anhand des Systems

Hmym = βe1.

Dies entspricht der Bedingung Q_m^T(b-Ax_m)=0 und definiert die Lösung xm 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 Hmym = βe1 mit einer QR-Zerlegung von Hm, 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.

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Arnoldi — ist der Name von Albert Jakob Arnoldi (1750–1835), reformierter Theologe Alberto Arnoldi (14. Jahrhundert), Architekt Bartholomäus Arnoldi (um 1465–1532), Philosoph und katholischer Theologe Charles Arnoldi (* 1946), US amerikanischer Künstler… …   Deutsch Wikipedia

  • Krylov-Unterraum-Verfahren — Krylow Unterraum Verfahren sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach… …   Deutsch Wikipedia

  • Krylow-Unterraum-Verfahren — sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach dem russischen… …   Deutsch Wikipedia

  • Lanczos-Verfahren — Das Lanczos Verfahren[1] (nach Cornelius Lanczos) ist sowohl ein iterativer Algorithmus zur Bestimmung einiger Eigenwerte und eventuell der zugehörigen Eigenvektoren einer Matrix, als auch ein iterativer Algorithmus zur approximativen Lösung… …   Deutsch Wikipedia

  • Numerische Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration 4 Approximation und Interpolation …   Deutsch Wikipedia

  • GMRES-Verfahren — Das GMRES Verfahren (für Generalized minimal residual method) ist ein iteratives numerisches Verfahren zur Lösung großer, dünnbesetzter linearer Gleichungssysteme. Das Verfahren ist aus der Klasse der Krylow Unterraum Verfahren und insbesondere… …   Deutsch Wikipedia

  • Liste numerischer Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration …   Deutsch Wikipedia

  • Hessenberg-Verfahren — Das Hessenberg Verfahren ist ein Verfahren der numerischen linearen Algebra zur Transformation einer quadratischen Matrix in Hessenberggestalt. Die Eigenwerte der entstehenden Hessenbergmatrix lassen sich anschließend einfach berechnen. Es ist… …   Deutsch Wikipedia

  • Symmetrisches Lanczos-Verfahren — In der numerischen Mathematik ist das symmetrische Lanczos Verfahren ein Verfahren zur Lösung von Eigenwertproblemen für symmetrische Matrizen . Es stellt sowohl einen Spezialfall des unsymmetrischen Lanczos Verfahrens, als auch des Arnoldi… …   Deutsch Wikipedia

  • Krylov-Unterraumverfahren — Krylow Unterraum Verfahren sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”