Algorithme de recherche de valeur propre

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 modifier

Article détaillé : Valeur propre, vecteur propre et espace propre.

Pour une matrice carrée $A$ de taille $n \times n$ réelle ou complexe, une valeur propre $λ$ et son vecteur propre généralisé associé $v$ sont un couple vérifiant la relation^[1]

\left(A-\lambda I\right)^{k}{\mathbf {v} }=0,

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

Pour toute valeur propre $λ$ de $A$ , le noyau $ker(A - λ I)$ 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 $ker((A - λ I) n)$ 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

p_{A}(z)={\rm {det}}(zI-A)=\prod _{i=1}^{k}(z-\lambda _{i})^{\alpha _{i}},

où $det$ est le déterminant, les $λ i$ sont les valeurs propres de $A$ et les $α i$ sont les multiplicités algébriques associées. La fonction $p A (z)$ est le polynôme caractéristique de $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 $n$ , le degré du polynôme caractéristique. L'équation $p A (z) = 0$ est appelé équation caractéristique, car ses racines sont les valeurs propres de $A$ . Par le théorème de Cayley-Hamilton, $A$ vérifie la même équation : $p A (A) = 0$ ^{[note 1]}. Par conséquent, les colonnes de la matrice $\textstyle \prod _{i\neq j}(A-\lambda _{i}I)^{\alpha _{i}}$ sont soit nulles soit des vecteurs propres généralisés de la valeur propre $λ j$ , car ils sont annulés par $(A - λ j I) α 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 $λ j .$

Toute collection de vecteurs propres généralisés de valeurs propres distinctes est linéairement indépendante, donc une base de $ℂ n$ peut être choisi à partir de vecteurs propres généralisés. Plus précisément, cette base $(v i) n i =1$ peut être choisie et ordonnée de sorte que

si $v i$ et $v j$ ont la même valeur propre, alors tout $v k$ pour tout $k$ entre $i$ et $j$ , et
si $v i$ n'est pas un vecteur propre ordinaire, associé à la valeur propre $λ i$ , alors $(A - λ i I) v i = v i -1$ (en particulier, $v 1$ doit être un vecteur propre ordinaire).

Si ces vecteurs de base sont rangés comme vecteurs colonnes d'une matrice $V = [v 1 v 2 ... v n]$ , alors $V$ peut être utilisé pour transformer $A$ en sa forme de Jordan :

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}},

où les $λ i$ sont les valeurs propres, $β i = 1$ si $(A - λ i +1) v i +1 = v i$ et $β i = 0$ sinon.

Plus généralement, si $W$ est une matrice inversible, et $λ$ est une valeur propre de $A$ de vecteur propre généralisé $v$ , alors $(W -1 AW - λ I) k W - k v = 0$ . Ainsi $λ$ est une valeur propre de $W -1 AW$ pour tout vecteur propre généralisé $W - k v$ . De plus, des matrices semblables ont les mêmes valeurs propres.

Matrices symétriques réelles, normales et hermitiennes modifier

Articles détaillés : Matrice adjointe, Matrice normale et Matrice hermitienne.

La matrice adjointe $M *$ d'une matrice complexe $M$ est la transposée de la conjuguée $M$ : $M * = M T$ . Une matrice carrée $A$ est appelée normale si elle commute avec son adjointe : $A * A = AA *$ . Elle est appelée hermitienne si elle est égale à son adjointe : $A * = A$ . Toutes les matrices hermitiennes sont normales. Si $A$ est réelle, l'adjointe est sa transposée, et $A$ 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 $ℂ n$ : $w \cdot v = w * v$ ^{[note 2]}. 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$ , $ℂ n$ a une base orthonormale de vecteurs propres de $A$ . La matrice correspondante de vecteurs propres est unitaire ;
les valeurs propres d'une matrice hermitienne sont réelles, car $(λ - λ) v = (A * - A) v = (A - A) v = 0$ pour un vecteur propre non nul $v$ ;
si $A$ est réelle, il y a une base orthonormale de $R n$ constituée de vecteurs propres de $A$ si et seulement si $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 modifier

