Trouver une matrice de passage "idéale"

Homo Topi · March 2023

Je me suis posé une question que j'ai un peu de mal à formuler. En gros, l'idée, c'est : peut-on trouver une base de réduction d'endomorphisme "optimale pour faire les calculs de tête". Je vais illustrer mon propos pour essayer d'être plus clair.

Je me suis inventé un exercice pour réviser la réduction de Jordan. Je partais d'une matrice $D = \begin{pmatrix} 2 & 2 & -3 \\ 5 & 1 & -5 \\ -3 & 4 & 0\end{pmatrix}$ dont je sais qu'elle est non diagonalisable mais trigonalisable (exo du Gourdon) et j'ai cherché une base dans laquelle elle prend une forme de Jordan.

Rapidement : son polynôme caractéristique est $(1-X)^3$, scindé, sa seule valeur propre est $1$ (de multiplicité $3$), le sous-espace propre associé à $1$ est $Vect(v_1)$ où $v_1=(1,1,1)$, de dimension $1$. Donc la matrice de Jordan est constituée d'un seul bloc et on s'attend à trouver $J=\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}$ comme forme de Jordan.

Je déroule donc l'algorithme de recherche d'une base de Jordan : je résous $(D-1I_3)v_2=v_1$ puis $(D-1I_3)v_3=v_2$ pour obtenir une base $(v_1,v_2,v_3)$ dans laquelle $D$ devient $J$. La manière dont j'ai mené mes calculs donnait un vecteur $v_2 = (x,y,z)$ qui doit vérifier $5x=5z+1$ et $5y=5z+2$, donc j'ai "naturellement" choisi $v_2 = (1/5,2/5,0)$. De même, mes calculs pour $v_3=(x',y'z')$ aboutissaient à $25x'=25z'+2$ et $50y'=50z'+3$ donc j'ai "naturellement" choisi $v_3=(4/50, 3/50, 0)$. J'aboutis à une matrice de passage $P=\begin{pmatrix} 1 & 1/5 & 4/50 \\ 1 & 2/5 & 3/50 \\ 1 & 0 & 0\end{pmatrix}$. J'ai pu calculer son inverse : $P^{-1} = \begin{pmatrix} 0 & 0 & 1 \\ -3 & 4 & -1 \\ 20 & -10 & -10\end{pmatrix}$. J'ai pu vérifier également que $P^{-1}DP=J$, donc tout est bon.

Seulement, comme annoncé dans mon préambule, je me suis demandé si on pouvait faire "mieux". Là, j'ai choisi $v_1$, $v_2$ et $v_3$ pour avoir une matrice $P$ relativement simple. J'aurais pu prendre n'importe quel vecteur colinéaire à $v_1$ au lieu de $v_1$, mais $(1,1,1)$ c'est sympathique et simple donc j'ai choisi celui-là. Ce choix a conditionné le système à résoudre pour trouver $v_2$, la manière dont j'ai fait les calculs a conditionné le système final où j'exprime tout en fonction de $z$, je n'étais pas obligé de prendre $z=0$ pour $v_2$ mais ça m'avait l'air d'être le plus simple, donc j'ai fait comme ça. Idem pour $v_3$. Je me retrouve avec une matrice $P$ qui m'a pris une page de calculs (j'écris grand, mais quand même) à inverser à la main, j'aurais préféré plus court si possible. Le calcul de $P^{-1}DP$ aussi faisait intervenir des "gros" nombres (deux chiffres, c'est trop !).

Je veux donc être un immense flemmard dès qu'il s'agit de faire des calculs à la main. Il existe une myriade infinité de bases adaptées à la réduction que j'ai faite. Ce qui aurait été pratique pour mes calculs, c'est que $P$ soit de la sorte que $P^{-1}$ soit "la plus simple possible" pour que le calcul de $P^{-1}DP$ soit aussi "le plus simple possible". Donc je tente de préciser ma notion de "base optimale" : idéalement, $P$ serait telle que $P$ et $P^{-1}$ toutes les deux contiennent un maximum de zéros, le moins possible d'irrationnels, le moins possible de non-entiers, le moins possible de signes $-$... en gros un maximum de coefficients entiers naturels (et si possible, tous inférieurs à $10$, tant qu'on y est).

