Voir la source de Algorithme de recherche de valeur propre


Un enjeu important en [[analyse numérique]] consiste à développer des [[Algorithme|algorithmes]] efficaces et stables pour trouver les [[Valeur propre (synthèse)|valeurs propres]] d'une [[Matrice (mathématiques)|matrice]]. Ces '''algorithmes de recherche de valeurs propres''' peuvent être étendus pour donner les [[vecteurs propres]] associés.

== Valeurs et vecteurs propres ==
{{article détaillé|Valeur propre, vecteur propre et espace propre}}
Pour une matrice carrée {{mvar|A}} de taille {{math|''n'' &times; ''n''}} réelle ou complexe, une ''[[valeur propre]]'' {{math|λ}} et son ''[[vecteur propre généralisé]]'' associé {{math|'''v'''}} sont un couple vérifiant la relation<ref name="Axler">{{article
 | nom = Axler
 | prénom = Sheldon
 | lien auteur = Sheldon Axler
 | titre = Down with Determinants!
 | journal = American Mathematical Monthly 
 | volume = 102
 | pages = 139–154
 | url = http://www.axler.net/DwD.pdf
 | année = 1995
 | doi=10.2307/2975348}}</ref>

:<math>\left(A - \lambda I\right)^k {\mathbf v} = 0,</math>

où {{math|'''v'''}} est un vecteur colonne {{math|''n'' &times; 1}} non nul, {{math|''I''}} la [[matrice identité]] de taille {{math|''n'' &times; ''n''}}, {{mvar|k}} un [[Entier naturel|entier positif]]. {{math|λ}} et {{math|'''v'''}} peuvent être complexes même pour {{mvar|A}} réelle. Si {{math|''k'' {{=}} 1}}, le vecteur est simplement appelé ''vecteur propre'' et vérifie donc {{math|''A'''''v''' {{=}} ''λ'''''v'''}}. Toute valeur propre {{math|λ}} de {{mvar|A}} a des vecteurs propres « ordinaires » qui lui sont associés, dans le sens où si {{mvar|k}} est le plus petit entier vérifiant {{math|1=(''A'' – λ''I'')<sup>''k''</sup> '''v''' = 0}} pour un vecteur propre généralisé {{math|'''v'''}}, alors {{math|1=(''A'' – λ''I'')<sup>''k''–1</sup> '''v'''}} est un vecteur propre ordinaire. La valeur {{mvar|k}} peut toujours être prise comme inférieure ou égale à {{mvar|n}}. En particulier, {{math|1=(''A'' – λ''I'')<sup>''n''</sup> '''v''' = 0}} pour tout vecteur propre généralisé {{math|'''v'''}} associé à {{math|λ}}.

Pour toute valeur propre {{math|λ}} de {{mvar|A}}, le [[Noyau (algèbre)|noyau]] {{math|ker(''A'' – λ''I'')}} est le [[sous-espace vectoriel engendré]] par tous les vecteurs propres associés à {{math|λ}} (dont le [[vecteur nul]]), qu'on appelle ''[[espace propre]]'' de {{math|λ}}, tandis que l'espace vectoriel {{math|ker((''A'' – λ''I'')<sup>''n''</sup>)}} est le sous-espace vectoriel engendré par tous les vecteurs propres généralisés associés, et donc appelé ''[[espace propre généralisé]]''. La ''[[multiplicité géométrique]]'' de {{math|λ}} est la dimension de ce sous-espace. La ''[[multiplicité algébrique]]'' de {{math|λ}} est la dimension de son espace propre généralisé. Cette terminologie se justifie en remarquant que

:<math>p_A(z) = {\rm det}( zI - A) = \prod_{i=1}^k (z - \lambda_i)^{\alpha_i},</math>

où {{math|det}} est le [[déterminant (mathématiques)|déterminant]], les {{math|λ<sub>''i''</sub>}} sont les valeurs propres de {{mvar|A}}et les {{math|α<sub>''i''</sub>}} sont les multiplicités algébriques associées. La fonction {{math|''p<sub>A</sub>''(''z'')}} est le ''[[polynôme caractéristique]]'' de {{mvar|A}}. Ainsi, la multiplicité algébrique est la multiplicité de la valeur propre comme racine du polynôme caractéristique. Comme tout vecteur propre est un vecteur propre généralisé, la multiplicité géométrique est inférieure ou égale à la multiplicité algébrique. La somme des multiplicités algébriques vaut {{mvar|n}}, le degré du polynôme caractéristique. L'équation {{math|1=''p<sub>A</sub>''(''z'') = 0}} est appelé ''équation caractéristique'', car ses racines sont les valeurs propres de {{mvar|A}}. Par le [[théorème de Cayley-Hamilton]], {{mvar|A}} vérifie la même équation : {{math|1=''p<sub>A</sub>''(''A'') = 0}}<ref group="note">Il faut cependant la considérer sous sa forme matricielle, où le terme constant vaut la matrice identité.</ref>. Par conséquent, les colonnes de la matrice <math>\textstyle \prod_{i \ne j} (A - \lambda_iI)^{\alpha_i}</math> sont soit nulles soit des vecteurs propres généralisés de la valeur propre {{math|λ<sub>''j''</sub>}}, car ils sont annulés par {{math|(''A'' – λ{{ind|''j''}}''I''){{exp|''α{{ind|j}}''}}}}. En fait, l'[[espace colonne]] (le sous-espace vectoriel engendré par les colonnes de la matrice) est l'espace propre généralisé de {{math|λ<sub>''j''</sub>.}}

Toute collection de vecteurs propres généralisés de valeurs propres distinctes est linéairement indépendante, donc une base de {{math|ℂ<sup>''n''</sup>}} peut être choisi à partir de vecteurs propres généralisés. Plus précisément, cette base {{math|('''v'''<sub>''i''</sub>){{indexp|''i''{{=}}1|''n''}}}} peut être choisie et ordonnée de sorte que
:* si {{math|'''v'''<sub>''i''</sub>}} et {{math|'''v'''<sub>''j''</sub>}} ont la même valeur propre, alors tout {{math|'''v'''<sub>''k''</sub>}} pour tout {{mvar|k}} entre {{mvar|i}} et {{mvar|j}}, et
:* si {{math|'''v'''<sub>''i''</sub>}} n'est pas un vecteur propre ordinaire, associé à la valeur propre {{math|λ<sub>''i''</sub>}}, alors {{math|1=(''A'' – λ<sub>''i''</sub>''I'' )'''v'''<sub>''i''</sub> = '''v'''<sub>''i''–1</sub>}} (en particulier, {{math|'''v'''<sub>1</sub>}} doit être un vecteur propre ordinaire).
Si ces vecteurs de base sont rangés comme [[Vecteur colonne|vecteurs colonnes]] d'une matrice {{math|''V'' {{=}} [ '''v'''<sub>1</sub>  '''v'''<sub>2</sub>  ... '''v'''<sub>''n''</sub> ]}}, alors {{mvar|V}} peut être utilisé pour transformer {{mvar|A}} en sa [[Réduction de Jordan|forme de Jordan]] :
:<math>V^{-1}AV = \begin{pmatrix} \lambda_1 & \beta_1 & 0 & \ldots & 0 \\ 0 & \lambda_2 & \beta_2 & \ldots & 0 \\ 0 & 0 & \lambda_3 & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & \lambda_n \end{pmatrix},</math>

où les {{math|λ<sub>''i''</sub>}} sont les valeurs propres, {{math|1=''β''<sub>''i''</sub> = 1}} si {{math|1=(''A'' – λ<sub>''i''+1</sub>)'''v'''<sub>''i''+1</sub> = '''v'''<sub>''i''</sub>}} et {{math|1=''β''<sub>''i''</sub> = 0}} sinon.

Plus généralement, si {{mvar|W}} est une [[matrice inversible]], et {{math|λ}} est une valeur propre de {{mvar|A}} de vecteur propre généralisé {{math|'''v'''}}, alors {{math|1=(''W''<sup>−1</sup>''AW'' – λ''I'' )<sup>''k''</sup> ''W''<sup>−''k''</sup>'''v''' = 0}}. Ainsi {{math|λ}} est une valeur propre de {{math|''W''<sup>−1</sup>''AW''}} pour tout vecteur propre généralisé {{math|''W''<sup>−''k''</sup>'''v'''}}. De plus, des [[matrices semblables]] ont les mêmes valeurs propres.

=== Matrices symétriques réelles, normales et hermitiennes ===
{{article détaillé|Matrice adjointe|Matrice normale|Matrice hermitienne}}

La [[matrice adjointe]] {{math|''M''<sup>*</sup>}} d'une matrice complexe {{mvar|M}} est la transposée de la conjuguée {{mvar|M}} : {{math|1=''M'' <sup>*</sup> = {{overline|''M''}} <sup>T</sup>}}. Une matrice carrée {{mvar|A}} est appelée ''[[matrice normale|normale]]'' si elle commute avec son adjointe : {{math|1=''A''<sup>*</sup>''A'' = ''AA''<sup>*</sup>}}. Elle est appelée ''[[Matrice hermitienne|hermitienne]]'' si elle est égale à son adjointe : {{math|1=''A''<sup>*</sup> = ''A''}}. Toutes les matrices hermitiennes sont normales. Si {{mvar|A}} est réelle, l'adjointe est sa transposée, et {{mvar|A}} est hermitienne si et seulement si elle est [[Matrice symétrique|symétrique]]. Une fois appliquée aux vecteurs colonnes, l'adjointe peut être utilisée pour définir le [[produit scalaire canonique]] sur {{math|ℂ<sup>''n''</sup>}}: {{math|1='''w''' · '''v''' = '''w'''<sup>*</sup> '''v'''}}<ref group="note">Cet ordre, avec le conjugué à gauche, est privilégié par les physiciens. Les algébristes placent plutôt le conjugué linéaire à droite : {{math|1='''w''' · '''v''' = '''v'''<sup>*</sup> '''w'''}}.</ref>. Les matrices normales, hermitiennes et symétriques de réelles ont plusieurs propriétés utiles :
:* tout vecteur propre généralisé d'une matrice normale est un vecteur propre ordinaire ;
:* toute matrice normale est similaire à une [[matrice diagonale]], car sa forme normale de Jordan est diagonale ;
:* deux vecteurs propres associés à des valeurs propres distinctes d'une même matrice normale sont orthogonaux ;
:* le noyau et l'image d'une matrice normale sont orthogonaux ;
:* pour toute matrice normale {{mvar|A}}, {{math|ℂ<sup>''n''</sup>}} a une [[Base orthonormée|base orthonormale]] de vecteurs propres de {{mvar|A}}. La matrice correspondante de vecteurs propres est [[Matrice unitaire|unitaire]] ;
:* les valeurs propres d'une matrice hermitienne sont réelles, car {{math|1=({{overline|λ}} − λ)'''v''' = (''A''<sup>*</sup> − ''A'')'''v''' = (''A'' − ''A'')'''v''' = 0}} pour un vecteur propre non nul {{math|'''v'''}} ;
:* si {{mvar|A}} est réelle, il y a une base orthonormale de {{math|'''R'''<sup>''n''</sup>}} constituée de vecteurs propres de {{mvar|A}} si et seulement si {{mvar|A}} est symétrique.

Il est possible qu'une matrice réelle ou complexe n'ait que des valeurs propres réelles sans être hermitienne. Par exemple, une matrice réelle triangulaire a ses valeurs propres sur sa diagonale, mais elle n'est pas symétrique dans le cas général.

== Conditionnement ==

Tout [[Problème mathématique|problème]] de calcul numérique peut être vu comme l'évaluation d'une [[Fonction (mathématiques)|fonction]] &fnof; en un point {{mvar|x}}. Le [[conditionnement (analyse numérique)|conditionnement]] {{math|''κ''(&fnof;, ''x'')}} du problème est le rapport de l'[[erreur relative]] de la réponse sur l'erreur relative de l'entrée, qui varie selon la fonction et l'entrée. Le conditionnement décrit la variation de l'erreur pendant le calcul. Son [[logarithme décimal]] donne le nombre de chiffres perdus entre l'entrée et la sortie. Il reste cependant un rapport optimal. Il reflète l'instabilité induite par le problème, indépendamment de la méthode de résolution. Aucun algorithme ne peut produire des résultats plus précis que ceux donnés par le conditionnement{{Référence souhaitée|date=6 janvier 2024}}, sauf cas exceptionnels{{Lesquels|date=6 janvier 2024}}. Cependant, un algorithme mal choisi peut empirer les résultats. Par exemple, le problème de recherche des valeurs propres d'une matrice normale est toujours bien conditionné mais la recherche des [[Racine d'un polynôme|racines d'un polynôme]] peut être très mal conditionné. Ainsi, les algorithmes de recherche de valeurs propres qui se reposent sur le calcul du polynôme caractéristique puis la recherche des zéros de ce polynôme peut donner de très mauvais résultats, car le calcul des coefficients du polynôme caractéristique est numériquement instable (voir le cas du [[polynôme de Wilkinson]]).

Pour le problème de résolution de l'équation linéaire {{math|1=''A'''''v''' = '''b'''}} où {{mvar|A}} est [[Inverse|inversible]], le [[Conditionnement (analyse numérique)#Conditionnement d'une matrice|conditionnement]] {{math|1=''κ''(''A''<sup>−1</sup>, '''b''')}} est donné par {{math|1={{!!}}''A''{{!!}}<sub>op</sub>{{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub>}}, où {{nowrap|{{!!}}  {{!!}}<sub>op</sub>}} est la [[norme d'opérateur]] subordonnée à la [[norme euclidienne]] sur {{math|ℂ<sup>''n''</sup>}}. Puisqu'il est indépendant de {{math|'''b'''}} et de la même forme pour {{mvar|A}} et {{math|''A''<sup>−1</sup>}}, on le désigne comme le conditionnement {{math|''κ''(''A'')}} de la matrice {{mvar|A}}. Cette valeur {{math|''κ''(''A'')}} est également la [[valeur absolue]] du rapport entre la plus grande valeur propre de {{math|''A''}} sur sa plus petite. Si {{mvar|A}} est [[Matrice unitaire|unitaire]], alors {{math|1={{!!}}''A''{{!!}}<sub>op</sub> = {{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub> = 1}}, et donc {{math|1=''κ''(''A'') = 1}}. <u>Pour une matrice quelconque, la norme d'opérateur est souvent difficile à calculer et le conditionnement est calculé par d'autres normes matricielles</u>{{Évasif}}.

Pour le problème de valeurs propres, le [[théorème de Bauer-Fike]] établit que si {{math|λ}} est une valeur propre d'une [[matrice diagonalisable]] {{mvar|A}} avec pour matrice de vecteurs propres {{math|''V''}}, alors l'erreur absolue en calculant {{math|λ}} est majorée par le produit de {{math|''κ''(''V'')}} et de l'erreur absolue en {{math|''A''}}<ref>{{article | auteur1 = F. L. Bauer
 | auteur2 = C. T. Fike | titre = Norms and exclusion theorems
 | journal = Numer. Math. 
 | volume = 2
 | pages = 137–141
 | année = 1960
 | doi=10.1007/bf01386217}}</ref>. Par corollaire, le conditionnement pour trouver {{math|λ}} vaut {{math|1=''κ''(λ, ''A'') = ''κ''(''V'') = {{!!}}''V'' {{!!}}<sub>op</sub> {{!!}}''V'' <sup>−1</sup>{{!!}}<sub>op</sub>}}. Si {{mvar|A}} est normale, alors {{mvar|V}} est unitaire, et {{math|1=''κ''(λ, ''A'') = 1}}. Ainsi, le problème de recherche de valeurs propres pour une matrice normale est toujours bien conditionné.

Il a été montré que le conditionnement du problème de recherche des [[Espace propre|espaces propres]] d'une [[matrice normale]] {{mvar|A}} correspondant à une valeur propre {{math|λ}} est inversement proportionnel à la distance minimum entre {{math|λ}} et les autres valeurs propres de {{mvar|A}}<ref>{{article
 | auteur = S.C. Eisenstat
 | auteur2 = I.C.F. Ipsen
 | titre = Relative Perturbation Results for Eigenvalues and Eigenvectors of Diagonalisable Matrices
 | journal = BIT
 | volume = 38
 | numéro = 3
 | pages = 502–9
 | année = 1998
 | doi=10.1007/bf02510256}}</ref>. En particulier, le problème d'espace propre pour les matrices normales est bien conditionné pour les valeurs propres isolées{{Quoi|date=6 janvier 2024}} ; sinon, on peut au mieux identifier le sous-espace engendré par les vecteurs propres de valeurs propres proches{{Référence souhaitée|date=6 janvier 2024}}.

== Idée directrice des algorithmes ==

Tout [[polynôme unitaire]] est le [[polynôme caractéristique]] de sa [[matrice compagnon]]. Ainsi, un algorithme général pour trouver des valeurs propres peut être basé sur la recherche des [[Racine d'un polynôme|racines d'un polynôme]]. Le [[théorème d'Abel-Ruffini]] montre que tout algorithme de la sorte pour des dimensions supérieures à 4 peut être soit infini, soit impliquer des fonctions plus compliquées que des polynômes ou des fonctions rationnelles. Pour cette raison, les algorithmes qui calculent exactement les valeurs propres en un nombre fini d'étapes n'existent que pour des classes spécifiques{{Lesquelles|date=6 janvier 2024}} de matrices. Dans le cas général{{Lequel|date=6 janvier 2024}}, les algorithmes sont [[Méthode itérative|itératifs]], améliorant l'approximation à chaque itération.

Certains algorithmes donnent toutes les valeurs propres, d'autres en donnent plusieurs à la fois, d'autres une seule. Toutefois, tous les algorithmes donnés plus bas peuvent être utilisés pour donner toutes les valeurs propres : une fois qu'une valeur propre {{mvar|λ}} d'une matrice {{mvar|A}} a été identifiée, la méthode peut être adaptée pour diriger les calculs vers une autre solution ou réduire le problème à un nouveau{{Quoi|date=6 janvier 2024}} dont {{mvar|λ}} n'est plus solution.

La redirection est souvent faite par décalage : remplacer {{mvar|A}} par {{math|''A'' – ''μI''}} pour une constante {{mvar|μ}}. La valeur propre obtenue par {{math|''A'' – ''μI''}} doit avoir {{mvar|μ}} ajoutée pour obtenir une valeur propre de {{mvar|A}}. Par exemple, pour la [[méthode de la puissance itérée]], on prend {{math|1=''μ'' = ''λ''}}. Cette méthode donne la valeur propre de valeur absolue plus élevée, ainsi même si {{mvar|λ}} n'est qu'approchée, on ne la trouvera pas une deuxième fois par la puissance itérée. Inversement, les méthodes basées sur la [[Méthode de la puissance inverse|puissance inverse]] trouvent la plus petite valeur propre, donc {{mvar|μ}} doit être choisi loin de {{mvar|λ}}, éventuellement plus proche d'une autre valeur propre.

La réduction peut être faite en restreignant {{mvar|A}} à l'espace colonne de la matrice {{math|''A'' – ''λI''}}. Comme cette matrice est [[Singularité (mathématiques)|singulière]], l'espace colonne est de [[dimension d'un espace vectoriel|dimension]] plus petite. L'algorithme de recherche des valeurs propres peut alors être appliqué à la matrice restreinte, et le processus peut être répété jusqu'à avoir obtenu toutes les valeurs propres.

Si un algorithme ne donne pas de vecteurs propres, une pratique courante est d'utiliser une algorithme d'itération inverse avec {{mvar|μ}} fixé proche d'une approximation de valeur propre. Cela va vite converger vers un vecteur propre associé à la valeur propre la plus proche de {{mvar|μ}}. Pour de petites matrices, une alternative est de regarder l'espace colonne du produit de {{math|''A'' – ''λ{{'}}I''}} pour chaque valeur propre {{mvar|λ{{'}}}}.

== Transformations en matrices de Hessenberg et tridiagonales ==

{{article détaillé|Matrice de Hessenberg}}

Un cas idéal est l'étude d'une matrice triangulaire, car ses valeurs propres sont ses coefficients diagonaux. Cependant, pour une matrice quelconque, il n'y a aucune méthode finie semblable que le [[pivot de Gauss]] pour triangulariser une matrice tout en préservant ses valeurs propres. Il est toutefois possible d'atteindre une forme proche de triangulaire. Une [[matrice de Hessenberg|matrice de Hessenberg supérieure]] est une matrice carrée dont tous les coefficients sous la première sous-diagonale sont nuls ; une matrice de Hessenberg inférieure est définie de manière similaire. Les matrices qui sont à la fois de Hessenberg inférieures et supérieures sont [[Matrice tridiagonale|tridiagonales]]. Les matrices de Hessenberg et tridiagonales sont les points de départ de nombreux algorithmes de recherche de valeurs propres car les nombreux coefficients nuls simplifient la complexité du problème. Plusieurs méthodes sont couramment utilisées pour convertir une matrice donnée en une forme de Hessenberg avec les mêmes valeurs propres. Si la matrice originale est symétrique ou hermitienne, la matrice résultante sera tridiagonale.

Si seules les valeurs propres sont recherchées, le calcul de la matrice de passage n'est pas nécessaire, les deux matrices partageant les mêmes valeurs propres. Si les vecteurs propres sont voulus, la matrice de passage peut être nécessaire pour transformer les vecteurs propres de la matrice de Hessenberg en ceux de la matrice originale.

{| class="wikitable" style="text-align: center"
|-
! Méthode !! S'applique à une matrice... !! Donne une matrice... !! Coût sans matrice de passage !! Coût avec matrice de passage !! Description
|-
| [[Transformation de Householder]] || Quelconque || de Hessenberg || {{math|{{frac|2''n''<sup>3</sup>|3}} + ''O''(''n''<sup>2</sup>)}}<ref name=NumericalRecipes>{{Ouvrage
| langue=en
| prénom1=William H.
| nom1=Press
| prénom2=Saul A.
| nom2=Teukolsky
| prénom3=William T.
| nom3=Vetterling
| prénom4=Brian P.
| nom4=Flannery
| titre=Numerical Recipes in C
| sous-titre=The Art of Scientific Computing
| éditeur=Cambridge University Press
| année=1992
| numéro d'édition=2nd
| pages totales=994
| isbn=978-0-521-43108-8
| isbn10=0-521-43108-5
| bnf=373821813
}}</ref>{{rp|page=474}} || {{math|{{frac|4''n''<sup>3</sup>|3}} + ''O''(''n''<sup>2</sup>)}}<ref name=NumericalRecipes />{{rp|page=474}} || align="left" | Envoie chaque colonne vers un sous-espace nul pour les coefficients bas.
|-
| {{Lien|trad=Givens rotation|Rotation de Givens|texte=Rotations de Givens}} || Quelconque || de Hessenberg || {{math|{{frac|4''n''<sup>3</sup>|3}} + ''O''(''n''<sup>2</sup>)}}<ref name=NumericalRecipes />{{rp|page=470}} ||  || align="left" | Application de rotations planaires pour annuler des coefficients choisis, dans un ordre telle qu'un coefficient annulé le reste. 
|-
| [[Algorithme d'Arnoldi]] || Quelconque || de Hessenberg || {{N/A}} || {{N/A}} || align="left" | [[Algorithme de Gram-Schmidt|Orthogonalisation de Gram-Schmidt]] sur des [[Sous-espace de Krylov|sous-espaces de Krylov]].
|-
| [[Algorithme de Lanczos]] || Hermitienne || Tridiagonale || {{N/A}} || {{N/A}} || align="left" | Itération d'Arnoldi adaptée au cas hermitien. 
|}

Pour les problèmes de valeurs propres d'une matrice tridiagonale, toutes les valeurs propres (sans les vecteurs propres) peuvent être calculées en {{math|''O''(''n'')}}, par dichotomie dans le polynôme caractéristique.

== Algorithmes itératifs ==

Les algorithmes itératifs résolvent le problème des valeurs propres en générant des suites convergeant vers les valeurs propres. Certains algorithmes créent également des suites de vecteurs convergeant vers les vecteurs propres. Plus communément, les suites de valeurs propres sont exprimées comme suites de matrices similaires convergeant vers une matrice diagonale ou tridiagonale, rendant la lecture des valeurs propres aisée. Les suites de vecteurs propres apparaissent dans les matrices de passage correspondantes.

{| class="wikitable" style="text-align: center"
|-
! Méthode !! S'applique à !! Produit !! Coût par itération !! Convergence !! Description
|-
| [[Méthode de la puissance itérée]] || Toutes || Valeur propre de plus grand module + vecteur propre associé || {{math|''O''(''n''<sup>2</sup>)}} || Linéaire || align="left" | Application répétée d'une matrice à un vecteur arbitraire puis renormalisation.
|-
| [[Méthode de la puissance inverse]]|| Toutes || {{nowrap|Valeur propre plus proche de {{mvar|μ}}}} || {{N/A}} || Linéaire ||  align="left" | Puissance itérée sur {{math|(''A'' − ''μI'' )<sup>−1</sup>}}
|-
| [[Itération de Rayleigh]] || Hermitienne || Valeur + vecteur propre le plus proche || {{N/A}} || Cubique ||  align="left" | Puissance itérée sur {{math|(''A'' − ''μ<sub>i</sub>I'' )<sup>−1</sup>,}} avec {{mvar|μ<sub>i</sub>}} à chaque pas le quotient de Rayleigh du pas précédent.
|-
| width="200" | [[Algorithme inverse préconditionné]]<ref>{{article
| nom=Neymeyr
| prénom=K.
| titre=A geometric theory for preconditioned inverse iteration IV: On the fastest convergence cases.
| journal=Linear Algebra Appl.
| volume=415
| numéro=1
| pages=114–139
| année=2006
| doi=10.1016/j.laa.2005.06.022
}}</ref> ou [[LOBPCG]] || Réelle symétrique [[Matrice définie positive|définie positive]] || Valeur propre plus proche de {{mvar|μ}} || colspan="2" |Dépend du préconditionneur || align="left" | Puissance inverse avec un [[préconditionneur]] (approximation de l'inverse de {{mvar|A}}).
|-
| [[Méthode de dichotomie pour les valeurs propres|Méthode de dichotomie]]|| Réelle symétrique tridiagonale || N'importe quelle valeur propre || {{N/A}} || Linéaire || align="left" | Utilise la [[méthode de dichotomie]] pour trouver les racines du polynôme caractéristique, à partir de sa [[Théorème de Sturm|suite de Sturm]].
|-
| [[Algorithme de Laguerre]]|| Réelle symétrique tridiagonale || N'importe quelle valeur propre || {{N/A}} || Cubique<ref>{{article|langue=en|auteur1=T.Y. Li|auteur2=Zhonggang Zeng | titre=Laguerre's Iteration In Solving The Symmetric Tridiagonal Eigenproblem - Revisited
| périodique=[[SIAM Journal on Scientific Computing]]
| année=1992
}}</ref> || align="left" | Utilisation de la [[méthode de Laguerre]] pour trouver les racines du polynôme caractéristique, à partir de sa suite de Sturm.
|-
| rowspan="2" | {{lien|trad=QR algorithm|Algorithme QR}} ||rowspan="2" | Hessenberg || Toutes les valeurs propres || {{math|''O''(''n''<sup>2</sup>)}} ||rowspan="2" | Cubique || align="left" rowspan="2" | Calcul de la factorisation ''A'' = ''QR'', avec ''Q'' orthogonale et ''R'' triangulaire, puis application à ''RQ'' au pas suivant.
|-
| Tous les couples valeur/vecteur propre || {{math|6''n''<sup>3</sup> + ''O''(''n''<sup>2</sup>)}}
|-
| {{lien|trad=Jacobi eigenvalue algorithm|texte=Méthode de Jacobi|Méthode de Jacobi pour les valeurs propres}} || Réelle symétrique || Toutes les valeurs propres ||{{math|''O''(''n''<sup>3</sup>)}} || Quadratique || align="left" | Rotations de Givens pour annuler si possible les termes non-diagonaux.
|-
| rowspan="2" | {{lien|trad=Divide-and-conquer eigenvalue algorithm|texte=Algorithme diviser-pour-régner|Algorithme diviser-pour-régner pour les valeurs propres}} || rowspan="2" | Hermitienne tridiagonale || Toutes les valeurs propres || {{math|''O''(''n''<sup>2</sup>)}} || rowspan="2" | || align="left" rowspan="2" | Découpe la matrice en sous-matrices qui sont diagonalisées puis recombinées.
|-
| Tous les couples valeur/vecteur propres || {{math|({{frac|4|3}})''n''<sup>3</sup> + ''O''(''n''<sup>2</sup>)}}
|-
| [[Méthode par homotopie]]|| Réelle symétrique tridiagonale || Tous les couples valeur/vecteur propre || {{math|''O''(''n''<sup>2</sup>)}}<ref>{{article
| nom=Chu
| prénom=Moody T.
| titre=A Note on the Homotopy Method for Linear Algebraic Eigenvalue Problems
| journal=Linear Algebra Appl.
| volume=105
| pages=225–236
| année=1988
| doi=10.1016/0024-3795(88)90015-8
}}</ref> || {{N/A}} || align="left" | Construction d'un chemin homotope calculable à partir d'un problème de valeurs propres diagonales.
|-
| [[Méthode du spectre replié]]|| Réelle symétrique || Valeur + vecteur propre de valeur plus proche de {{mvar|μ}} || {{N/A}} || {{N/A}} || align="left" | Puissance inverse préconditionné sur {{math|(''A'' − μ''I'' )<sup>2</sup>}}
|-
| [[Algorithme RRRM]]<ref>{{article
| nom1=Dhillon
| prénom1=Inderjit S.
| nom2=Parlett
| prénom2=Beresford N.
| nom3=Vömel
| prénom3=Christof
| titre=The Design and Implementation of the MRRR Algorithm
| journal=[[ACM Transactions on Mathematical Software]]
| volume=32
| numéro=4
| pages=533–560
| année=2006
| doi=10.1145/1186785.1186788
}}</ref> || Réelle symétrique tridiagonale || Couples valeur/vecteur propres || {{math|''O''(''n''<sup>2</sup>)}} || {{N/A}} || align="left" | "représentation relativement robustes multiples" – puissance inverse sur la [[Factorisation de Cholesky|décomposition de Cholesky]] de la matrice décalée.
	
|}

== Méthodes directes ==

S'il n'existe aucun algorithme simple permettant de calculer directement les valeurs propres pour une matrice quelconque, il existe plusieurs cas où le calcul direct est possible.

=== Matrices triangulaires ===

Puisque le déterminant d'une [[matrice triangulaire]] est le produit de ses coefficients diagonaux, si {{mvar|T}} est triangulaire, alors <math>\textstyle \det(\lambda I - T) = \prod_i (\lambda - T_{ii})</math>. Ainsi, les valeurs propres de {{mvar|T}} sont ses coefficients diagonaux.

=== Équations polynomiales factorisables ===

Si {{mvar|p}} est un polynôme tel que {{math|1=''p''(''A'') = 0}}, alors les valeurs propres de {{mvar|A}} vérifient la même équation. Si {{mvar|p}} peut être simplement factorisé, alors les valeurs propres de {{mvar|A}} sont parmi les racines.

Par exemple, une [[Projecteur (mathématiques)|projection]] est une matrice carrée {{mvar|P}} satisfaisant {{math|1=''P''<sup>2</sup> = ''P''}}. Les racines de l'équation polynomiale scalaire correspondante, {{math|1=λ<sup>2</sup> = λ}}, sont donc 0 et 1. Ainsi, toutes les projections ont 0 et 1 comme valeurs propres. La multiplicité de 0 comme valeur propre est la dimension du [[Noyau (algèbre)#Noyau d'une application linéaire|noyau]] de {{mvar|P}}, et la multiplicité de 1 est le rang de {{mvar|P}}.

Un autre exemple est une matrice {{mvar|A}} vérifiant {{math|1=''A''<sup>2</sup> = α<sup>2</sup>''I''}} pour un scalaire {{mvar|α}}. Les valeurs propres valent donc {{math|±''α''}}. Les opérateurs de projection
:<math>P_+=\frac{1}{2}\left(I+\frac{A}{\alpha}\right),\, P_-=\frac{1}{2}\left(I-\frac{A}{\alpha}\right)</math>
vérifient
:<math>AP_+=\alpha P_+ \quad AP_-=-\alpha P_-</math>
et
:<math>P_+P_+=P_+ \quad P_-P_-=P_- \quad P_+P_-=P_-P_+=0.</math>

Les [[Espace colonne|espaces colonne]] de {{math|''P''<sub>+</sub>}} et {{math|''P''<sub>−</sub>}} sont les espaces propres de {{mvar|''A''}} correspondant à {{math|+''α''}} et {{math|–''α''}}, respectivement.

=== Matrices 2×2 ===

Pour les dimensions 2 à 4, les valeurs propres peuvent être exprimées par des radicaux (d'après le [[théorème de Gauss-Wantzel]]). Si les formules sont connues pour les matrices 2×2 et 3×3, la complexité de l'écriture des [[Méthode de Ferrari|racines d'une équation quartique]] pour les matrices 4×4 peut décourager et amener à les trouver par d'autres moyens.

Pour une matrice 2×2
:<math>A = \begin{pmatrix} a  & b \\ c & d \end{pmatrix},</math>
le polynôme caractéristique est
:<math>\left| \begin{matrix} \lambda - a & -b \\ -c & \lambda - d \end{matrix} \right| = \lambda^2\, -\, ( a + d )\lambda\, +\, ( ad - bc ) = \lambda^2\, -\, \lambda\, {\rm Tr}(A)\, +\, {\rm det}(A).</math>
Ainsi, les valeurs propres peuvent être obtenues par [[Équation du second degré|les égalités usuelles]] :

:<math>\lambda = \frac{{\rm Tr}(A) \pm \sqrt{{\rm Tr} (A)^2 - 4\, {\rm det}(A)}}{2}.</math>

On pose {{math|''δ''(''A'') {{=}} {{racine|Tr (''A''){{2}} – 4 det(''A'')}}}} la distance entre les deux valeurs, ce qui permet d'obtenir
:<math>\frac{\partial\lambda}{\partial a} = \frac{1}{2}\left ( 1 \pm \frac{a - d}{\delta(A)} \right ),\qquad \frac{\partial\lambda}{\partial b} =  \frac{\pm c}{\delta(A)}</math>
avec des formules similaires pour {{mvar|c}} et {{mvar|d}}. De là, on en déduit que le calcul est bien conditionné si les valeurs propres sont isolées.

Les vecteurs propres peuvent être trouvés en utilisant le [[théorème de Cayley-Hamilton]]. Si {{math|''λ''<sub>1</sub>, ''λ''<sub>2</sub>}} sont les valeurs propres, alors {{math|1=(''A'' – ''λ''<sub>1</sub>''I'' )(''A'' – ''λ''<sub>2</sub>''I'' ) {{=}} (''A'' – ''λ''<sub>2</sub>''I'' )(''A'' – ''λ''<sub>1</sub>''I'' ) {{=}} 0}}, donc les colonnes de {{math|(''A'' – λ<sub>2</sub>''I'' )}} sont annulées par {{math|(''A'' – ''λ''<sub>1</sub>''I'' )}} et réciproquement. En supposant que les deux matrices sont non nulles, les colonnes de chacune doivent contenir des vecteurs propres de l'autre valeur propre. (Si l'une des matrices est nulle, alors {{mvar|A}} est un multiple de l'identité et tout vecteur non nul est vecteur propre.)

;Exemple
:<math>A = \begin{pmatrix} 4 & 3 \\ -2 & -3 \end{pmatrix},</math>
vérifie {{math|1=Tr(''A'') = 4 – 3 = 1}} et {{math|1=det(''A'') = 4(–3) – 3(–2) = –6}}, donc l'équation caractéristique vaut

:<math> 0 = \lambda^2 - \lambda - 6 = (\lambda - 3)(\lambda + 2),</math>
et les valeurs propres sont 3 et –2. De là,

:<math>A - 3I = \begin{pmatrix} 1 & 3 \\ -2 & -6 \end{pmatrix}, \qquad  A + 2I = \begin{pmatrix} 6 & 3 \\ -2 & -1 \end{pmatrix}.</math>

Dans les deux matrices, les colonnes sont multiples l'une de l'autre, donc une peut être utilisée. Ainsi, {{math|(1, –2)}} peut être utilisé comme vecteur propre associée à –2, et {{math|(3, –1)}} comme vecteur propre associé à la valeur propre 3, ce qui se vérifie simplement.

=== Matrices 3×3 ===

Si {{mvar|''A''}} est une matrice 3×3, alors son polynôme caractéristique peut s'écrire sous la forme :
:<math>{\rm det} \left( \alpha I - A \right) = \alpha^3 - \alpha^2 {\rm Tr}(A) - \alpha \frac{1}{2}\left( {\rm Tr}(A^2) - {\rm Tr}(A)^2 \right) - {\rm det}(A) = 0.</math>

On peut obtenir les racines par la [[méthode de Cardan]] ou de [[Méthode de Lagrange|Lagrange]], mais un changement affine de {{mvar|A}} peut grandement simplifier l'expression et permettre d'écrire les solutions sous forme trigonométrique. Si {{math|1=''A'' = ''pB'' + ''qI''}}, alors {{mvar|A}} et {{mvar|B}} ont les mêmes vecteurs propres, et {{mvar|β}} est valeur propre de {{mvar|B}} si et seulement si {{math|1=''α'' = ''pβ'' + ''q''}} est valeur propre de {{mvar|A}}. On pose {{math|''q'' {{=}} Tr(''A'')/3}} et {{math|''p'' {{=}} (Tr((''A'' – ''qI''){{2}})/6){{exp|1/2}}}}, ce qui donne
:<math>{\rm det} ( \beta I - B ) = \beta^3 - 3 \beta - {\rm det}(B) = 0.</math>

La substitution {{math|1=''β'' = 2cos ''θ''}} et des calculs de simplification par le développement {{math|1=cos (3''θ'') = 4cos{{3}} ''θ'' – 3cos ''θ''}} mènent à l'égalité {{math|1=cos (3''θ'') = det(''B'')/2}}. Ainsi, les racines s'écrivent sous la forme :
:<math>\beta = 2 \cos\left(\frac{1}{3}\arccos\left( \frac{{\rm det}(B)}{2} \right) + \frac{2k\pi}{3}\right), \quad k = 0, 1, 2.</math>

Si {{math|det(''B'')}} est complexe ou supérieur à 2 en valeur absolue, l'arc cosinus doit être pris sur la même branche pour les trois valeurs de {{mvar|k}}. Ceci n'apparaît pas si {{mvar|A}} est réelle et symétrique, et les calculs des valeurs propres sont grandement simplifiés<ref name=Smith>{{article|nom=Smith |prénom=Oliver K. |titre=Eigenvalues of a symmetric 3 × 3 matrix. |journal=[[Communications of the ACM]] |volume=4 |numéro=4 |date=avril 1961 |page=168 |doi=10.1145/355578.366316}}</ref>.

On peut également obtenir les vecteurs propres de {{mvar|A}} par le [[théorème de Cayley-Hamilton]]. Si {{math|''α''<sub>1</sub>, ''α''<sub>2</sub>, ''α''<sub>3</sub>}} sont trois valeurs propres distinctes pour {{mvar|A}}, alors {{math|1=(''A'' – ''α''<sub>1</sub>''I'')(''A'' – ''α''<sub>2</sub>''I'')(''A'' – ''α''<sub>3</sub>''I'') = 0}}. Donc les colonnes du produit de deux de ces matrices consisteront des vecteurs propres de la troisième. Si {{math|1=''α''<sub>3</sub> = ''α''<sub>1</sub>}}, alors {{math|1=(''A'' – ''α''<sub>1</sub>''I'')<sup>2</sup>(''A'' – ''α''<sub>2</sub>''I'') = (''A'' – ''α''<sub>2</sub>''I'')(''A'' – ''α''<sub>1</sub>''I'')<sup>2</sup> = 0}}. Ainsi l'espace propre généralisé associé à {{math|''α''<sub>1</sub>}} est généré par les colonnes de {{math|''A'' – ''α''<sub>2</sub>''I''}} tandis que l'espace propre ordinaire est généré par les colonnes de {{math|1=(''A'' – ''α''<sub>1</sub>''I'')(''A'' – ''α''<sub>2</sub>''I'')}}. L'espace propre ordinaire de {{math|''α''<sub>2</sub>}} est généré par les colonnes de {{math|(''A'' – ''α''<sub>1</sub>''I''){{2}}}}.

;Exemple
:<math>A = \begin{pmatrix} 3 & 2 & 6 \\ 2 & 2 & 5 \\ -2 & -1 & -4 \end{pmatrix}.</math>

L'équation caractéristique vaut
:<math> 0 = \lambda^3 - \lambda^2 - \lambda + 1 = (\lambda - 1)^2(\lambda + 1),</math>
avec pour valeurs propres 1 (de multiplicité 2) et -1. Ainsi,

:<math>A - I = \begin{pmatrix} 2 & 2 & 6 \\ 2 & 1 & 5 \\ -2 & -1 & -5 \end{pmatrix}, \qquad A + I = \begin{pmatrix} 4 & 2 & 6 \\ 2 & 3 & 5 \\ -2 & -1 & -3 \end{pmatrix}</math>
et
:<math>(A - I)^2 = \begin{pmatrix} -4 & 0 & -8 \\ -4 & 0 & -8 \\ 4 & 0 & 8 \end{pmatrix}, \qquad (A - I)(A + I) = \begin{pmatrix} 0 & 4 & 4 \\ 0 & 2 & 2 \\ 0 & -2 & -2 \end{pmatrix}</math>

Donc {{math|(–4, –4, 4)}} est un vecteur propre pour –1, et {{math|(4, 2, –2)}} est un vecteur propre pour 1. {{math|(2, 3, –1)}} et {{math|(6, 5, –3)}} sont deux vecteurs propres généralisés associés à 1, chacun pouvant être combiné à {{math|(–4, –4, 4)}} et {{math|(4, 2, –2)}} pour former une base de vecteurs propres généralisés pour {{mvar|A}}. Ces vecteurs peuvent être normalisés si nécessaire.

==== Vecteurs propres de matrices 3×3 normales ====
Si {{mvar|A}} est une matrice 3×3 normale, alors le [[produit vectoriel]] peut être utilisé pour trouver les vecteurs propres, car pour ce cas, les noyaux et les espaces colonne sont orthogonaux (ce n'est pas toujours vérifié).

Si {{mvar|λ}} est une valeur propre de {{mvar|A}}, alors le noyau de {{math|''A'' – ''λI''}} est perpendiculaire à son espace colonne, le produit vectoriel de deux colonnes [[Indépendance linéaire|linéairement indépendantes]] de {{math|''A'' – ''λI''}} sera dans le noyau, donc un vecteur propre associé avec {{mvar|λ}}. Comme l'espace colonne est de dimension 2 dans ce cas, l'espace propre doit être de dimension 1, donc tout vecteur propre sera parallèle à celui-ci.

Si {{math|''A'' – ''λI''}} ne contient pas deux colonnes indépendantes mais est différente de {{math|'''0'''}}, le produit vectoriel peut toujours être utilisé. Dans ce cas, {{mvar|λ}} est une valeur propre de multiplicité 2, donc tout vecteur orthogonal à l'espace colonne sera un vecteur propre. Supposons que {{math|'''v'''}} est une colonne non nulle de {{math|''A'' – ''λI''}}. On choisit un vecteur arbitraire {{math|'''u'''}} non [[Colinéarité|colinéaire]] à {{math|'''v'''}}. Alors {{math|'''v''' × '''u'''}} et {{math|('''v''' × '''u''') × '''v'''}} sera orthogonal à {{math|'''v'''}} et sont donc vecteurs propres associés à {{mvar|λ}}.

== Applications ==

La détermination des valeurs et vecteurs propres d'une matrice permet de travailler sur une base propre de celle-ci et de résoudre plus simplement certains problèmes par l'exploitation des propriétés de la base de vecteurs propres.

Parmi les problèmes physiques directes, la [[Équation de Schrödinger#Résolution de l'équation|résolution de l'équation de Schrödinger]] passe par une recherche de modes propres.

Par extension, la résolution numérique d'un problème physique peut se ramener à un problème aux valeurs propres. Par exemple, on étudie un problème de [[corde vibrante]] :
:<math>\forall t\geqslant 0,\, \forall x\in[0;1],\, m \frac{\partial^2 u}{\partial t^2}(t,x)-k\frac{\partial^2 u}{\partial x^2}(t,x)=0,\, u(t,x=0)=u(t,x=1)=0.</math>
Une résolution directe n'est pas possible dans le cas général (pour des coefficients non constants), aussi on va discrétiser {{math|[0;1]}} en un nombre fini de points équirépartis {{math|{''x{{ind|i}}''}{{ind|''i''{{=}}0,...,''n''}}}} et décomposer sur les solutions périodiques en temps : {{math|''u''(''t'',''x'') {{=}} ''w''(''x'')exp(i''ωt'')}}.
L'approximation classique de la [[dérivée seconde]] en espace donne :
:<math>w(x) \approx \frac{-w(x_{i-1}) +2w(x_i)-w(x_{i+1})}{1/n^2}.</math>
Après réécriture, la résolution du problème physique de la corde vibrante revient à la résolution du problème aux valeurs propres :
:<math>A_n \mathbf{w} = \lambda \mathbf{w},</math>
avec
:<math>A_n = 
\begin{pmatrix} 
2 & -1 & 0 & \cdots & 0 \\
-1 & 2 & -1 & \ddots & \vdots \\
0 & \ddots & \ddots & \ddots & 0 \\
\vdots & \ddots & -1 & 2 & -1 \\
0 & \cdots & 0 & -1 & 2
\end{pmatrix},\ \mathbf{w} = \begin{pmatrix} w(x_0) \\ w(x_1) \\ \vdots \\ w(x_n) \end{pmatrix},\ \lambda = \frac{m\omega^2}{k}.
</math>

==Notes==
{{Références|group="note"}}

==Références==
{{Traduction/Référence|en|Eigenvalue algorithm|868852322}}

{{Références}}

== Bibliographie ==
*{{article
 | nom = Bojanczyk
 | prénom = Adam W. 
 | lien auteur =
 |auteur2=Adam Lutoborski
 | titre = Computation of the Euler angles of a symmetric 3X3 matrix
 | journal = [[SIAM Journal on Matrix Analysis and Applications]]
 | volume = 12
 | numéro = 1
 | pages = 41–48
 | périodique =
 | lieu =
 | date = Jan 1991
 | url = http://cacm.acm.org/magazines/1961/4/14532-eigenvalues-of-a-symmetric-3-%C3%83-3-matrix/abstract
 | jstor =
 | issn =
 | doi = 10.1137/0612005}}

{{Palette Analyse Numérique}}

{{Portail|algèbre|informatique théorique}}

{{DEFAULTSORT:Algorithme de recherche des valeurs propres}}
[[Catégorie:Algèbre linéaire]]
[[Catégorie:Analyse numérique]]