From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik) Subject: Re: Power method, dominant eigenvalue of a matrix Date: 7 Dec 1999 17:59:15 -0500 Newsgroups: sci.math.num-analysis Keywords: power method, Rayleigh quotients In article <384D7E25.7400B352@uh.edu>, N. Shamsundar wrote: :Here is a curious experience with the power method that I should :like to share with s.m.n-a. : :Background: :If, starting with an arbitrary initial vector x_0, we compute :successive vectors x_1, x_2, ..., with x_{n+1}=A x_n, usually :||x_{n+1}||/||x_n| converges to the eigenvalue of highest :magnitude. Only if the dominant eigenvalue is indeed positive. Rayleigh quotients give you the correct sign, even for complex cases: s(x_n) = x_n' * A * x_n / (x_n' * x_n) where x' is the Hermitian transpose of x. There is another tempting reason why choose s(x_n): Suppose (a non-zero vector) x is a candidate for an approximate eigenvector of a matrix A, Hermitian or not. Then (following the philosophy of backward error analysis) x is the exact eigenvector of a nearby matrix B, corresponding to the eigenvalue s(x), and the difference B-A can be made of rank 1, and of the smallest possible norm. (Construction of B is based on Cauchy-Schwarz inequality.) The distance ||B-A|| is ||A*x - s(x)*x||/||x||. :Commonly, the finite precision of floating point :will introduce a contribution from the corresponding :eigenvector, even if x_0 happens to be orthogonal to this :eigenvector. : That's why it is recommended to start iterations, especially inverse iterations, with a "messy" vector, such as x_j = sin((j*k*pi)/(n+1) , j=1,...,n n being the dimension, and if the choice k=1 is not good enough, try k=2, and so on. How good? Backward error analysis formula can guide us. :Curious example: :If we pick a toy example where the dominant eigenvector is [1 -1 :1 -1 .... 1 -1], and x_0=[1 1 .... 1 1] (an innocent, simple :choice), the power method converges to the --second-- highest :magnitude, since the dominant eigenvector and x_0 are exactly :representable in floating point. : The "messy" starter will be quite likely to avoid it. Cheers, ZVK(Slavek). :N. Shamsundar :University of Houston