Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to write a program which computes the largest and the smallest (in terms of absolute value) eigenvalues using both Power Iteration and Inverse Iteration.

I can find them using the Inverse Iteration, and I can also find the largest one using the Power Method. But I have no idea how to find the smallest one using the Power Method. I tried applying some kind of shift such as $A - \lambda_{max}I$, but to no avail.

So, how can I modify the Power Method so that it computes the smallest eigenvalue?

Thank you!

share|improve this question

2 Answers 2

up vote 3 down vote accepted

If you know that $A$ is symmetric positive-definite, then the spectral shift $B = A-\lambda_\max I$ will work. Use the power method on $B$, then add $\lambda_\max$ to the result to get the smallest eigenvalue of $A$.

The reason this shift works is that a positive-definite matrix has all positive eigenvalues. Therefore $B$ has all non-positive eigenvalues, with the smallest eigenvalue of $A$ now the largest-magnitude (most negative) eigenvalue of $B$. The power method will then find that eigenvalue.

The same approach works for negative-definite matrices, for the same reason.

share|improve this answer
    
This seems to work for symmetric negative-definite matrices as well. –  user825089 Jan 7 '13 at 1:55
    
Yes. I'll make a note of that. –  user7530 Jan 7 '13 at 1:56
    
While this is the best result we've got so far, any thoughts on symmetric indefinite matrices are still very welcome! –  user825089 Jan 7 '13 at 2:02
1  
Well, using this approach you can always find the largest (most positive) and smallest (most negative) eigenvalues. But for indefinite matrices it won't help you find the least-magnitude eigenvalue. –  user7530 Jan 7 '13 at 2:05
    
This is true, but it is one thing if you are doing this for fun or homework, but in practice computing the smallest eigenvalue with the power method can be very very slow (I believe it is linear). –  csta Apr 30 at 12:46

Suppose $A$ is invertible and has eigenvalue $\lambda$. Then $A^{-1}$ has eigenvalue $\lambda^{-1}$: this follows straight from the eigenvector equation $$Av = \lambda v \Rightarrow \frac{v}{\lambda} = A^{-1}v.$$

Since the smallest eigenvalue of $A$ is the largest eigenvalue of $A^{-1}$, you can find it using power iteration on $A^{-1}$:

$$v_{i+1} = A^{-1} \frac{v_i}{\|v_i\|}.$$

Unfortunately you now have to perform a linear solve at each iteration (or compute a decomposition of $A$), instead of just taking matrix-vector products.

share|improve this answer
    
Thank you! This is exactly the Inverse Iteration and I already know how to use it. The trick is to find the smallest one using the "pure" Power Method, without inverting $A$ or linear solve at each step. –  user825089 Jan 7 '13 at 1:21
    
I'm afraid I'm not aware of any "purer" way of getting at the smallest eigenvalue. –  user7530 Jan 7 '13 at 1:32
    
I'm reading that using the shift $\sigma = \lambda_{max}$ indeed works, but only for positive-definite matrices. Can someone confirm this? –  user825089 Jan 7 '13 at 1:39
    
Yes. I'll write up a second answer. –  user7530 Jan 7 '13 at 1:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.