Franklin's Notes

Power iteration

Power iteration is an iterative method of approximating the eigenvalues of a matrix. The algorithm is relatively simple:

1. Let $v^{(0)}$ be some unit vector
2. For $k=1,2,\cdots$
1. Let $w=Av^{(k-1)}$
2. Let $v^{(k)}=w/\lVert w\rVert$, normalizing $w$
3. Let $\lambda^{(k)}=r(v^{(k)})$ where $r$ is the Rayleigh quotient

Power iteration is guaranteed to converge when $A$ is nondefective and has a unique eigenvalue of largest magnitude. For if $\lambda_1>\lambda_2\geq \lambda_3\geq \cdots$ with corresponding unit eigenvectors $q_1,q_2,q_3,\cdots$, then if we rewrite the unit vector $v^{(k)}$ as a linear combination of this basis: then we have that where $c=\pm 1/\lVert w\rVert$ is the constant needed to normalize the vector $w=Av^{(k)}$. This implies that the magnitude of the component in the direction of $q_1$ increases by a factor of at least $\lambda_1/\lambda_2$ relative to each of the other eigenvectors $q_i$, and therefore we have that as $k$ increases.




back to home page