Calcul matriciel : suites et convergence

Introduction :

Ce cours complète l’étude des matrices. Nous verrons ce qu’est une suite arithmético-géométrique puis l’utilité des matrices dans ce cas avec l’étude de la convergence. Nous modéliserons ensuite un problème à l’aide de graphes probabilistes puis à l’aide de matrices.

Suites et convergence

Suites de nombres et convergence

bannière definition

Définition

Suite arithmético-géométrique :

Soit $u_n$ une suite de nombres vérifiant $u_{n+1}=au_n+b$.

Une telle suite est dite arithmético-géométrique ou récurrence affine.

bannière astuce

Astuce

Passer de la formule de récurrence à la formule explicite avec les suites de nombres :

Une suite de nombres $u_n$ vérifie $u_{n+1}=a\ u_n+b $ avec $a≠1$.

  • on résout l’équation $x=ax+b$1 : elle a une solution unique $c$.
  • on introduit la suite auxiliaire $x_n$ définie par $x_n=u_n-c$. On prouve qu’elle est géométrique (de raison $a$) ; il en résulte que pour tout naturel $n$, $x_n=a^n\ x_0$.
  • on revient à la suite initiale : pour tout naturel $n$, $u_n=x_n+c$. D’où l’expression : $u_n=a^n(u_0-c)+c$.
bannière exemple

Exemple

$\bigg\lbrace\begin{aligned} u_0&=12\\u_{n+1}&=0,2u_n+4 \end{aligned}$

Si $u_n$ converge, alors sa limite $x$ est solution de l’équation $x=0,2x+4$.

Cette équation a pour solution $x = 5$.

Cela suggère de poser : pour tout naturel $n$, $x_n=u_n-5$.

De $u_{n+1}=0,2u_n+4$ et $5+0,2×5+4$, on déduit par soustraction : $u_{n+1}-5=0,2(u_n-5)$ soit $x_{n+1}=0,2x_n$.

La suite $x_n$ est géométrique de raison $a=0,2$ et de premier terme $x_0=u_0-5=7$.

D’où pour tout naturel $n$, $x_n=x_0\ a^n$ soit $x_n=7×0,2^n$. Ainsi $u_n-5=7×0,2^n$.

On obtient donc la formule explicite : $u_n=7×0,2^n+5$.

bannière propriete

Propriété

Propriété : convergence

Une suite de nombres $u_n$ vérifie $u_{n+1}=a\ u_n+b$ avec $-1 < a < 1$.

Alors la suite $u_n$ converge vers le nombre $c$ vérifiant $c=ac+b$.

bannière à retenir

À retenir

La suite est divergente si $a\leq-1$ ou $a>1$.

bannière exemple

Exemple

Reprenons la suite définie par $\bigg\lbrace\begin{aligned} u_0&=12\\u_{n+1}&=0,2u_n+4 \end{aligned}$

La raison $a = 0,2$ est telle que $-1 < a < 1$ donc $\lim\limits_{n\to+\infty}0,2^n=0$. Ainsi $\lim\limits_{n\to+\infty}u_n=5$.

Suites de matrices

Voyons maintenant l’équivalent avec une suite de matrice $U_n$ vérifiant $U_{n+1}=\text A\ U_n+\text B$.

Par exemple, la suite $U_n$ de matrices colonnes de format $(2,1)$ est définie par :

$U_0=\begin{pmatrix} 3 \\ -2 \end{pmatrix}$ et pour tout naturel $n$, $U_{n+1}=\text A\ U_n+\text B$ où $\text A=\begin{pmatrix}1&4\\1&2\end{pmatrix}$ et $\text B=\begin{pmatrix}12\\ -2\end{pmatrix}$.

La méthode pour passer de la forme par récurrence à la forme explicite est inspirée de la méthode précédente avec les suites de nombres.

bannière astuce

Astuce

Passer de la formule de récurrence à la formule explicite avec les suites de matrices :

Une suite de matrices colonnes $U_n$ vérifie $U_{n+1}=\text A\ U_n+\text B$, où la matrice $\text I-\text A$ est inversible.

  • On résout l’équation $\text C=\text A\text C+\text B$ : elle a une solution unique $\text C=(\text I-\text A)^{-1}\text B$.
  • On introduit la suite auxiliaire $X_n$ définie par $X_n=U_n-\text C$. On prouve qu’elle vérifie, pour tout naturel $n$, $X_{n+1}=\text A\ X_n$, puis par récurrence que $X_n=\text A^n\ X_0$.
  • On revient à la suite initiale : pour tout naturel $n$, $U_n=X_n+\text C$.

