de Ce matin avec les Spé on a fait un exo de recherche d'état stable en dimension 3 et un des élèves a remarqué que le procédé était assez mécanique, et que d'un point de vue algorithmique cela devait pouvoir se faire.
J'ai donc réfléchi un peu à la manière de précéder pour que cela puisse passer sur une calculatrice, en conservant l'esprit du programme en obtenant l'éventuel état stable par système.
Voilà donc les grandes lignes du procédé :
- on détermine la matrice de transition $mathjax$M$mathjax$carrée d'ordre$mathjax$n$mathjax$du graphe (qui admet une puissance dont aucun des coefficients n'est nul...)
- l'état stable $mathjax$\Pi$mathjax$vérifiant$mathjax$\Pi=\Pi \times M$mathjax$donne un système linéaire de$mathjax$n$mathjax$équations à$mathjax$n$mathjax$inconnues (en transposant...)
- ce système, tel quel, ne peut pas se résoudre car les équations sont "liées"
- on retire une équation (la première par exemple) que l'on remplace par celle venant du fait que la somme des coefficients de $mathjax$\Pi$mathjax$vaut 1
- le nouveau système se transforme matriciellement sous forme $mathjax$AX=B$mathjax$
- la solution du système est donnée par $mathjax$X=A^{-1} \times B$mathjax$
Prenons un petit exemple pour comprendre comment "construire" les matrices
$mathjax$A$mathjax$
et $mathjax$B$mathjax$
:- on prend par exemple comme matrice de transition $mathjax$M=\begin{pmatrix} 0,1 & 0 & 0,9 \\ 0,9 & 0,1 & 0 \\ 0,3 & 0,1 & 0,6 \end{pmatrix}$mathjax$
- on vérifie que $mathjax$M^2$mathjax$ne comporte aucun 0, et donc qu'il existe un état stable$mathjax$\Pi=\begin{pmatrix} x & y & z \end{pmatrix}$mathjax$
- $mathjax$\Pi=\Pi \times M$mathjax$donne directement$mathjax$\begin{pmatrix} x & y & z \end{pmatrix}=\begin{pmatrix} 0,1x+0,9y+0,3z & 0x+0,1y+0,1z & 0,9x+0y+0,6z \end{pmatrix}$mathjax$
- soit encore $mathjax$\begin{cases}0,1x+0,9y+0,3z=x \\ 0x+0,1y+0,1z=y \\ 0,9x+0y+0,6z=z \end{cases} \Leftrightarrow \begin{cases}-0,9x+0,9y+0,3z=0 \\ 0x-0,9y+0,1z=0 \\ 0,9x+0y-0,4z=0 \end{cases}$mathjax$
- la matrice associée à ce système est $mathjax$\begin{pmatrix} -0,9 & 0,9 & 0,3 \\ 0 & -0,9& 0,1 \\ 0,9 & 0 & -0,4 \end{pmatrix}$mathjax$et le lecteur peut vérifier "facilement" qu'elle vaut$mathjax$(M-I_3)^\top$mathjax$
- on remplace la première équation par $mathjax$x+y+z=1$mathjax$et on obtient$mathjax$\begin{cases}x+y+z=1 \\ 0x-0,9y+0,1z=0 \\ 0,9x+0y-0,4z=0 \end{cases}$mathjax$
- ce nouveau système s'écrit $mathjax$AX=B$mathjax$avec$mathjax$A=\begin{pmatrix} 1 & 1 & 1 \\ 0 & -0,9& 0,1 \\ 0,9 & 0 & -0,4 \end{pmatrix}$mathjax$,$mathjax$X=\begin{pmatrix} x \\ y \\ z \end{pmatrix}$mathjax$et$mathjax$B=\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}$mathjax$
- on fait travailler la calculatrice, et on obtient $mathjax$X=A^{-1}B=\begin{pmatrix} \frac27 \\ \frac{1}{14} \\ \frac{9}{14} \end{pmatrix}$mathjax$soit$mathjax$\Pi=\begin{pmatrix} \dfrac27 & \dfrac{1}{14} & \dfrac{9}{14} \end{pmatrix}$mathjax$
Il restait donc à programmer tout cela, ce n'est pas du tout optimisé, mais cela fonctionne !
Avec la matrice
$mathjax$M$mathjax$
définie coefficient par coefficient, on calcule $mathjax$A=(M-I_n)^\top$mathjax$
puis on remplace la première ligne par des 1 ; la matrice $mathjax$B$mathjax$
est quant à elle constituée d'un 1 et de 0 ensuite...J'ai rajouté un petit test après la saisie d'une ligne pour vérifier une éventuelle erreur (je pense que le test est suffisant d'ailleurs...)
- Code: Tout sélectionner
Disp "MATRICE M CARREE ORDRE n"
Input "n=",N
{N,N}→dim([J])
For(I,1,N)
0→S
For(J,1,N)
Input "COEFF DANS [0,1]=",K
K→[J](I,J)
S+K→S
End
If S=1
Then
Disp "LIGNE OK"
Else
Disp "LIGNE PAS OK"
Stop
End
End
Disp "MATRICE M"
Pause [J]
([J]-unité(N))t→[I] (avec t la transposition !)
For(L,1,N)
1→[I](1,L)
End
Disp "SYSTEME AX=B"
Disp "A=",[I]
Pause
{N,1}→dim([H])
1→[H](1,1)
For(L,2,N)
0→[H](L,1)
End
Disp "B=",[H]
Pause
Disp "X="
Pause [I]^(-1])[H]>Frac
Disp "ETAT STABLE="
Disp [I]^(-1)[H]>Frac
Et voilà le déroulé sur TI83CE :
ils sont un peu curieux !!
