Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Inverse iteration
Résumé
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 .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.