Let $A \in $Sym$_{n}(\mathbb R)$ with eigenvalues $\lambda_i$ such that $|\lambda_1| > |\lambda_2| \geq |\lambda_3 |\geq … \geq |\lambda_n|$
We define the following process as "Power Iteration":
1) choose any $u^{(o)} \in \mathbb R^n$
2) for $k\geq 0$: $$u^{(k+1)}=\frac{Au^{(k)}}{||Au^{(k)}||}$$
Show that $\langle u^{(k)},Au^{(k)} \rangle$ converges to $\lambda_1$ and that the error is $O(|\frac{\lambda_2}{\lambda_1}|^{2k})$
I managed to show convergence. $u^{(k)}$ converges to the normalized eigenvector corresponding to $\lambda_1$ and so that inner product converges to $\lambda_1$, but I don't know why the error is bound by that value.
What I did:
write $u^{(o)}$ in the basis of orthonormal eigenvectors of A which we know exists since $A$ is symmetric:
$$A^ku^{(0)} = A^k \sum_{i=1}^{n} \alpha_iv_i = \sum_{i=1}^{n} \lambda^k_i \alpha_iv_i = \lambda^k_1\alpha_1(v_1+\sum_{i=2}^n \frac{\alpha_i}{\alpha_1}\frac{\lambda^k_i}{\lambda^k_1}v_i)$$
since $\lambda_1$ is largest, as $k$ approaches infinity, the term in the parenthesis converges to $v_1$, and so $A^ku^{(0)} = \alpha_1\lambda^k_1v_1$, and $u^{(k+1)} = =\frac{Au^{(k)}}{||Au^{(k)}||} = \frac{\alpha_1\lambda^k_1v_1}{||\alpha_1\lambda^k_1v_1||}=v_1$
it follows that the inner product converges to $\lambda_1$
Best Answer
Hint: expand the value of $u^{(0)}$ along the basis of eigenvectors of $A$.