Eigenvalue problems

Eigenvalue problems appear as part of the solution in many scientific or engineering applications. An example is the determination of the main axes of a second order surface File:Hepa img253.gif (with a symmetric matrix A). The task is to find the places where the normal

is parallel to the vector x, i.e File:Hepa img255.gif .

A solution x of the above equation with File:Hepa img257.gif has the squared distance File:Hepa img258.gif from the origin. Therefore, File:Hepa img259.gif and File:Hepa img260.gif . The main axes are File:Hepa img261.gif .

The general algebraic eigenvalue problem is given by

with I the identity matrix, with an arbitrary square matrix A, an unknown scalar , and the unknown vector x. A non-trivial solution to this system of n linear homogeneous equations exists if and only if the determinant

This nth degree polynomial in is called the characteristic equation. Its roots are called the eigenvalues and the corresponding vectors x eigenvectors. In the example, x is a right eigenvector for  ; a left eigenvector y is defined by File:Hepa img265.gif .

Solving this polynomial for is not a practical method to solve eigenvalue problems; a QR-based method is a much more adequate tool ( Golub89); it works as follows:

A is reduced to the (upper) Hessenberg matrix H or, if A is symmetric, to a tridiagonal matrix T. The Hessenberg and tridiagonal matrices have the form:

This is done with a ``similarity transform: if S is a non-singular (n,n) matrix, then File:Hepa img255.gif is transformed to File:Hepa img267.gif or File:Hepa img268.gif with y = Sx and B = SAS^-1, i.e. A and B share the same eigenvalues (not the eigenvectors). We will choose for S Householder transformation. The eigenvalues are then found by applying iteratively the QR decomposition, i.e. the Hessenberg (or tridiagonal) matrix H will be decomposed into upper triangular matrices R and orthogonal matrices Q.

The algorithm is surprisingly simple: H = H₁ is decomposed H₁ = Q₁R₁, then an H₂ is computed, H₂ = R₁Q₁. H₂ is similar to H₁ because H₂ = R₁Q₁ = Q₁^-1H₁Q₁, and is decomposed to H₂ = Q₂R₂. Then H₃ is formed, H₃ = R₂Q₂, etc. In this way a sequence of H_i's (with the same eigenvalues) is generated, that finally converges to (for conditions, see Golub89)

respectively.

For access to software, Linear Algebra Packages; the modern literature also gives code, e.g. Press95.