Convergence of the shifted algorithm for unitary Hessenberg matrices

Authors:
Tai-Lin Wang and William B. Gragg

Journal:
Math. Comp. **71** (2002), 1473-1496

MSC (2000):
Primary 65F15, 15A18

Published electronically:
November 30, 2001

MathSciNet review:
1933041

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper shows that for unitary Hessenberg matrices the 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.

**1.**H. Bowdler, R. S. Martin, C. Reinsch, and J. H. Wilkinson,*The and algorithms for symmetric matrices*, Numer. Math.**11**(1968), 293-306.**2.**Hendrik Jan Buurema,*A geometric proof of convergence for the 𝑄𝑅 method*, Rijksuniversiteit te Groningen, Groningen, 1970. Doctoral dissertation, University of Groningen. MR**0383717****3.**T. J. Dekker and J. F. Traub,*The shifted 𝑄𝑅 algorithm for Hermitian matrices*, Linear Algebra and Appl.**4**(1971), 137–154. MR**0283977****4.**P. J. Eberlein and C. P. Huang,*Global convergence of the 𝑄𝑅 algorithm for unitary matrices with some results for normal matrices*, SIAM J. Numer. Anal.**12**(1975), 97–104. MR**0356478****5.**J. G. F. Francis,*The 𝑄𝑅 transformation. II*, Comput. J.**4**(1961/1962), 332–345. MR**0137289****6.**W. B. Gragg,*The algorithm for unitary Hessenberg matrices*, J. Comput. Appl. Math.**16**(1986), 1-8.**7.**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**, 10.1016/0377-0427(93)90294-L**8.**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**, 10.1137/0715060**9.**Hou De Han,*Nonconforming elements in the mixed finite element method*, J. Comput. Math.**2**(1984), no. 3, 223–233. MR**815417****10.**Er Xiong Jiang and Zhen Yue Zhang,*A new shift of the 𝑄𝐿 algorithm for irreducible symmetric tridiagonal matrices*, Linear Algebra Appl.**65**(1985), 261–272. MR**774356**, 10.1016/0024-3795(85)90101-6**11.**Beresford Parlett,*Singular and invariant matrices under the 𝑄𝑅 transformation*, Math. Comp.**20**(1966), 611–615. MR**0213005**, 10.1090/S0025-5718-1966-0213005-9**12.**B. N. Parlett,*The Rayleigh quotient iteration and some generalizations for nonnormal matrices*, Math. Comp.**28**(1974), 679–693. MR**0405823**, 10.1090/S0025-5718-1974-0405823-3**13.**Beresford N. Parlett,*The symmetric eigenvalue problem*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. Prentice-Hall Series in Computational Mathematics. MR**570116****14.**T.-L. Wang,*Convergence of the algorithm with origin shifts for real symmetric tridiagonal and unitary Hessenberg matrices*, Ph.D. thesis, University of Kentucky, Lexington, Kentucky, 1988.**15.**T.-L. Wang and W. B. Gragg,*Convergence of the shifted algorithm for unitary Hessenberg matrices*, Technical Report NPS-53-90-007, Naval Postgraduate School, Monterey, California, 1990.**16.**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**, 10.1016/0024-3795(91)90004-G**17.**J. H. Wilkinson,*The Algebraic Eigenvalue Problem*, Clarendon Press, Oxford, 1965.**18.**J. H. Wilkinson,*Global convergence of tridiagonal 𝑄𝑅 algorithm with origin shifts*, Linear Algebra and Appl.**1**(1968), 409–420. MR**0234622**

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

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

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

DOI:
https://doi.org/10.1090/S0025-5718-01-01387-4

Keywords:
$QR$ algorithm,
shift strategy,
unitary Hessenberg matrices

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

Dedicated:
Dedicated to the memory of James H. Wilkinson

Article copyright:
© Copyright 2001
American Mathematical Society