A simple stability analysis of the Lanczos algorithm in finite precision arithmetic

Abstract

We give a self-contained analysis of the symmetric Lanczos algorithm without reorthogonalization when computations are performed inexactly. We show the computed Lanczos vectors are well-behaved locally. From this we (i) prove Paige's loss-of-orthogonality identity, and (ii) construct a Greenbaum-type backward stability result, exhibiting a nearby problem on which exact Lanczos produces the computed tridiagonal matrix. This allows us to derive several facts about the computed Ritz values at the original eigenvalues. Our analysis simplifies the analyses of Paige and Greenbaum, at the cost of hiding polynomial factors in the iteration count.

arXiv commentsimplified analysis from v1