---
tag: CJ5EC820S7
kind: statement
role: proposition
name: Arnoldi iteration
msc: [65F15, 65F10, 65F25]
uses: [QB45PCGQPV, YCEEWJTX56, 0VT6P0GNQR, 0P17NGQQMQ, DARX1KZRHZ, 0BQAA2BK3Q, 7RRB4PCRJB]
about: [QB45PCGQPV, YCEEWJTX56]
sources:
  - url: https://en.wikipedia.org/wiki/Arnoldi_iteration
same_as:
  wikidata: Q696822
  wikipedia: Arnoldi iteration
---

## Statement

Let $A$ be a complex $n \times n$ matrix and let $b \in \C^n$ be nonzero.
The *Arnoldi iteration* sets $q_1 = b / \norm{b}$ and, for $j = 1, 2, \dots$, computes
$$h_{ij} = q_i^* A q_j \ (1 \le i \le j), \quad w_j = A q_j - \sum_{i=1}^{j} h_{ij} q_i, \quad h_{j+1, j} = \norm{w_j}, \quad q_{j+1} = w_j / h_{j+1, j}.$$
Here $\norm{\cdot}$ is the Euclidean norm.
Suppose $h_{j+1, j} \ne 0$ for $j = 1, \dots, m$.
Let $Q_m$ be the $n \times m$ matrix with columns $q_1, \dots, q_m$.
Let $\tilde{H}_m$ be the $(m+1) \times m$ matrix of the $h_{ij}$, with $h_{ij} = 0$ for $i > j + 1$, and let $H_m$ be its first $m$ rows.
Then:

1. $q_1, \dots, q_{m+1}$ is an orthonormal basis of the [[Krylov subspace|QB45PCGQPV]] $\mathcal{K}_{m+1}(A, b)$;
2. $A Q_m = Q_{m+1} \tilde{H}_m$, and $H_m = Q_m^* A Q_m$ is an upper [[Hessenberg matrix|YCEEWJTX56]];
3. if $h_{m+1, m} = 0$ instead, the iteration stops at step $m$, $\mathcal{K}_m(A, b)$ is invariant under $A$, and every eigenvalue of $H_m$ is an eigenvalue of $A$.

## Remarks

The iteration is the [[Gram–Schmidt process|0VT6P0GNQR]], in its modified form in practice, applied to the vectors $b, A q_1, A q_2, \dots$.
Since $A q_j$ lies in $\mathcal{K}_{j+1}(A, b)$, clause 1 follows by induction, and clause 2 is the matrix form of the defining recurrence.
Clause 3 holds because $A Q_m = Q_m H_m$ when $h_{m+1, m} = 0$.
The [[eigenvalues|0BQAA2BK3Q]] of $H_m$ are the Ritz values; the extreme ones often approximate eigenvalues of $A$ well for $m$ much smaller than $n$.
Example: if $b$ is an eigenvector of $A$ for $\lambda$, then $w_1 = 0$, the iteration stops at $m = 1$, and $H_1 = (\lambda)$.
If $A$ is [[Hermitian|0P17NGQQMQ]], then $H_m$ is Hermitian and Hessenberg, hence [[tridiagonal|DARX1KZRHZ]].
Then the recurrence has only three terms, and it becomes the [[Lanczos algorithm|7RRB4PCRJB]].

## Explanations

### L1 human

The Arnoldi iteration builds an orthonormal basis of the space spanned by $b, A b, A^2 b, \dots$, one vector at a time.
In this basis, the action of $A$ looks like a small matrix that is almost triangular.
Studying this small matrix reveals information about the large one, such as its extreme eigenvalues.

### L2 human

Arnoldi is the engine of GMRES for nonsymmetric linear systems and of the implicitly restarted Arnoldi method for eigenvalues.
Its cost grows with $m$: step $j$ needs one product with $A$ and $j$ inner products, and all $q_j$ must be stored.
This is why practical codes restart after a fixed number of steps.
The relation $A Q_m = Q_{m+1} \tilde{H}_m$ reduces large problems on $\mathcal{K}_m$ to small problems with $\tilde{H}_m$.