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.

Characteristic polynomial

The usual method for finding the eigenvalues of a small matrix is by using the characteristic polynomial. The characteristic polynomial, defined as det(A - λI), is a polynomial in λ whose roots are the eigenvalues of A.

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 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.

Power iteration

The basic idea of this method is choosing an initial vector b (either an eigenvector approximation or a random vector) and iteratively calculating Ab,A²b,A³b,.... Except for a set of zero measure, 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.

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.