Sharpness in rates of convergence for the symmetric Lanczos method
HTML articles powered by AMS MathViewer
- by Ren-Cang Li PDF
- Math. Comp. 79 (2010), 419-435 Request permission
Abstract:
The Lanczos method is often used to solve a large and sparse symmetric matrix eigenvalue problem. There is a well-established convergence theory that produces bounds to predict the rates of convergence good for a few extreme eigenpairs. These bounds suggest at least linear convergence in terms of the number of Lanczos steps, assuming there are gaps between individual eigenvalues. In practice, often superlinear convergence is observed. The question is “do the existing bounds tell the correct convergence rate in general?”. An affirmative answer is given here for the two extreme eigenvalues by examples whose Lanczos approximations have errors comparable to the error bounds for all Lanczos steps.References
- Owe Axelsson, Iterative solution methods, Cambridge University Press, Cambridge, 1994. MR 1276069, DOI 10.1017/CBO9780511624100
- E. W. Cheney, Introduction to approximation theory, AMS Chelsea Publishing, Providence, RI, 1998. Reprint of the second (1982) edition. MR 1656150
- James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942, DOI 10.1137/1.9781611971446
- A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl. 113 (1989), 7–63. MR 978581, DOI 10.1016/0024-3795(89)90285-1
- Anne Greenbaum, Iterative methods for solving linear systems, Frontiers in Applied Mathematics, vol. 17, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1474725, DOI 10.1137/1.9781611970937
- A. Greenbaum and Z. Strakoš, Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. Matrix Anal. Appl. 13 (1992), no. 1, 121–137. MR 1146656, DOI 10.1137/0613011
- Martin Hanke, Superlinear convergence rates for the Lanczos method applied to elliptic operators, Numer. Math. 77 (1997), no. 4, 487–499. MR 1473393, DOI 10.1007/s002110050297
- I. C. F. Ipsen, Expressions and bounds for the GMRES residual, BIT 40 (2000), no. 3, 524–535. MR 1780406, DOI 10.1023/A:1022371814205
- Zhongxiao Jia and G. W. Stewart, An analysis of the Rayleigh-Ritz method for approximating eigenspaces, Math. Comp. 70 (2001), no. 234, 637–647. MR 1697647, DOI 10.1090/S0025-5718-00-01208-4
- Shmuel Kaniel, Estimates for some computational techniques in linear algebra, Math. Comp. 20 (1966), 369–378. MR 234618, DOI 10.1090/S0025-5718-1966-0234618-4
- J. Kovač-Striko and K. Veselić, Some remarks on the spectra of Hermitian matrices, Linear Algebra Appl. 145 (1991), 221–229. MR 1080687, DOI 10.1016/0024-3795(91)90298-B
- A. B. J. Kuijlaars, Which eigenvalues are found by the Lanczos method?, SIAM J. Matrix Anal. Appl. 22 (2000), no. 1, 306–321. MR 1779731, DOI 10.1137/S089547989935527X
- Arno B. J. Kuijlaars, Convergence analysis of Krylov subspace iterations with methods from potential theory, SIAM Rev. 48 (2006), no. 1, 3–40. MR 2219308, DOI 10.1137/S0036144504445376
- Ren Cang Li, On eigenvalues of a Rayleigh quotient matrix, Linear Algebra Appl. 169 (1992), 249–255. MR 1158372, DOI 10.1016/0024-3795(92)90181-9
- Ren-Cang Li, Accuracy of computed eigenvectors via optimizing a Rayleigh quotient, BIT 44 (2004), no. 3, 585–593. MR 2106018, DOI 10.1023/B:BITN.0000046798.28622.67
- —, Sharpness in rates of convergence for CG and symmetric Lanczos methods, Technical Report 2005-01, Department of Mathematics, University of Kentucky, 2005, Avaliable at http://www.ms.uky.edu/$\sim$math/MAreport/.
- Ren-Cang Li, Vandermonde matrices with Chebyshev nodes, Linear Algebra Appl. 428 (2008), no. 8-9, 1803–1832. MR 2398120, DOI 10.1016/j.laa.2007.10.029
- Ren-Cang Li, On Meinardus’ examples for the conjugate gradient method, Math. Comp. 77 (2008), no. 261, 335–352. MR 2353956, DOI 10.1090/S0025-5718-07-01922-9
- J. Liesen, M. Rozložník, and Z. Strakoš, Least squares residuals and minimal residual methods, SIAM J. Sci. Comput. 23 (2002), no. 5, 1503–1525. MR 1885072, DOI 10.1137/S1064827500377988
- Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR 570116
- Y. Saad, On the rates of convergence of the Lanczos and the block-Lanczos methods, SIAM J. Numer. Anal. 17 (1980), no. 5, 687–706. MR 588755, DOI 10.1137/0717059
- Yousef Saad, Iterative methods for sparse linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR 1990645, DOI 10.1137/1.9780898718003
- D. S. Scott, How to make the Lanczos algorithm converge slowly, Math. Comp. 33 (1979), no. 145, 239–247. MR 514821, DOI 10.1090/S0025-5718-1979-0514821-5
- G. L. G. Sleijpen and A. van der Sluis, Further results on the convergence behavior of conjugate-gradients and Ritz values, Linear Algebra Appl. 246 (1996), 233–278. MR 1407670, DOI 10.1016/0024-3795(94)00360-2
- Ji Guang Sun, Eigenvalues of Rayleigh quotient matrices, Numer. Math. 59 (1991), no. 6, 603–614. MR 1124130, DOI 10.1007/BF01385798
- Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820, DOI 10.1137/1.9780898719574
- A. van der Sluis and H. A. van der Vorst, The convergence behavior of Ritz values in the presence of close eigenvalues, Linear Algebra Appl. 88/89 (1987), 651–694. MR 882466, DOI 10.1016/0024-3795(87)90129-7
Additional Information
- Ren-Cang Li
- Affiliation: Department of Mathematics, University of Texas at Arlington, P.O. Box 19408, Arlington, Texas 76019-0408.
- Email: rcli@uta.edu
- Received by editor(s): July 31, 2006
- Received by editor(s) in revised form: January 14, 2008, and January 6, 2009
- Published electronically: May 14, 2009
- Additional Notes: This work was supported in part by the National Science Foundation under Grant No. DMS-0702335 and DMS-0810506.
- © Copyright 2009 American Mathematical Society
- Journal: Math. Comp. 79 (2010), 419-435
- MSC (2000): Primary 65F10
- DOI: https://doi.org/10.1090/S0025-5718-09-02258-3
- MathSciNet review: 2552233