Uniform Error Estimates for the Lanczos Method
share
The Lanczos method is one of the most powerful and fundamental techniques for solving an extremal symmetric eigenvalue problem. Convergence-based error estimates are well studied, with the estimate depending heavily on the eigenvalue gap. However, in practice, this gap is often relatively small, resulting in significant overestimates of error. One way to avoid this issue is through the use of uniform error estimates, namely, bounds that depend only on the dimension of the matrix and the number of iterations. In this work, we prove a number of upper and lower uniform error estimates for the Lanczos method. These results include the first known lower bounds for error in the Lanczos method and significantly improved upper bounds for error measured in the p-norm, p>1. These lower bounds imply that the maximum error of m iterations of the Lanczos method over all n × n symmetric matrices does indeed depend on the dimension n. In addition, we prove more specific results for matrices that possess some level of eigenvalue regularity or whose eigenvalues converge to some limiting empirical spectral distribution. Through numerical experiments, we show that the theoretical estimates of this paper do apply to practical computations for reasonably sized matrices.
READ FULL TEXT