Linear convergence in the shifted 𝑄𝑅 algorithm

Batterson, Steve; Day, David

doi:10.1090/S0025-5718-1992-1134713-7

Linear convergence in the shifted $QR$ algorithm
HTML articles powered by AMS MathViewer

by Steve Batterson and David Day PDF

Math. Comp. 59 (1992), 141-151 Request permission

Abstract:

Global and asymptotic convergence properties for the QR algorithm with Francis double shift are established for certain orthogonal similarity classes of $4 \times 4$ real matrices. It is shown that in each of the classes every unreduced Hessenberg matrix will decouple and that the rate of decoupling is almost always linear. The effect of the EISPACK exceptional shift strategy is shown to be negligible.

References

Steve Batterson, Convergence of the shifted $QR$ algorithm on $3\times 3$ normal matrices, Numer. Math. 58 (1990), no. 4, 341–352. MR 1077582, DOI 10.1007/BF01385629

The dynamics of eigenvalue computation

Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
Heisuke Hironaka, Triangulations of algebraic sets, Algebraic geometry (Proc. Sympos. Pure Math., Vol. 29, Humboldt State Univ., Arcata, Calif., 1974) Amer. Math. Soc., Providence, R.I., 1975, pp. 165–185. MR 0374131
R. S. Martin, G. Peters, and J. H. Wilkinson, Handbook Series Linear Algebra: The $QR$ algorithm for real hessenberg matrices, Numer. Math. 14 (1970), no. 3, 219–231. MR 1553971, DOI 10.1007/BF02163331
B. T. Smith, J. M. Boyle, J. J. Dongarra, B. S. Garbow, Y. Ikebe, V. C. Klema, and C. B. Moler, Matrix eigensystem routines—EISPACK guide, 2nd ed., Lecture Notes in Computer Science, Vol. 6, Springer-Verlag, Berlin-New York, 1976. MR 0494879, DOI 10.1007/3-540-07546-1
G. W. Stewart, Introduction to matrix computations, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. MR 0458818
Robert A. van de Geijn, Deferred shifting schemes for parallel $QR$ methods, SIAM J. Matrix Anal. Appl. 14 (1993), no. 1, 180–194. MR 1199555, DOI 10.1137/0614016
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