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.

If we know all the eigenvalues of a matrix A except the largest one. We want to apply shifted power iteration to get the largest eigenvalue. Something like $(A-\alpha I)$ . Then what should be the value of shift ($\alpha$) to make it converge as fast as possible ?

share|improve this question

1 Answer 1

If the eigenvalues of $A$ are all real:

$$\lambda_1 \gt \lambda_2 \gt \ldots \gt \lambda_k$$

then the power iterations of the shifted matrix $A - \alpha I$ converge at the optimal rate when $\alpha = \frac{\lambda_2 + \lambda_k}{2}$.

Something similar can be done if the eigenvalues are complex but known except for the one of greatest modulus.

share|improve this answer
    
I am sorry I forgot to mention about the real eigenvalues. So for shifted power method we can say convergence will happen at the rate of $\mod(\frac{\lambda_2 - \alpha}{\lambda_1 - \alpha})$. Which means we want to make $\alpha$ as close as possible to $\lambda_2$. And above condition will ensure that. Is the understanding correct ? –  Anonym Dec 2 '12 at 17:41
    
You want to put $\alpha$ halfway between $\lambda_2$ and the eigenvalue at the other end of the spectrum, which I labelled $\lambda_k$. If you put $\alpha$ any closer to $\lambda_2$, then the shifted other end of the spectrum $\lambda_k - \alpha$ starts to get bigger (in absolute value) than $\lambda_2 - \alpha$. –  hardmath Dec 2 '12 at 17:46
    
Yes. got that.. Thanks a lot. –  Anonym Dec 2 '12 at 18:00

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.