ISSN 1088-6842(online) ISSN 0025-5718(print)

The convergence of harmonic Ritz values, harmonic Ritz vectors, and refined harmonic Ritz vectors

Author: Zhongxiao Jia
Journal: Math. Comp. 74 (2005), 1441-1456
MSC (2000): Primary 15A18, 65F15, 65F30
DOI: https://doi.org/10.1090/S0025-5718-04-01684-9
Published electronically: June 1, 2004
MathSciNet review: 2137011
Full-text PDF

Abstract: This paper concerns a harmonic projection method for computing an approximation to an eigenpair of a large matrix . Given a target point and a subspace that contains an approximation to , the harmonic projection method returns an approximation to . Three convergence results are established as the deviation of from approaches zero. First, the harmonic Ritz value converges to if a certain Rayleigh quotient matrix is uniformly nonsingular. Second, the harmonic Ritz vector converges to if the Rayleigh quotient matrix is uniformly nonsingular and remains well separated from the other harmonic Ritz values. Third, better error bounds for the convergence of are derived when converges. However, we show that the harmonic projection method can fail to find the desired eigenvalue --in other words, the method can miss if it is very close to . To this end, we propose to compute the Rayleigh quotient of with respect to and take it as a new approximate eigenvalue. is shown to converge to once tends to , no matter how is close to . Finally, we show that if the Rayleigh quotient matrix is uniformly nonsingular, then the refined harmonic Ritz vector, or more generally the refined eigenvector approximation introduced by the author, converges. We construct examples to illustrate our theory.

References [Enhancements On Off] (What's this?)

• 1. R. W. Freund. Quasi-kernel polynomials and their use in non-Hermitian matrix iterations, J. Comput. Appl. Math., 43 (1992): 135-158. MR 94a:65018
• 2. G. H. Golub and C. F. van Loan. Matrix Computations, the 3rd ed., The Johns Hopkins University Press, Baltimore and London, 1996. MR 97g:65006
• 3. Z. Jia. The convergence of generalized Lanczos methods for large unsymmetric eigenproblems, SIAM J. Matrix Anal. Appl., 16 (1995): 843-862. MR 96d:65062
• 4. Z. Jia. Refined iterative algorithms based on Arnoldi's process for large unsymmetric eigenproblems, Linear Algebra Appl., 259 (1997): 1-23. MR 98c:65060
• 5. Z. Jia. A refined iterative algorithm based on the block Arnoldi process for large unsymmetric eigenproblems, Linear Algebra Appl., 270 (1998): 171-189. MR 98m:65055
• 6. Z. Jia. Generalized block Lanczos methods for large unsymmetric eigenproblems, Numer. Math., 80 (1998): 239-266. MR 99f:65059
• 7. Z. Jia. Polynomial characterizations of the approximate eigenvectors by the refined Arnoldi method and an implicitly restarted refined Arnoldi algorithm, Linear Algebra Appl., 287 (1999): 191-214. MR 99j:65046
• 8. Z. Jia. Composite orthogonal projection methods for large matrix eigenproblems, Science in China, Ser.A, 42 (1999): 577-585. MR 2000b:65056
• 9. Z. Jia. A refined subspace iteration algorithm for large sparse eigenproblems, Appl. Numer. Math., 32 (2000): 35-52. MR 2000j:65045
• 10. Z. Jia. The refined harmonic Arnoldi method and an implicitly restarted refined algorithm for computing interior eigenpairs of large matrices, Appl. Numer. Math., 42 (2002): 489-512. MR 2003g:65049
• 11. Z. Jia. Some theoretical comparisons of refined Ritz vectors and Ritz vectors, Science in China, Ser.A, 47 (Supp.) (2004): 222-233.
• 12. Z. Jia and G. W. Stewart. An analysis of the Rayleigh-Ritz method for approximating eigenspaces, Math. Comput., 70 (2001): 637-647. MR 2001g:65040
• 13. Z. Jia and D. Niu. An implicitly restarted refined bidiagonalization Lanczos algorithm for computing a partial singular value decomposition, SIAM J. Matrix Anal. Appl., 25 (2003): 246-265.
• 14. T. A. Manteuffel and J. Otto. On the roots of orthogonal polynomials and residual polynomials associated with a conjugate gradient method, Numer. Linear Algebra Appl., 1 (1994): 449-475. MR 95i:65051
• 15. R. B. Morgan. Computing interior eigenvalues of large matrices, Linear Algebra Appl., 154/156 (1991): 289-309. MR 92e:65050
• 16. R. B. Morgan and M. Zeng. Harmonic projection methods for large nonsymmetric eigenvalue problems, Numer. Linear Algebra Appl., 5 (1998): 35-55. MR 99g:65046
• 17. C. C. Paige, B. N. Parlett and H. A. van der Vorst. Approximate solutions and eigenvalue bounds from Krylov subspaces, Numer. Linear Algebra Appl., 2 (1995): 115-134. MR 96a:65054
• 18. B. N. Parlett. The Symmetric Eigenvalue Problem, SIAM, Philadelphia, PA, 1998. MR 99c:65072
• 19. Y. Saad. Numerical Methods for Large Eigenvalue Problems, Manchester University Press, 1992. MR 93h:65052
• 20. G. L. G. Sleijpen and H. A. van der Vorst. A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl., 17 (1996): 401-425. MR 96m:65042
• 21. G. L. G. Sleijpen, H. A. van der Vorst and E. Meijerink. Efficient expansion of subspaces in the Jacobi-Davidson method for standard and generalized eigenproblems, Electr. Trans. Numer. Anal., 7 (1998): 75-89. MR 99i:65040
• 22. G. W. Stewart. Matrix Algorithms: Vol. II Eigensystems, SIAM, Philadelphia, PA, 2001.
• 23. G. W. Stewart and J.-G Sun. Matrix Perturbation Theory, Academic Press, New York, 1990. MR 92a:65017
• 24. H. A. van der Vorst. Computational Methods for Large Eigenvalue Problems, In P.G. Ciarlet and J.L. Lions (eds), Handbook of Numerical Analysis, Volume VIII, North-Holand (Elsevier), Amsterdam, 2002, pp. 3-179. MR 2003e:65058

Retrieve articles in Mathematics of Computation with MSC (2000): 15A18, 65F15, 65F30

Retrieve articles in all journals with MSC (2000): 15A18, 65F15, 65F30