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