Lanczos Algorithm - Power Method For Finding Eigenvalues

Power Method For Finding Eigenvalues

The power method for finding the largest eigenvalue of a matrix can be summarized by noting that if is a random vector and, then in the large limit, approaches the normed eigenvector corresponding to the largest eigenvalue in magnitude.

If is the eigenvalue decomposition of, then . As gets very large, the diagonal matrix of eigenvalues will be dominated by whichever eigenvalue is largest (neglecting the case of two or more equally large eigenvalues, of course). As this happens, will converge to the largest eigenvalue and to the associated eigenvector. If the largest eigenvalue is multiple, then will converge to a vector in the subspace spanned by the eigenvectors associated with those largest eigenvalues.Having found the first eigenvector/value, one can then successively restrict the algorithm to the null space of the known eigenvectors to get the second largest eigenvector/values and so on.

In practice, this simple algorithm does not work very well for computing very many of the eigenvectors because any round-off error will tend to introduce slight components of the more significant eigenvectors back into the computation, degrading the accuracy of the computation. Pure power methods also can converge slowly, even for the first eigenvector.