POWER METHOD
-
Let $x_0$ be an initial approximation to the eigenvector.
-
For $k=1,2,3,\ldots$ do
- Compute $x_k=Ax_{k-1}$,
- Normalize $x_k=x_k/\|x_k\|_\infty$.
Then $\|x_k\|_\infty$ approaches the dominant eigenvalue and $x_k$ approaches the corresponding eigenvector of the matrix $A$.
My question: But why?
A part of an answer shared by all numerical books: If the eigenvectors $v_1,\ldots,v_n$ associated with $\lambda_1,\ldots,\lambda_n$ are linearly independent, we can write
$$x_0=c_1v_1+c_2v_2+\cdots+c_nv_n$$
Multiplying both sides by $A^k$ gives
$$\begin{align}
A^Kx_0 &=A^k(c_1v_1+c_2v_2+\cdots+c_nv_n)\\
&=c_1\lambda_1^k v_1+c_2\lambda_2^k v_2+\cdots+c_n\lambda_n^k v_n\\
&=\lambda_1^k \left( c_1v_1+c_2 \left(\frac{\lambda_2}{\lambda_1}\right)^k v_2+\cdots+\left(\frac{\lambda_n}{\lambda_1}\right)^k v_n \right)
\end{align}$$
Since the $\lambda_1$ is the dominant eigenvalue, i.e. $|\lambda_1|>|\lambda_i|$ for each $i$, $\left( \frac{\lambda_i}{\lambda_1}\right)^k \to 0$ as $k \to \infty$. Then
$$
A^k x_0=\lambda_1^k c_1 v_1
$$
Up to this point, there is no problem. After reading many books, I couldn't find a clear and general proof for after this point.
I found a new hint, but yet why?: Of course we don't have $\lambda_1$ available but virtually any homogeneous scaling
of $A^k x_0$ that is proportional to $\lambda_1^k$ will do. [Jack J. Dongarra]
Extra question: Why am I stupid?
Best Answer
It's a litle confusing that you call ${\bf x_k}$ both the unnormalized and the normalized vector. Let's call ${\bf y_k} $ the normalized vector. We agree that, as $k\to \infty$
$${\bf x_k}=A^k {\bf x_0}=\lambda_1^k c_1 {\bf v_1}$$
Actually, this would correspond to the procedure without normalization. But the normalization would just multiply each ${\bf x_k}$ by some scalar, then we should actually write
$$ {\bf y_k} = \alpha \lambda_1^k c_1 {\bf v_1} = \beta {\bf v_1} $$
But this means that ${\bf y_k} $ is a multiple of the dominant eigenvector... then it's a (dominant) eigenvector. The same goes for ${\bf x_k} $.
Then $${\bf x_{k+1}} = A {\bf y_{k}} = \lambda_1 {\bf y_{k}} = \lambda_1 \frac{{\bf x_{k}}}{|{\bf x_{k}}|}$$
Then, because as $k$ grows ${\bf x_{k+1}} \approx {\bf x_{k}}$ we must have $\lambda_1 = |{\bf x_{k}}|$