Bon, évidemment, posé tel quel, ça m'a l'air assez utopique d'obtenir rapidement une réponse parfaite à ce problème-là. Mais histoire de ne pas devoir faire de trial and error jusqu'à la fin de mes jours (et ce, uniquement pour cette matrice $D$), j'imagine qu'il va falloir hiérarchiser mes priorités pour avoir des éléments de réponse, donc, je vais commencer par : chercher des bases telles que les $P$ et $P^{-1}$ correspondantes contiennent toutes les deux autant de zéros que possible. Peut-on déjà chercher ça ?

D'ailleurs si un algorithme "d'amélioration de base" existe, ça m'intéresserait. J'imagine que sur un ordinateur, comme on a des méthodes de stockage de matrices où on ne stocke que les coefficients non nuls, il y a un intérêt à chercher une matrice de passage aussi creuse que possible. Là je travaille sur une matrice $3\times 3$ parce que ça sort d'un livre de prépa et doit être fait à la main, mais évidemment, pour des systèmes linéaires gigantesques traités sur ordinateur le problème reste très pertinent.

Héhéhé · March 2023

La réduction de Jordan a un intérêt théorique énorme mais un intérêt pratique assez limité voire nulle, personne ne s'amuse à calculer une réduite de Jordan sur des matrices énormes.

J'ajoute à cela que la décomposition de Dunford n'est pas continue donc numériquement c'est compliqué, j'imagine que ce genre de difficulté surgit aussi pour la réduction de Jordan.

Le simple calcul de valeurs propres (approchées dès qu'on a des matrices plus grandes que 5) est une vraie difficulté ! Même la diagonalisation est difficile dès qu'on a des valeurs propres multiples en raison d'instabilité numérique.

Bref on préfère éviter la réduction en pratique sur des grosses matrices et à préférer des méthodes différentes (décomposition LU ou méthodes itératives par exemple).

Homo Topi · March 2023

Intéressant. Et point taken sur l'utilité pratique des décompositions.

Héhéhé a dit :

Le simple calcul de valeurs propres (approchées dès qu'on a des matrices plus grandes que 5) est une vraie difficulté !

Les polynômes non résolubles par radicaux sont-ils vraiment une difficulté numérique ? Certes on ne peut en général qu'espérer des approximations des racines, mais quand même, ta remarque me surprend un peu. Les polynômes sont des fonctions très gentilles, on a des algorithmes (ne serait-ce que la dichotomie) pour approcher les racines et le TVI associé à 2-3 étapes de calcul formel (réalisable sur machine) pour démarrer la recherche. Non ?

Héhéhé · March 2023

Tu fais comment pour calculer le polynome caractéristique d'une matrice énorme ?

JavierT · March 2023

Bonjour,

Pour la matrrice proposée, Xcas donne pour information

$P=\left[\begin{array}{ccc}-10&2&0\\-10&0&1\\-10&4&0\end{array}\right]$ et $T=\left[\begin{array}{ccc}1&1&0\\0&1&1\\0&0&1\end{array}\right]$

et donc $P^{-1}=\left[\begin{array}{ccc}-\frac{1}{5}&0&\frac{1}{10}\\-\frac{1}{2}&0&\frac{1}{2}\\-2&1&1\end{array}\right]$

Comment Xcas trouve cette matrice de passage, je ne sais pas. Faudrait regarder dans le code ou demander à Bernard Parisse.

Homo Topi · March 2023

Héhéhé a dit :

Tu fais comment pour calculer le polynome caractéristique d'une matrice énorme ?

Ben, tu développes le déterminant et tu réduis, ça prend du temps de calcul mais ça doit se faire quand même, non ?

Héhéhé · March 2023

La formule de développement selon une ligne ou une colonne sont en complexité de l'ordre de $n!$ (pour une matrice carrée de taille $n \times n$), inutilisable dès que $n$ dépasse la dizaine.

Le pivot de Gauss est en $n^3$, ce qui n'est pas terrible (impossible de gérer des matrices avec des centaines de milliers de ligne).

Et surtout avec ta méthode (1) tu te retrouves avec des polynômes énormes à gérer (d'ordre $n$), ce n'est pas si facile de les étudier (c'est pas juste un "coup de Newton" ou de "dichotomie" pour trouver toutes les racines complexes, surtout quand elles sont multiples) et (2) tu dois faire du calcul formel pour te trainer ton indéterminée ce qui fait que tes calculs vont être horriblement lent (bien plus qu'avec du calcul sur les flottants).

Il ne faut surtout pas faire comme ça. Le polynôme caractéristique c'est bien pour les calculs à la main pour $n < 5$.