\Annee{2002}
\Titre{Exemples de syst\`emes dynamiques lin\'eaires, matrices stochastiques}
\Date{2002/03/13}
\Niveau{\DEUGii} 
\NiveauxSecondaires{\DEUGbio,\DEUGphys}
\Auteur{Fr\'ed\'eric \textsc{Le Roux}}
\AnglePedagogique{\AQuoiCaSert} 
\AnglesSecondaires{\Ludique} 
\Theme{\AlgLin}
\ThemesSecondaires{\Suites, suites r\'ecurrentes lin\'eaires}

\Objectif{
  \begin{itemize}
  \item[Objectif ``m\'eta'' :] voir comment un m\^eme concept
    math\'ematique peut mod\'eliser des situations issues de domaines
    vari\'es, et comment un th\'eor\`eme abstrait peut r\'esumer toutes ces
situations, ce qui illustre la g\'en\'eralit\'e des outils d\'evelopp\'es 
par les math\'ematiciens~;
\item[Objectif d'ouverture :] donner une id\'ee de ce qu'est un syst\`eme
  dynamique~;
\item[Objectif interne :] voir des situations o\`u les puissances de
  matrices, et les vecteurs propres, ont un sens concret (voir ci-dessous)~;
\item[Objectif ``technique'' :] calcul de suites d\'efinies par une relation
  de r\'ecurrence lin\'eaire, puissances d'une matrice, diagonalisation. 
  \end{itemize}

\paragraph{Remarques math\'ematiques}
A cause de la nature des probl\`emes choisis,
tous les syst\`emes propos\'es ici (sauf la derni\`ere question)
sont r\'egis par des matrices de transition (ce qui signifie que les
coefficients sont positifs, et que la somme des coefficients de chaque
colonne vaut $1$).
On peut montrer qu'une telle matrice a toujours une
direction propre dans le cône positif (ensemble des vecteurs dont toutes
les coordonn\'ees sont positives), qui correspond \`a la valeur propre $1$.
\footnote{L'existence peut s'obtenir facilement comme cons\'equence du th\'eor\`eme de
point fixe de Brouwer, mais peut aussi se prouver par des consid\'erations
d'alg\`ebre lin\'eaire \'el\'ementaire : voir  le th\'eor\`eme de Perron-Frobenius, 
par exemple dans le livre Katok, Hasselblatt,
Introduction to the modern theory of dynamical systems, Cambridge
University Press, 1995.}
De plus, si la matrice est transitive
(c'est-\`a-dire qu'il existe une certaine puissance dont tous les termes
sont strictement positifs), alors cette direction propre est unique, et
attire tout vecteur du c\^one positif. Autrement dit, les syst\`emes
dynamiques consid\'er\'es ici ont un unique point fixe qui attire toutes les
orbites.

\paragraph{Remarques p\'edagogiques}
Le sujet est tr\`es long, mais il garde un sens si on n'en fait
seulement la partie~I, ou bien seulement I et II (on peut \'eventuellement ensuite leur
raconter ``magistralement'' la preuve de III).


Ces exercices peuvent \^etre propos\'es en travail en groupe de trois \`a
quatre personnes. On sugg\`ere
de disposer de deux heures, de donner, dans la partie~I,
 un exercice diff\'erent \`a chaque groupe
(en adaptant \'eventuellement aux niveaux~: l'exercice sur la maladie est
plus difficile, puisqu'on est en dimension 3 au lieu de 2, et qu'il y a
des valeurs propres complexes). Il vaut probablement mieux ne pas donner
l'\'enonc\'e complet \`a l'avance aux \'etudiants, puisque le principe consiste \`a leur
faire construire l'\'enonc\'e du th\'eor\`eme \`a partir des cas particuliers \'etudi\'es.

Vers la fin de la r\'esolution, on peut faire remarquer aux \'el\`eves que les
vecteurs propres associ\'es \`a la valeur propre $1$ ont un sens par rapport au
probl\`eme pos\'e~: il s'agit d'\'etats d'\'equilibre, et on montre facilement
que si le syst\`eme admet un \'etat limite, alors ce doit \^etre un tel
vecteur propre (par contre l'existence th\'eorique et la propri\'et\'e de
contraction \'evoqu\'es ci-dessus sont plus difficiles). De plus, le calcul
des valeurs propres suffit pour prouver que la suite converge (pas
besoin pour cela de calculer les autres vecteurs propres,
 ni d'inverser la matrice de passage).

On peut enfin demander aux \'etudiants de critiquer les mod\`eles
(il s'agit \'evi\-dem\-ment de ``mod\`eles-jouets''). Les mod\`eles pertinents
sont rarement lin\'eaires, mais le lin\'eaire a l'avantage de conduire \`a des
calculs explicites, et est souvent une bonne approximation d'un syst\`eme g\'en\'eral au
voisinage des \'etats d'\'equilibre. On peut \'egalement introduire le cadre
g\'en\'eral des syst\`emes dynamiques, et \'evoquer d'autres probl\`emes
y conduisant (m\'ecanique c\'eleste, m\'et\'eo, \textit{etc.}), l'analogue en
temps continu (\'equations diff\'erentielles), \textit{etc.}.

Certains de ces exercices sont librement inspir\'es d'un document
d'accompagnement de la mise en \oe uvre des programmes de Terminale
Economique et Sociale sur la th\'eorie des graphes (rentr\'ee 2002), voir
l'adresse~:

\href{http\deuxpoints//www.eduscol.education.fr/D0015/Intentions.htm}{http\deuxpoints//www.eduscol.education.fr/D0015/Intentions.htm}
.}

%%%%%%%%%%%%%%%%%
\begin{exo}
\emph{Afin de pr\'eserver le suspense, il est fortement recommender
de ne pas lire la partie II avant d'avoir r\'esolu l'une des
questions de la  partie I, ni la partie III avant d'avoir r\'epondu aux
questions de la partie II.}


%%%%%%%%%%%%%%%%
\partie{O\`u les maths mod\'elisent des situations diverses}
Choisissez l'un des quatre exercices suivants.



\qst{Migration entre deux villes}
 Deux villes X et Y totalisent une population
d'un million d'habitants. La ville X est plus agr\'eable, mais la ville Y
offre plus de possibilit\'es d'emplois ; 20\% des habitants de Y partent
chaque ann\'ee habiter X pour avoir un meilleur cadre de vie, et 5\% des
habitants de X partent chaque ann\'ee habiter Y pour trouver un meilleur
emploi.  Sachant qu'\`a l'ann\'ee 0, un quart des habitants sont en X,
quelle est la population de X et de Y au bout de 1 an, 2 ans, 5 ans, 10
ans ?

\qst{Agence matrimoniale}
 Dans une ville donn\'ee, 30\% des femmes mari\'ees
divorcent chaque ann\'ee, et chaque ann\'ee, 20\% des femmes c\'elibataires se
marient. De plus, le nombre total de femmes reste constant.  On suppose
qu'en l'an 2000, il y a 8000 femmes mari\'ees et 2000 c\'elibataires. Quel
est le nombre de femmes mari\'ees apr\`es une ann\'ee, deux ann\'ees, cinq
ann\'ees, dix ann\'ees ?


\qst{L'allumeur de r\'everb\`ere}
 Chaque matin, l'allumeur de r\'everb\`ere du
Petit Prince change l'\'etat du r\'everb\`ere de sa plan\`ete avec une
probabilit\'e de 75\%. Au jour 0, le r\'everb\`ere est \'eteint. Quelle est la
probabilit\'e qu'il soit \'eteint demain, et la probabilit\'e qu'il soit
allum\'e ? Que valent ces probabilit\'es dans deux jours, cinq jours, dix
jours, un an ?

\textbf{Indication~:} si les probabilit\'es vous emb\`etent, vous pouvez
consid\'erer une formulation \'equivalente~:
on imagine qu'il y a cent r\'everb\`eres, chacun pouvant \^etre allum\'e ou
\'eteint~; chaque jour, l'allumeur change l'\'etat de 75\% des
r\'everb\`eres. Sachant qu'au jour 0, tous les r\'everb\`eres sont \'eteints,
calculer le nombre de r\'everb\`eres \'eteints et allum\'es le lendemain, \textit{etc.}.


\qst{Propagation d'une maladie}
 On consid\`ere une maladie caus\'ee par une piqûre
d'insecte. Dans la population touch\'ee par cette maladie, les individus
sont dans trois \'etats possibles : immunis\'es, malades, ou
porteurs sains. D'un mois \`a l'autre, l'\'etat d'un individu peut
changer de la mani\`ere suivante~:
\begin{itemize}
\item un individu immunis\'e \`a 90\% de chance
de le rester, mais peut aussi devenir porteur sain avec une probabilit\'e
de 10\%~;
\item un porteur sain a une chance sur deux de devenir malade, et
une chance sur deux de rester porteur sain~;
\item un individu malade a 20\%
de chance de rester malade, et 80\% de chance de gu\'erir (il devient
alors immunis\'e).
\end{itemize}
Sur une population d'un million d'habitants, quelles sont les
proportions de gens malades, porteurs sains et immunis\'es au bout d'un
mois, de 2 mois, de 5 mois, de 10 mois, de 10 ans~? On pourra supposer
qu'au d\'epart, la population est totalement immunis\'ee, ou bien au
contraire qu'un tiers des gens est dans chacun des trois \'etats.
\footnote{Ici le calcul de la matrice inverse n'est pas tr\`es
  agr\'eable. Une fois que les \'el\`eves ont constat\'e cette difficult\'e, on
  peut leur sugg\'erer de laisser tomber ce calcul, et de le remplacer par
  le calcul de la limite et par une estimation de la vitesse de
  convergence (ici, celle de suites g\'eom\'etriques dont le module de la
  raison est de l'ordre de 1/10).}


\vspace{0.15cm}\centerline{\rule{4cm}{.3pt}}


%***********************
\partie{O\`u l'on tente de d\'egager un \'enonc\'e g\'en\'eral}
Dans cette partie, on suppose que chaque \'etudiant est au courant des
r\'esultats des quatre questions de la partie~I~; la mise en commun des
r\'esultats peut se faire \`a l'occasion de la question~\ref{qst.commun}.

\textbf{Les quatre exemples ci-dessus semblent indiquer que la
  mod\'elisation de nombreux probl\`emes va conduire \`a calculer les
  puissances d'un certain type de matrices. Il serait donc int\'eressant
  d'avoir des r\'esultats g\'en\'eraux sur ce type de matrices. Dans la suite, on essaie
  de construire un \'enonc\'e de th\'eor\`eme d'alg\`ebre lin\'eaire, puis de le d\'emontrer.}


\qst{Points communs aux mod\`eles \'etudi\'es (hypoth\`eses)}
On cherche d'abord \`a relever les points communs aux quatre situations
\'etudi\'ees dans la premi\`ere partie.

Habituellement, dans ce genre de situation, on r\'esume les informations
dans un diagramme appel\'e \emph{graphe de transition}.
Voici par exemple le graphe de transition correspondant aux migrations
entre les deux villes~:

$$
\xymatrix{
\mbox{ X } \ar@(ul,dl) []_{95\%} \ar@/^/[rr]^{5\%}&  &
  \mbox{ Y }  \ar@/^/[ll]^{20\%} \ar@(ur,dr) []^{80\%}}
$$

 Les sommets du
graphes correspondent aux diff\'erents \'etats possibles (ici, habiter la
ville X ou la ville Y), et les fl\`eches donnent le pourcentage de gens qui passent
d'un \'etat \`a un autre, d'une ann\'ee sur l'autre.

\sq
Dessiner les graphes de transition correspondant aux autres
situations de la premi\`ere partie.


Dans chacune de ces situations,
la suite des \'etats successifs \'etait d\'ecrite par une relation de
r\'ecurrence lin\'eaire, de la forme
$$
X_{n+1}=AX_n.
$$
Le vecteur $X_n$ s'appelle \emph{vecteur d'\'etat} du syst\`eme, et la
matrice $A$ est la \emph{matrice de transition}.
Par exemple, pour la migration entre villes, $X_n=(a_n,b_n)$ est un
vecteur de $\bbR^2$, o\`u $a_n$ est la population de la ville X apr\`es
$n$ jours, et $b_n$ la population de Y.
  
\sq Ecrivez les matrices de transition correspondant aux situations de la
premi\`ere partie.

\sq Trouvez des propri\'et\'es v\'erifi\'ees par les coefficients de ces quatre
 matrices.\footnote{Les coefficients sont positifs ou nuls, et la somme
 des coefficients de chaque colonne est \'egale \`a  $1$}
 Comment ces propri\'et\'es sont-elles reli\'ees aux situations
 concr\`etes que l'on a mod\'elis\'ees~?

%Une matrice poss\'edant ces deux propri\'et\'es est appel\'ee \emph{matrice
%  stochastique}.
%\footnote{Plus exactement, c'est souvent la transpos\'ee de $A$ qui est appel\'ee
%  matrice stochastique.} 



%*****************************
\qst{Points communs (r\'esultats)}\label{qst.commun}
\sq Trouvez le plus de points communs possibles concernant les valeurs propres et vecteurs
propres des quatre matrices. Fabriquez un \'enonc\'e plausible de th\'eor\`eme
d'alg\`ebre lin\'eaire r\'esumant ces propri\'et\'es. 

\sq Testez votre \'enonc\'e sur des exemples les plus
simples possibles~; modifiez \'even\-tuel\-lement l'\'enonc\'e si vous trouvez des
contre-exemples~! 

\sq Trouvez des points communs concernant la convergence de la suite
de vecteurs $(X_n)$. Compl\'etez votre ``th\'eor\`eme'' (ou bien mettez ces
r\'esultats dans un deuxi\`eme \'enonc\'e).



\vspace{0.15cm}\centerline{\rule{4cm}{.3pt}}


%***********************
\partie{O\`u l'on tente de prouver l'\'enonc\'e g\'en\'eral !}


On sugg\`ere les \'enonc\'es suivants~:

\begin{enonce1*}{Th\'eor\`eme}
  Soit $A$ une matrice carr\'ee de taille $n$, dont les coefficients sont
  tous strictement positifs, et telle que la somme des coefficients dans
  chaque colonne est \'egale \`a~$1$.

Alors $1$ est valeur propre de $A$, et le sous-espace propre associ\'e est
de dimension $1$. Toutes les autres valeurs propres (dans $\bbC$) sont de
modules strictement inf\'erieurs \`a $1$.

%Si de plus $A$ est diagonalisable, alors la suite de matrice $(A^n)_{n
%  \geq 0}$ converge vers une matrice $A_\infty$.
\end{enonce1*}

\begin{enonce1*}{Corollaire}
Soit $A$ une matrice v\'erifiant les hypoth\`eses du th\'eor\`eme pr\'ec\'edent, et
   $X_0$ un vecteur non nul, dont les coordonn\'ees sont toutes positives
  ou nulles.
 Soit $(X_n)_{n \geq 0}$ la suite de vecteurs d\'efinie par la relation de r\'ecurrence
$X_{n+1}=AX_n$.

 Alors la suite $(X_n)$ converge vers un vecteur $X_\infty$. Ce vecteur
 est un vecteur propre associ\'e \`a la
 valeur propre $1$, dont toutes les coordonn\'ees sont strictement
 positives, et dont la somme des coordonn\'ees est \'egale
 \`a la somme des coordonn\'ees de $X_0$.
\end{enonce1*}



\begin{enonce2*}{Remarques concernant le th\'eor\`eme}~
\begin{itemize}
%\item La  convergence d'une suite de matrice signifie
%  tout simplement que dans chaque case, la suite (r\'eelle) des coefficients converge~;
\item L'hypoth\`ese ``\emph{strictement} positifs'' est un peu emb\^etante,
    puisque la matrice du quatri\`eme exemple ne v\'erifie pas cette
    hypoth\`ese. Expliquer n\'eanmoins pourquoi on ne peut pas supprimer le
    mot ``strictement'' dans l'\'enonc\'e. \emph{Question optionnelle~: en
      regardant la matrice $A^2$, expliquer pourquoi on peut quand m\^eme
      utiliser le th\'eor\`eme pour le quatri\`eme exemple}.
\item On va se contenter ici de prouver le th\'eor\`eme dans le
  cas diagonalisable.
\end{itemize}
\end{enonce2*}

\qst{La valeur propre $1$}
On consid\`ere donc une matrice $A$ v\'erifiant les hypoth\`eses du th\'eor\`eme,
et diagonalisable.

L'id\'ee-cl\'e est de consid\'erer la matrice $B$ transpos\'ee de la matrice
$A$.

\sq Montrer que $1$ est valeur propre de $A$ et de $B$. Trouver un
vecteur propre $V$ associ\'e \`a la valeur propre $1$ pour la matrice $B$.

\sq Montrer le lemme suivant (pour une matrice diagonalisable)~:

\begin{enonce1*}{Lemme}
Une matrice a les m\^emes valeurs propres que sa transpos\'ee, avec m\^emes
multiplicit\'es, et m\^emes dimensions pour les sous-espaces propres.
\end{enonce1*}

\sq Montrer que, pour la matrice $B$,  le sous-espace
propre $E_1$ est de dimension $1$.

\textbf{Aide~:} commencer par le cas des matrices de taille 2.
\footnote{On traduit sur les coordonn\'ees le fait que $BU=U$, et on
consid\`ere la coordonn\'ee $U_{i_0}$ de $U$ la plus grande (sans valeur
absolue)~; si il existe une coordonn\'ee strictement plus petite, on
obtient $U_0 < U_0$, contradiction, d'o\`u $U$ est multiple du vecteur $V$.}

\qst{Les autres valeurs propres}
Montrer que les autres valeurs propres sont de modules strictement
inf\'erieurs \`a $1$.
(On peut se contenter de traiter le cas de taille 2, et admettre le
cas g\'en\'eral).

\qst{Preuve du corollaire}
\sq En utilisant l'hypoth\`ese que $A$ est diagonalisable, montrer que la suite
$(X_n)$ converge. 
\sq Terminer la preuve du corollaire.




\vspace{0.15cm}\centerline{\rule{4cm}{.3pt}}
%%%%%%%%%%%%%%%%%%
\partie{Applications}

Dans des mod\`eles de ce type, on appelle \emph{\'etat d'\'equilibre} 
toute r\'epartition de la population qui ne change pas d'ann\'ee en ann\'ee. 

\begin{enonce1*}{Cons\'equences pratiques du th\'eor\`eme}
  ``Pour tout probl\`eme du type des quatre questions de la partie~I, on
  sait \`a l'avance (sans calcul !) que~:
\begin{itemize}
\item pour une population totale donn\'ee, il existe un unique \'etat d'\'equilibre~;
\item on trouvera cet \'etat d'\'equilibre en r\'esolvant le syst\`eme d'\'equations lin\'eaires qui
  traduit le fait que la population ne change pas (en langage savant, en
  cherchant un vecteur propre pour la valeur propre $1$~!)~;
\item quelle que soit la r\'epartition initiale de la population, la suite
  des r\'epartitions convergera vers l'\'etat d'\'equilibre.
\end{itemize}
\end{enonce1*}

Appliquez le th\'eor\`eme obtenu \`a l'\'etude d'une des situations
ci-dessous. Comparez \`a l'\'etude faite dans la partie~I, quand on ne
connaissait pas encore le th\'eor\`eme.

\qst{M\'et\'eo}
Dans ce pays, il ne fait jamais beau deux jours de suite. S'il a fait beau un jour, il
y a autant de chances qu'il neige que de chances qu'il pleuve le
lendemain. S'il fait mauvais (pluie ou neige), il y a une chance sur
deux que ca ne change pas le lendemain, mais si ca change, alors
le changement se fait seulement une fois sur deux vers le beau temps.

Dans ce pays, quelle est la proportion de jours de beau temps, de pluie
et de neige~?
\footnote{\'Etat d'\'equilibre~: $(1,2,2)$. Les autres valeurs propres sont
  $1/4$ et $-1/4$.}

\qst{Machines en panne}
 Une unit\'e de production comprend deux machines automatiques
      fonctionnant ind\'ependamment l'une de l'autre. Chaque machine a la
      fiabilit\'e $p$ au cours d'une journ\'ee, ce qui signifie que sa
      probabilit\'e de tomber en panne pendant cette p\'eriode est \'egale \`a
      $1-p$. Dans ce cas, elle sera r\'epar\'ee pendant la nuit et se
      retrouvera en \'etat de marche le lendemain. Une seule machine peut
      \^etre r\'epar\'ee \`a la fois~: si les deux machines tombent en panne le
 m\^eme jour, alors la deuxi\`eme ne sera r\'epar\'ee que la nuit d'apr\`es.

 Apr\`es une longue p\'eriode, quelle est le
 nombre moyen de journ\'ees o\`u une seule machine est en panne,
et de journ\'ees o\`u les deux machines sont en panne simultan\'ement~?





\subsection*{Autres id\'ees} Les cha\^{\i}nes de Markov permettent de mod\'eliser le
parcourt d'un prince charmant qui d\'elivre sa Princesse, les gains ou
pertes d'un parieur, la croissance des branche d'un arbre,
des propri\'et\'es statistiques d'un langage ou d'un
morceau de musique (comment \'ecrire un texte qui ait l'apparence de
l'anglais, ou bien un morceau de musique qui ``ressemble'' \`a du Bach,
jusqu'\`a la m\'ethode d'authentification d'un sonnet de Shakespeare...).
Les r\'ef\'erences sur le Web sont innombrables, voir par exemple
\href{http\deuxpoints//bi.snu.ac.kr/Courses/g-ai01/HMM-Introduction.pdf}{http\deuxpoints//bi.snu.ac.kr/Courses/g-ai01/HMM-Introduction.pdf}
pour du pseudo-anglais.

\end{exo}

