[Math] Convergence rate of the power method for finding eigenvectors

Question

Let $M$ be a real-valued square matrix with an eigenvector $w$ strictly larger (in absolute value of the corresponding eigenvalue $\lambda$) than all others, and let $v$ be any vector not orthogonal to $w$. The power method says that
$$\lim \limits_{k \to \infty} \lambda^{-k}M^kv = w$$
I am curious about the convergence rate of this process. Can we bound
$$\max \limits_i |(M^k v)_i – w_i|$$
as a function of $k, v, w,$ or perhaps the other eigenvalues of $M$?

Answer 1

Suppose the eigenvalue $\lambda$ has algebraic multiplicity $1$. Then we have $\mathbb R^n = U \oplus \mathbb R w$ where $M U \subseteq U$ and the restriction $M|_U$ has spectral radius $r < |\lambda|$: $r$ is the maximum absolute value of the other eigenvalues of $M$. Then for any vector $v$, $v = u + t w$ with $u \in U$ and $t \in \mathbb R$, and $$| \| \lambda^{-k} M^k v - t w \|_\infty = \|\lambda^{-k} M^k u\|_\infty \le |\lambda|^{-k} \|M^{k}\| \|u\|_\infty$$ where $\|M^k\|$ is the operator norm of $M^k$ induced by the $\infty$ norm on $\mathbb R^n$. The spectral radius $r = \lim_{k \to \infty} \|M^k\|^{1/k}$, so for any $\epsilon > 0$, $\|M^k\| < (r + \epsilon)^k$ for sufficiently large $k$. Thus for sufficiently large $k$, $$\max_i |(\lambda^{-k} M^k v- t w)_i| \le \left(\dfrac{r+\epsilon}{|\lambda|}\right)^k \|u\|_\infty$$