Convergence of the shifted algorithm for unitary Hessenberg matrices
Authors:
TaiLin Wang and William B. Gragg
Journal:
Math. Comp. 71 (2002), 14731496
MSC (2000):
Primary 65F15, 15A18
Published electronically:
November 30, 2001
MathSciNet review:
1933041
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: This paper shows that for unitary Hessenberg matrices the algorithm, with (an exceptional initialvalue 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), 293306.
 2.
Hendrik
Jan Buurema, A geometric proof of convergence for the
𝑄𝑅 method, Rijksuniversiteit te Groningen, Groningen,
1970. Doctoral dissertation, University of Groningen. MR 0383717
(52 #4597)
 3.
T.
J. Dekker and J.
F. Traub, The shifted 𝑄𝑅 algorithm for Hermitian
matrices, Linear Algebra and Appl. 4 (1971),
137–154. MR 0283977
(44 #1207)
 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
(50 #8948)
 5.
J.
G. F. Francis, The 𝑄𝑅 transformation. II,
Comput. J. 4 (1961/1962), 332–345. MR 0137289
(25 #744)
 6.
W. B. Gragg, The algorithm for unitary Hessenberg matrices, J. Comput. Appl. Math. 16 (1986), 18.
 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. 12,
183–198. Computational complex analysis. MR 1222480
(94e:65046), http://dx.doi.org/10.1016/03770427(93)90294L
 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
(80a:65075), http://dx.doi.org/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 (87d:65130)
 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
(86g:65082), http://dx.doi.org/10.1016/00243795(85)901016
 11.
Beresford
Parlett, Singular and invariant matrices under
the 𝑄𝑅 transformation, Math.
Comp. 20 (1966),
611–615. MR 0213005
(35 #3870), http://dx.doi.org/10.1090/S00255718196602130059
 12.
B.
N. Parlett, The Rayleigh quotient iteration and
some generalizations for nonnormal matrices, Math. Comp. 28 (1974), 679–693. MR 0405823
(53 #9615), http://dx.doi.org/10.1090/S00255718197404058233
 13.
Beresford
N. Parlett, The symmetric eigenvalue problem, PrenticeHall,
Inc., Englewood Cliffs, N.J., 1980. PrenticeHall Series in Computational
Mathematics. MR
570116 (81j:65063)
 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 NPS5390007, 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 (91m:65114), http://dx.doi.org/10.1016/00243795(91)90004G
 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
(38 #2938)
 1.
 H. Bowdler, R. S. Martin, C. Reinsch, and J. H. Wilkinson, The and algorithms for symmetric matrices, Numer. Math. 11 (1968), 293306.
 2.
 H. J. Buurema, A geometric proof of convergence for the method, doctoral dissertation, Rijksuniversiteit Te Groningen, Groningen, The Netherlands, 1970. MR 52:4597
 3.
 T. J. Dekker and J. F. Traub, The shifted algorithm for Hermitian matrices, Linear Algebra Appl. 4 (1971), 137154. MR 44:1207
 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), 97104. MR 50:8948
 5.
 J. G. F. Francis, The transformation. I, II, Comput. J. 4 (19611962), 265271, 332345. MR 25:744
 6.
 W. B. Gragg, The algorithm for unitary Hessenberg matrices, J. Comput. Appl. Math. 16 (1986), 18.
 7.
 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
 8.
 W. Hoffmann and B. N. Parlett, A new proof of global convergence for the tridiagonal algorithm, SIAM J. Numer. Anal. 15 (1978), 929937. MR 80a:65075
 9.
 C. P. Huang, On the convergence of the QR algorithm with origin shifts for normal matrices, IMA J. Numer. Anal. 1 (1981), 127133. MR 87d:65130
 10.
 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
 11.
 B. N. Parlett, Singular and invariant matrices under the transformation, Math. Comp. 20 (1966), 611615. MR 35:3870
 12.
 B. N. Parlett, The Rayleigh quotient iteration and some generalizations for nonnormal matrices, Math. Comp. 28 (1974), 679693. MR 53:9615
 13.
 B. N. Parlett, The Symmetric Eigenvalue Problem, PrenticeHall, Englewood Cliffs, N.J., 1980. MR 81j:65063
 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 NPS5390007, 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), 1947. MR 91m:65114
 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 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/S0025571801013874
PII:
S 00255718(01)013874
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 DMS8704196
Dedicated:
Dedicated to the memory of James H. Wilkinson
Article copyright:
© Copyright 2001
American Mathematical Society
