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 = H1 is decomposed H1 = Q1R1, then an H2 is computed, H2 = R1Q1. H2 is similar to H1 because H2 = R1Q1 = Q1-1H1Q1, and is decomposed to H2 = Q2R2. Then H3 is formed, H3 = R2Q2, etc. In this way a sequence of Hi'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.