Convergence of the unitary $QR$ algorithm with a unimodular Wilkinson shift
HTML articles powered by AMS MathViewer
- by Tai-Lin Wang and William B. Gragg PDF
- Math. Comp. 72 (2003), 375-385 Request permission
Abstract:
In applying the $Q\!R$ algorithm to compute the eigenvalues of a unitary Hessenberg matrix, a projected Wilkinson shift of unit modulus is proposed and proved to give global convergence with (at least) a quadratic asymptotic rate for the $Q\!R$ iteration. Experimental testing demonstrates that the unimodular shift produces more efficient numerical convergence.References
- P. J. Eberlein and C. P. Huang, Global convergence of the $\textrm {QR}$ algorithm for unitary matrices with some results for normal matrices, SIAM J. Numer. Anal. 12 (1975), 97β104. MR 356478, DOI 10.1137/0712009
- W. B. Gragg, The $Q\!R$ algorithm for unitary Hessenberg matrices, J. Comput. Appl. Math. 16 (1986), 1-8.
- William B. Gragg, Positive definite Toeplitz matrices, the Arnoldi process for isometric operators, and Gaussian quadrature on the unit circle, J. Comput. Appl. Math. 46 (1993), no.Β 1-2, 183β198. Computational complex analysis. MR 1222480, DOI 10.1016/0377-0427(93)90294-L
- Er Xiong Jiang and Zhen Yue Zhang, A new shift of the $QL$ algorithm for irreducible symmetric tridiagonal matrices, Linear Algebra Appl. 65 (1985), 261β272. MR 774356, DOI 10.1016/0024-3795(85)90101-6
- R. S. Martin, G. Peters, and J. H. Wilkinson, The $Q\!R$ algorithm for real Hessenberg matrices, Numer. Math. 14 (1970), 219-231.
- Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR 570116
- T.-L. Wang, Convergence of the $Q\!R$ algorithm with origin shifts for real symmetric tridiagonal and unitary Hessenberg matrices, Ph.D. thesis, University of Kentucky, Lexington, KY, 1988.
- T.-L. Wang, Convergence of the tridiagonal $Q\!R$ algorithm, Linear Algebra Appl. 322 (2001), 1-17.
- T.-L. Wang and W. B. Gragg, Convergence of the shifted $Q\!R$ algorithm for unitary Hessenberg matrices , to appear in Math. Comp.
- T.-L. Wang and W. B. Gragg, Convergence of the unitary Hessenberg $Q\!R$ algorithm with unimodular shifts, Report NPS-53-90-008, Naval Postgraduate School, Monterey, CA, 1990.
- J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
- J. H. Wilkinson, Global convergence of tridiagonal $\textrm {QR}$ algorithm with origin shifts, Linear Algebra Appl. 1 (1968), 409β420. MR 234622, DOI 10.1016/0024-3795(68)90017-7
Additional Information
- Tai-Lin Wang
- Affiliation: Department of Mathematical Sciences, National Chengchi University, Taipei, Taiwan, Republic of China
- Email: wang@math.nccu.edu.tw
- William B. Gragg
- Affiliation: Department of Mathematics, Naval Postgraduate School, Monterey, California 93943
- Email: gragg@nps.navy.mil
- Received by editor(s): May 5, 1999
- Received by editor(s) in revised form: April 3, 2001
- Published electronically: June 25, 2002
- Additional Notes: The first authorβs research was supported by the Center for Computational Sciences at the University of Kentucky
The second authorβs research was supported in part by the National Science Foundation under grant DMS-8704196 - © Copyright 2002 American Mathematical Society
- Journal: Math. Comp. 72 (2003), 375-385
- MSC (2000): Primary 65F15, 15A18
- DOI: https://doi.org/10.1090/S0025-5718-02-01444-8
- MathSciNet review: 1933826