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 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^{2}q,\ldots \,A^{{m-1}}q\}

berechnet. Da die Spalten 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 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 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_{j}h_{{jk}}
end for

end for

Einsatz beim Eigenwertproblem

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_{m}H_{m}+h_{{m+1,m}}q_{{m+1}}e_{m}^{T}

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

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 Q_{m} mit dem Startvektor r_{0}=b auf und ersetzt beim linearen System Ax=b die Matrix A durch die Approximation Q_{m}H_{m}Q_{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_{m}y_{m} bestimmt anhand des Systems

H_{m}y_{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_{m}y_{m}=\beta e_{1} mit einer QR-Zerlegung von H_{m}.

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung:  Jena, den: 03.10. 2018