Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm stuck trying to get upper bound on iterations count for power iteration algroithm for finding first eigenvalue of adjacency matrix $A$ given tolerance value. I've tried to figure something out from equations $Ax^{\*}=\lambda x^\*$ ($x^\*$ is exact solution) and $Ax^{(k+1)}=\lambda x^{(k)}$ and got this (if needed, I can write all steps):

$ ||x^{(k)} - x^\*|| \le {{log \left( {{\varepsilon} \over {C}} \right)} \over {log\ q}}$, where $C = {{\left|\left| x^{(0)} - x^{(1)} \right|\right|} \over {1-q}}$ and $q = \left|\left| {{A} \over {\lambda}} \right|\right| $.

It's awful. First, it depends on $x^{0}$ and $||A|| \sim O({m \over \sqrt{n}}) $. Second, it is not even upper bound. I've tried to google it, but found nothing specific. I'm sure better estimate exists.

Please, if you know something about that issue, share with me. Any help will be good: advices, possible way to solutions, articles, etc.

P.S. $A$ is sparce, n-by-n matrix with all non-negative real values. Number of positive elements is m.

share|improve this question
add comment

1 Answer

Let $(\lambda_i)_i$ be the spectrum of $A$ where $\lambda_1\geq |\lambda_2|\geq \cdots$. You must assume that $\lambda_1> |\lambda_2|$. The correct iteration is: $x_0$ randomly chosen with modulus $1$ and $x_{k+1}=\dfrac{Ax_k}{||Ax_k||}$. The error $||x_k-x^*||$ is in $O((\dfrac{|\lambda_2|}{\lambda_1})^k)$. The complexity of a step is essentially $m$ multiplications.

share|improve this answer
    
Presumably you want $x_0$ to have only positive entries? –  Carl Jun 26 '13 at 11:43
    
Carl, you are right. –  loup blanc Jun 26 '13 at 11:58
add comment

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.