L'algorithme de Lanczos est une méthode itérative conçue par Cornelius Lanczos qui adapte les méthodes de puissance pour trouver les m valeurs propres et vecteurs propres « les plus utiles » (tendant vers les extrêmes, les plus hautes ou les plus basses) d'une matrice hermitienne n×n, où m est souvent, mais pas nécessairement, beaucoup plus petit que n. Bien que efficace en principe sur le plan computationnel, la méthode telle qu'initialement formulée n'était pas utile en raison de son instabilité numérique. En 1970, Ojalvo et Newman ont montré comment rendre la méthode numériquement stable et l'ont appliquée à la résolution de très grandes structures d'ingénierie soumises à des charges dynamiques. Cela a été réalisé en utilisant une méthode de purification des vecteurs de Lanczos (c'est-à-dire en réorthogonalisant de manière répétée chaque vecteur nouvellement généré avec tous les vecteurs précédemment générés) à n'importe quel degré de précision, ce qui, lorsqu'elle n'était pas effectuée, produisait une série de vecteurs fortement contaminés par ceux associés aux fréquences naturelles les plus basses.
Dans leur travail original, ces auteurs ont également suggéré comment sélectionner un vecteur de départ (c'est-à-dire utiliser un générateur de nombres aléatoires pour sélectionner chaque élément du vecteur de départ) et ont suggéré une méthode déterminée empiriquement pour déterminer m, le nombre réduit de vecteurs (c'est-à-dire qu'il devrait être sélectionné comme étant environ 1,5 fois le nombre de valeurs propres précises souhaitées). Peu après, leur travail a été suivi par Paige, qui a également fourni une analyse d'erreur. En 1988, Ojalvo a produit une histoire plus détaillée de cet algorithme et un test d'erreur efficace pour les valeurs propres.
Aperçu de l'algorithme
Entrez une matrice hermitienne A de taille n×n, et éventuellement un nombre d'itérations m (par défaut, soit m=n). Strictement parlant, l'algorithme n'a pas besoin d'accéder à la matrice explicite, mais seulement à une fonction v↦Av qui calcule le produit de la matrice par un vecteur arbitraire. Cette fonction est appelée au plus m fois. Sortez une matrice n×m V avec des colonnes orthonormales et une matrice tridiagonale symétrique réelle T=VAV de taille m×m. Si m=n, alors V est unitaire, et A=VTV. L'itération de Lanczos est sujette à l'instabilité numérique ; lorsqu'elle est exécutée en arithmétique non exacte, des mesures supplémentaires (comme décrit dans les sections suivantes) doivent être prises pour garantir la validité des résultats.
L'algorithme procède en générant une séquence de vecteurs orthonormaux v1, v2, ..., vm qui forment une base pour le sous-espace de Krylov. En commençant par un vecteur arbitraire v1 de norme 1, chaque étape calcule un nouveau vecteur en appliquant la matrice A, en orthogonalisant par rapport au vecteur précédent, et en normalisant. Les coefficients αj et βj forment les entrées diagonales et hors diagonale de la matrice tridiagonale T, dont les valeurs propres approximent celles de A.
Stabilité numérique et réorthogonalisation
L'algorithme de Lanczos original souffrait d'une perte d'orthogonalité due à l'arrondi en virgule flottante, conduisant à des valeurs propres parasites et des vecteurs propres inexacts. La stabilisation de 1970 par Ojalvo et Newman a introduit la réorthogonalisation complète : chaque vecteur nouvellement généré est orthogonalisé par rapport à tous les vecteurs précédemment générés. Cela purifie les vecteurs de Lanczos et restaure la stabilité numérique, bien qu'au prix d'un surcoût computationnel accru. L'analyse d'erreur de Paige au début des années 1970 a fourni des bornes théoriques sur les effets de l'arrondi et a justifié l'approche de réorthogonalisation.
Applications en apprentissage automatique
En apprentissage automatique, l'algorithme de Lanczos est utilisé pour les problèmes de valeurs propres à grande échelle, tels que le calcul des valeurs propres supérieures des matrices de covariance dans ACP ou le clustering spectral. Il est également employé en apprentissage profond pour approximer le spectre du Hessien de réseaux neuronaux, ce qui aide à l'analyse d'optimisation et de généralisation. La capacité de l'algorithme à travailler uniquement avec des produits matrice-vecteur le rend adapté aux très grandes matrices apparaissant dans les grands modèles de langage et les systèmes de IA générative, où le stockage explicite de la matrice est infaisable.
Méthodes connexes et extensions
L'algorithme de Lanczos est étroitement lié à la méthode du gradient conjugué pour résoudre des systèmes linéaires, car les deux construisent des sous-espaces de Krylov. Il se connecte également à l'itération d'Arnoldi pour les matrices non hermitiennes. Des variantes telles que l'algorithme de Lanczos par blocs gèrent plusieurs vecteurs de départ, et la méthode de Lanczos redémarrée implicitement (utilisée dans ARPACK) améliore la convergence et l'utilisation de la mémoire. Ces extensions sont implémentées dans des bibliothèques numériques comme LAPACK et SciPy, faisant de l'algorithme un outil standard en calcul scientifique.
Impact historique et utilisation moderne
Depuis sa stabilisation, l'algorithme de Lanczos a été appliqué à l'ingénierie structurelle, à la chimie quantique et au traitement du signal. Dans le contexte de l'intelligence artificielle, il sous-tend de nombreuses méthodes spectrales utilisées dans l'analyse de données et la compression de modèles. L'efficacité et la robustesse de l'algorithme en ont fait une pierre angulaire de l'algèbre linéaire numérique, avec des recherches en cours pour améliorer sa stabilité et sa parallélisation pour le matériel moderne tel que les GPU et les accélérateurs d'IA spécialisés.
Voir aussi
- itération de puissance
- décomposition en valeurs propres
- sous-espace de Krylov
- gradient conjugué