= Power iteration
{title2=$x_{k+1}=Ax_k/\|Ax_k\|_2$}
{wiki}
<Power iteration> finds a <dominant eigenvalue> and its <eigenvector> by repeatedly applying a <matrix> and rescaling the resulting <vector>. The essential idea is selective amplification: components along different <eigenvectors> grow at different rates, so one direction can eventually dominate. It is the computational form of the <power method> and is useful when applying a large <sparse matrix> to a <vector> is cheap but computing its whole <spectral decomposition> is expensive.
For a square <matrix> over the <real numbers> or <complex numbers> $A$, choose a <unit vector> $x_0$ and repeat
$$
y_{k+1}=Ax_k,\qquad x_{k+1}=\frac{y_{k+1}}{\|y_{k+1}\|_2}.
$$
Here $\|\cdot\|_2$ is the <Euclidean norm>. If $y_{k+1}=0$, stop before division: the current <vector> is an <eigenvector> for the <zero eigenvalue>, and this iteration cannot continue. Otherwise, in exact arithmetic,
$$
x_k=\frac{A^kx_0}{\|A^kx_0\|_2}.
$$
Repeated normalization keeps the stored <vectors> at manageable size without changing their directions; it does not guarantee that an individual multiplication cannot exceed the range of <floating-point arithmetic>. The <dominant eigenvalue> means largest <modulus>, which need not mean largest signed real value.<Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide/Power Method>{ref}
Back to article page
