# Upper bound on iterations count for power iteration algorithm

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.

-

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.
Presumably you want $x_0$ to have only positive entries? – Carl Jun 26 '13 at 11:43