Eigenvalues and eigenvectors: Difference between revisions

Revision as of 20:53, 21 August 2007

Revision as of 00:25, 3 September 2007

Line 153:

{{details|eigenvalue algorithm}}

In practice, eigenvalues of large matrices are not computed using the characteristic polynomial. Computing the polynomial becomes expensive in itself, and exact (symbolic) roots of a high-degree polynomial can be difficult to compute and express: the [[Abel–Ruffini theorem]] implies that the roots of high-degree (5 and above) polynomials cannot be expressed simply using <math>n</math>th roots. Effective numerical algorithms for approximating roots of polynomials exist, but small errors in the eigenvalues can lead to large errors in the eigenvectors. Therefore, general algorithms to find eigenvectors and eigenvalues, are [[iterative method|iterative]]. The easiest method is the [[power method]]: a [[random]] vector <math>v</math> is chosen and a sequence of [[unit vector]]s is computed as

: <math>\frac{Av}{\|Av\|}</math>, <math>\frac{A^2v}{\|A^2v\|}</math>, <math>\frac{A^3v}{\|A^3v\|}</math>, ...

This [[sequence]] will almost always converge to an eigenvector corresponding to the eigenvalue of greatest magnitude. This algorithm is easy, but not very useful by itself. However, popular methods such as the [[QR algorithm]] are based on it.