The Arnoldi iteration is a numerically stable algorithm to produce an orthonormal basis for the Krylov subspace associated with a matrix A ∈ ℝm × m and a vector as b ∈ ℝm. The Krylov subspace of order r ≤ m associated with A and b is defined as Kr := span{b, Ab, Ab⋯Ar − 1b}. The spanning vectors of Kr are not orthogonal.
The algorithm is related to the Gram-Schmidt orthogonalization procedure and it produces an upper Hessenberg matrix Hn (i.e. that is zero below the first subdiagonal) and a matrix Q having orthonormal columns such that AQi − 1 = QiHi. With the subscripts we signify that at iteration i there are i columns of Q available (we denote this as Qi − 1) and we must find the i + 1th.
The method starts from a normalized vector q1 and iteratively produces the next basis vectors. This process eventually “breaks down” since the norm of the iterates qi decreases, at which point the algorithm is said to have converged.
If we consider for example the second iteration, we have
$$ A {Q_1} = {Q_2}
=
$$
which yields the recursion:
[_3 = .]
In the previous equation the entries of the H matrix are obtained by exploiting the orthonormality of the q vectors, i.e.
$$ \langle \mathbf{q}_i, \mathbf{q}_j \rangle = \delta_{i, j} = \begin{cases} 1 & i = j\\ 0 & \mathrm{otherwise} \end{cases} $$
that is, we project the last equation above onto the basis vectors obtained so far, in order:
$$ \langle \mathbf{q}_1, \mathbf{q}_3 \rangle = \frac{\langle \mathbf{q}_1, A \mathbf{q}_2 \rangle - \left[ h_{1, 2} \langle \mathbf{q}_1, \mathbf{q}_1 \rangle + h_{2, 2} \langle \mathbf{q}_1, \mathbf{q}_2 \rangle \right] }{h_{3, 2}} $$
thus obtaining h1, 2 = ⟨q1, Aq2⟩ (and analogously for h2, 2), whereas h3, 2 is obtained by the normalization condition ∥q3∥ = 1. At this point, it is straightforward to justify the usual nested-loop representation of the algorithm. The normalizing coefficient is also used as a breakdown test, i.e. when hi + 1, i ≤ ϵ e.g. 10−12 in double precision floating point arithmetic, the algorithm terminates.