Dunford algorithmique
Bonjour,
vous connaissez peut-être le développement d'agreg/algorithme suivant pour trouver la décomposition de Dunford d'une matrice $A$ à coefficients dans un corps $\mathbb{K}$ dont le polynôme caractéristique est scindé sur $\mathbb{K}$.
On suppose qu'on connaît le polynôme $P := \prod_{\lambda \in \sigma(A)} (X-\lambda)$ qui est scindé à racines simples, et on pose, pour toute matrice $B$ où ça a un sens, $\phi(B) := B - P(B)P'(B)^{-1}$.
On vérifie ensuite que $(A,\phi(A),\phi^2(A),\cdots)$ est une suite bien définie, stationnaire, et que la limite est la $D$ de Dunford.
J'ai voulu essayer de comprendre ce phénomène par un autre angle : si $\phi$ est définie en $B$, et si $Q$ est une matrice inversible, alors $\phi$ est définie en $QBQ^{-1}$ et $\phi(QBQ^{-1}) = Q\phi(B)Q^{-1}$. En effet, supposons que $P'(B)$ est inversible. Alors $P'(QBQ^{-1}) = QP'(B)Q^{-1}$, donc $P'(QBQ^{-1})^{-1} = QP'(B)^{-1}Q^{-1} $, et donc $\phi(QBQ^{-1}) = QBQ^{-1} - QP(B)Q^{-1}\left(P'(QBQ^{-1})\right)^{-1} = QBQ^{-1} - QP(B)Q^{-1}\left(QP'(B)Q^{-1}\right)^{-1}=QBQ^{-1} - QP(B)Q^{-1}Q\left(P'(B)\right)^{-1}Q^{-1} =Q\phi(B)Q^{-1}.$
Ainsi, pour suivre (et "comprendre") ce qui se passe sur $A$, il suffit de suivre ce qui se passe sur la matrice $\tilde{A}$ qui est semblable à $A$ et qui est sous forme de Jordan.
Si $\tilde{A}$ a une seule valeur propre, on voit tout de suite (et même pas besoin de passer à la forme de Jordan) que l'algorithme termine en un coup.
Par contre, si $\tilde{A}$ a au moins deux valeurs propres (et donc au moins deux blocs de Jordan), alors je vois par le calcul, à la main et avec Sage, qu'à chaque étape, l'algorithme garde la diagonale telle quelle et fait s'échapper dans les coins en haut à droite des blocs les surdiagonales non nulles de quelques crans - tout en les multipliant par des grosses fractions (par exemple, pour une matrice avec trois blocs (vp 2, taille 5 ; vp 3, taille 6 ; vp 5, taille 4) j'ai, à la première étape, un $-\frac{172}{27}$, ARGH !) - et je vois bien pourquoi l'algorithme converge : après quelques étapes, il ne reste plus que la diagonale.
Par contre, je n'ai pas réussi à écrire ces observations proprement.
Avez-vous des idées ?
PS : De temps en temps, mon ordi a l'air de ne pas essayer de compiler le LaTeX du forum, et donc je ne sais pas encore si j'ai fait des erreurs.Réponses
-
Je ne connaissais pas l'algorithme et j'ai eu un peu de mal à comprendre, notamment le lien entre $P$ et le polynôme caractéristique ne me semble pas clair, après quelques recherches on a $P = \chi_A/(\chi_A\wedge \chi_A ')$ où $\chi_A$ est le polynôme caractéristique de $A$ et $\wedge$ designe le pgcd. Je crois que j'ai compris comment marchait l'algorithme "par blocs".Puisqu'une forme de Jordan est diagonale par blocs et que $\phi$ préserve cette forme il suffit de regarder ce qu'il se passe sur un bloc $J_1$ de Jordan, disons que le bloc est de taille $n$ et qu'il est associé à la valeur propre $\lambda_1$. Ce bloc sera transformé en\[J_1-P(J_1)P'(J_1)^{-1}.\]On a d'une part\[P(J_1) = (J_1-\lambda_1 \mathrm{Id}) \ldots (J_1-\lambda_k\mathrm{Id})\]qui va être triangulaire supérieure à diagonale nulle puisque le premier terme du produit est de cette forme. Sur la surdiagonale on retrouvera $\prod_{j\neq 1} \lambda_1-\lambda_j$ comme coefficients.D'autre part $P'(X) = \sum_i \prod_{j\neq i} (X-\lambda_j)$, si on applique $P'$ à $J_1$ le seul terme qui va donner une matrice à diagonale non nulle est $\prod_{j\neq 1 }(J_1- \lambda_j \mathrm{Id})$, on retrouvera donc sur la diagonale uniquement le coefficient $\prod_{j\neq 1} \lambda_1-\lambda_j$, donc $P'(J_1)^{-1}$ sera triangulaire supérieure et on retrouvera sur la diagonale un seul et même coefficient : $\left(\prod_{j\neq 1} \lambda_1-\lambda_j\right)^{-1}$. Ainsi $P(J_1)P'(J_1)^{-1}$ est triangulaire supérieure, sa diagonale est nulle et sa surdiagonale vaut $1$, on en déduit que $\phi(J_1)- \lambda_1 \mathrm{Id}=J_1-P(J_1)P'(J_1)^{-1} - \lambda_1\mathrm{Id}$ est nilpotente d'ordre au plus $n-1$. Il en va de même pour tous les autres blocs.En reprenant alors la forme de Jordan de $\phi(A)$ on voit que tous les blocs je Jordan voient leur taille diminuer de $1$ (ou éventuellement plus) par rapport à ceux de $A$. Au bout d'au plus $n$ étapes on se retrouve avec uniquement des blocs de Jordan de taille $1$ : la matrice est diagonale.Moi non plus l'aperçu ne me donne pas de compilation latex donc je ne sais pas si ce sera lisible... Edit : ça devrait être bon maintenant, au moins au niveau du latex.
-
Pour plus d'infos, ça se trouve dans le livre "131 développements d'agreg" et dans un livre de Boyer-Risler (voir https://les-mathematiques.net/vanilla/index.php?p=discussion/490529#Comment_490529).L'algorithme converge en au plus $\log_2 n$ étapes, donc en général, la taille des blocs diminue de plus de $1$, oui !Bon j'aurais dû persévérer un peu alors, ça a l'air de se démontrer proprement !En fait cet algorithme est un analogue de la méthode de Newton, et en y réfléchissant un peu, je crois que je viens de piger un truc (désolé si vous l'aviez déjà compris ou si vous n'y voyez pas d'intérêt) !Soit $R$ un anneau, avec des "infinitésimaux" : il y a les éléments "standard" et on peut leur ajouter des infinitésimaux (ça veut rien dire a priori mais faisons comme si).
Soit $f$ un polynôme (définissant donc une fonction) sur $R$, et $a$ un zéro standard de $f$. On suppose que $f'(a)$ est inversible. La méthode de Newton sert, habituellement, à partir d'un $b_0$ voisin de $a$, poser \[b_1 := b_0 - \frac{f(b_0)}{f'(b_0)},\]intérer et espérer que ça converge vers $a$.
Là, on part... directement de $a$ ! Enfin, pas tout à fait : on prend un infinitésimal $\epsilon$, et on part de $a+\epsilon$.
Posons $\phi : x \mapsto x - \frac{f(x)}{f'(x)}$ là où ça a un sens.
Alors $f(a+\epsilon) = f(a) + \epsilon f'(a) = \epsilon f'(a)$, et $f'(a+\epsilon) = f'(a) + \epsilon f''(a)$, et donc \[\begin{array}{rcl}
\displaystyle f'(a +\epsilon)^{-1} &= &\displaystyle \left(f'(a)(1+\epsilon f''(a)/f'(a)\right)^{-1}\\
&= &\displaystyle \left(f'(a)\right)^{-1}\left(1+\frac{\epsilon f''(a)}{f'(a)}\right)^{-1}\\
&= &\displaystyle \left(f'(a)\right)^{-1}\left(1-\frac{\epsilon f''(a)}{f'(a)} + \frac{\epsilon^2 f''(a)^2}{f'(a)^2} - \cdots\right)\\
\end{array}.\]
Alors \[\begin{array}{rcl}
\phi(a+\epsilon) &= &\displaystyle a+\epsilon - f(a+\epsilon)f'(a+\epsilon)^{-1}\\
&= &\displaystyle a+\epsilon - \left(\epsilon - \epsilon^2\frac{f''(a)}{f'(a)} + \epsilon^3\frac{f''(a)^2}{f'(a)^2}\cdots\right)\\
&= &\displaystyle a + \epsilon^2 blablabla.\\
\end{array}\]
Bref, je savais déjà que (si on part assez près) la méthode de Newton converge quadratiquement ; mais en fait, ça marche aussi avec des infinitésimaux : si on est infinitésimalement près de la racine, après une itération, l'infinitésimal qui nous sépare est le carré de l'infinitésimal d'avant.
En outre, je crois que certains pans de la géométrie algébrique consistent justement à développer à fond la philosophie "les nilpotents sont des infinitésimaux" ! Eh ben là, c'est exactement ce qui se passe. -
Ah oui tiens je n'avais pas remarqué qu'il s'agissait d'une méthode de Newton 🙃C'est très joli, et ça permet de comprendre d'où vient le $\log_2(n)$ étapes. D'ailleurs on peut aussi voir dans mon calcul que la taille des blocs est divisée par environ $2$ à chaque itération : quand je dis que la matrice est nilpotente d'ordre au plus $n-1$ en fait on obtient qu'elle est nilpotente d'ordre (au plus) $\lfloor (n+1)/2\rfloor$.
-
Un énoncé un peu plus général qu'on trouve dans ACMC à l'exercice 25 du chapitre III qui est corrigé.Soit $A$ un anneau commutatif et $M\in M_n(A)$ tel que son polynôme caractéristique divise une puissance d'un polynôme séparable $f$.
Alors il existe $D,N\in M_n(A)$ uniques telles que :
1) $D$ et $N$ sont des polynômes en $M$ à coefficients dans $A$.
2) $M=D+N$.
3) $f(D)=0$.
4) $N$ est nilpotente. -
Vous avez attisé ma curiosité avec ce fil, je ne connaissais pas du tout.Du coup, j'ai écrit un truc adapté au programme des étudiants que je fréquente (pas de structure algébrique, pas de déterminant ni de polynôme caractéristique évidemment, pas d'arithmétique dans l'anneau des polynômes) donc j'ai fait ça exclusivement en termes de matrices à coefficients (disparition des complexes l'an prochain pour moi). Je n'ai pas encore écrit le corrigé donc je vais nécessairement modifier encore deux ou trois trucs. Si vous des retours à me faire, je suis preneur.Par contre, je ne sais pas si je le donnerai un jour à mes étudiants, ça me paraît bien compliqué.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.6K Toutes les catégories
- 65 Collège/Lycée
- 22.2K Algèbre
- 37.7K Analyse
- 6.3K Arithmétique
- 61 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 26 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.8K Géométrie
- 86 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 29 Mathématiques et finance
- 344 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.4K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 805 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres