-1
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Presumably you want $x_0$ to have only positive entries? $\endgroup$
    – user25199
    Jun 26, 2013 at 11:43
  • $\begingroup$ Carl, you are right. $\endgroup$
    – loup blanc
    Jun 26, 2013 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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