Tout problème de calcul numérique peut être vu comme l'évaluation d'une fonction ƒ en un point $x$ . Le conditionnement $κ (ƒ, 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. souhaitée]}, sauf cas exceptionnels^{[Lesquels ?]}. 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 $A v = b$ où $A$ est inversible, le conditionnement $κ (A -1, b)$ est donné par $|| A || op || A -1 || op$ , où || ||_op est la norme d'opérateur subordonnée à la norme euclidienne sur $ℂ n$ . Puisqu'il est indépendant de $b$ et de la même forme pour $A$ et $A -1$ , on le désigne comme le conditionnement $κ (A)$ de la matrice $A$ . Cette valeur $κ (A)$ est également la valeur absolue du rapport entre la plus grande valeur propre de $A$ sur sa plus petite. Si $A$ est unitaire, alors $|| A || op = || A -1 || op = 1$ , et donc $κ (A) = 1$ . Pour une matrice quelconque, la norme d'opérateur est souvent difficile à calculer et le conditionnement est calculé par d'autres normes matricielles^[évasif].

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 $A$ avec pour matrice de vecteurs propres $V$ , alors l'erreur absolue en calculant $λ$ est majorée par le produit de $κ (V)$ et de l'erreur absolue en $A$ ^[2]. Par corollaire, le conditionnement pour trouver $λ$ vaut $κ (λ, A) = κ (V) = || V || op || V -1 || op$ . Si $A$ est normale, alors $V$ est unitaire, et $κ (λ, 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 espaces propres d'une matrice normale $A$ correspondant à une valeur propre $λ$ est inversement proportionnel à la distance minimum entre $λ$ et les autres valeurs propres de $A$ ^[3]. En particulier, le problème d'espace propre pour les matrices normales est bien conditionné pour les valeurs propres isolées^[Quoi ?] ; sinon, on peut au mieux identifier le sous-espace engendré par les vecteurs propres de valeurs propres proches^{[réf. souhaitée]}.

Idée directrice des algorithmes modifier

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^{[Lesquelles ?]} de matrices. Dans le cas général^[Lequel ?], 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$ 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 ?] dont $λ$ n'est plus solution.

La redirection est souvent faite par décalage : remplacer $A$ par $A - μI$ pour une constante $μ$ . La valeur propre obtenue par $A - μI$ doit avoir $μ$ ajoutée pour obtenir une valeur propre de $A$ . 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 $A$ à l'espace colonne de la matrice $A - λI$ . 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 $A - λ'I$ pour chaque valeur propre $λ'$ .

Transformations en matrices de Hessenberg et tridiagonales modifier

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 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.

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	$2 n 3 ⁄ 3 + O (n 2)$ ^[4]^(p474)	$4 n 3 ⁄ 3 + O (n 2)$ ^[4]^(p474)	Envoie chaque colonne vers un sous-espace nul pour les coefficients bas.
Rotations de Givens (en)	Quelconque	de Hessenberg	$4 n 3 ⁄ 3 + O (n 2)$ ^[4]^(p470)		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	NC	NC	Orthogonalisation de Gram-Schmidt sur des sous-espaces de Krylov.
Algorithme de Lanczos	Hermitienne	Tridiagonale	NC	NC	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 $O (n)$ , par dichotomie dans le polynôme caractéristique.

