Method of power iteration

Intuition:

1. Stretching and shrinking: Imagine the matrix A as a transformation that stretches or shrinks space along different directions. The eigenvectors represent these special directions, and the eigenvalues represent the amount of stretching or shrinking.
2. Dominant direction: The eigenvector corresponding to the largest eigenvalue represents the direction of maximum stretching.
3. Repeated application: As we apply A repeatedly ($A^k$), the stretching along the dominant direction becomes more and more pronounced compared to other directions.

Derivation:

The 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$.

Intuitive analogy.

• Each eigenvector is scaled by its corresponding eigenvalue when multiplied by A.
• The largest eigenvalue causes the fastest growth.
• Over many iterations, the component along the dominant eigenvector outgrows all others.
• We can think of it like repeatedly sieving sand through increasingly fine meshes. Eventually, only the largest particles (analogous to the dominant eigenvector) remain.

Eigenvalues, Eigenvalues cannot be computed exactly, Why eigenvalues