[Math] Power iteration- What are the conditions

matrices

I read about the Power iteration in Wikipedia and I don't understand the conditions needed to hold to use the method. Wikipedia states that

If we assume $A$ has an eigenvalue that is strictly greater in magnitude than its other eigenvalues and the starting vector has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue, then the algorithm converges to an eigenvector associated with the dominant eigenvalue.

What does it mean "has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue" ?

For example if $A$ have eigenvalues $2,1$ and $v$ is an eigenvector corresponding to the eigenvalue of $1$ then $A^kv=v$ and the sequence does not converge to an eigenvector corresponding to the eigenvalue of $2$

Best Answer

To meet the objections of Henning, one obviously presupposes $n\geq 2$.

The power iteration is a great and simple algorithm. It works as follows.

  1. Randomly choose a vector $b_0$ in $[-1,1]^n$.

  2. Consider the recurrence $b_{k+1}=\dfrac{Ab_k}{||b_k||}$.

EDIT. Correction.

  1. Stop when there is $\lambda$ s.t. $||Ab_k-\lambda b_k||<\epsilon$.

If $\rho(A)$ is reached for only one eigenvalue $\lambda_1$ (with mutiplicity), then $\lambda,b_k$ are approximations of $\lambda_1$ and of an associated eigenvector. The speed of convergence is in $O((\dfrac{|\lambda_2|}{|\lambda_1|})^k)$ where $\lambda_2$ is the second eigenvalue (in modulus).

Remark. When $A\in M_n(\mathbb{R})$, often there are two simple eigenvalues $\lambda_1,\bar{\lambda_1}$ that realize $\rho(A)$. Then, most people say that the method does not work; that is false, it works!!

Indeed, choose a real $b_0$ and for large enough $k$, $b_k$ goes throught a plane $P$; $b_{k},b_{k+1}$ is an approximation of a basis of $P$; it remains to obtain the complex eigenvectors and eigenvalues of a $2\times 2$ real matrix.

Related Question