Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Inverse iteration
Summary
In numerical analysis, inverse iteration (also known as the inverse power method) is an iterative eigenvalue algorithm. It allows one to find an approximate
eigenvector when an approximation to a corresponding eigenvalue is already known.
The method is conceptually similar to the power method.
It appears to have originally been developed to compute resonance frequencies in the field of structural mechanics.
The inverse power iteration algorithm starts with an approximation for the eigenvalue corresponding to the desired eigenvector and a vector , either a randomly selected vector or an approximation to the eigenvector. The method is described by the iteration
where are some constants usually chosen as Since eigenvectors are defined up to multiplication by constant, the choice of can be arbitrary in theory; practical aspects of the choice of are discussed below.
At every iteration, the vector is multiplied by the matrix and normalized.
It is exactly the same formula as in the power method, except replacing the matrix by
The closer the approximation to the eigenvalue is chosen, the faster the algorithm converges; however, incorrect choice of can lead to slow convergence or to the convergence to an eigenvector other than the one desired. In practice, the method is used when a good approximation for the eigenvalue is known, and hence one needs only few (quite often just one) iterations.
The basic idea of the power iteration is choosing an initial vector (either an eigenvector approximation or a random vector) and iteratively calculating . Except for a set of zero measure, for any initial vector, the result will converge to an eigenvector corresponding to the dominant eigenvalue.
The inverse iteration does the same for the matrix , so it converges to the eigenvector corresponding to the dominant eigenvalue of the matrix .
Eigenvalues of this matrix are where are eigenvalues of .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.