Ê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
Algorithme de Lanczos
Résumé
En algèbre linéaire, l’algorithme de Lanczos (ou méthode de Lanczos) est un algorithme itératif pour déterminer les valeurs et vecteurs propres d'une matrice carrée, ou la décomposition en valeurs singulières d'une matrice rectangulaire.
Cet algorithme n'a pas de lien avec le fenêtrage de Lanczos (utilisé par exemple pour le redimensionnement d'images), si ce n'est que tous les deux tirent leur nom du même inventeur, le physicien et mathématicien hongrois Cornelius Lanczos.
La méthode de la puissance itérée pour trouver la plus grande valeur propre d'une matrice carrée symétrique d'ordre p est la suivante.
Si est un vecteur et , alors .
On sait qu'une matrice symétrique est diagonalisable, et les termes de la matrice diagonale sont les valeurs propres de la matrice. Soit donc
la décomposition en valeurs propres de , où U est une matrice orthogonale ;
alors
Pour des valeurs de très grandes, la matrice diagonale des valeurs propres sera dominée par la plus grande d'entre elles - à l'exception du cas où il y a deux plus grandes valeurs égales : en effet, soit la valeur propre de plus grand module.
Alors, converge vers la plus grande valeur propre et au vecteur propre correspondant.
Dans le cas où il y a plusieurs valeurs propres maximales, converge vers un vecteur dans le sous-espace engendré par les vecteurs propres associés à ces valeurs. Après avoir déterminé le premier, on peut successivement restreindre l'algorithme au noyau des vecteurs propres connus pour déterminer les autres.
En pratique, cet algorithme possède deux inconvénients : une vulnérabilité aux erreurs d'arrondi, et une vitesse de convergence parfois trop faible.
L'algorithme de Lanczos améliore la méthode précédente, dans laquelle chaque est restreint à l'orthogonal de toutes les valeurs précédentes. Lors de la construction de ces vecteurs, les constantes de normalisation sont regroupées dans une matrice tridiagonale dont les valeurs propres les plus significatives convergent, rapidement, vers les valeurs propres de la matrice de départ.
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.