Rayleigh quotient iteration for nonsymmetric matrices

Batterson, Steve; Smillie, John

doi:10.1090/S0025-5718-1990-1023041-4

Rayleigh quotient iteration for nonsymmetric matrices
HTML articles powered by AMS MathViewer

by Steve Batterson and John Smillie PDF

Math. Comp. 55 (1990), 169-178 Request permission

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

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 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 10.1016/0893-9659(89)90107-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, DOI 10.1007/978-1-4612-1140-2

The dynamics of some birational maps on rational varieties with application to computational linear algebra

Mike Hurley, Multiple attractors in Newton’s method, Ergodic Theory Dynam. Systems 6 (1986), no. 4, 561–569. MR 873432, DOI 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 10.1137/0515020
J. E. Marsden and M. McCracken, The Hopf bifurcation and its applications, Applied Mathematical Sciences, Vol. 19, 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. MR 0494309
Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR 570116
B. N. Parlett, The Rayleigh quotient iteration and some generalizations for nonnormal matrices, Math. Comp. 28 (1974), 679–693. MR 405823, DOI 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 10.1090/S0273-0979-1985-15391-1