État stable marche aléatoire
Posted: 26 Feb 2016, 14:56Hello la communauté, je reviens "à la charge" avec les graphes probabilistes / chaînes de Markov et la recherche de l'éventuel état stable.
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é :
Prenons un petit exemple pour comprendre comment "construire" les matrices
Il restait donc à programmer tout cela, ce n'est pas du tout optimisé, mais cela fonctionne !
Avec la matrice
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...)
Et voilà le déroulé sur TI83CE :
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: Select all
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 !!