Power method §

Is the simplest eigenvalue algorithm, it finds the eigenvalue of largest modulus.

Consider a diagonalizable matrix $A$, then the eigenvectors form a basis for ${\mathbb{C}}^n$. Therefore, for every vector $x^0$, it’s expantion in the eigen-base:

$$x^0=\sum _{i=1}^n{\alpha }_i{v}_i$$

If we apply iterativly $x$ to the matrix $A$, i.e. $x^k=A^k{x}^0$, in the eigenvector base this is just:

$$x^k=\sum _{i=1}^n{\alpha }_i{\lambda }_i^k{v}_i$$

putting in evidence the biggest eigenvalue ${\lambda }_n$

$$x^k={\lambda }_n^k\left({\alpha }_n{v}_n+\sum _{i=1}^{n-1}{\alpha }_i{\left[\frac{{\lambda }_i}{{\lambda }_j}\right]}^k{v}_i\right)$$

in the limit $k\to \infty$, the terms ${\left[\frac{{\lambda }_i}{{\lambda }_j}\right]}^k\to 0$ since ${\lambda }_i<{\lambda }_n$.

The error therm goes to zero lineart as $o(\frac{|{\lambda }_{n-1}|}{|{\lambda }_n|})$. So the convergence is better if the greates eigenvalue if well separated from the rest of the spectrum.

To avoid overflow or underflow (${\lambda }_n^k\to \infty$ or to $0$) each iteration we normalize the vector.

Remaks the starting vector should have a nonzero component in $v_n$, i.e. it should not be perperdicular to $v_n$. This is however unlikely, and rounding error will introduce nonzero component helping us!

If the is more than one max eigenvalue, the algorithm will converge to an eigenspace.

Shifts §

Consider the shifted matrix $A-\sigma I$, for $\sigma \in \mathbb{R}$. The spectrum of the shifted matrix is just the spectrum of $A$ shift $-\sigma$, the eigenvectors are the same:

$$(A-\sigma I)v=(\lambda -\sigma )v$$

With shifts we can compute other eigenvalues insted of the greates absolute value one!

It can also be used to speed up convergence by decreasing the factor $\frac{|{\lambda }_n|}{|{\lambda }_{n-1}|}$.