D’où l’expression : $U_n=\text A^n(U_0-\text C)+\text C$.

bannière exemple

Exemple

Chercher une matrice colonne $\text C$ de format $(2,1)$, telle que $\text C=\text A\text C+\text B$.

Cette équation d’inconnue $\text C$ s’écrit $\text C-\text A\text C=\text B$, c’est-à-dire $(\text I-\text A) \text C= \text B$.

Si $\text I-\text A$ est inversible, il faut multiplier à gauche les deux membres par $(\text I-\text A)^{-1}$ ce qui donne : $\text C=(\text I-\text A)^{-1}\ \text B$.

Or $\text I-\text A=\begin{pmatrix}0&-4\\ -1&-1\end{pmatrix}$, cette matrice est inversible, et $(\text I-\text A)^{-1}=\begin{pmatrix}0,25&-1\\ -0,25&0\end{pmatrix}$ donc $\text C=\begin{pmatrix}5\\ -3\end{pmatrix}$.

De $U_{n+1}=\text A\ U_n+\text B$ et $\text C=\text A\text C+\text B$, on déduit par soustraction : $U_{n+1}-\text C=\text A( U_n-\text C)$. En posant $X_n=U_n-\text C$ pour tout entier naturel $n$, on obtient : $X_{n+1}=\text A\ X_n$.

On démontre alors par récurrence que l’égalité $X_n=\text A^n\ X_0$ pour tout entier naturel $n$. Pour $n = 0$, $\text A_0=\text I$. Donc l’égalité est vraie au rang $0$.

Si $X_n=\text A^n\ X_0$, alors en multipliant à gauche les deux membres par $\text A$, on obtient $\text A\ X_n=\text A^{n+1}\ X_0$, c’est-à-dire, $X_{n+1}=\text A^{n+1}\ X_0$ ( car $X_{n+1}=\text A\ X_n$).

  • L’égalité est donc héréditaire.

On conclut que pour tout $n\in\mathbb N$, $X_n=\text A^n\ X_0$

En revenant à la suite $U_n$ : pour tout $n\in\mathbb N$, $U_n-\text C=\text A^n\ ( U_0-\text C)$ d’où $U_n=\text A^n\ ( U_0-\text C)+\text C$ qu’on appelle formule explicite.

bannière propriete

Propriété

Convergence lorsque la suite est une matrice ligne :

Si $V_n$ est une suite de matrice lignes de même format telle que $V_{n+1}=V_n\ \text A+\text B$, où $\text A$ est une matrice carrée et $\text B$ une matrice ligne, on obtient des résultats analogues : si $\text I-\text A$ est inversible, l’équation $\text C=\text C\text A+\text B$ a une solution unique : $\text C+\text B(\text I-\text A)^{-1}$.

Alors pour tout $n\in\mathbb N$, $V_n=(V_0-\text C)\text A_n+\text C$.

bannière propriete

Propriété

Convergence d’une suite de matrices :

$U_n$ est une suite de matrices de format donné, $\text L$ une matrice de même format. Dire que la suite $U_n$ a pour limite $\text L$ signifie que, pour chaque emplacement, la suite des coefficients de $U_n$ a pour limite le coefficient de $\text L$. On dit aussi que $U_n$ converge vers $\text L$.

Modélisation par un graphe probabiliste puis par des matrices

Vocabulaire des graphes

bannière definition

Définition

Graphes :

  • Un graphe est constitué d’un ensemble de points reliés par des arcs.
  • Un point du graphe est appelé un sommet.
  • Un arc reliant deux sommets est appelé une arête.
  • Lorsque ces arêtes sont munies d’un sens, on dit que le graphe est orienté.
  • Lorsque ces arêtes sont affectées de coefficients positifs, on dit que le graphe est pondéré et le coefficient associé à une arête est appelé le poids de l’arête.
  • Lorsque la somme des poids des arêtes issues de chaque sommet est égale à 1, on dit que le graphe est un graphe probabiliste.

Marche aléatoire entre deux états

On considère un système qui peut se trouver soit dans un état $\text A$, soit dans un état $\text B$, et qui évolue par étapes successives, en changeant d’état à chaque étape de façon aléatoire.

On note $p$ la probabilité qu’il passe de l’état $\text A$ à l’état $\text B$, $q$ la probabilité qu’il passe de l’état $\text B$ à l’état $\text A$. La probabilité qu’il reste en $\text A$ est donc $1-p$, la probabilité qu’il reste en $\text B$ est $1 - q$.

