Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Convergence of the shifted algorithm for unitary Hessenberg matrices

Author(s): Tai-Lin Wang; William B. Gragg.
Journal: Math. Comp. 71 (2002), 1473-1496.
MSC (2000): Primary 65F15, 15A18
Posted: November 30, 2001
MathSciNet review: 1933041
Retrieve article in: PDF
This article is available free of charge

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.

References:

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.: 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), 137-154. 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), 97-104. MR 50:8948
5.: J. G. F. Francis, The transformation. I, II, Comput. J. 4 (1961-1962), 265-271, 332-345. MR 25:744
6.: W. B. Gragg, The algorithm for unitary Hessenberg matrices, J. Comput. Appl. Math. 16 (1986), 1-8.
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), 183-198. 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), 929-937. 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), 127-133. 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), 261-272. MR 86g:65082
11.: B. N. Parlett, Singular and invariant matrices under the transformation, Math. Comp. 20 (1966), 611-615. MR 35:3870
12.: B. N. Parlett, The Rayleigh quotient iteration and some generalizations for nonnormal matrices, Math. Comp. 28 (1974), 679-693. MR 53:9615
13.: B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, 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 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 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), 409-420. 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:

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: 10.1090/S0025-5718-01-01387-4
PII: S 0025-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
Posted: 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
Copyright of article: Copyright 2001, American Mathematical Society

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|