Arnoldi Verfahren In der numerischen Mathematik ist das wie das Lanczos Verfahren ein iteratives Verfahren zur Bestimmun

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 und einem gegebenen Startvektor eine orthonormale Basis des zugeordneten Krylowraumes

berechnet. Da die Spalten 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 aus.

Der Algorithmus (MGS-Variante) Bearbeiten

Gegeben sei eine quadratische Matrix und ein (nicht notwendig normierter) Startvektor .

for and do

end for

Einsatz beim Eigenwertproblem Bearbeiten

Nach Schritten hat das Arnoldi-Verfahren im Wesentlichen eine Orthonormalbasis in der Matrix bestimmt und eine Hessenbergmatrix

Für diese im Arnoldi-Verfahren berechneten Größen gilt der Zusammenhang

wo der -te Einheitsvektor ist. Daraus folgt:

Für definiert die Gleichung einen invarianten Unterraum der Matrix und alle Eigenwerte der Matrix sind auch Eigenwerte von . In diesem Fall bricht das Arnoldi-Verfahren vorzeitig ab aufgrund der zweiten Bedingung .
Wenn klein ist, sind die Eigenwerte von gute Approximationen an einzelne Eigenwerte von . 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 mit dem Startvektor auf und ersetzt beim linearen System die Matrix durch die Approximation . Die rechte Seite ist also Element des Krylowraums, . Die Näherungslösung im Krylow-Raum wird in der Basisdarstellung bestimmt anhand des Systems

Dies entspricht der Bedingung und definiert die Lösung durch die Orthogonalitätsbedingung . Daher ist die FOM ein Galerkin-Verfahren. Löst man das kleine System mit einer QR-Zerlegung von , 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. Jahrgang, 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.

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele

Veröffentlichungsdatum: Dezember 01, 2023, 03:39 am

In der numerischen Mathematik ist das Arnoldi Verfahren wie das Lanczos Verfahren ein iteratives Verfahren zur Bestimmung einiger Eigenwerte und zugehoriger Eigenvektoren Es ist nach Walter Edwin Arnoldi benannt Im Arnoldi Verfahren wird zu einer gegebenen Matrix A C n n displaystyle A in mathbb C n times n und einem gegebenen Startvektor q C n displaystyle q in mathbb C n eine orthonormale Basis des zugeordneten Krylowraumes K m A q span q A q A 2 q A m 1 q displaystyle mathcal K m A q mbox span q Aq A 2 q ldots A m 1 q berechnet Da die Spalten A i q 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 wurde und anschliessend zum Beispiel nach Gram Schmidt orthonormalisiert wurde Der Algorithmus kommt allerdings ohne die vorherige Aufstellung der sogenannten Krylowmatrix K m A q q A q A 2 q A m 1 q displaystyle K m A q left q Aq A 2 q ldots A m 1 q right aus Inhaltsverzeichnis 1 Der Algorithmus MGS Variante 2 Einsatz beim Eigenwertproblem 3 Anwendung auf Lineare Systeme FOM und GMRES 4 LiteraturDer Algorithmus MGS Variante BearbeitenGegeben sei eine quadratische Matrix A C n n displaystyle A in mathbb C n times n nbsp und ein nicht notwendig normierter Startvektor r 0 C n displaystyle r 0 in mathbb C n nbsp for k N displaystyle k in mathbb N nbsp and r k 1 0 displaystyle r k 1 not 0 nbsp do h k k 1 r k 1 displaystyle h k k 1 leftarrow r k 1 nbsp q k r k 1 h k k 1 displaystyle q k leftarrow r k 1 h k k 1 nbsp r k A q k displaystyle r k leftarrow Aq k nbsp for j 1 k displaystyle j 1 ldots k nbsp doh j k q j r k displaystyle h jk leftarrow langle q j r k rangle nbsp r k r k q j h j k displaystyle r k leftarrow r k q j h jk nbsp dd end forend forEinsatz beim Eigenwertproblem BearbeitenNach m displaystyle m nbsp Schritten hat das Arnoldi Verfahren im Wesentlichen eine Orthonormalbasis in der Matrix Q m q 1 q m displaystyle Q m q 1 ldots q m nbsp bestimmt und eine Hessenbergmatrix H m h 11 h 12 h 1 m h 21 h 22 h 2 m 0 h m m 1 h m m displaystyle H m begin pmatrix h 11 amp h 12 amp ldots amp h 1m h 21 amp h 22 amp ldots amp h 2m 0 amp ddots amp ddots amp vdots amp amp h m m 1 amp h mm end pmatrix nbsp Fur diese im Arnoldi Verfahren berechneten Grossen gilt der Zusammenhang A Q m Q m H m h m 1 m q m 1 e m T displaystyle AQ m Q m H m h m 1 m q m 1 e m T nbsp wo e m displaystyle e m nbsp der m displaystyle m nbsp te Einheitsvektor ist Daraus folgt Fur h m 1 m 0 displaystyle h m 1 m 0 nbsp definiert die Gleichung A Q m Q m H m displaystyle AQ m Q m H m nbsp einen invarianten Unterraum der Matrix A displaystyle A nbsp und alle m displaystyle m nbsp Eigenwerte der Matrix H m displaystyle H m nbsp sind auch Eigenwerte von A displaystyle A nbsp In diesem Fall bricht das Arnoldi Verfahren vorzeitig ab aufgrund der zweiten Bedingung r k 1 0 displaystyle r k 1 not 0 nbsp Wenn h m 1 m displaystyle h m 1 m nbsp klein ist sind die Eigenwerte von H m displaystyle H m nbsp gute Approximationen an einzelne Eigenwerte von A displaystyle A nbsp Insbesondere Eigenwerte am Rand des Spektrums werden gut approximiert ahnlich wie beim Lanczos Verfahren Anwendung auf Lineare Systeme FOM und GMRES BearbeitenDas Arnoldi Verfahren ist ausserdem der Kern Algorithmus des GMRES Verfahrens zur Losung Linearer Gleichungssysteme und der Full Orthogonalization Method FOM In der FOM baut man den Krylow Unterraum und die Basen Q m displaystyle Q m nbsp mit dem Startvektor r 0 b displaystyle r 0 b nbsp auf und ersetzt beim linearen System A x b displaystyle Ax b nbsp die Matrix A displaystyle A nbsp durch die Approximation Q m H m Q m T displaystyle Q m H m Q m T nbsp Die rechte Seite ist also Element des Krylowraums b b q 1 displaystyle b beta q 1 nbsp Die Naherungslosung x m K m A b displaystyle x m in K m A b nbsp im Krylow Raum wird in der Basisdarstellung x m Q m y m displaystyle x m Q m y m nbsp bestimmt anhand des Systems H m y m b e 1 displaystyle H m y m beta e 1 nbsp Dies entspricht der Bedingung Q m T b A x m 0 displaystyle Q m T b Ax m 0 nbsp und definiert die Losung x m displaystyle x m nbsp durch die Orthogonalitatsbedingung b A x m K m A q displaystyle b Ax m perp K m A q nbsp Daher ist die FOM ein Galerkin Verfahren Lost man das kleine System H m y m b e 1 displaystyle H m y m beta e 1 nbsp mit einer QR Zerlegung von H m displaystyle H m nbsp so unterscheidet sich die Methode nur minimal vom Pseudocode im Artikel GMRES Verfahren Literatur BearbeitenW E Arnoldi The Principle of Minimized Iterations in the Solution of the Matrix Eigenvalue Problem In Quarterly of Applied Mathematics 9 Jahrgang 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 Abgerufen von https de wikipedia org w index php title Arnoldi Verfahren amp oldid 180488528