Rayleigh quotient iteration for nonsymmetric matrices
Authors:
Steve Batterson and John Smillie
Journal:
Math. Comp. 55 (1990), 169-178
MSC:
Primary 65F15; Secondary 58F08, 58F12, 58F14
DOI:
https://doi.org/10.1090/S0025-5718-1990-1023041-4
MathSciNet review:
1023041
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: Rayleigh quotient iteration is an iterative algorithm for the calculation of approximate eigenvectors of a matrix. Given a matrix, the algorithm supplies a function whose iteration of an initial vector, ${v_0}$, produces a sequence of vectors, ${v_n}$. If the matrix is symmetric, then for almost any choice of ${v_0}$ the sequence will converge to an eigenvector at an eventually cubic rate. In this paper we show that there exist open sets of real matrices, each of which possesses an open set of initial vectors for which the algorithm will not converge to an eigenspace. The proof employs techniques from dynamical systems and bifurcation theory.
- Béla Barna, Über das Newtonsche Verfahren zur Annäherung von Wurzeln algebraischer Gleichungen, Publ. Math. Debrecen 2 (1951), 50–63 (German). MR 41902
- Béla Barna, Über die Divergenzpunkte des Newtonschen Verfahrens zur Bestimmung von Wurzeln algebraischer Gleichungen. I, Publ. Math. Debrecen 3 (1953), 109–118 (1954) (German). MR 61472
- Steve Batterson and John Smillie, The dynamics of Rayleigh quotient iteration, SIAM J. Numer. Anal. 26 (1989), no. 3, 624–636. MR 997660, DOI https://doi.org/10.1137/0726037
- Steve Batterson and John Smillie, Rayleigh quotient iteration fails for nonsymmetric matrices, Appl. Math. Lett. 2 (1989), no. 1, 19–20. MR 989851, DOI https://doi.org/10.1016/0893-9659%2889%2990107-9
- Louis Block, John Guckenheimer, Michał Misiurewicz, and Lai Sang Young, Periodic points and topological entropy of one-dimensional maps, Global theory of dynamical systems (Proc. Internat. Conf., Northwestern Univ., Evanston, Ill., 1979) Lecture Notes in Math., vol. 819, Springer, Berlin, 1980, pp. 18–34. MR 591173
- Robert L. Devaney, An introduction to chaotic dynamical systems, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1986. MR 811850
- John Guckenheimer and Philip Holmes, Nonlinear oscillations, dynamical systems, and bifurcations of vector fields, Applied Mathematical Sciences, vol. 42, Springer-Verlag, New York, 1983. MR 709768 P. Hriljac, The dynamics of some birational maps on rational varieties with application to computational linear algebra. I, II, preprint.
- Mike Hurley, Multiple attractors in Newton’s method, Ergodic Theory Dynam. Systems 6 (1986), no. 4, 561–569. MR 873432, DOI https://doi.org/10.1017/S0143385700003692
- M. Hurley and C. Martin, Newton’s algorithm and chaotic dynamical systems, SIAM J. Math. Anal. 15 (1984), no. 2, 238–252. MR 731865, DOI https://doi.org/10.1137/0515020
- J. E. Marsden and M. McCracken, The Hopf bifurcation and its applications, Springer-Verlag, New York, 1976. With contributions by P. Chernoff, G. Childs, S. Chow, J. R. Dorroh, J. Guckenheimer, L. Howard, N. Kopell, O. Lanford, J. Mallet-Paret, G. Oster, O. Ruiz, S. Schecter, D. Schmidt and S. Smale; Applied Mathematical Sciences, Vol. 19. MR 0494309
- Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. Prentice-Hall Series in Computational Mathematics. MR 570116
- B. N. Parlett, The Rayleigh quotient iteration and some generalizations for nonnormal matrices, Math. Comp. 28 (1974), 679–693. MR 405823, DOI https://doi.org/10.1090/S0025-5718-1974-0405823-3
- Michael Shub, Some remarks on dynamical systems and numerical analysis, Dynamical systems and partial differential equations (Caracas, 1984) Univ. Simon Bolivar, Caracas, 1986, pp. 69–91. MR 882014
- Steve Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 2, 87–121. MR 799791, DOI https://doi.org/10.1090/S0273-0979-1985-15391-1
Retrieve articles in Mathematics of Computation with MSC: 65F15, 58F08, 58F12, 58F14
Retrieve articles in all journals with MSC: 65F15, 58F08, 58F12, 58F14
Additional Information
Keywords:
Rayleigh quotient iteration,
eigenvector,
bifurcation
Article copyright:
© Copyright 1990
American Mathematical Society