Convergence of the unitary algorithm with a unimodular Wilkinson shift
Authors:
TaiLin Wang and William B. Gragg
Journal:
Math. Comp. 72 (2003), 375385
MSC (2000):
Primary 65F15, 15A18
Published electronically:
June 25, 2002
MathSciNet review:
1933826
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In applying the 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 iteration. Experimental testing demonstrates that the unimodular shift produces more efficient numerical convergence.
 1.
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), 97104. MR 50:8948
 2.
W. B. Gragg, The algorithm for unitary Hessenberg matrices, J. Comput. Appl. Math. 16 (1986), 18.
 3.
W. 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), 183198. MR 94e:65046
 4.
E. Jiang and Z. Zhang, A new shift of the algorithm for irreducible symmetric tridiagonal matrices, Linear Algebra Appl. 65 (1985), 261272. MR 86g:65082
 5.
R. S. Martin, G. Peters, and J. H. Wilkinson, The algorithm for real Hessenberg matrices, Numer. Math. 14 (1970), 219231.
 6.
B. N. Parlett, The Symmetric Eigenvalue Problem, PrenticeHall, Englewood Cliffs, NJ, 1980. MR 81j:65063
 7.
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, KY, 1988.
 8.
T.L. Wang, Convergence of the tridiagonal algorithm, Linear Algebra Appl. 322 (2001), 117.
 9.
T.L. Wang and W. B. Gragg, Convergence of the shifted algorithm for unitary Hessenberg matrices , to appear in Math. Comp.
 10.
T.L. Wang and W. B. Gragg, Convergence of the unitary Hessenberg algorithm with unimodular shifts, Report NPS5390008, Naval Postgraduate School, Monterey, CA, 1990.
 11.
J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. MR 32:1894
 12.
J. H. Wilkinson, Global convergence of tridiagonal algorithm with origin shifts, Linear Algebra Appl. 1 (1968), 409420. MR 38:2938
 1.
 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), 97104. MR 50:8948
 2.
 W. B. Gragg, The algorithm for unitary Hessenberg matrices, J. Comput. Appl. Math. 16 (1986), 18.
 3.
 W. 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), 183198. MR 94e:65046
 4.
 E. Jiang and Z. Zhang, A new shift of the algorithm for irreducible symmetric tridiagonal matrices, Linear Algebra Appl. 65 (1985), 261272. MR 86g:65082
 5.
 R. S. Martin, G. Peters, and J. H. Wilkinson, The algorithm for real Hessenberg matrices, Numer. Math. 14 (1970), 219231.
 6.
 B. N. Parlett, The Symmetric Eigenvalue Problem, PrenticeHall, Englewood Cliffs, NJ, 1980. MR 81j:65063
 7.
 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, KY, 1988.
 8.
 T.L. Wang, Convergence of the tridiagonal algorithm, Linear Algebra Appl. 322 (2001), 117.
 9.
 T.L. Wang and W. B. Gragg, Convergence of the shifted algorithm for unitary Hessenberg matrices , to appear in Math. Comp.
 10.
 T.L. Wang and W. B. Gragg, Convergence of the unitary Hessenberg algorithm with unimodular shifts, Report NPS5390008, Naval Postgraduate School, Monterey, CA, 1990.
 11.
 J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. MR 32:1894
 12.
 J. H. Wilkinson, Global convergence of tridiagonal algorithm with origin shifts, Linear Algebra Appl. 1 (1968), 409420. MR 38:2938
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
65F15,
15A18
Retrieve articles in all journals
with MSC (2000):
65F15,
15A18
Additional Information
TaiLin 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:
http://dx.doi.org/10.1090/S0025571802014448
PII:
S 00255718(02)014448
Keywords:
$QR$ algorithm,
shift strategy,
unitary Hessenberg matrices
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 DMS8704196
Article copyright:
© Copyright 2002
American Mathematical Society
