A simple question on power iteration...
Hiu Chung Law
v[i+1] = A v[i]
v[i+1] = v[i+1] / norm(v[i+1])
can be used to find the eigenvector corresponding to the eigenvalue
with largest absolute value, though not efficiently.
So... if I want to use the power method to find the eigenvector with
largest * positive * eigenvalue, what should I do?
The first thought that came to my mind is to find a "magical" shift
sigma, such that the most positive eigenvalue of (A+sigma*I) is much
larger than the absolute value of the most negative eigenvalue
of (A+sigma*I). However, how can we find sigma?
I check with the book matrix computation and it seems that it has not
discussed this.
Thank you for your help!
P.S. My email is lawhiu at cse dot msu dot edu
Arnold Neumaier
>
> Given a real symmetric matrix A, the power method
>
> v[i+1] = A v[i]
> v[i+1] = v[i+1] / norm(v[i+1])
>
> can be used to find the eigenvector corresponding to the eigenvalue
> with largest absolute value, though not efficiently.
>
> So... if I want to use the power method to find the eigenvector with
> largest * positive * eigenvalue, what should I do?
> The first thought that came to my mind is to find a "magical" shift
> sigma, such that the most positive eigenvalue of (A+sigma*I) is much
> larger than the absolute value of the most negative eigenvalue
> of (A+sigma*I). However, how can we find sigma?
Take sigma=||A|| in any norm.
But using the lanczos algorithm will be much more efficient than your proposal.
Arnold Neumaier
Ron Shepard
Hiu Chung Law <anti...@antispam.org> wrote:
> Given a real symmetric matrix A, the power method
>
> v[i+1] = A v[i]
> v[i+1] = v[i+1] / norm(v[i+1])
>
> can be used to find the eigenvector corresponding to the eigenvalue
> with largest absolute value, though not efficiently.
>
> So... if I want to use the power method to find the eigenvector with
> largest * positive * eigenvalue, what should I do?
> The first thought that came to my mind is to find a "magical" shift
> sigma, such that the most positive eigenvalue of (A+sigma*I) is much
> larger than the absolute value of the most negative eigenvalue
> of (A+sigma*I). However, how can we find sigma?
There are several ways to estimate lower bounds for the eigenvalues.
Look for residual norm bounds and Gerschgoren disk bounds in your
reference books.
However, unless this is purely an academic exercise, there are
probably better approaches to finding specific eigenpairs. For
example, if you can solve linear equations easily for your matrix A,
then consider Rayleigh Quotient Inverse Iteration or the subspace
version which is called the Generalized Jacobi-Davidson method. In
this approach, you find new vectors by solving a linear equation
(A - shift*I) v[i+1] = v[i]
With a shift that is close to your desired eigenvalue, this has the
effect of amplifying the vector you want significantly compared to
the power method. If shift is the Rayleigh quotient for v[i], then
this converges cubically. If shift magically just happens to be the
right eigenvalue, then it converges in a single step (although the
solution has infinite norm, which you have to account for).
$.02 -Ron Shepard
Ian Smith
If you let v(n) = A v(n-1) - lambda v(n-1) and find the
minimum/maximum with respect to lambda of v(n)TAv(n)/(v(n)Tv(n))
subject to v(n)Tv(n) = 1 (T is meant to be transpose). Then the two
possible sequences of v's will tend to the eigen vectors of the
minimum/maximum eigen values. It will also improve the rate of
convergence.
This is a simplified version of someone's algorithm for finding the
largest/smallest n eigen vectors. I'm ashamed to say I cannot remember
whose algorithm it is but it's a long time since I studied these
things! I'm sure someone else can provide a reference.
Ian Smith