19 Lanczos Algorithm
Iterative method for finding extreme eigenpairs of large, symmetric matrices without explicit \(O(n^2)\) formation.
19.1 Krylov Subspaces
\(\mathcal{K}_k(\bA, \bv) = \text{span}\{\bv,\, \bA\bv,\, \bA^2\bv,\, ...,\, \bA^{k-1}\bv\}\). Intuition: \(\bA^j\bv\) amplifies components along dominant eigenvectors, concentrating information about the spectral edges.
19.2 The Lanczos Recurrence
The process builds an orthonormal basis \(V_k = [\bv_1, ..., \bv_k]\) for \(\mathcal{K}_k\) satisfying: \[ \begin{align} \bA V_k = V_k T_k + \beta_k \bv_{k+1} \be_k^T. \end{align} \]
\(T_k\): Symmetric tridiagonal matrix.
\(\alpha_j = \bv_j^T \bA \bv_j\): Rayleigh quotients (diagonal).
Orthogonalization coefficients (off-diagonal).
Performance Advantage: Unlike Gram-Schmidt, which orthogonalizes against all previous vectors, Lanczos only requires the two previous vectors (three-term recurrence). This makes it \(O(k \cdot \text{nnz})\) for sparse matrices.
19.3 Ritz Values and Vectors
Approximations to the true eigenpairs from the Krylov subspace.
Ritz Value (\(\theta_i\)): Eigenvalue of \(T_k\).
\(V_k \bs_i\), where \(\bs_i\) is an eigenvector of \(T_k\).
The residual of the \(i\)-th Ritz pair \((\theta_i, \tilde{\bu}_i)\) satisfies: \[ \begin{align} \|\bA\tilde{\bu}_i - \theta_i \tilde{\bu}_i\|_2 = \beta_k |s_i(k)|. \end{align} \] Significance: Convergence of a Ritz pair can be monitored for \(O(k)\) cost without forming the full \(n\)-vector \(\tilde{\bu}_i\).
Starting from the Lanczos relation \(\bA V_k = V_k T_k + \beta_k \bv_{k+1} \be_k^T\), multiply by the \(i\)-th eigenvector \(\bs_i\) of \(T_k\) on the right: \[ \begin{align} \bA V_k \bs_i &= V_k T_k \bs_i + \beta_k \bv_{k+1} \be_k^T \bs_i \\ \bA \tilde{\bu}_i &= V_k (\theta_i \bs_i) + \beta_k \bv_{k+1} s_i(k). \end{align} \] where \(s_i(k)\) is the \(k\)-th entry of \(\bs_i\). Rearranging: \[ \begin{align} \bA \tilde{\bu}_i - \theta_i \tilde{\bu}_i = \beta_k \bv_{k+1} s_i(k). \end{align} \] Taking the \(L_2\) norm and using the fact that \(\|\bv_{k+1}\|_2 = 1\): \[ \begin{align} \|\bA \tilde{\bu}_i - \theta_i \tilde{\bu}_i\|_2 &= |\beta_k s_i(k)| \|\bv_{k+1}\|_2 \\ &= \beta_k |s_i(k)|. \end{align} \]
Ghost Eigenvalues: In floating-point, the three-term recurrence loses orthogonality, leading to ``ghost’’ (spurious) copies of eigenvalues. Practical Rule: Use full or selective reorthogonalization to maintain basis integrity.
Connection to Conjugate Gradient: The Lanczos algorithm applied to a symmetric system \(\bA\bx=\bb\) is mathematically equivalent to the Conjugate Gradient method. Both algorithms build the same Krylov subspace and produce identical iterates in exact arithmetic.
Carry out 2 steps of Lanczos for \(\bA = \text{diag}(5, 3, 1)\) starting with \(\bv_1 = \frac{1}{\sqrt{3}}\mathbf{1}\).
Show that \(T_k = V_k^T \bA V_k\) (Galerkin Projection).
Implement Lanczos on a \(50 \times 50\) Hilbert matrix. Count spurious eigenvalues without reorthogonalization.