Uniform Error Estimates for the Lanczos Method
Preprint
Abstract
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 \times 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.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Interlacing of the zeros of Jacobi polynomials with different parametersNumerical Algorithms, 2008
- An elementary proof of a theorem of Johnson and LindenstraussRandom Structures & Algorithms, 2002
- Computing Probabilistic Bounds for Extreme Eigenvalues of Symmetric Matrices with the Lanczos MethodSIAM Journal on Matrix Analysis and Applications, 2001
- A strong law for weighted sums of i.i.d. random variablesJournal of Theoretical Probability, 1995
- Probabilistic Bounds on the Extremal Eigenvalues and Condition Number by the Lanczos AlgorithmSIAM Journal on Matrix Analysis and Applications, 1994
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random StartSIAM Journal on Matrix Analysis and Applications, 1992
- On the Rates of Convergence of the Lanczos and the Block-Lanczos MethodsSIAM Journal on Numerical Analysis, 1980