MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|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

Your Answer


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.