Algorithmes itératifs modifier

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.

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é	$O (n 2)$	Linéaire	Application répétée d'une matrice à un vecteur arbitraire puis renormalisation.
Méthode de la puissance inverse	Toutes	Valeur propre plus proche de $μ$	NC	Linéaire	Puissance itérée sur $(A - μI) -1$
Itération de Rayleigh	Hermitienne	Valeur + vecteur propre le plus proche	NC	Cubique	Puissance itérée sur $(A - μ i I) -1,$ avec $μ i$ à chaque pas le quotient de Rayleigh du pas précédent.
Algorithme inverse préconditionné^[5] ou LOBPCG	Réelle symétrique définie positive	Valeur propre plus proche de $μ$	Dépend du préconditionneur		Puissance inverse avec un préconditionneur (approximation de l'inverse de $A$ ).
Méthode de dichotomie	Réelle symétrique tridiagonale	N'importe quelle valeur propre	NC	Linéaire	Utilise la méthode de dichotomie pour trouver les racines du polynôme caractéristique, à partir de sa suite de Sturm.
Algorithme de Laguerre	Réelle symétrique tridiagonale	N'importe quelle valeur propre	NC	Cubique^[6]	Utilisation de la méthode de Laguerre pour trouver les racines du polynôme caractéristique, à partir de sa suite de Sturm.
Algorithme QR (en)	Hessenberg	Toutes les valeurs propres	$O (n 2)$	Cubique	Calcul de la factorisation A = QR, avec Q orthogonale et R triangulaire, puis application à RQ au pas suivant.
Algorithme QR (en)	Hessenberg	Tous les couples valeur/vecteur propre	$6 n 3 + O (n 2)$	Cubique
Méthode de Jacobi (en)	Réelle symétrique	Toutes les valeurs propres	$O (n 3)$	Quadratique	Rotations de Givens pour annuler si possible les termes non-diagonaux.
Algorithme diviser-pour-régner (en)	Hermitienne tridiagonale	Toutes les valeurs propres	$O (n 2)$		Découpe la matrice en sous-matrices qui sont diagonalisées puis recombinées.
Algorithme diviser-pour-régner (en)	Hermitienne tridiagonale	Tous les couples valeur/vecteur propres	$(4 ⁄ 3) n 3 + O (n 2)$
Méthode par homotopie	Réelle symétrique tridiagonale	Tous les couples valeur/vecteur propre	$O (n 2)$ ^[7]	NC	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 $μ$	NC	NC	Puissance inverse préconditionné sur $(A - μ I) 2$
Algorithme RRRM^[8]	Réelle symétrique tridiagonale	Couples valeur/vecteur propres	$O (n 2)$	NC	"représentation relativement robustes multiples" – puissance inverse sur la décomposition de Cholesky de la matrice décalée.

Méthodes directes modifier

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 modifier

Puisque le déterminant d'une matrice triangulaire est le produit de ses coefficients diagonaux, si $T$ est triangulaire, alors $\textstyle \det(\lambda I-T)=\prod _{i}(\lambda -T_{ii})$ . Ainsi, les valeurs propres de $T$ sont ses coefficients diagonaux.

Équations polynomiales factorisables modifier

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

Par exemple, une projection est une matrice carrée $P$ satisfaisant $P 2 = P$ . Les racines de l'équation polynomiale scalaire correspondante, $λ 2 = λ$ , 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 de $P$ , et la multiplicité de 1 est le rang de $P$ .

Un autre exemple est une matrice $A$ vérifiant $A 2 = α 2 I$ pour un scalaire $α$ . Les valeurs propres valent donc $\pm α$ . Les opérateurs de projection

P_{+}={\frac {1}{2}}\left(I+{\frac {A}{\alpha }}\right),\,P_{-}={\frac {1}{2}}\left(I-{\frac {A}{\alpha }}\right)

vérifient

AP_{+}=\alpha P_{+}\quad AP_{-}=-\alpha P_{-}

et

P_{+}P_{+}=P_{+}\quad P_{-}P_{-}=P_{-}\quad P_{+}P_{-}=P_{-}P_{+}=0.

Les espaces colonne de $P +$ et $P -$ sont les espaces propres de $A$ correspondant à $+ α$ et $- α$ , respectivement.

Matrices 2×2 modifier

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 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

A={\begin{pmatrix}a&b\\c&d\end{pmatrix}},

le polynôme caractéristique est

\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).

Ainsi, les valeurs propres peuvent être obtenues par les égalités usuelles :

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

On pose $δ (A) = \sqrt Tr (A) 2 - 4 det(A)$ la distance entre les deux valeurs, ce qui permet d'obtenir

{\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)}}

