Computing Probabilistic Bounds for Extreme Eigenvalues of Symmetric Matrices with the Lanczos Method
Authors:
- Jos L. M. van DorsselaerJDJos L. M. van Dorsselaer
- Michiel E. HochstenbachMHMichiel E. Hochstenbach
- Henk A. van der VorstHVHenk A. van der Vorst
- 1 January 2001
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 22 (3) , 837-852
Abstract
We study the Lanczos method for computing extreme eigenvalues of a symmetric or Hermitian matrix. It is not guaranteed that the extreme Ritz values are close to the extreme eigenvalues---even when the norms of the corresponding residual vectors are small. Assuming that the starting vector has been chosen randomly, we compute probabilistic bounds for the extreme eigenvalues from data available during the execution of the Lanczos process. Four different types of bounds are obtained using Lanczos, Ritz, and Chebyshev polynomials. These bounds are compared theoretically and numerically. Furthermore we show how one can determine, after each Lanczos step, a probabilistic upper bound for the number of steps still needed (without performing these steps) to obtain an approximation to the largest or smallest eigenvalue within a prescribed tolerance.Keywords
This publication has 10 references indexed in Scilit:
- Matrix Iterative Analysis2000
- Chebyshev Polynomials with Integer Coefficients1999
- Computation of pseudospectraActa Numerica, 1999
- Computing the field of values and pseudospectra using the Lanczos method with continuationBIT Numerical Mathematics, 1996
- 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
- The convergence behavior of ritz values in the presence of close eigenvaluesLinear Algebra and its Applications, 1987
- On estimating the largest eigenvalue with the Lanczos algorithmMathematics of Computation, 1982
- On the Rates of Convergence of the Lanczos and the Block-Lanczos MethodsSIAM Journal on Numerical Analysis, 1980
- Estimates for some computational techniques in linear algebraMathematics of Computation, 1966