From: sci.math.num-analysis@elsner.org (Ulrich Elsner) Subject: Re: Inverse Rayleigh iteration Date: 29 Jan 2001 19:28:13 GMT Newsgroups: sci.math.num-analysis Summary: Rayleigh Quotient iteration to compute eigenvalues Hi, According to Stefan Maehlmann : >i'm looking for a so called 'inverse Rayleigh iteration' procedure >to get an improved eigenvalue from an initial guessed one. It is usually called Rayleigh Quotient iteration: Let x_0 be your guess for an eigenvector (with ||x_0|| = 1) and A your matrix. Then For i = 0,1,... m_i = (x_i^T A x) /* actually (..)/x^T x */ z_{k+1} = (A-m_i)^-1 z_k /* solve a linear system */ x_{k+1} = z_{k+1} / || z_k+1 || end m_i is the so called Rayleigh quotient of x_k. It is an approximation to the eigenvalue. The second line is just inverse iteration with m_i as guess. The third line just makes sure that the elements of x_j don't grow too much. >I could'd find literature or pseudo-code that explains how to set up such >a routine. Any help is welcome. As the poet says: Golub and Van Loan "Matrix Computations" is A good place to start. Ulrich Elsner -- Ulrich Elsner, Fak. fuer Mathematik, TU Chemnitz, D-09107 Chemnitz, Germany ============================================================================== From: danloy@anma.ucl.ac.be (Bernard DANLOY) Subject: Re: Inverse Rayleigh iteration Date: Tue, 30 Jan 2001 12:13:53 +0200 Newsgroups: sci.math.num-analysis In article <954g8d$90v$1@narses.hrz.tu-chemnitz.de>, sci.math.num-analysis@elsner.org (Ulrich Elsner) wrote : [quote of previous article deleted --djr] Another valuable reference ( if your matrix is symmetric ) is B. Parlett, The Symmetric Eigenvalue Problem Let me also stress that, strictly speaking, RQI ( described above ) is NOT " a procedure to get an improved eigenvalue from an initial ^^^^^^^^^^ guessed one " ; RQI is a procedure to get an improved eigenvector ^^^^^^^^^^^ from an initial guessed one. RQI is nothing but a special case of shifted inverse iteration : Take a unit-vector u Repeat Choose a good shift s Replace u by a unit-vector in the direction (A-s)^(-1).u Until ... The Rayleigh Quotient u^T.A.u is just one possible choice of shift. In the 60's, Wilkinson found another famous choice ( often better ) In the 80's, Jiang-Zhang proposed a mixed use of those two. And research is going on ( see Wang, LAA, vol 322, Jan 2001 or Parlett, JCAM, vol 123, Nov 2000 ) .... It can be proved that R(ayleigh)-shift and W(ilkinson)-shift are approximations of at least one eigenvalue of A ; in that sense, shifted inverse iteration is also a method to find eigenvalues. If A is symmetric, it actually happens to be the best one known ( since QR, LR and related approaches can be viewed as pertinent and computationnaly reliable implementations of inverse iteration ). B. Danloy University of Louvain-la-Neuve