How does the Lanczos iteration find small eigenvalues?

Question

I have seen it claimed in a couple of places that the classical Lanczos iteration (without shifts or being able to apply the inverse or anything fancy) yields good approximations to both the smallest and largest eigenvalue of a large, sparse, self-adjoint linear operator, but this is very surprising to me. As a Krylov subspace method, I would expect it to be accurate on the large eigenvalues and inaccurate on the small ones, for the same reasons as the power method. Does anyone know how Lanczos accomplishes this? I have seen it work in practice, but can't figure out why.

Answer 1

Unsurprisingly, Golub and van Loan (3rd ed.) had an answer. In chapter 9, they present this justification:

Consider an initial set of vectors $\{q_1,...,q_{k-1}\}$, and consider the optimal vector to add to this set to minimize $$ \min_{x\in\text{span}\{q_1,...,q_k\} - 0} r(x) $$ where $r$ is the quotient $$ \frac{x^TAx}{x^Tx} .$$ Let $u$ be the vector in the span of $q_1,...,q_{k-1}$ that minimizes $r$, and consider the gradient of $r$ at $u$, which is given by $$ \frac{2}{u^Tu} \left(Au - r(u)u\right).$$ If this vector is included in the span of $q_1,...,q_k$, then we have a guarantee that the minimum of $r$ on this subspace will decrease, and the decrease is "locally optimal" in a sense. Since the gradient lies in the next Krylov subspace, this heuristic motivates the use of Krylov subspaces to find the smallest eigenvalues rather than just the largest ones.

The preceding argument is informal, in the sense that it is not clear that the "local optimality" condition is good enough, but much more rigorous arguments are presented subsequently in Golub and van Loan, and ultimately a precise convergence analysis is possible.

There may be other, more complete and/or intuitive arguments people know, and I would be very interested to see them if that is the case.