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 ∈ ℝⁿ×ⁿ und einen gegebenen Vektor q₁ mit ||q₁||₂ = 1 berechnet das Arnoldi-Verfahren eine orthogonale Matrix Q ∈ ℝⁿ×ⁿ, Q^TQ = I, deren erste Spalte Qe₁ = q₁ 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 = (q₁, q₂,…, q_n) mit q_j ∈ ℝⁿ, so berechnet das Arnoldi-Verfahren die Spalten von Q sukzessive aus der Gleichung AQ = QH_n

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

Aus der Orthonormalität der q_i 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 q_j+1 von Q benötigt man also alle vorher berechneten Spalten q₁, q₂,…, q_j. 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 H_n, sondern stoppt bei einem H_j mit j < n.

Man berechnet nur die ersten j Spalten Q_j = (q₁, q₂,…, q_j) 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 H_j (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 x₁, ∈ ℂ^j, und einer oberen Dreiecksmatrix S_j ∈ ℂ^j×j.

Von der Diagonalen

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

der Matrix S_j können die Eigenwerte λ₁,…, λ_j ∈ ℝ von H_j abgelesen werden:

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

Ist r_j = 0, dann sind die Eigenwerte λ_k, k = 1, …, j, der berechneten j-ten Hauptabschnittsmatrix H_j der Hessenberg-Matrix H_n Eigenwerte von A. Fur r_j ≠ 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 Q_j auch der Verlust der Orthogonalität der Spalten von Q_j ein großes Problem. Es ist erforderlich, die theoretisch gegebene Orthonormalität der Vektoren q_i 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 q₁

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

bestimme neuen Startvektor q₁

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

Wählt man den neuen Startvektor geschickt, so wird r_m 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 {q₁, q₂,…, q_n} 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.