avec des formules similaires pour $c$ et $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 $λ 1, λ 2$ sont les valeurs propres, alors $(A - λ 1 I)(A - λ 2 I) = (A - λ 2 I)(A - λ 1 I) = 0$ , donc les colonnes de $(A - λ 2 I)$ sont annulées par $(A - λ 1 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 $A$ est un multiple de l'identité et tout vecteur non nul est vecteur propre.)

Exemple: $A={\begin{pmatrix}4&3\\-2&-3\end{pmatrix}},$

vérifie $Tr(A) = 4 - 3 = 1$ et $det(A) = 4(-3) - 3(-2) = -6$ , donc l'équation caractéristique vaut

0=\lambda ^{2}-\lambda -6=(\lambda -3)(\lambda +2),

et les valeurs propres sont 3 et –2. De là,

A-3I={\begin{pmatrix}1&3\\-2&-6\end{pmatrix}},\qquad A+2I={\begin{pmatrix}6&3\\-2&-1\end{pmatrix}}.

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

Matrices 3×3 modifier

Si $A$ est une matrice 3×3, alors son polynôme caractéristique peut s'écrire sous la forme :

{\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.

On peut obtenir les racines par la méthode de Cardan ou de Lagrange, mais un changement affine de $A$ peut grandement simplifier l'expression et permettre d'écrire les solutions sous forme trigonométrique. Si $A = pB + qI$ , alors $A$ et $B$ ont les mêmes vecteurs propres, et $β$ est valeur propre de $B$ si et seulement si $α = pβ + q$ est valeur propre de $A$ . On pose $q = Tr(A)/3$ et $p = (Tr((A - qI) 2)/6) 1/2$ , ce qui donne

{\rm {det}}(\beta I-B)=\beta ^{3}-3\beta -{\rm {det}}(B)=0.

La substitution $β = 2cos θ$ et des calculs de simplification par le développement $cos (3 θ) = 4cos 3 θ - 3cos θ$ mènent à l'égalité $cos (3 θ) = det(B)/2$ . Ainsi, les racines s'écrivent sous la forme :

\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.

Si $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 $k$ . Ceci n'apparaît pas si $A$ est réelle et symétrique, et les calculs des valeurs propres sont grandement simplifiés^[9].

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

Exemple: $A={\begin{pmatrix}3&2&6\\2&2&5\\-2&-1&-4\end{pmatrix}}.$

L'équation caractéristique vaut

0=\lambda ^{3}-\lambda ^{2}-\lambda +1=(\lambda -1)^{2}(\lambda +1),

avec pour valeurs propres 1 (de multiplicité 2) et -1. Ainsi,

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}}

et

(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}}

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

Vecteurs propres de matrices 3×3 normales modifier

Si $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 $λ$ est une valeur propre de $A$ , alors le noyau de $A - λI$ est perpendiculaire à son espace colonne, le produit vectoriel de deux colonnes linéairement indépendantes de $A - λI$ sera dans le noyau, donc un vecteur propre associé avec $λ$ . 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 $A - λI$ ne contient pas deux colonnes indépendantes mais est différente de $0$ , le produit vectoriel peut toujours être utilisé. Dans ce cas, $λ$ est une valeur propre de multiplicité 2, donc tout vecteur orthogonal à l'espace colonne sera un vecteur propre. Supposons que $v$ est une colonne non nulle de $A - λI$ . On choisit un vecteur arbitraire $u$ non colinéaire à $v$ . Alors $v \times u$ et $(v \times u) \times v$ sera orthogonal à $v$ et sont donc vecteurs propres associés à $λ$ .

Applications modifier

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 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 :

\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.

Une résolution directe n'est pas possible dans le cas général (pour des coefficients non constants), aussi on va discrétiser $[0;1]$ en un nombre fini de points équirépartis ${x i} i =0,..., n$ et décomposer sur les solutions périodiques en temps : $u (t, x) = w (x)exp(i ωt)$ . L'approximation classique de la dérivée seconde en espace donne :

w(x)\approx {\frac {-w(x_{i-1})+2w(x_{i})-w(x_{i+1})}{1/n^{2}}}.

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 :

A_{n}\mathbf {w} =\lambda \mathbf {w} ,

avec

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}}.

Notes modifier

↑ Il faut cependant la considérer sous sa forme matricielle, où le terme constant vaut la matrice identité.
↑ Cet ordre, avec le conjugué à gauche, est privilégié par les physiciens. Les algébristes placent plutôt le conjugué linéaire à droite : $w \cdot v = v * w$ .

Références modifier

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Eigenvalue algorithm » (voir la liste des auteurs).

