Method of power iteration

This approach goes back to the fundamental motivation behind eigenvalue:

$$A^k=X{\Lambda }^k{X}^{-1}=X{\Lambda }^k{Y}^T$$

We can write this product using the outer form of matrix-matrix products:

$$A^k=X{\Lambda }^k{Y}^T={\lambda }_1^k{\mathbf{x}}_{,1}{\mathbf{y}}_{,1}^T+\cdots +{\lambda }_n^k{\mathbf{x}}_{,n}{\mathbf{y}}_{,n}^T$$

Assume that

$$|{\lambda }_1|>|{\lambda }_2|\ge \cdots \ge |{\lambda }_n|$$

Then:

$$A^k\approx {\lambda }_1^k{\mathbf{x}}_1{\mathbf{y}}_1^T$$

The range of $A^k$ is nearly $\text{span}\{{\mathbf{x}}_1\}.$

Pick a random vector $\mathbf{q}$ with ${\mathbf{y}}_1^T\mathbf{q}\ne 0$ and

$$A^k\mathbf{q}\sim {\lambda }_1^k({\mathbf{y}}_1^T\mathbf{q}){\mathbf{x}}_1$$

We have that $A^k\mathbf{q}$ simply converges to the span of ${\mathbf{x}}_1$.

Algorithm pseudo-code:

while not_converged:
    zk = A * qk
    ev = dot(zk, qk)
    qk = zk / norm(zk)

• ev converges to the eigenvalue.
• qk does not necessarily converge, but span(qk) converges to span(x1).

We can make a more precise statement. Denote by

$${\lambda }_1=\rho e^{i\theta }$$

for a general complex eigenvalue. ${\mathbf{x}}_1$ is a unit eigenvector associated with ${\lambda }_1$.

Then, because of the step qk = zk / norm(zk), we get

$${\mathbf{q}}_k\to e^{ik\theta }{\mathbf{x}}_1$$

So $e^{-ik\theta }{\mathbf{q}}_k$ converges to ${\mathbf{x}}_1$.

Eigenvalues, Eigenvalues cannot be computed exactly, Why eigenvalues