Arnoldi & Lanczos iteration

The raw Krylov vectors b, Ab, A^2 b, ... are numerically hopeless — they all drift toward the dominant eigenvector and become nearly parallel. The Arnoldi iteration cures this by orthogonalizing as it goes: each new vector A q_k is made orthogonal to all previous basis vectors via modified Gram-Schmidt and then normalized. The result is an orthonormal basis Q for the Krylov subspace, computed stably.

The bookkeeping of that orthogonalization is itself the prize. The coefficients fill an upper-Hessenberg matrix H (zero below the first subdiagonal), satisfying the Arnoldi relation A Q_k = Q_{k+1} H. In words: projected onto the Krylov basis, the giant operator A becomes a small almost-triangular matrix H whose eigenvalues (called Ritz values) approximate the eigenvalues of A. This is the engine inside GMRES and inside large-scale eigensolvers like ARPACK's implicitly restarted Arnoldi.

When A is symmetric (or Hermitian), Arnoldi simplifies dramatically into the Lanczos iteration. The Hessenberg matrix H collapses to a symmetric tridiagonal matrix T, so almost all the orthogonalization coefficients are forced to zero. The consequence is a three-term recurrence: each new vector only needs to be orthogonalized against the previous two, not all of them. This is exactly the saving that makes conjugate gradient and MINRES so cheap.

There is a wrinkle worth flagging. In finite precision, Lanczos loses orthogonality among its vectors as Ritz values converge, sometimes producing ghost copies of eigenvalues. Practical codes reorthogonalize selectively to keep the basis honest. The conceptual takeaway stands: Arnoldi and Lanczos are the machinery that turns an enormous matrix into a small one you can actually analyze.