Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
MathSciNet review: 1023041
Full-text PDF

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.

References [Enhancements On Off] (What's this?)

  • [1] B. Barna, Über das Newtonsche Verfahren zur Annäherung von Wurzeln algebraischer Gleichungen, Publ. Math. Debrecen 2 (1951), 50-63. MR 0041902 (13:18b)
  • [2] -, Über die Divergenzpunkte des Newtonschen Verfahrens zur Bestimmung von Wurzeln algebraischer Gleichungen. I; II; III, Publ. Math. Debrecen 3 (1953), 109-118, 4 (1956), 384-397; 8 (1961), 193-207. MR 0061472 (15:831f)
  • [3] S. Batterson and J. Smillie, The dynamics of Rayleigh quotient iteration, SIAM J. Numer. Anal. 26 (1989), 624-636. MR 997660 (90j:65055)
  • [4] -, Rayleigh quotient iteration fails for nonsymmetric matrices, Appl. Math. Lett. 2 (1989), 19-20. MR 989851 (90b:65086)
  • [5] L. Block, J. Guckenheimer, M. Misiurewicz, and L. S. Young, Periodic points and topological entropy of one dimensional maps, Lecture Notes in Math., vol. 819, Springer-Verlag, New York, 1980, pp. 18-34. MR 591173 (82j:58097)
  • [6] R. Devaney, An introduction to chaotic dynamical systems, Benjamin Cummings, 1986. MR 811850 (87e:58142)
  • [7] J. Guckenheimer and P. Holmes, Nonlinear oscillations, dynamical systems, and bifurcations of vector fields, Springer-Verlag, New York, 1983. MR 709768 (85f:58002)
  • [8] P. Hriljac, The dynamics of some birational maps on rational varieties with application to computational linear algebra. I, II, preprint.
  • [9] M. Hurley, Multiple attractors in Newton's method, Ergodic Theory Dynamical Systems 6 (1986), 561-569. MR 873432 (88a:58123)
  • [10] M. Hurley and C. Martin, Newton's algorithm and chaotic dynamical systems, SIAM J. Math. Anal. 15 (1984), 238-252. MR 731865 (85j:58101)
  • [11] J. Marsden and M. McCracken, The Hopf bifurcation and its applications, Springer-Verlag, New York, 1976. MR 0494309 (58:13209)
  • [12] B. N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Englewood Cliffs, N.J., 1980. MR 570116 (81j:65063)
  • [13] -, The Rayleigh quotient iteration and some generalizations for nonnormal matrices, Math. Comp. 28 (1974), 679-693. MR 0405823 (53:9615)
  • [14] M. Shub, Some remarks on dynamical systems and numerical analysis, in Dynamical Systems and Partial Differential Equations: Proceedings of the VII ELAM, Equinoccio, Universidad Simon Bolivar, Caracas, 1986, pp. 69-92. MR 882014 (88j:58065)
  • [15] S. Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), 87-121. MR 799791 (86m:65061)

Similar Articles

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

American Mathematical Society