Lanczos algorithm

Remarks

The proof is by induction on $j$. The vector $A q_j$ is orthogonal to $q_1, \dots, q_{j-2}$ because $q_i^T A q_j = (A q_i)^T q_j$ and $A q_i \in \mathcal{K}_{i+1}$, which is orthogonal to $q_j$ for $i + 1 < j$. So only the two most recent vectors must be subtracted, and the short recurrence suffices; this is the Arnoldi iteration specialized to symmetric matrices.

The eigenvalues of $T_m$, called Ritz values, approximate eigenvalues of $A$, and the extreme ones converge first, often long before $m$ reaches $n$. Example: for $A = \mathrm{diag}(1, 2, 3)$ and $q_1 = (1, 1, 1)/\sqrt{3}$, one gets $\alpha_1 = 2$ and $w_1' = (-1, 0, 1)/\sqrt{3}$, so $\beta_1 = \sqrt{2/3}$ and the Ritz values of $T_2$ are $2 \pm \sqrt{2/3}$, approaching $1$ and $3$. In floating point arithmetic the vectors $q_j$ lose orthogonality once a Ritz value converges, and copies of converged eigenvalues appear. Paige's analysis explains this, and practical codes use selective or full reorthogonalization.

Going deeper

For a student

The algorithm builds an orthonormal basis of a Krylov subspace with a three-term recurrence, which is cheap in memory and time. Applied to linear systems with a symmetric positive definite matrix, the same recurrence underlies the conjugate gradient method. Its convergence for extreme eigenvalues is described by the Kaniel–Paige theory using Chebyshev polynomials, and the gap between eigenvalues controls the speed. For nonsymmetric matrices one uses the Arnoldi iteration or a two-sided Lanczos process.