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

HTML articles powered by AMS MathViewer

- by Zhongxiao Jia PDF
- Math. Comp.
**74**(2005), 1441-1456 Request permission

## Abstract:

This paper concerns a harmonic projection method for computing an approximation to an eigenpair $(\lambda , x)$ of a large matrix $A$. Given a target point $\tau$ and a subspace $\mathcal {W}$ that contains an approximation to $x$, the harmonic projection method returns an approximation $(\mu +\tau , \tilde x)$ to $(\lambda ,x)$. Three convergence results are established as the deviation $\epsilon$ of $x$ from $\mathcal {W}$ approaches zero. First, the harmonic Ritz value $\mu +\tau$ converges to $\lambda$ if a certain Rayleigh quotient matrix is uniformly nonsingular. Second, the harmonic Ritz vector $\tilde x$ converges to $x$ if the Rayleigh quotient matrix is uniformly nonsingular and $\mu +\tau$ remains well separated from the other harmonic Ritz values. Third, better error bounds for the convergence of $\mu +\tau$ are derived when $\tilde x$ converges. However, we show that the harmonic projection method can fail to find the desired eigenvalue $\lambda$—in other words, the method can miss $\lambda$ if it is very close to $\tau$. To this end, we propose to compute the Rayleigh quotient $\rho$ of $A$ with respect to $\tilde x$ and take it as a new approximate eigenvalue. $\rho$ is shown to converge to $\lambda$ once $\tilde x$ tends to $x$, no matter how $\tau$ is close to $\lambda$. 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

