From power iteration to the QR algorithm
In Vol I you found eigenvalues by factoring the characteristic polynomial — fine for 2x2, hopeless for 2000x2000, and notoriously ill-conditioned. Machines never do that. The seed idea is the power method: repeatedly multiply a vector by A and renormalize, and it homes in on the dominant eigenvector because that direction grows fastest. Inverse iteration applies the power method to (A - sigma I)^-1, converging to the eigenvalue nearest a chosen shift sigma — letting you target any eigenvalue you like.
The workhorse for all eigenvalues at once is the QR algorithm. Repeatedly factor A = Q R (a QR decomposition) and recombine in reverse order, A_{new} = R Q. This similarity transform preserves eigenvalues while driving the matrix toward upper-triangular form, whose diagonal then reveals every eigenvalue at once. With shifts to accelerate it, the QR algorithm is one of the most important algorithms of the twentieth century.
Preconditioning: bending the problem into shape
Recall the verdict from the last guide: Krylov convergence is governed by the condition number. Preconditioning attacks that number directly. Instead of solving A x = b, you solve the equivalent system M^-1 A x = M^-1 b, where M is a preconditioner chosen so that (a) M^-1 A is far better conditioned than A, and (b) applying M^-1 to a vector is cheap. Get both and a 10000-iteration solve can drop to 30.
The art is the tension between those two goals. The perfect preconditioner is M = A, which makes M^-1 A = I converge in one step — but applying A^-1 is the very problem you couldn't solve. The useless preconditioner is M = I, cheap but doing nothing. Every practical choice lives between: an incomplete LU (factor A but discard most fill), a Jacobi/diagonal preconditioner (the diagonal of A), or a problem-specific multigrid or domain-decomposition scheme.
- Start with a no-cost preconditioner (Jacobi/diagonal scaling) and measure the iteration count.
- If still too slow, try an incomplete LU that keeps only the larger fill entries.
- For structured PDE problems, reach for a multigrid or domain-decomposition preconditioner.
- Balance setup cost against per-iteration savings — the best M minimizes total time, not iteration count.
The payoff: a quiet engine under everything
Step back and see what these five guides assembled. Backward-stable factorizations with pivoting, Krylov solvers CG and GMRES, eigenvalue engines like the QR algorithm, all sharpened by preconditioning — this is the machinery that turns Vol I's pristine theory into answers you can trust on a finite machine. None of it is visible to the end user, and all of it is everywhere.