Eigenvalue algorithm

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-\lambda I)$ , is a polynomial in $\lambda$ whose roots are the eigenvalues of $A$ .

Unfortunately, this method has some limitations. A 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 having that polynomial as its characteristic polynomial (actually, there are infinitely many). If we had a method of finding eigenvalues in a finite number of steps, we would have a method for solving an arbitrary polynomial with a finite number of arithmetic operations and radicals, in direct contradiction with the Abel-Ruffini theorem. Therefore, all general eigenvalue algorithms must be iterative.

Power iteration

Power iteration by itself 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.

The basic idea is iteratively choosing an initial vector b (either an eigenvector approximation or a random vector) and iteratively calculating $Ab,A^{2}b,A^{3}b,...$ . Except for a set of zero measure, for any intial vector, the result will converge to an eigenvector corresponding to the dominant eigenvalue. In practice, the vector should be normalized after every 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

More advanced methods of finding eigenvalues include:

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