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 (with a symmetric matrix A). The task is to find the places where the normal

is parallel to the vector x, i.e .

A solution x of the above equation with has the squared distance from the origin. Therefore, and . The main axes are .

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 .

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 is transformed to or 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].