[Math] Derivation of power method

eigenvalues-eigenvectorsnumerical methods

POWER METHOD

  1. Let $x_0$ be an initial approximation to the eigenvector.

  2. For $k=1,2,3,\ldots$ do

    1. Compute $x_k=Ax_{k-1}$,
    2. 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}}|$

Related Question