Direkt zum Inhalt

Lexikon der Mathematik: Arnoldi-Verfahren

Verfahren zur sukzessiven Transformation einer nichtsymmetrischen Matrix A ∈ ℝn×n auf obere Hessenberg-Form.

Kombiniert mit einer Methode zur Bestimmung von Eigenwerten und Eigenvektoren oberer Hessenberg-Matrizen ist es ein effizientes Verfahren zur Lösung des Eigenwertproblems für große sparse Matrizen.

Für eine gegebene Matrix A ∈ ℝn×n und einen gegebenen Vektor q1 mit ||q1||2 = 1 berechnet das Arnoldi-Verfahren eine orthogonale Matrix Q ∈ ℝn×n, QTQ = I, deren erste Spalte Qe1 = q1 ist und die A auf obere Hessenberg-Form transformiert, d. h.

\begin{eqnarray}{Q}^{T}AQ & = & {H}_{n}=\\ & = & ({h}_{11} & {h}_{12} & \cdots & \cdots & {h}_{1n}\\ {h}_{21} & {h}_{22} & \cdots & \cdots & {h}_{2n}\\ 0 & {h}_{31} & \ddots & & {h}_{3n}\\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & {h}_{n,n-1} & {h}_{nn})\text{.}\end{eqnarray}

Setzt man Q = (q1, q2,…, qn) mit qj ∈ ℝn, so berechnet das Arnoldi-Verfahren die Spalten von Q sukzessive aus der Gleichung AQ = QHn

\begin{eqnarray}A{q}_{j}=\displaystyle \sum _{k=1}^{j+1}{h}_{kj}{q}_{j}.\end{eqnarray}

Aus der Orthonormalität der qi folgt dann

\begin{eqnarray}{h}_{kj}={q}_{k}^{T}A{q}_{j}\end{eqnarray}

für k = 1,…, j und, wenn

\begin{eqnarray}{r}_{j}=(A-{h}_{jj}I){q}_{j}-\displaystyle \sum _{k=1}^{j-1}{h}_{kj}{q}_{j}\end{eqnarray}

ungleich Null ist, dann

\begin{eqnarray}{q}_{j+1}=\frac{{r}_{j}}{{h}_{j+1j}}\text{mit}{h}_{j+1j}={\Vert {r}_{j}\Vert }_{2}.\end{eqnarray}

Zur Berechnung der nächsten Spalte qj+1 von Q benötigt man also alle vorher berechneten Spalten q1, q2,…, qj. Daher wächst der Speicheraufwand für die Spalten von Q mit j an. Für große Eigenwertprobleme läßt sich daher aus Speicherplatzgründen nicht die vollständige Reduktion von A auf obere Hessenberg-Form berechnen.

Da bei den Berechnungen zudem nur das Produkt von A mit einem Vektor benötigt wird, d. h. A selbst nicht verändert wird, verwendet man das Arnoldi-Verfahren häufig zur näherungsweisen Berechnung einiger Eigenwerte und Eigenvektoren großer sparser Matrizen. Dabei reduziert man A nicht vollständig zu der Hessenberg-Matrix Hn, sondern stoppt bei einem Hj mit j < n.

Man berechnet nur die ersten j Spalten Qj = (q1, q2,…, qj) von Q und erhält

\begin{eqnarray}A{Q}_{j}={Q}_{j}{H}_{j}+{r}_{j}{e}_{j}^{T}.\end{eqnarray}

Nun berechnet man die Schur-Zerlegung von Hj (z. B. mit dem QR-Algorithmus)

\begin{eqnarray}{H}_{j}={X}_{j}{S}_{j}{X}_{j}^{-1}\end{eqnarray}

mit einer nichtsingulären Matrix

\begin{eqnarray}X=({x}_{1},\ldots, {x}_{j})\in {{\rm{{\mathbb{C}}}}}^{j\times j},\end{eqnarray}

also x1, ∈ ℂj, und einer oberen Dreiecksmatrix Sj ∈ ℂj×j.

Von der Diagonalen

\begin{eqnarray}\text{diag}({S}_{j})=\text{diag}({s}_{11},{s}_{22},\ldots, {s}_{jj})\end{eqnarray}

der Matrix Sj können die Eigenwerte λ1,…, λj ∈ ℝ von Hj abgelesen werden:

\begin{eqnarray}{\lambda }_{k}={s}_{kk},k=1,\ldots, j.\end{eqnarray}

Ist rj = 0, dann sind die Eigenwerte λk, k = 1, …, j, der berechneten j-ten Hauptabschnittsmatrix Hj der Hessenberg-Matrix Hn Eigenwerte von A. Fur rj ≠ 0 betrachtet man die λi als Näherungen an die Eigenwerte von A.

Bei der numerischen Berechnung ist neben dem wachsenden Speicherplatzbedarf für die Spalten von Qj auch der Verlust der Orthogonalität der Spalten von Qj ein großes Problem. Es ist erforderlich, die theoretisch gegebene Orthonormalität der Vektoren qi explizit zu erzwingen. Das erhöht die benötigte Rechenzeit erheblich.

Daher existieren zahlreiche Vorschläge in der Literatur, wie mit diesen Problemen umgegangen werden sollte.

Besonders erfolgreich sind Ansätze, das Arnoldi-Verfahren nach m Schritten neuzustarten. Dazu iteriert man

wähle Startvektor q1

führe m Schritte des Arnoldi-Verfahrens durch solange rm ≠ 0 wiederhole

bestimme neuen Startvektor q1

führe m Schritte des Arnoldi-Verfahrens durch ende wiederhole

Wählt man den neuen Startvektor geschickt, so wird rm nach jedem neuen Start des Arnoldi-Verfahrens kleiner und konvergiert rasch gegen Null.

Für symmetrische Matrizen A entspricht das Arnoldi-Verfahren dem Lanczos-Verfahren.

Das Arnoldi-Verfahren kann auch interpretiert werden als Berechnung einer orthogonalen Basis {q1, q2,…, qn} für den Krylów-Raum

\begin{eqnarray}\{{q}_{1},A{q}_{1},{A}^{2}{q}_{1},\ldots, {A}^{n-1}{q}_{1}\},\end{eqnarray}

bzw. als Berechnung einer QR-Zerlegung der Krylow-Matrix

\begin{eqnarray}K(A,{q}_{1},n) & = & ({q}_{1},A{q}_{1},{A}^{2}{q}_{1},\ldots, {A}^{n-1}{q}_{1})\\ & = & ({q}_{1},{q}_{2},\ldots, {q}_{n})R=QR.\end{eqnarray}

Diese Eigenschaft nutzt das GMRES-Verfahren, um ein lineares Gleichungssystem Ax = b zu lösen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos