Power Method and Inverse Iteration
The eigenvalue problem 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 ). Iterative methods are therefore essential.
The Power Method
The power method generates iterates starting from . If has a dominant eigenvalue with , and has a nonzero component in the -eigenspace, then (the dominant eigenvector) and the Rayleigh quotient . The convergence rate is .
For with eigenvalues , : the ratio , so convergence is rapid. Starting with : , , and after iterations the angle to decreases as . The Rayleigh quotient converges twice as fast: .
Inverse Iteration and Shift-Invert
Inverse iteration applies the power method to : solve , then normalize . This converges to the eigenvector of whose eigenvalue is closest to the shift , with rate . When is a good eigenvalue approximation, convergence is very rapid.
Rayleigh quotient iteration (RQI) updates the shift at each step: (the Rayleigh quotient), then performs inverse iteration with this shift. For symmetric , RQI converges cubically: . This means roughly tripling the number of correct digits per iteration -- just 2-3 iterations typically suffice.
Deflation
After finding an eigenpair , deflation removes it from the problem. For symmetric : form (Hotelling deflation), then apply the power method to to find . For non-symmetric : deflation by restriction uses a Schur complement. The main concern is that rounding errors in deflation can contaminate subsequent eigenvectors, necessitating re-orthogonalization.
For with initial guess : . After iteration 1: . After iteration 2: . The error shrinks from to to , demonstrating cubic convergence.