Algorithmes de valeurs propres

Les algorithmes de valeurs propres calculent les valeurs propres et les vecteurs propres d'une matrice de manière itérative, car pour les matrices de taille supérieure à quatre par quatre, aucune formule finie ne peut exister.

Definition

Un algorithme de valeurs propres est une procédure numérique itérative visant à approximer les valeurs propres et, éventuellement, les vecteurs propres d'une matrice, étant donné que les valeurs propres sont les racines du polynôme caractéristique et ne peuvent généralement pas être trouvées en un nombre fini d'opérations arithmétiques.

Scope

Ce sujet aborde les itérations de puissance et inverses, la réduction à la forme de Hessenberg ou tridiagonale, l'algorithme QR avec décalages, et les méthodes spécialisées pour le problème des valeurs propres symétriques, ainsi que la théorie des perturbations qui régit la sensibilité des valeurs propres calculées.

Core questions

• Pourquoi le calcul général des valeurs propres doit-il être itératif plutôt que direct ?
• Comment l'algorithme QR décalé converge-t-il vers la forme de Schur, et pourquoi la réduction préliminaire à la forme de Hessenberg est-elle essentielle pour l'efficacité ?
• Qu'est-ce qui rend le problème des valeurs propres symétriques mieux conditionné et propice à des algorithmes spécialisés ?
• Quelle est la sensibilité des valeurs propres aux perturbations, et comment cela dépend-il de la non-normalité de la matrice ?

Key theories

L'algorithme QR

La factorisation répétée d'une matrice en QR et sa recombinaison en RQ, avec des décalages bien choisis et une réduction préliminaire de Hessenberg, conduit la matrice vers une forme triangulaire supérieure (Schur) dont la diagonale contient les valeurs propres ; c'est la méthode standard pour le problème des valeurs propres denses.

Itération de puissance et itération inverse

La multiplication répétée par la matrice converge vers le vecteur propre dominant, tandis que l'itération inverse avec un décalage cible la valeur propre la plus proche du décalage ; ces méthodes sous-tendent à la fois les approches classiques et le raffinement moderne des vecteurs propres.

Théorie des perturbations des valeurs propres

Le théorème de Bauer-Fike et les résultats connexes bornent l'ampleur du déplacement des valeurs propres sous l'effet de perturbations ; pour les matrices symétriques (normales), les valeurs propres sont parfaitement conditionnées, tandis que pour les matrices fortement non normales, elles peuvent être extrêmement sensibles.

Mechanisms

Une matrice dense est d'abord réduite par des transformations de similarité orthogonales à la forme de Hessenberg supérieure (tridiagonale dans le cas symétrique), ce qui préserve les valeurs propres tout en rendant chaque étape QR peu coûteuse. L'itération QR décalée déflate ensuite les valeurs propres convergées une ou deux à la fois à partir du bas de la matrice. Pour les problèmes symétriques, les algorithmes de division et conquête (divide-and-conquer) et MRRR exploitent la structure pour calculer les valeurs propres et les vecteurs propres avec précision et en parallèle.

Clinical relevance

Les calculs de valeurs propres déterminent les modes vibratoires et les fréquences naturelles en ingénierie structurelle et mécanique, la stabilité des systèmes dynamiques et des boucles de contrôle, les niveaux d'énergie en chimie quantique et en physique, ainsi que les méthodes spectrales sous-jacentes à la partition de graphes, au PageRank et à l'analyse en composantes principales.

History

L'algorithme QR a été introduit indépendamment par John Francis et Vera Kublanovskaya vers 1961 et, avec l'ajout de décalages et de la réduction de Hessenberg, est devenu la méthode dominante pour le problème des valeurs propres denses ; l'analyse de Wilkinson a établi sa fiabilité et la théorie des perturbations qui explique sa précision.

Key figures

• James H. Wilkinson
• John G. F. Francis
• Vera Kublanovskaya
• Beresford Parlett

Seminal works

• trefethen1997
• golub2013
• wilkinson1965

Frequently asked questions

Pourquoi les valeurs propres ne peuvent-elles pas être calculées par une formule directe comme une résolution linéaire ?

Les valeurs propres sont les racines du polynôme caractéristique, et selon le théorème d'Abel, les polynômes de degré cinq ou plus n'ont pas de formule générale par radicaux, de sorte que le calcul des valeurs propres pour les matrices de taille supérieure à quatre par quatre doit être itératif.

Les valeurs propres sont-elles toujours bien conditionnées ?

Pour les matrices symétriques et autres matrices normales, les valeurs propres sont parfaitement conditionnées, mais pour les matrices fortement non normales, elles peuvent être très sensibles aux perturbations, c'est pourquoi le spectre seul pourrait ne pas rendre compte du comportement de ces matrices.