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 et convergence
Suites de nombres et convergence
Suites de nombres et convergence
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.
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$.
$\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$.
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$.
La suite est divergente si $a\leq-1$ ou $a>1$.
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
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.
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$.
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.
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$.
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
Modélisation par un graphe probabiliste puis par des matrices
Vocabulaire des graphes
Vocabulaire des graphes
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
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
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 :
- 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
Matrice de transition
On peut reporter les probabilités de transition dans un tableau :
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$.
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
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.
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$.