A simple question on power iteration...
flag
4 messages - Collapse all
/groups/adfetch?adid=ilAzWBAAAABgKcB-DOlFVgYcrEcZRp3L
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Follow-up To:
Add Cc | Add Follow-up to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers that you hear
 
1.  Hiu Chung Law  
View profile   Translate to Translated (View Original)
 More options 25 Apr 2003, 19:20
Newsgroups: sci.math.num-analysis
From: Hiu Chung Law <antis...@antispam.org>
Date: 25 Apr 2003 18:17:40 GMT
Local: Fri 25 Apr 2003 19:17
Subject: A simple question on power iteration...
Reply to author | Forward | Print | Individual message | Show original | Report this message | Find messages by this author
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?

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


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message, you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
2.  Arnold Neumaier  
View profile   Translate to Translated (View Original)
 More options 25 Apr 2003, 19:59
Newsgroups: sci.math.num-analysis
From: Arnold Neumaier <Arnold.Neuma...@univie.ac.at>
Date: Fri, 25 Apr 2003 20:59:35 +0200
Local: Fri 25 Apr 2003 19:59
Subject: Re: A simple question on power iteration...
Reply to author | Forward | Print | Individual message | Show original | Report this message | Find messages by this author

Take sigma=||A|| in any norm.
But using the lanczos algorithm will be much more efficient than your proposal.

Arnold Neumaier


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message, you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
3.  Ron Shepard  
View profile   Translate to Translated (View Original)
 More options 26 Apr 2003, 16:29
Newsgroups: sci.math.num-analysis
From: Ron Shepard <ron-shep...@NOSPAM.attbi.com>
Date: Sat, 26 Apr 2003 15:29:01 GMT
Local: Sat 26 Apr 2003 16:29
Subject: Re: A simple question on power iteration...
Reply to author | Forward | Print | Individual message | Show original | Report this message | Find messages by this author
In article <b8bu44$ib...@msunews.cl.msu.edu>,
 Hiu Chung Law <antis...@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


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message, you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
4.  Ian Smith  
View profile   Translate to Translated (View Original)
 More options 28 Apr 2003, 08:47
Newsgroups: sci.math.num-analysis
From: iandjmsm...@aol.com (Ian Smith)
Date: 28 Apr 2003 00:47:30 -0700
Local: Mon 28 Apr 2003 08:47
Subject: Re: A simple question on power iteration...
Reply to author | Forward | Print | Individual message | Show original | Report this message | Find messages by this author
Hiu Chung Law <antis...@antispam.org> wrote in message <news:b8bu44$ibi$1@msunews.cl.msu.edu>...

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


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message, you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.

Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
©2009 Google