2
$\begingroup$

I've implemented a program for computing eigenvectors of some random, symmetric, $N$x$N$ matrix using the power method. I have found difficulty in calculating all $N$ eigenvectors consistently, almost every time the algorithm fails to converge for all $N$. The Wikipedia page on the power method tells me this algorithm is not guaranteed to converge for all $N$ eigenvectors, can someone suggest a way for me to encourage convergence, at least in a majority of the cases? Is this possible? If not, can someone suggest a better algorithm for computing eigenvectors?

$\endgroup$
2
$\begingroup$

Whole books and fields of research are devoted to methods for computing eigenvalues and eigenvectors. Properties of the matrix matter, a lot. The ideal method will depend on whether

  • the matrices are symmetric or nonsymmetric,
  • positive definite or indefinite,
  • sparse or not sparse,
  • you need all the eigenvalues/vectors or just a few,
  • you have $O(1)$ access to the elements of the matrix or just the ability to apply it to vectors via a function call
  • etc...

That said, at the core of most modern methods for finding all the eigenvalues of a generic matrix is the The QR algorithm (the eigenvalue algorithm, not the related orthogonalization algorithm). The methods most used in practice such as the Arnoldi iteration (or Lanczos for symmetric problems) are basically a 2 step process in which the matrix is converted into a nicer form, and then the QR algorithm is used.

Understanding the power method is a good place to start from because it's intuition informs most of the other methods in some way or another.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.