Convergence of the shifted $QR$ algorithm for unitary Hessenberg matrices
HTML articles powered by AMS MathViewer
- by Tai-Lin Wang and William B. Gragg PDF
- Math. Comp. 71 (2002), 1473-1496 Request permission
Abstract:
This paper shows that for unitary Hessenberg matrices the $Q\!R$ algorithm, with (an exceptional initial-value modification of) the Wilkinson shift, gives global convergence; moreover, the asymptotic rate of convergence is at least cubic, higher than that which can be shown to be quadratic only for Hermitian tridiagonal matrices, under no further assumption. A general mixed shift strategy with global convergence and cubic rates is also presented.References
- H. Bowdler, R. S. Martin, C. Reinsch, and J. H. Wilkinson, The $Q\!R$ and $Q\!L$ algorithms for symmetric matrices, Numer. Math. 11 (1968), 293-306.
- Hendrik Jan Buurema, A geometric proof of convergence for the $QR$ method, Rijksuniversiteit te Groningen, Groningen, 1970. Doctoral dissertation, University of Groningen. MR 0383717
- T. J. Dekker and J. F. Traub, The shifted $QR$ algorithm for Hermitian matrices, Linear Algebra Appl. 4 (1971), 137–154. MR 283977, DOI 10.1016/0024-3795(71)90035-8
- 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
- J. G. F. Francis, The $QR$ transformation. II, Comput. J. 4 (1961/62), 332–345. MR 137289, DOI 10.1093/comjnl/4.4.332
- 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
- W. Hoffmann and B. N. Parlett, A new proof of global convergence for the tridiagonal QL algorithm, SIAM J. Numer. Anal. 15 (1978), no. 5, 929–937. MR 507555, DOI 10.1137/0715060
- Hou De Han, Nonconforming elements in the mixed finite element method, J. Comput. Math. 2 (1984), no. 3, 223–233. MR 815417
- 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
- Beresford Parlett, Singular and invariant matrices under the $QR$ transformation, Math. Comp. 20 (1966), 611–615. MR 213005, DOI 10.1090/S0025-5718-1966-0213005-9
- B. N. Parlett, The Rayleigh quotient iteration and some generalizations for nonnormal matrices, Math. Comp. 28 (1974), 679–693. MR 405823, DOI 10.1090/S0025-5718-1974-0405823-3
- 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, Kentucky, 1988.
- T.-L. Wang and W. B. Gragg, Convergence of the shifted $Q\!R$ algorithm for unitary Hessenberg matrices, Technical Report NPS-53-90-007, Naval Postgraduate School, Monterey, California, 1990.
- D. S. Watkins and L. Elsner, Convergence of algorithms of decomposition type for the eigenvalue problem, Linear Algebra Appl. 143 (1991), 19–47. MR 1077722, DOI 10.1016/0024-3795(91)90004-G
- J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965.
- 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): March 9, 1999
- Received by editor(s) in revised form: January 6, 2000, and November 7, 2000
- Published electronically: November 30, 2001
- Additional Notes: The research of the first author was supported by the Center for Computational Sciences at the University of Kentucky
The research of the second author was supported in part by the National Science Foundation under grant DMS-8704196 - © Copyright 2001 American Mathematical Society
- Journal: Math. Comp. 71 (2002), 1473-1496
- MSC (2000): Primary 65F15, 15A18
- DOI: https://doi.org/10.1090/S0025-5718-01-01387-4
- MathSciNet review: 1933041
Dedicated: Dedicated to the memory of James H. Wilkinson