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.

A product of two tridiagonal matrices is a tridiagonal matrix; a QR decomposition of a tridiagonal matrix is a tridiagonal matrix. Therefore one can use special subroutines which work with tridiagonal matrices and thus perform QR diagonalization very effectively.

Lanczos tridiagonalization. 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 {a₁,...,a_n} are the diagonal elements of T and {b₂,...,b_n} are the off-diagonal elements, then the equation AQ=QT can be written as Aq_i=b_iq_i-1+a_iq_i+b_i+1q_i+1 , where a_i=q_i^TAq_i.

From this we can define the iterative procedure q_i+1=normalized[(A-a_i1)q_i-b_iq_i-1] , b_i+1=norm_of_that_vector

One starts with a randomly chosen starting vector q₁ and makes as many iterations as needed for the convergence of the desired number of eigenvalues.

Steepest descent method. The method is used when only few lowest (nondegenerate) eigenvalues are needed. It is based on the variational principle λ[x]~ ≡ ~^(xTAx)/_(x^Tx)~≥~λ₁. We start with an arbitrary initial vector x and make an improvement upon it by adding a (small) correction x~→~x~+~αΔx, where Δx~ ≡ ~(A-λ)x, and α is a parameter. For small α<0 the new eigenvalue λ[x~+~αΔx]~λ[x]~+ 2α(Δx^TΔx) + α²(Δx^TAΔx) will always be smaller than the original unless we are at the solution (Δx=0). The parameter α is chosen to minimize the new λ

Problems

1. Implement the Lanczos tridiagonalization. For simplicity let your subroutine return the tridiagonal matrix T as an ordinary matrix.
2. (Non-obligatory) Implement the steepest descent method.