Power iteration

Finding the dominant direction by repeated multiplication

Solving a characteristic polynomial is hopeless for a $1000\times1000$ matrix, and often only the largest eigenpair is wanted, for example the first principal component. Power iteration finds it with nothing but matrix-vector products. Start from any vector $\mathbf x_0$ and repeat $\mathbf x_{k+1}=A\mathbf x_k/\lVert A\mathbf x_k\rVert$. Each multiplication stretches the component along the dominant eigenvector more than every other component, so after enough steps the vector points along it.

Write $\mathbf x_0=c_1\mathbf v_1+c_2\mathbf v_2+\cdots$ in eigenvectors. After $k$ steps the coefficients are multiplied by $\lambda_i^k$, so the ratio of the second to the first is $(\lambda_2/\lambda_1)^k$. The method converges when $|\lambda_1|>|\lambda_2|$ and the starting vector has some component along $\mathbf v_1$, and the speed is set by $|\lambda_2/\lambda_1|$: close eigenvalues mean slow convergence. The normalisation only stops the numbers from overflowing; the direction is what matters. The eigenvalue estimate is the Rayleigh quotient. For the next eigenpair subtract $\lambda_1\mathbf v_1\mathbf v_1^{T}$ from a symmetric $A$ and repeat, which is called deflation.

• Update: multiply by $A$, divide by the norm, repeat; each step costs one matrix-vector product.
• Speed: the error falls like $|\lambda_2/\lambda_1|^k$, so close top eigenvalues converge slowly.
• Needs: a gap $|\lambda_1|>|\lambda_2|$ and a start vector not orthogonal to $\mathbf v_1$.

Lab · what's graded

• What it converges to15 pts
• A Rayleigh quotient20 pts
• The convergence ratio10 pts
• How many iterations15 pts
• The algorithm in order15 pts
• When it is slow or fails15 pts
• Why normalise10 pts