Un enjeu important en analyse numérique consiste à développer des algorithmes efficaces et stables pour trouver les valeurs propres d'une matrice. Ces algorithmes de recherche de valeurs propres peuvent être étendus pour donner les vecteurs propres associés.
Valeurs et vecteurs propres
Pour une matrice carrée de taille réelle ou complexe, une valeur propre et son vecteur propre généralisé associé sont un couple vérifiant la relation
où est un vecteur colonne non nul, la matrice identité de taille , un entier positif. et peuvent être complexes même pour réelle. Si , le vecteur est simplement appelé vecteur propre et vérifie donc . Toute valeur propre de a des vecteurs propres « ordinaires » qui lui sont associés, dans le sens où si est le plus petit entier vérifiant pour un vecteur propre généralisé , alors est un vecteur propre ordinaire. La valeur peut toujours être prise comme inférieure ou égale à . En particulier, pour tout vecteur propre généralisé associé à .
Pour toute valeur propre de , le noyau est le sous-espace vectoriel engendré par tous les vecteurs propres associés à (dont le vecteur nul), qu'on appelle espace propre de , tandis que l'espace vectoriel 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 est la dimension de ce sous-espace. La multiplicité algébrique de est la dimension de son espace propre généralisé. Cette terminologie se justifie en remarquant que
où est le déterminant, les sont les valeurs propres de et les sont les multiplicités algébriques associées. La fonction est le polynôme caractéristique de . 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 , le degré du polynôme caractéristique. L'équation est appelé équation caractéristique, car ses racines sont les valeurs propres de . Par le théorème de Cayley-Hamilton, vérifie la même équation : Il faut cependant la considérer sous sa forme matricielle, où le terme constant vaut la matrice identité.. Par conséquent, les colonnes de la matrice sont soit nulles soit des vecteurs propres généralisés de la valeur propre , car ils sont annulés par . En fait, l'espace colonne (le sous-espace vectoriel engendré par les colonnes de la matrice) est l'espace propre généralisé de
Toute collection de vecteurs propres généralisés de valeurs propres distinctes est linéairement indépendante, donc une base de peut être choisi à partir de vecteurs propres généralisés. Plus précisément, cette base peut être choisie et ordonnée de sorte que si et ont la même valeur propre, alors tout pour tout entre et , et si n'est pas un vecteur propre ordinaire, associé à la valeur propre , alors (en particulier, doit être un vecteur propre ordinaire). Si ces vecteurs de base sont rangés comme vecteurs colonnes d'une matrice , alors peut être utilisé pour transformer en sa forme de Jordan :
où les sont les valeurs propres, si et sinon.
Plus généralement, si est une matrice inversible, et est une valeur propre de de vecteur propre généralisé , alors . Ainsi est une valeur propre de pour tout vecteur propre généralisé . De plus, des matrices semblables ont les mêmes valeurs propres.
Matrices symétriques réelles, normales et hermitiennes
La matrice adjointe d'une matrice complexe est la transposée de la conjuguée : . Une matrice carrée est appelée normale si elle commute avec son adjointe : . Elle est appelée hermitienne si elle est égale à son adjointe : . Toutes les matrices hermitiennes sont normales. Si est réelle, l'adjointe est sa transposée, et est hermitienne si et seulement si elle est symétrique. Une fois appliquée aux vecteurs colonnes, l'adjointe peut être utilisée pour définir le produit scalaire canonique sur : Cet ordre, avec le conjugué à gauche, est privilégié par les physiciens. Les algébristes placent plutôt le conjugué linéaire à droite : .. 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 , a une base orthonormale de vecteurs propres de . La matrice correspondante de vecteurs propres est unitaire ; les valeurs propres d'une matrice hermitienne sont réelles, car pour un vecteur propre non nul ; si est réelle, il y a une base orthonormale de constituée de vecteurs propres de si et seulement si 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 de calcul numérique peut être vu comme l'évaluation d'une fonction ƒ en un point . Le conditionnement 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, sauf cas exceptionnels. 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 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 où est inversible, le conditionnement est donné par , où est la norme d'opérateur subordonnée à la norme euclidienne sur . Puisqu'il est indépendant de et de la même forme pour et , on le désigne comme le conditionnement de la matrice . Cette valeur est également la valeur absolue du rapport entre la plus grande valeur propre de sur sa plus petite. Si est unitaire, alors , et donc . Pour une matrice quelconque, la norme d'opérateur est souvent difficile à calculer et le conditionnement est calculé par d'autres normes matricielles.
Pour le problème de valeurs propres, le théorème de Bauer-Fike établit que si est une valeur propre d'une matrice diagonalisable avec pour matrice de vecteurs propres , alors l'erreur absolue en calculant est majorée par le produit de et de l'erreur absolue en . Par corollaire, le conditionnement pour trouver vaut . Si est normale, alors est unitaire, et . 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 espaces propres d'une matrice normale correspondant à une valeur propre est inversement proportionnel à la distance minimum entre et les autres valeurs propres de . En particulier, le problème d'espace propre pour les matrices normales est bien conditionné pour les valeurs propres isolées ; sinon, on peut au mieux identifier le sous-espace engendré par les vecteurs propres de valeurs propres proches.
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 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 de matrices. Dans le cas général, les algorithmes sont 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 d'une matrice 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 dont n'est plus solution.
La redirection est souvent faite par décalage : remplacer par pour une constante . La valeur propre obtenue par doit avoir ajoutée pour obtenir une valeur propre de . Par exemple, pour la méthode de la puissance itérée, on prend . Cette méthode donne la valeur propre de valeur absolue plus élevée, ainsi même si 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 puissance inverse trouvent la plus petite valeur propre, donc doit être choisi loin de , éventuellement plus proche d'une autre valeur propre.
La réduction peut être faite en restreignant à l'espace colonne de la matrice . Comme cette matrice est singulière, l'espace colonne est de 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 fixé proche d'une approximation de valeur propre. Cela va vite converger vers un vecteur propre associé à la valeur propre la plus proche de . Pour de petites matrices, une alternative est de regarder l'espace colonne du produit de pour chaque valeur propre .
Transformations en matrices de Hessenberg et tridiagonales
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 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 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.