An analysis of the Rayleigh-Ritz method for approximating eigenspaces
Authors:
Zhongxiao Jia and G. W. Stewart
Journal:
Math. Comp. 70 (2001), 637-647
MSC (2000):
Primary 15A18, 65F15, 65F50
DOI:
https://doi.org/10.1090/S0025-5718-00-01208-4
Published electronically:
February 18, 2000
MathSciNet review:
1697647
Full-text PDF
Abstract | References | Similar Articles | Additional Information
This paper concerns the Rayleigh-Ritz method for computing an approximation to an eigenspace of a general matrix
from a subspace
that contains an approximation to
. The method produces a pair
that purports to approximate a pair
, where
is a basis for
and
. In this paper we consider the convergence of
as the sine
of the angle between
and
approaches zero. It is shown that under a natural hypothesis--called the uniform separation condition--the Ritz pairs
converge to the eigenpair
. When one is concerned with eigenvalues and eigenvectors, one can compute certain refined Ritz vectors whose convergence is guaranteed, even when the uniform separation condition is not satisfied. An attractive feature of the analysis is that it does not assume that
has distinct eigenvalues or is diagonalizable.
- 1. R. Bhatia, L. Elsner, and G. Krause, Bounds for the variation of the roots of a polynomial and the eigenvalues of a matrix, Linear Algebra and Its Applications 142 (1990), 195-209. MR 92i:12001
- 2. L. Elsner, An optimal bound for the spectral variation of two matrices, Linear Algebra and Its Applications 71 (1985), 77-80. MR 87c:15035
- 3. G. H. Golub and C. F. Van Loan, Matrix computations, second ed., Johns Hopkins University Press, Baltimore, MD, 1989. MR 90d:65055
- 4. I. C. F. Ipsen, Absolute and relative perturbation bounds for invariant subspaces of matrices, Technical Report TR97-35, Center for Research in Scientific Computation, Mathematics Department, North Carolina State Unversity, 1998.
- 5. Z. Jia, Some numerical methods for large unsymmetric eigenproblems, Ph.D. thesis, University of Bielefeld, 1994.
- 6. -, The convergence of generalized Lanczos methods for large unsymmetric eigenproblems, SIAM Journal on Matrix Analysis and Applications 16 (1995), 843-862. MR 96d:65062
- 7. -, Refined iterative algorithm based on Arnoldi's process for large unsymmetric eigenproblems, Linear Algebra and Its Applications 259 (1997), 1-23. MR 98c:65060
- 8. -, Generalized block Lanczos methods for large unsymmetric eigenproblems, Numerische Mathematik 80 (1998), 171-189. MR 95f:65059
- 9. -, A refined iterative algorithm based on the block Arnoldi algorithm, Linear Algebra and Its Applications 270 (1998), 171-189. MR 98m:65055
- 10. -, Polynomial characterizations of the approximate eigenvectors by the refined Arnoldi method and an implicitly restarted refined Arnoldi algorithm, Linear Algebra and Its Applications 287 (1999), 191-214. MR 99j:65046
- 11. -, A refined subspace iteration algorithm for large sparse eigenproblems, To appear in Applied Numerical Mathemtics., 1999.
- 12. Y. Saad, Numerical methods for large eigenvalue problems: Theory and algorithms, John Wiley, New York, 1992. MR 93h:65052
- 13. G. L. G. Sleijpen and H. A. Van der Vorst, A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM Journal on Matrix Analysis and Applications 17 (1996), 401-425. MR 96m:65042
- 14. G. W. Stewart and J.-G. Sun, Matrix perturbation theory, Academic Press, New York, 1990. MR 92a:65017
Retrieve articles in Mathematics of Computation with MSC (2000): 15A18, 65F15, 65F50
Retrieve articles in all journals with MSC (2000): 15A18, 65F15, 65F50
Additional Information
Zhongxiao Jia
Affiliation:
Department of Applied Mathematics, Dalian University of Technology, Dalian 116024, P.R. China
Email:
zxjia@dlut.edu.cn
G. W. Stewart
Affiliation:
Department of Computer Science, Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742, USA
Email:
stewart@cs.umd.edu
DOI:
https://doi.org/10.1090/S0025-5718-00-01208-4
Received by editor(s):
April 9, 1998
Received by editor(s) in revised form:
May 5, 1999
Published electronically:
February 18, 2000
Additional Notes:
The first author’s work was supported by the China State Major Key Project for Basic Researches, the National Natural Science Foundation of China, the Foundation for Excellent Young Scholars of the Ministry of Education and the Doctoral Point Program of the Ministry of Education, China.
The second author’s work was supported by the National Science Foundation under Grant No. 970909-8562.
Article copyright:
© Copyright 2000
American Mathematical Society