The above procedure
will stop if the vector computed in line (8) vanishes.
The vectors
form an orthonormal system
by construction and are called *Arnoldi vectors*.
An easy induction argument shows that this system is a basis of
the Krylov subspace .

Next we consider a fundamental relation between quantities
generated by the algorithm.
The following equality is readily derived:

Relation eq:VmTAVm follows from eq:AVm by multiplying both sides of eq:AVm by and making use of the orthonormality of .

As was noted earlier the algorithm breaks down when the norm of computed on line (8) vanishes at a certain step . As it turns out, this happens if and only if the starting vector is a combination of eigenvectors (i.e., the minimal polynomial of is of degree ). In addition, the subspace is then invariant and the approximate eigenvalues and eigenvectors are exact [387].

The approximate eigenvalues
provided by the
projection process onto are the eigenvalues of the Hessenberg
matrix . These are known as *Ritz values*.
A *Ritz approximate eigenvector* associated with a Ritz value
is defined by
, where is an eigenvector associated with the eigenvalue
. A number of the Ritz eigenvalues,
typically a small
fraction of , will usually constitute good approximations
for corresponding eigenvalues of , and the quality of the
approximation will usually improve as increases.

The original algorithm consists of increasing until all desired eigenvalues of are found. For large matrices, this becomes costly both in terms of computation and storage. In terms of storage, we need to keep vectors of length plus an Hessenberg matrix, a total of approximately . For the arithmetic costs, we need to multiply by , at the cost of , where is number of nonzero elements in , and then orthogonalize the result against vectors at the cost of which increases with the step number . Thus an -dimensional Arnoldi procedure costs in storage and in arithmetic operations.

Obtaining the residual norm, for a Ritz pair,
as the algorithm progresses is fairly inexpensive.
Let be an eigenvector of associated with the
eigenvalue
, and let be the Ritz approximate
eigenvector
.
We have the relation

and, therefore,

Thus, the residual norm is equal to the absolute value of the last component of the eigenvector multiplied by . The residual norms are not always indicative of actual errors in , but can be quite helpful in deriving stopping procedures.