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/λ1k|\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(2k)O(2^{-k}). The Rayleigh quotient converges twice as fast: ρ(k)4=O(4k)|\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σ/minijλ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(λσk3)|\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)\|: σ04.54\sigma_0 \approx 4.54. After iteration 1: σ14.9987\sigma_1 \approx 4.9987. After iteration 2: σ25.000000000\sigma_2 \approx 5.000000000. The error shrinks from O(101)O(10^{-1}) to O(103)O(10^{-3}) to O(1010)O(10^{-10}), demonstrating cubic convergence.