Arnoldi Iteration - Finding Eigenvalues With The Arnoldi Iteration

Finding Eigenvalues With The Arnoldi Iteration

The idea of the Arnoldi iteration as an eigenvalue algorithm is to compute the eigenvalues of the orthogonal projection of A onto the Krylov subspace. This projection is represented by H_n. The eigenvalues of H_n are called the Ritz eigenvalues. Since H_n is a Hessenberg matrix of modest size, its eigenvalues can be computed efficiently, for instance with the QR algorithm.

It is often observed in practice that some of the Ritz eigenvalues converge to eigenvalues of A. Since H_n is n-by-n, it has at most n eigenvalues, and not all eigenvalues of A can be approximated. Typically, the Ritz eigenvalues converge to the extreme eigenvalues of A. This can be related to the characterization of H_n as the matrix whose characteristic polynomial minimizes ||p(A)q₁|| in the following way. A good way to get p(A) small is to choose the polynomial p such that p(x) is small whenever x is an eigenvalue of A. Hence, the zeros of p (and thus the Ritz eigenvalues) will be close to the eigenvalues of A.

However, the details are not fully understood yet. This is in contrast to the case where A is symmetric. In that situation, the Arnoldi iteration becomes the Lanczos iteration, for which the theory is more complete.