ConceptComplete

Power Method and Inverse Iteration

The eigenvalue problem Ax=λxAx = \lambda x is fundamental in scientific computing. Unlike linear systems, eigenvalue problems cannot be solved in finitely many steps (Abel's theorem prevents algebraic solutions for degree ≥5\geq 5). Iterative methods are therefore essential.


The Power Method

Definition6.1Power Method

The power method generates iterates v(k+1)=Av(k)/∥Av(k)∥v^{(k+1)} = Av^{(k)} / \|Av^{(k)}\| starting from v(0)v^{(0)}. If AA has a dominant eigenvalue λ1\lambda_1 with ∣λ1∣>∣λ2∣≥⋯≥∣λn∣|\lambda_1| > |\lambda_2| \geq \cdots \geq |\lambda_n|, and v(0)v^{(0)} has a nonzero component in the λ1\lambda_1-eigenspace, then v(k)→±v1v^{(k)} \to \pm v_1 (the dominant eigenvector) and the Rayleigh quotient ρ(k)=(v(k))TAv(k)/(v(k))Tv(k)→λ1\rho^{(k)} = (v^{(k)})^T A v^{(k)} / (v^{(k)})^T v^{(k)} \to \lambda_1. The convergence rate is ∣λ2/λ1∣k|\lambda_2/\lambda_1|^k.

ExamplePower Method Convergence

For A=(3113)A = \begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix} with eigenvalues λ1=4\lambda_1 = 4, λ2=2\lambda_2 = 2: the ratio ∣λ2/λ1∣=1/2|\lambda_2/\lambda_1| = 1/2, so convergence is rapid. Starting with v(0)=(1,0)Tv^{(0)} = (1, 0)^T: v(1)∝(3,1)v^{(1)} \propto (3, 1), v(2)∝(10,6)v^{(2)} \propto (10, 6), and after kk iterations the angle to (1,1)T(1, 1)^T decreases as O(2−k)O(2^{-k}). The Rayleigh quotient converges twice as fast: ∣ρ(k)−4∣=O(4−k)|\rho^{(k)} - 4| = O(4^{-k}).


Inverse Iteration and Shift-Invert

Definition6.2Inverse Iteration

Inverse iteration applies the power method to (A−σI)−1(A - \sigma I)^{-1}: solve (A−σI)w(k+1)=v(k)(A - \sigma I)w^{(k+1)} = v^{(k)}, then normalize v(k+1)=w(k+1)/∥w(k+1)∥v^{(k+1)} = w^{(k+1)}/\|w^{(k+1)}\|. This converges to the eigenvector of AA whose eigenvalue λj\lambda_j is closest to the shift σ\sigma, with rate ∣λj−σ∣/min⁡i≠j∣λi−σ∣|\lambda_j - \sigma|/\min_{i \neq j}|\lambda_i - \sigma|. When σ\sigma is a good eigenvalue approximation, convergence is very rapid.

Definition6.3Rayleigh Quotient Iteration

Rayleigh quotient iteration (RQI) updates the shift at each step: σk=ρ(v(k))\sigma_k = \rho(v^{(k)}) (the Rayleigh quotient), then performs inverse iteration with this shift. For symmetric AA, RQI converges cubically: ∣λ−σk+1∣=O(∣λ−σk∣3)|\lambda - \sigma_{k+1}| = O(|\lambda - \sigma_k|^3). This means roughly tripling the number of correct digits per iteration -- just 2-3 iterations typically suffice.


Deflation

RemarkDeflation Techniques

After finding an eigenpair (λ1,v1)(\lambda_1, v_1), deflation removes it from the problem. For symmetric AA: form A1=A−λ1v1v1TA_1 = A - \lambda_1 v_1 v_1^T (Hotelling deflation), then apply the power method to A1A_1 to find λ2\lambda_2. For non-symmetric AA: deflation by restriction uses a Schur complement. The main concern is that rounding errors in deflation can contaminate subsequent eigenvectors, necessitating re-orthogonalization.

ExampleRQI Cubic Convergence

For A=diag(5,3,1)A = \mathrm{diag}(5, 3, 1) with initial guess v(0)=(0.9,0.3,0.1)T/∥(0.9,0.3,0.1)∥v^{(0)} = (0.9, 0.3, 0.1)^T / \|(0.9,0.3,0.1)\|: σ0≈4.54\sigma_0 \approx 4.54. After iteration 1: σ1≈4.9987\sigma_1 \approx 4.9987. After iteration 2: σ2≈5.000000000\sigma_2 \approx 5.000000000. The error shrinks from O(10−1)O(10^{-1}) to O(10−3)O(10^{-3}) to O(10−10)O(10^{-10}), demonstrating cubic convergence.