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.
Read more about this topic: Lanczos Algorithm
Famous quotes containing the words power, method and/or finding:
“Generally speaking, the political news, whether domestic or foreign, might be written today for the next ten years with sufficient accuracy. Most revolutions in society have not power to interest, still less alarm us; but tell me that our rivers are drying up, or the genus pine dying out in the country, and I might attend.”
—Henry David Thoreau (1817–1862)
“Too poor for a bribe, and too proud to importune,
He had not the method of making a fortune.”
—Thomas Gray (1716–1771)
“One of the many reasons for the bewildering and tragic character of human existence is the fact that social organization is at once necessary and fatal. Men are forever creating such organizations for their own convenience and forever finding themselves the victims of their home-made monsters.”
—Aldous Huxley (1894–1963)