Linear convergence in the shifted 𝑄𝑅 algorithm

Batterson, Steve; Day, David

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

Linear convergence in the shifted algorithm

Authors: Steve Batterson and David Day
Journal: Math. Comp. 59 (1992), 141-151
MSC: Primary 65F15
DOI: https://doi.org/10.1090/S0025-5718-1992-1134713-7
MathSciNet review: 1134713
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

[1] Steve Batterson, Convergence of the shifted 𝑄𝑅 algorithm on 3×3 normal matrices, Numer. Math. 58 (1990), no. 4, 341–352. MR 1077582, https://doi.org/10.1007/BF01385629
[2] -, The dynamics of eigenvalue computation, preprint.
[3] 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
[4] 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
[5] R. S. Martin, G. Peters, and J. H. Wilkinson, Handbook Series Linear Algebra: The 𝑄𝑅 algorithm for real hessenberg matrices, Numer. Math. 14 (1970), no. 3, 219–231. MR 1553971, https://doi.org/10.1007/BF02163331
[6] 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., Springer-Verlag, Berlin-New York, 1976. Lecture Notes in Computer Science, Vol. 6. MR 0494879
[7] G. W. Stewart, Introduction to matrix computations, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Computer Science and Applied Mathematics. MR 0458818
[8] Robert A. van de Geijn, Deferred shifting schemes for parallel 𝑄𝑅 methods, SIAM J. Matrix Anal. Appl. 14 (1993), no. 1, 180–194. MR 1199555, https://doi.org/10.1137/0614016
[9] 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, https://doi.org/10.1016/0024-3795(91)90004-G