Eigenvalue algorithm

From Wikipedia, the free encyclopedia

In linear algebra, one of the most important problems is designing efficient and stable algorithms for finding the eigenvalues of a matrix. These eigenvalue algorithms may also find eigenvectors.

Contents 1 Characteristic polynomial 2 Power iteration 3 Advanced methods 4 See also

[edit] Characteristic polynomial

Given a matrix A, an eigenvalue λ and its associated eigenvector v are, by definition, a pair such that

Equivalently, (A−λI)v = 0, implying det(A−λI) = 0. This determinant expands to a polynomial in λ, called the characteristic polynomial of A. One common method for finding the eigenvalues of a small matrix is by finding roots of the characteristic polynomial. This is explained in more detail in the article Symbolic computation of matrix eigenvalues.

Unfortunately, this method has some limitations. A general polynomial of order n > 4 cannot be solved by a finite sequence of arithmetic operations and radicals (see Abel-Ruffini theorem). There do exist efficient root-finding algorithms for higher order polynomials. However, finding the roots of the characteristic polynomial may be an ill-conditioned problem even when the underlying eigenvalue problem is well-conditioned. For this reason, this method is rarely used.

The above discussion implies a restriction on all eigenvalue algorithms. It can be shown that for any polynomial, there exists a matrix (see companion matrix) having that polynomial as its characteristic polynomial (actually, there are infinitely many). If there did exist a finite sequence of arithmetic operations for exactly finding the eigenvalues of a general matrix, this would provide a corresponding finite sequence for general polynomials, in contradiction of the Abel-Ruffini theorem. Therefore, general eigenvalue algorithms are expected to be iterative.

[edit] Power iteration

The basic idea of this method is to choose an initial vector b (either an eigenvector approximation or a random vector) and then repeatedly multiply it by the matrix, iteratively calculating Ab, A²b, A³b,…. Suppose the eigenvalues are ordered by magnitude, with λ₁ being the largest, and with associated eigenvector v₁. Then each iteration scales the component of b in the v₁ direction by λ₁, and every other direction by a smaller amount (assuming |λ₂| < |λ₁|). Except for a set of measure zero, for any initial vector the result will converge to an eigenvector corresponding to the dominant eigenvalue. In practice, the vector should be normalized after every iteration.

By itself, power iteration is not very useful. Its convergence is slow except for special cases of matrices, and without modification, it can only find the largest or dominant eigenvalue (and the corresponding eigenvector). However, we can understand a few of the more advanced eigenvalue algorithms as variations of power iteration. In addition, some of the better algorithms for the generalized eigenvalue problem are based on power iteration.

This method can in general be quite slow. It is especially slow if there is an eigenvalue close in magnitude to the dominant eigenvalue.

[edit] Advanced methods

A popular method for finding eigenvalues is the QR algorithm, which is based on the QR decomposition. Other advanced methods include:

• Inverse iteration
• Rayleigh quotient iteration
• Arnoldi iteration
• Lanczos iteration
• Jacobi method
• Bisection
• Divide-and-conquer

Most eigenvalue algorithms rely on first reducing the matrix A to Hessenberg or tridiagonal form. This is usually accomplished via projections.

[edit] See also

• Eigenvector algorithm
  • Richardson eigenvector algorithm
  • Max-Plus eigenvector algorithm
  • Abrams and Lloyd eigenvector algorithm