Tridiagonalization. Each iteration of the QR/QL is an O(n³) operation. On a tridiagonal matrix it is only O(n). Therefore the effective strategy is first to make the matrix tridiagonal and then apply the QR/QL algorithm. Tridiagonalization of a matrix is a non-iterative operation with a fixed number of steps. The QR transformation preserves the symmetry and the tridiagonal form of the matrix (and also the Hessenberg form).

Lanczos. Lanczos algorithm is an orthogonal transformation of a (real symmetric) matrix A into a tridiagonal form T: Q^TAQ=T. The tridiagonal matrix T may be of a lower dimension. If {α₁,...,α_n} are the diagonal elements of T and {β₂,...,β_n} are the off-diagonal elements, then the equation AQ=QT can be written as Aq_i=β_iq_i-1+α_iq_i+β_i+1q_i+1, where α_i=q_i^TAq_i. From this we can define the iterative procedure q_i+1=^u/_||u||, β_i+1=||u||, where u=(A-α_i)q_i-β_iq_i-1. One would start with a randomly chosen vector q₁ and make as many iterations as needed for the convergence of the desired number of eigenvalues.

Householder reflection. If x and y are vectors with the same norm, there exists an orthogonal symmetric (Householder) matrix H, such that y=Hx, where H=1-2uu^T, u = ^x-y/_||x-y||, (HH=1 and H=H^T). In particular if x={x₁,...,x_n} the vector y can be chosen as y={x₁,...,x_k,-S,0,...,0}, where S=sign(x_k+1)||{x_k+1,..,x_n}||.

Householder QR decomposition. Using consecutive Householder reflections H_i, i=1..n-1, each of which eliminates subdiagonal elements of the i-th column of matrix A, one can reduce the matrix into a triangular form HA=R, or A=HR, where H=H_n-2...H₁.

Householder tridiagonalization of a real symmetric matrix A is performed by consecutive Householder transformations A→ H_iAH_i, i=1..n-1, each eliminating elements below the subdiagonal of the column i. A useful trick: HAH=A-2uq^T-2qu^T, where q=Au-(u^TAu)u, H=1-2uu^T.

Problems

1. Implement the Lanczos tridiagonalization. For simplicity let your subroutine return the tridiagonal matrix T as an ordinary matrix.
2. (Non-obl.) Implement Householder QR decomposition. Consider the Hilbert matrix A_ij=¹/_i+j-1 and find its QR decomposition using Gram-Schmidt and Housholder methods. Compare accuracy and speed.
3. (Non-obl.) Implement Housholder tridiagonalization.
4. (Non-obl.) Prove that if A is a symmetric tridiagonal matrix and A=QR is its QR-decomposition, then RQ is also a symmetric tridiagonal matrix.