Lanczos Tridiagonalization

The Lanczos algorithm computes an orthonormal basis for the Krylov subspace of a real symmetric matrix A. By enforcing orthogonality against previous vectors, it effectively reduces the original matrix to a symmetric tridiagonal form T.

Worked Example

Consider a 3x3 Diagonal matrix A = diag(1, 2, 3) and a Uniform starting vector q₁ = [1/√3, 1/√3, 1/√3].

Iteration 1:
We compute v = A q₁ = [1/√3, 2/√3, 3/√3].
The projection scalar α₁ = q₁^T v = 1/√3 * 1/√3 + 1/√3 * 2/√3 + 1/√3 * 3/√3 = 1/3 + 2/3 + 3/3 = 6/3 = 2.0.
We orthogonalize v against q₁: v' = v - α₁ q₁ = [1/√3 - 2/√3, 2/√3 - 2/√3, 3/√3 - 2/√3] = [-1/√3, 0, 1/√3].
The residual norm β₁ = ||v'|| = √(1/3 + 0 + 1/3) = √(2/3) ≈ 0.81649658.
We normalize v' to get the next basis vector q₂ = [-1/√2, 0, 1/√2].
Iteration 2:
Compute v = A q₂ = [-1/√2, 0, 3/√2].
The projection scalar α₂ = q₂^T v = 1/2 + 0 + 3/2 = 4/2 = 2.0.
We orthogonalize v against q₂ and q₁: v' = v - α₂ q₂ - β₁ q₁.
v' = [-1/√2 - (-2/√2) - √(2/3)/√3, ... ] which yields the residual norm β₂.

This process constructs a tridiagonal matrix T whose diagonal entries are the α values and subdiagonal entries are the β values.

Experiment

In the Lanczos Tridiagonalization module, you can observe the algorithm step-by-step.

Select Matrix as "Diagonal" and Start as "Uniform".
Set Iterations to 1. Observe the first alpha and beta values being computed from the first basis vector.
Change Iterations to 2. The basis dimension increases to 2, and the tridiagonal matrix T grows accordingly.
Select Start as "Axis". Notice how the algorithm breaks down happily at step 1 because the starting vector is an eigenvector of the matrix. The residual norm drops to 0.

Limitations

The theoretical Lanczos algorithm assumes exact arithmetic. In finite precision (floating-point arithmetic), the computed basis vectors lose their mutual orthogonality. This loss of orthogonality means that the generated basis is no longer strictly orthonormal, which can lead to spurious eigenvalues ("ghosts") in practical eigenvalue computations. The breakdown condition (β = 0) is a "happy breakdown" because it implies an invariant subspace has been found, but in practice, near-zero values require careful handling.

References

Templates for the Solution of Linear Systems - Discusses iterative methods including Lanczos.

The provided reference explains the Lanczos three-term recurrence and its application to symmetric matrices, detailing both the mathematical formulation and the practical implications of finite precision arithmetic.

Lanczos Tridiagonalization