Eigenvalues and Eigenvectors - Calculation

Calculation

The complexity of the problem for finding roots/eigenvalues of the characteristic polynomial increases rapidly with increasing the degree of the polynomial (the dimension of the vector space). There are exact solutions for dimensions below 5, but for dimensions greater than or equal to 5 there are generally no exact solutions and one has to resort to numerical methods to find them approximately. (In fact, since the roots of any polynomial can be expressed as eigenvalues of a companion matrix, the Abel–Ruffini theorem implies that there is no general algebraic solution for eigenvalues of 5×5 or larger matrices: any general eigenvalue algorithm is necessarily approximate, although in practice one can obtain any desired accuracy.) Worse, any computational procedure that starts by computing the coefficients of the characteristic polynomial can be very inaccurate in the presence of round-off error, because the roots of a polynomial are an extremely sensitive function of the coefficients (see Wilkinson's polynomial). Efficient, accurate methods to compute eigenvalues and eigenvectors of arbitrary matrices were not known until the advent of the QR algorithm in 1961. Combining Householder transformation with LU decomposition offers better convergence than the QR algorithm. For large Hermitian sparse matrices, the Lanczos algorithm is one example of an efficient iterative method to compute eigenvalues and eigenvectors, among several other possibilities.