Exercices Alternatifs

Exemples de systèmes dynamiques linéaires, matrices stochastiques

\begin{matrix}c \\ ◯ \end{matrix}2002 Frédéric Le Roux (copyleft LDL : Licence pour Documents Libres).

Source: systemes dynamiques lineaires.tex.
Version imprimable: systemes dynamiques lineaires.pdf

Algèbre linéaire. DEUG deuxième année. Angle pédagogique : À quoi ça sert.

Objectifs et commentaires.

Objectif “méta” : voir comment un même concept mathématique peut modéliser des situations issues de domaines variés, et comment un théorème abstrait peut résumer toutes ces situations, ce qui illustre la généralité des outils développés par les mathématiciens ;

Objectif d’ouverture : donner une idée de ce qu’est un système dynamique ;

Objectif interne : voir des situations où les puissances de matrices, et les vecteurs propres, ont un

sens concret (voir ci-dessous) ;

Objectif “technique” : calcul de suites définies par une relation de récurrence linéaire, puissances d’une matrice, diagonalisation.

Remarques mathématiques A cause de la nature des problèmes choisis, tous les systèmes proposés ici (sauf la dernière question) sont régis 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ées sont positives), qui correspond à la valeur propre 1. ^{1} De plus, si la matrice est transitive (c’est-à-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ône positif. Autrement dit, les systèmes dynamiques considérés ici ont un unique point fixe qui attire toutes les orbites.

Remarques pédagogiques Le sujet est très long, mais il garde un sens si on n’en fait seulement la partie I, ou bien seulement I et II (on peut éventuellement ensuite leur raconter “magistralement” la preuve de III). Ces exercices peuvent être proposés en travail en groupe de trois à quatre personnes. On suggère de disposer de deux heures, de donner, dans la partie I, un exercice différent à chaque groupe (en adaptant éventuellement 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’énoncé complet à l’avance aux étudiants, puisque le principe consiste à leur faire construire l’énoncé du théorème à partir des cas particuliers étudiés. Vers la fin de la résolution, on peut faire remarquer aux élèves que les vecteurs propres associés à la valeur propre 1 ont un sens par rapport au problème posé : il s’agit d’états d’équilibre, et on montre facilement que si le système admet un état limite, alors ce doit être un tel vecteur propre (par contre l’existence théorique et la propriété de contraction évoqués 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 étudiants de critiquer les modèles (il s’agit évidemment de “modèles-jouets”). Les modèles pertinents sont rarement linéaires, mais le linéaire a l’avantage de conduire à des calculs explicites, et est souvent une bonne approximation d’un système général au voisinage des états d’équilibre. On peut également introduire le cadre général des systèmes dynamiques, et évoquer d’autres problèmes y conduisant (mécanique céleste, météo, etc.), l’analogue en temps continu (équations différentielles), etc.. Certains de ces exercices sont librement inspirés d’un document d’accompagnement de la mise en œuvre des programmes de Terminale Economique et Sociale sur la théorie des graphes (rentrée 2002), voir l’adresse : http://www.eduscol.education.fr/D0015/Intentions.htm .

1L’existence peut s’obtenir facilement comme conséquence du théorème de point fixe de Brouwer, mais peut aussi se prouver par des considérations d’algèbre linéaire élémentaire : voir le théorème de Perron-Frobenius, par exemple dans le livre Katok, Hasselblatt, Introduction to the modern theory of dynamical systems, Cambridge University Press, 1995.

Afin de préserver le suspense, il est fortement recommender de ne pas lire la partie II avant d’avoir résolu l’une des questions de la partie I, ni la partie III avant d’avoir répondu aux questions de la partie II.

I. Où les maths modélisent des situations diverses

Choisissez l’un des quatre exercices suivants.

Question 1. Migration entre deux villes

Deux villes X et Y totalisent une population d’un million d’habitants. La ville X est plus agréable, mais la ville Y offre plus de possibilités d’emplois ; 20% des habitants de Y partent chaque année habiter X pour avoir un meilleur cadre de vie, et 5% des habitants de X partent chaque année habiter Y pour trouver un meilleur emploi. Sachant qu’à l’année 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 ?

Question 2. Agence matrimoniale

Dans une ville donnée, 30% des femmes mariées divorcent chaque année, et chaque année, 20% des femmes célibataires se marient. De plus, le nombre total de femmes reste constant. On suppose qu’en l’an 2000, il y a 8000 femmes mariées et 2000 célibataires. Quel est le nombre de femmes mariées après une année, deux années, cinq années, dix années ?

Question 3. L’allumeur de réverbère

Chaque matin, l’allumeur de réverbère du Petit Prince change l’état du réverbère de sa planète avec une probabilité de 75%. Au jour 0, le réverbère est éteint. Quelle est la probabilité qu’il soit éteint demain, et la probabilité qu’il soit allumé ? Que valent ces probabilités dans deux jours, cinq jours, dix jours, un an ?

Indication : si les probabilités vous embètent, vous pouvez considérer une formulation équivalente : on imagine qu’il y a cent réverbères, chacun pouvant être allumé ou éteint ; chaque jour, l’allumeur change l’état de 75% des réverbères. Sachant qu’au jour 0, tous les réverbères sont éteints, calculer le nombre de réverbères éteints et allumés le lendemain, etc..

Question 4. Propagation d’une maladie

On considère une maladie causée par une piqûre d’insecte. Dans la population touchée par cette maladie, les individus sont dans trois états possibles : immunisés, malades, ou porteurs sains. D’un mois à l’autre, l’état d’un individu peut changer de la manière suivante :

– un individu immunisé à 90% de chance de le rester, mais peut aussi devenir porteur sain avec une probabilité de 10% ;

– un porteur sain a une chance sur deux de devenir malade, et une chance sur deux de rester porteur sain ;

– un individu malade a 20% de chance de rester malade, et 80% de chance de guérir

(il devient alors immunisé). Sur une population d’un million d’habitants, quelles sont les proportions de gens malades, porteurs sains et immunisés au bout d’un mois, de 2 mois, de 5 mois, de 10 mois, de 10 ans ? On pourra supposer qu’au départ, la population est totalement immunisée, ou bien au contraire qu’un tiers des gens est dans chacun des trois états. ^{2}

II. Où l’on tente de dégager un énoncé général

Dans cette partie, on suppose que chaque étudiant est au courant des résultats des quatre questions de la partie I ; la mise en commun des résultats peut se faire à l’occasion de la question 2.

Les quatre exemples ci-dessus semblent indiquer que la modélisation de nombreux problèmes va conduire à calculer les puissances d’un certain type de matrices. Il serait donc intéressant d’avoir des résultats généraux sur ce type de matrices. Dans la suite, on essaie de construire un énoncé de théorème d’algèbre linéaire, puis de le démontrer.

Question 1. Points communs aux modèles étudiés (hypothèses)

On cherche d’abord à relever les points communs aux quatre situations étudiées dans la première partie.

Habituellement, dans ce genre de situation, on résume les informations dans un diagramme appelé graphe de transition. Voici par exemple le graphe de transition correspondant aux migrations entre les deux villes :

[figure: X; 95%; 5%; Y; 20%; 80%]

Les sommets du graphes correspondent aux différents états possibles (ici, habiter la ville X ou la ville Y), et les flèches donnent le pourcentage de gens qui passent d’un état à un autre, d’une année sur l’autre. a. Dessiner les graphes de transition correspondant aux autres situations de la première partie.

2Ici le calcul de la matrice inverse n’est pas très agréable. Une fois que les élèves ont constaté cette difficulté, on peut leur suggérer 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éométriques dont le module de la raison est de l’ordre de 1/10).

Dans chacune de ces situations, la suite des états successifs était décrite par une relation de récurrence linéaire, de la forme

X_{n+1} = AX_{n}.

Le vecteur X_{n} s’appelle vecteur d’état du système, et la matrice A est la matrice de transition. Par exemple, pour la migration entre villes, X_{n} = (a_{n}, b_{n}) est un vecteur de ℝ^{2}, où a_{n} est la population de la ville X après n jours, et b_{n} la population de Y.

b. Ecrivez les matrices de transition correspondant aux situations de la première partie.

c. Trouvez des propriétés vérifiées par les coefficients de ces quatre matrices.^{3} Comment ces propriétés sont-elles reliées aux situations concrètes que l’on a modélisées ?

Question 2. Points communs (résultats)

a. Trouvez le plus de points communs possibles concernant les valeurs propres et vecteurs propres des quatre matrices. Fabriquez un énoncé plausible de théorème d’algèbre linéaire résumant ces propriétés.

b. Testez votre énoncé sur des exemples les plus simples possibles ; modifiez éventuellement l’énoncé si vous trouvez des contre-exemples !

c. Trouvez des points communs concernant la convergence de la suite de vecteurs (X_{n}). Complétez votre “théorème” (ou bien mettez ces résultats dans un deuxième énoncé).

III. Où l’on tente de prouver l’énoncé général !

On suggère les énoncés suivants :

Théorème Soit A une matrice carrée de taille n, dont les coefficients sont tous strictement positifs, et telle que la somme des coefficients dans chaque colonne est égale à 1.

Alors 1 est valeur propre de A, et le sous-espace propre associé est de dimension 1. Toutes les autres valeurs propres (dans ℂ) sont de modules strictement inférieurs à 1.

Corollaire Soit A une matrice vérifiant les hypothèses du théorème précédent, et X_{0} un vecteur non nul, dont les coordonnées sont toutes positives ou nulles. Soit (X_{n})_{n≥0} la suite de vecteurs définie par la relation de récurrence X_{n+1} = AX_{n}.

Alors la suite (X_{n}) converge vers un vecteur X_{∞}. Ce vecteur est un vecteur propre associé à la valeur propre 1, dont toutes les coordonnées sont strictement positives, et dont la somme des coordonnées est égale à la somme des coordonnées de X_{0}.

Remarques concernant le théorème – L’hypothèse “strictement positifs” est un peu embêtante, puisque la matrice du

3Les coefficients sont positifs ou nuls, et la somme des coefficients de chaque colonne est égale à 1

quatrième exemple ne vérifie pas cette hypothèse. Expliquer néanmoins pourquoi on ne peut pas supprimer le mot “strictement” dans l’énoncé. Question optionnelle : en regardant la matrice A^{2}, expliquer pourquoi on peut quand même utiliser le théorème pour le quatrième exemple.

– On va se contenter ici de prouver le théorème dans le cas diagonalisable.

Question 1. La valeur propre 1

On considère donc une matrice A vérifiant les hypothèses du théorème, et diagonalisable.

L’idée-clé est de considérer la matrice B transposée de la matrice A.

a. Montrer que 1 est valeur propre de A et de B. Trouver un vecteur propre V associé à la valeur propre 1 pour la matrice B.

b. Montrer le lemme suivant (pour une matrice diagonalisable) :

Lemme Une matrice a les mêmes valeurs propres que sa transposée, avec mêmes multiplicités, et mêmes dimensions pour les sous-espaces propres.

c. Montrer que, pour la matrice B, le sous-espace propre E_{1} est de dimension 1. Aide : commencer par le cas des matrices de taille 2. ^{4}

Question 2. Les autres valeurs propres

Montrer que les autres valeurs propres sont de modules strictement inférieurs à 1. (On peut se contenter de traiter le cas de taille 2, et admettre le cas général).

Question 3. Preuve du corollaire

a. En utilisant l’hypothèse que A est diagonalisable, montrer que la suite (X_{n}) converge.

b. Terminer la preuve du corollaire.

IV. Applications

Dans des modèles de ce type, on appelle état d’équilibre toute répartition de la population qui ne change pas d’année en année.

Conséquences pratiques du théorème “Pour tout problème du type des quatre questions de la partie I, on sait à l’avance (sans calcul !) que :

– pour une population totale donnée, il existe un unique état d’équilibre ; – on trouvera cet état d’équilibre en résolvant le système d’équations linéaires qui tra-

4On traduit sur les coordonnées le fait que BU = U, et on considère la coordonnée U_{i_{0}} de U la plus grande (sans valeur absolue) ; si il existe une coordonnée strictement plus petite, on obtient U_{0} < U_{0}, contradiction, d’où U est multiple du vecteur V.

duit le fait que la population ne change pas (en langage savant, en cherchant un vecteur propre pour la valeur propre 1 !) ;

– quelle que soit la répartition initiale de la population, la suite des répartitions convergera vers l’état d’équilibre.

Appliquez le théorème obtenu à l’étude d’une des situations ci-dessous. Comparez à l’étude faite dans la partie I, quand on ne connaissait pas encore le théorème.

Question 1. Météo

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 ? ^{5}

Question 2. Machines en panne

Une unité de production comprend deux machines automatiques fonctionnant indépendamment l’une de l’autre. Chaque machine a la fiabilité p au cours d’une journée, ce qui signifie que sa probabilité de tomber en panne pendant cette période est égale à 1 − p. Dans ce cas, elle sera réparée pendant la nuit et se retrouvera en état de marche le lendemain. Une seule machine peut être réparée à la fois : si les deux machines tombent en panne le même jour, alors la deuxième ne sera réparée que la nuit d’après.

Après une longue période, quelle est le nombre moyen de journées où une seule machine est en panne, et de journées où les deux machines sont en panne simultanément ?

Autres idées

Les chaînes de Markov permettent de modéliser le parcourt d’un prince charmant qui délivre sa Princesse, les gains ou pertes d’un parieur, la croissance des branche d’un arbre, des propriétés statistiques d’un langage ou d’un morceau de musique (comment écrire un texte qui ait l’apparence de l’anglais, ou bien un morceau de musique qui “ressemble” à du Bach, jusqu’à la méthode d’authentification d’un sonnet de Shakespeare...). Les références sur le Web sont innombrables, voir par exemple http://bi.snu.ac.kr/Courses/g-ai01/HMM-Introduction.pdf pour du pseudo-anglais.

5État d’équilibre : (1, 2, 2). Les autres valeurs propres sont 1/4 et −1/4.