Matrix diagonalization. Eigensystems,eigenvalues and eigenvectors.

A vector x is called an eigenvector of a matrix A with an eigenvalue λ, if Ax=λx. Matrix diagonalization means finding all eigenvalues λ_i and (optionally) eigenvectors x_i of the matrix A. If A is hermitian then its eigenvalues are real and its eigenvectors X={x₁,...,x_n} form a full basis in which the matrix A is diagonal X^TAX=diag{λ₁,...,λ_n}.

Orthogonal transformations A→Q^TAQ, where Q^TQ=1, preserve eigenvalues and eigenvectors.

QR/QL algorithm. If we know QR (or QL) decomposition of matrix A, then the orthogonal transformation A→Q^TAQ=RQ partly turn the matrix A into a triangular form. Successive iterations eventually make it triangular where the eigenvalues are on the diagonal. If there are degenerate eigenvalues there will be a corresponding block-diagonal sub-matrix. For convergence properties it is better to use shifts: instead of QR[A] we do QR[A-s1] and then A→Q^TAQ=RQ+s1. The shift s can be chosen as A_nn. As soon as an eigenvalue is found the matrix is deflated, that is the corresponding row and column are crossed out.

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 (with, e.g. Householder transformation) and then apply the QR/QL algorithm. Tridiagonalization of a matrix is a non-iterative operation with a fixed number of steps.

Lanczos tridiagonalization. Lanczos algorithm is an orthogonal transformation of a 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=normofthatvector

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

Steepest descent method. The method is used when only few lowest 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. Implement after your choice:

1. Lanczos tridiagonalization + QR/QL algorithm with shifts and deflation.
2. Steepest descent method with deflation.