↑ Sheldon Axler, « Down with Determinants! », American Mathematical Monthly, vol. 102,‎ 1995, p. 139–154 (DOI 10.2307/2975348, lire en ligne)
↑ F. L. Bauer et C. T. Fike, « Norms and exclusion theorems », Numer. Math., vol. 2,‎ 1960, p. 137–141 (DOI 10.1007/bf01386217)
↑ S.C. Eisenstat et I.C.F. Ipsen, « Relative Perturbation Results for Eigenvalues and Eigenvectors of Diagonalisable Matrices », BIT, vol. 38, n^o 3,‎ 1998, p. 502–9 (DOI 10.1007/bf02510256)
↑ ^{a b et c} (en) William H. Press, Saul A. Teukolsky, William T. Vetterling et Brian P. Flannery, Numerical Recipes in C : The Art of Scientific Computing, Cambridge University Press, 1992, 2nd éd., 994 p. (ISBN 978-0-521-43108-8, BNF 37382181)
↑ K. Neymeyr, « A geometric theory for preconditioned inverse iteration IV: On the fastest convergence cases. », Linear Algebra Appl., vol. 415, n^o 1,‎ 2006, p. 114–139 (DOI 10.1016/j.laa.2005.06.022)
↑ (en) T.Y. Li et Zhonggang Zeng, « Laguerre's Iteration In Solving The Symmetric Tridiagonal Eigenproblem - Revisited », SIAM Journal on Scientific Computing,‎ 1992
↑ Moody T. Chu, « A Note on the Homotopy Method for Linear Algebraic Eigenvalue Problems », Linear Algebra Appl., vol. 105,‎ 1988, p. 225–236 (DOI 10.1016/0024-3795(88)90015-8)
↑ Inderjit S. Dhillon, Beresford N. Parlett et Christof Vömel, « The Design and Implementation of the MRRR Algorithm », ACM Transactions on Mathematical Software, vol. 32, n^o 4,‎ 2006, p. 533–560 (DOI 10.1145/1186785.1186788)
↑ Oliver K. Smith, « Eigenvalues of a symmetric 3 × 3 matrix. », Communications of the ACM, vol. 4, n^o 4,‎ avril 1961, p. 168 (DOI 10.1145/355578.366316)

Bibliographie modifier

Adam W. Bojanczyk et Adam Lutoborski, « Computation of the Euler angles of a symmetric 3X3 matrix », SIAM Journal on Matrix Analysis and Applications, vol. 12, n^o 1,‎ janvier 1991, p. 41–48 (DOI 10.1137/0612005, lire en ligne)

[2] Il faut cependant la considérer sous sa forme matricielle, où le terme constant vaut la matrice identité.

[3] Cet ordre, avec le conjugué à gauche, est privilégié par les physiciens. Les algébristes placent plutôt le conjugué linéaire à droite : $w \cdot v = v * w$ .

[Axler-1] Sheldon Axler, « Down with Determinants! », American Mathematical Monthly, vol. 102,‎ 1995, p. 139–154 (DOI 10.2307/2975348, lire en ligne)

[4] F. L. Bauer et C. T. Fike, « Norms and exclusion theorems », Numer. Math., vol. 2,‎ 1960, p. 137–141 (DOI 10.1007/bf01386217)

[5] S.C. Eisenstat et I.C.F. Ipsen, « Relative Perturbation Results for Eigenvalues and Eigenvectors of Diagonalisable Matrices », BIT, vol. 38, n^o 3,‎ 1998, p. 502–9 (DOI 10.1007/bf02510256)

[NumericalRecipes-6] {a b et c} (en) William H. Press, Saul A. Teukolsky, William T. Vetterling et Brian P. Flannery, Numerical Recipes in C : The Art of Scientific Computing, Cambridge University Press, 1992, 2nd éd., 994 p. (ISBN 978-0-521-43108-8, BNF 37382181)

[7] K. Neymeyr, « A geometric theory for preconditioned inverse iteration IV: On the fastest convergence cases. », Linear Algebra Appl., vol. 415, n^o 1,‎ 2006, p. 114–139 (DOI 10.1016/j.laa.2005.06.022)

[8] (en) T.Y. Li et Zhonggang Zeng, « Laguerre's Iteration In Solving The Symmetric Tridiagonal Eigenproblem - Revisited », SIAM Journal on Scientific Computing,‎ 1992

[9] Moody T. Chu, « A Note on the Homotopy Method for Linear Algebraic Eigenvalue Problems », Linear Algebra Appl., vol. 105,‎ 1988, p. 225–236 (DOI 10.1016/0024-3795(88)90015-8)

[10] Inderjit S. Dhillon, Beresford N. Parlett et Christof Vömel, « The Design and Implementation of the MRRR Algorithm », ACM Transactions on Mathematical Software, vol. 32, n^o 4,‎ 2006, p. 533–560 (DOI 10.1145/1186785.1186788)

[Smith-11] Oliver K. Smith, « Eigenvalues of a symmetric 3 × 3 matrix. », Communications of the ACM, vol. 4, n^o 4,‎ avril 1961, p. 168 (DOI 10.1145/355578.366316)

[1]

[note 1]

[note 2]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]