- Roland W. Freund,
*Quasi-kernel polynomials and their use in non-Hermitian matrix iterations*, J. Comput. Appl. Math.**43**(1992), no. 1-2, 135–158. Orthogonal polynomials and numerical methods. MR**1193298**, DOI 10.1016/0377-0427(92)90263-W - Gene H. Golub and Charles F. Van Loan,
*Matrix computations*, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR**1417720** - Zhong Xiao Jia,
*The convergence of generalized Lanczos methods for large unsymmetric eigenproblems*, SIAM J. Matrix Anal. Appl.**16**(1995), no. 3, 843–862. MR**1337649**, DOI 10.1137/S0895479893246753 - Zhongxiao Jia,
*Refined iterative algorithms based on Arnoldi’s process for large unsymmetric eigenproblems*, Linear Algebra Appl.**259**(1997), 1–23. MR**1450527**, DOI 10.1016/S0024-3795(96)00238-8 - Zhongxiao Jia,
*A refined iterative algorithm based on the block Arnoldi process for large unsymmetric eigenproblems*, Linear Algebra Appl.**270**(1998), 171–189. MR**1484080** - Zhongxiao Jia,
*Generalized block Lanczos methods for large unsymmetric eigenproblems*, Numer. Math.**80**(1998), no. 2, 239–266. MR**1645025**, DOI 10.1007/s002110050367 - Zhongxiao Jia,
*Polynomial characterizations of the approximate eigenvectors by the refined Arnoldi method and an implicitly restarted refined Arnoldi algorithm*, Linear Algebra Appl.**287**(1999), no. 1-3, 191–214. Special issue celebrating the 60th birthday of Ludwig Elsner. MR**1662868**, DOI 10.1016/S0024-3795(98)10197-0 - U. Meier Yang and K. A. Gallivan,
*A new family of block methods*, Appl. Numer. Math.**30**(1999), no. 2-3, 155–173. Iterative methods and preconditioners (Berlin, 1997). MR**1688622**, DOI 10.1016/S0168-9274(98)00108-1 - Zhongxiao Jia,
*A refined subspace iteration algorithm for large sparse eigenproblems*, Appl. Numer. Math.**32**(2000), no. 1, 35–52. MR**1724408**, DOI 10.1016/S0168-9274(99)00008-2 - Zhongxiao Jia,
*The refined harmonic Arnoldi method and an implicitly restarted refined algorithm for computing interior eigenpairs of large matrices*, Appl. Numer. Math.**42**(2002), no. 4, 489–512. MR**1925329**, DOI 10.1016/S0168-9274(01)00132-5 - Z. Jia.
*Some theoretical comparisons of refined Ritz vectors and Ritz vectors*, Science in China, Ser.A, 47 (Supp.) (2004): 222–233. - 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 - 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. - Thomas A. Manteuffel and James S. Otto,
*On the roots of the orthogonal polynomials and residual polynomials associated with a conjugate gradient method*, Numer. Linear Algebra Appl.**1**(1994), no. 5, 449–475. MR**1307329**, DOI 10.1002/nla.1680010503 - Ronald B. Morgan,
*Computing interior eigenvalues of large matrices*, Linear Algebra Appl.**154/156**(1991), 289–309. MR**1113147**, DOI 10.1016/0024-3795(91)90381-6 - Ronald B. Morgan and Min Zeng,
*Harmonic projection methods for large non-symmetric eigenvalue problems*, Numer. Linear Algebra Appl.**5**(1998), no. 1, 33–55. MR**1618785**, DOI 10.1002/(SICI)1099-1506(199801/02)5:1<33::AID-NLA125>3.0.CO;2-1 - Chris C. Paige, Beresford N. Parlett, and Henk A. van der Vorst,
*Approximate solutions and eigenvalue bounds from Krylov subspaces*, Numer. Linear Algebra Appl.**2**(1995), no. 2, 115–133. MR**1323816**, DOI 10.1002/nla.1680020205 - Beresford N. Parlett,
*The symmetric eigenvalue problem*, Classics in Applied Mathematics, vol. 20, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Corrected reprint of the 1980 original. MR**1490034**, DOI 10.1137/1.9781611971163 - Youcef Saad,
*Numerical methods for large eigenvalue problems*, Algorithms and Architectures for Advanced Scientific Computing, Manchester University Press, Manchester; Halsted Press [John Wiley & Sons, Inc.], New York, 1992. MR**1177405** - Gerard L. G. Sleijpen and Henk A. Van der Vorst,
*A Jacobi-Davidson iteration method for linear eigenvalue problems*, SIAM J. Matrix Anal. Appl.**17**(1996), no. 2, 401–425. MR**1384515**, DOI 10.1137/S0895479894270427 - Gerard L. G. Sleijpen, Henk A. van der Vorst, and Ellen Meijerink,
*Efficient expansion of subspaces in the Jacobi-Davidson method for standard and generalized eigenproblems*, Electron. Trans. Numer. Anal.**7**(1998), 75–89. Large scale eigenvalue problems (Argonne, IL, 1997). MR**1667640** - G. W. Stewart.
*Matrix Algorithms: Vol. II Eigensystems*, SIAM, Philadelphia, PA, 2001. - G. W. Stewart and Ji Guang Sun,
*Matrix perturbation theory*, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR**1061154** - Henk A. van der Vorst,
*Computational methods for large eigenvalue problems*, Handbook of numerical analysis, Vol. VIII, Handb. Numer. Anal., VIII, North-Holland, Amsterdam, 2002, pp. 3–179. MR**1893417**

## Additional Information

**Zhongxiao Jia**- Affiliation: Department of Mathematical Sciences, Tsinghua University, Beijing 100084, Peoples Republic of China
- Email: zjia@math.tsinghua.edu.cn
- Received by editor(s): June 7, 2002
- Received by editor(s) in revised form: December 23, 2003
- Published electronically: June 1, 2004
- Additional Notes: Work supported by Special Funds for the State Major Basic Research Projects (G1999032805)
- © Copyright 2004 American Mathematical Society
- Journal: Math. Comp.
**74**(2005), 1441-1456 - MSC (2000): Primary 15A18, 65F15, 65F30
- DOI: https://doi.org/10.1090/S0025-5718-04-01684-9
- MathSciNet review: 2137011