Ces probabilités sont appelées les probabilités de transition du système. On suppose qu’elles sont constantes au cours de cette « marche aléatoire ».

Pout tout $n\in\mathbb N$, on note :

  • $\text A_n$ l’événement : « à l’étape $n$, le système est dans l’état $\text A$ », et $a_n$ sa probabilité ;
  • $\text B_n$ l’événement contraire : « à l’étape $n$, le système est dans l’état $\text B$ », et $b_n$ sa probabilité.

Les nombres $a_n$ et $b_n$ sont compris entre $0$ et $1$, et leur somme est $1$.

De plus, pour tout $n\in\mathbb N$ :

  • $P_{\text A_n}(\text A_{n+1})=1-p$
  • $P_{\text A_n}(\text B_{n+1})=p$
  • $P_{\text B_n}(\text A_{n+1})=q$
  • $P_{\text B_n}(\text B_{n+1})=1-q$

Arbre probabiliste Arbre probabiliste

D’après cet arbre, pour tout nombre $n$ : $\bigg\lbrace \begin{aligned} a_{n+1}&=(1-p)a_n+q_{b_n}\\ b_{n+1}&=pa_n+(1-q)b_n \end{aligned}$

On représente l’évolution de ce système d’une étape à la suivante par un graphe probabiliste, dont les sommets indiquent les états et les flèches indiquent les probabilités de transition.

Graphe probabiliste Graphe probabiliste

bannière propriete

Propriété

Graphe probabiliste :

  • Tous les coefficients sont compris entre 0 et 1.
  • Pour toutes les flèches partant d’un même sommet, la somme des probabilités vaut 1.

Matrice de transition

On peut reporter les probabilités de transition dans un tableau :

bannière definition

Définition

Matrice de transition T :

La matrice de transition d’une marche aléatoire est la matrice carrée $T= m_{ij}$ dont le coefficient $m_{ij}$ est la probabilité de transition du sommet $j$ vers le sommet $i$.

On note : $T=\begin{pmatrix} 1-p & p \\ q & 1-q \end{pmatrix}$

Attention à la position de chaque coefficient : l’état de départ définit le numéro de ligne, l’état d’arrivée le numéro de colonne.

  • La matrice de transition a les propriétés suivantes :
  • Tous les coefficients sont compris entre 0 et 1.
  • Pour chaque ligne, la somme des coefficients vaut 1.
  • Continuons avec l’écriture matricielle du problème. Voici, les définitions et théorèmes qui vont nous aider.
  • La matrice ligne $P_n=(a_n \; b_n)$ est appelée la répartition de probabilité à l’étape $n$.
  • Pour tout naturel $n$, $P_{n+1}=P_nT$ et donc $P_n=P_0T^n$
  • On appelle répartition stable de probabilité une matrice ligne $P$, dont tous les coefficients sont positifs et de somme 1, vérifiant $P=PT$.
  • Une marche aléatoire entre deux états a pour matrice de transition : $T=\begin{pmatrix} 1-p & p \\ q & 1-q \end{pmatrix}$
  • $P_n=(a_n \; b_n)$ est la répartition de probabilité à l’étape $n$.
bannière propriete

Propriété

Répartition de probabilité :

Si $p$ et $q$ ne sont pas tous les deux nuls, ni tous les deux égaux à 1, alors il existe une répartition stable de probabilité P et une seule : $\begin{aligned}P= \lbrace\{\frac{q}{p+q} \; \frac{p}{p+q}\rbrace\}\end{aligned}$

De plus, quelle que soit la répartition de probabilité initiale $P_0$, la suite $(P_n)$ converge vers $P$.

Marche aléatoire entre plusieurs états

On en arrive à la dernière partie de cette leçon avec la marche aléatoire entre plusieurs états.

On considère un système qui peut se trouver dans plusieurs états, incompatibles deux à deux, et recouvrant toutes les possibilités. Il évolue par étapes successives, en changeant d’état de façon aléatoire, les probabilités de transition étant supposées constantes.

On peut représenter son évolution par un graphe et lui associer une matrice de transition. Ce graphe et cette matrice ont les mêmes propriétés que dans le cas des deux états.

bannière propriete

Propriété

Marche aléatoire entre deux états:

Si la matrice de transition $T$ admet une puissance n’ayant aucun coefficient nul, alors :

  • Il existe une répartition stable de probabilité $P$ et une seule, telle que $PT=P$;
  • Quelle que soit la répartition de probabilité initiale $P_0$, la suite $(P_n)$ converge vers $P$.