Derivation of power method
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?
$\endgroup$ 32 Answers
$\begingroup$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}}|$
$\endgroup$ 1 $\begingroup$After including normalization, you should get that $$ v:= \lim_{k \rightarrow \infty} x_k = \lim_{k \rightarrow \infty} \frac{A^kx_0}{\lambda_1^k} = \pm \frac{v_1}{||v_1||} .$$
Hence $v$ is some constant multiple of $v_1$, and is therefore an eigenvector itself. Being a constant multiple of $v_1$ implies $v$ and $v_1$ have the same associated eigenvalue-- in this case, the dominant eigenvalue $\lambda_1$.
For the record, I extracted this from A Friendly Introduction to Numerical Analysis by Brian Bradie. It's an excellent book.
$\endgroup$ 5
