\documentclass[12pt]{article}
\usepackage[frenchb]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[everytoc,ant]{pas-cours}
\usepackage{pas-math}
\usepackage{amssymb,amsmath}
\usepackage[hmargin=2cm,vmargin=1.5cm]{geometry}
\usepackage[colorlinks=true]{hyperref}
\usepackage{multicol,cellspace,tabularx}
\usepackage{systeme}
\usetikzlibrary{matrix}
\setlength{\parindent}{0pt}
\begin{document}
\chap[num=C,pos=right,color=purple]{Applications du calcul matriciel}{\emph{Stéphane PASQUET, \today}}

%--------------- TOC
\renewcommand{\contentsname}{\color{purple}\titreFONT\huge Sommaire}
{\color{purple}\hrulefill}
{\tocFONT\tableofcontents}
{\color{purple}\hrulefill}

\vspace*{1cm} %---------- PREREQUIS

\begin{prerequis}
\item Calculs matriciels (of course !)
\item Probabilités et variables aléatoires discrètes
\item Raisonnement par récurrence
\end{prerequis}

\newpage %----------------- DEBUT


\`A travers plusieurs exemples, nous allons introduire diverses notions dans lesquelles le calcul matriciel a son importance.

\bigskip

\begin{pasbox}[degrade,style=ex,name={Marche aléatoire et graphe probabiliste}]
Valentin est un adolescent comme tant d'autres ... Dans sa chambre, il est soit sur son lit, soit devant son ordinateur (sur son bureau).\\
S'il est sur son lit, la probabilité qu'il y soit encore une minute plus tard est égale à $\dfrac{4}{5}$.\\
S'il est devant son ordinateur, la probabilité pour qu'il y soit encore une minute plus tard est égale à $\dfrac{2}{3}$.
\end{pasbox}

Pour schématiser cette situation, on fait appel à un  \definmot{graphe probabiliste}. En convenant de noter L pour \og il est sur son lit \fg{}  et O pour \og il est devant son ordinateur \fg, on a :

\begin{center}
\begin{tikzpicture}[label/.style={draw,circle}]
\node[label] (R) at (0,0) {L};
\node[label] (T) at (4,0) {O};
\draw[->,>=stealth'] (R.north east) to[bend left=60] (T.north west);
\node[above] at (2,1.2) {$\dfrac{1}{5}$};
\draw[->,>=stealth'] (T.south west) to[bend left=60] (R.south east);
\node[below] at (2,-1.2) {$\dfrac{1}{3}$};
\draw[<-,>=stealth',yscale=15,xscale=3] (R.west) to[loop left] (R.west);
\node[left] at (-1.5,0) {$\dfrac{4}{5}$};
\draw[<-,>=stealth',yscale=15,xscale=3] (T.east) to[loop right] (T.east);
\node[right] at (5.5,0) {$\dfrac{2}{3}$};
\end{tikzpicture}
\end{center}

\og L \fg{} et \og O \fg{} sont appelés les \definmot{sommet} du graphe.\\
En convenant que L est le 1\ier{} sommet, la matrice du graphe, ou \definmot{matrice de transition} est :\renewcommand{\arraystretch}{1.5}
\[
A=\begin{pmatrix}
\frac{4}{5} & \frac{1}{5}\\
\frac{1}{3} & \frac{2}{3}
\end{pmatrix}
\]

On appellera \definmot{état initial du graphe} le vecteur ligne $X_0$ nous informant du lieu où Valentin se trouve au début de notre observation (par exemple, s'il est sur son lit, alors $X_0=\begin{pmatrix}1 & 0\end{pmatrix}$.

\begin{pasbox}[degrade,style=prop]
Soit un graphe de matrice de transition $A$ et d'état initial $X_0=\begin{pmatrix}1 & 0\end{pmatrix}$.\\
Alors, l'état du graphe après $n$ observations sera :
\[ X_n=X_0A^n \]
\end{pasbox}

\newpage

Ouvrons maintenant le logiciel gratuit \texttt{XCAS}, puis tapons les lignes suivantes :

\medskip

\renewcommand{\arraystretch}{1.5}
\begin{tabularx}{\linewidth}{|>{\ttfamily\arraybackslash}X|}
\hline
A:=[[4/5,1/5],[1/3,2/3]];\\
\centering\arraybackslash $\begin{bmatrix}\frac{4}{5} & \frac{1}{5}\\
\frac{1}{3} & \frac{2}{3}\end{bmatrix}$\\
\hline
P:=egv(A);\\
\centering\arraybackslash $\begin{bmatrix}1 & -3\\
1 & 5\end{bmatrix}$\\
\hline
D:=inv(P)*A*P;\\
\centering\arraybackslash $\begin{bmatrix}1 & 0\\
0 & \frac{7}{15}\end{bmatrix}$\\
\hline
Q:=inv(P);\\
\centering\arraybackslash$\begin{bmatrix}\frac{5}{8} & \frac{3}{8}\\-\frac{1}{8} & \frac{1}{8}\end{bmatrix}$\\
\hline
\end{tabularx}

\medskip

La première commande définit notre matrice de transition ;\\
La seconde et la troisième calculent les matrices $P$ et $D$ telles que :
\[ A=PDP^{-1} \]
où $D$ est une matrice diagonale.\\
La dernière affiche la matrice inverse de $P$.

\medskip

On peut ainsi écrire que, pour tout entier naturel $n$, 
\[ A^n = PD^nP^{-1} \]
pour ensuite calculer $\limite{n}{+\infty}A^n$. En effet,
\[ \limite{n}{+\infty} D^n=\begin{pmatrix}
1 & 0 \\ 0 & 0\end{pmatrix}\qquad\text{car }\limite{n}{+\infty}\left(\frac{7}{15}\right)^n=0.\]
Donc,
\[ \limite{n}{+\infty} X_n=\begin{pmatrix}1 & 0\end{pmatrix} \begin{pmatrix}1 & -3\\1 & 5\end{pmatrix}\begin{pmatrix}1 & 0\\0 & 0\end{pmatrix}\begin{pmatrix}
\frac{5}{8} & \frac{3}{8}\\-\frac{1}{8} & \frac{1}{8}\end{pmatrix}=\begin{pmatrix}\frac{5}{8} & \frac{3}{8}\end{pmatrix}\]

\begin{pasbox}[degrade,style=defi,name={\'Etat d'équilibre d'un graphe (résultat asymptotique)}]
Lorsque $\limite{n}{+\infty} X_n$ existe, il est appelé l'\definmot{état d'équilibre} du graphe, ou \definmot{résultat asymptotique} pour la marche aléatoire.
\end{pasbox}

\begin{pasbox}[degrade,style=rem]
La matrice d'un graphe probabiliste est de la forme :
\[ A = \begin{pmatrix}p & 1-p\\1-q & q\end{pmatrix}\]
Avec $p$ et $q$ deux probabilités.\\
Or, $A$ est inversible si et seulement si :
\begin{align*}
pq-(1-p)(1-q)\neq 0 & \Leftrightarrow pq-(1-p-q+pq)\\
& \Leftrightarrow p+q-1
\end{align*}

Ainsi, $A$ est inversible quand $p+q\neq1$.
\end{pasbox}


%----------------------------- Suites de matrices --------------------

\begin{pasbox}[degrade,style=ex,name={Suite de matrices colonnes}]
On considère les deux suites \suite{u}{n}{} et \suite{v}{n}{} telles que :
\[
\left\lbrace
\begin{array}{l}
u_0=a\\
v_0=b
\end{array}
\right.\qquad,\qquad\forall n\in\N,\quad
\left\lbrace
\begin{array}{l}
u_{n+1}=\dfrac{u_n+v_n}{2}\\
v_{n+1}=\dfrac{u_n-v_n}{2}
\end{array}
\right.
\]
L'objectif est d'étudier ces deux suites à l'aide des matrices.
\end{pasbox}

Pour cela, on va poser :
\[ V_n=\begin{pmatrix}u_n\\v_n\end{pmatrix}\qquad;\qquad A=\begin{pmatrix}
\frac{1}{2} & \frac{1}{2}\\\frac{1}{2} & -\frac{1}{2}\end{pmatrix}=\frac{1}{2}\begin{pmatrix}1 & 1\\1 & -1\end{pmatrix}
\]
Ainsi, on a :
\[ V_0=\begin{pmatrix}a \\ b\end{pmatrix}\qquad;\qquad V_{n+1}=AV_n\]
On en déduit alors :
\[ V_{n} = A^nV_0.\]
Il ne nous reste plus qu'à trouver une expression de $A^n$.\\
On peut remarquer dans un premier temps, à l'aide de XCAS par exemple, que :
\[\forall p\in\N,\ A^{2p} = \dfrac{1}{2^p}I_2\]
et donc :
\[ \forall p\in\N,\ A^{2p+1}=\dfrac{1}{2^{p+1}}\begin{pmatrix}1 & 1\\1 & -1\end{pmatrix}.\]
Ainsi, pour tout entier naturel $p$,
\[ 
V_{2p}=\dfrac{1}{2^p}\begin{pmatrix}a\\b\end{pmatrix}
\qquad ; \qquad
V_{2p+1}=\dfrac{1}{2^{p+1}}\begin{pmatrix}a+b\\a-b\end{pmatrix}
\]

Abordons maintenant le cas général.

\bigskip\renewcommand{\arraystretch}{1}

\begin{pasbox}[degrade,style=prop,name={Système linéaire de suites récurrentes avec second membre}]
Soient les suites \suite{u}{n}{} et \suite{v}{n}{} définies par leur premier terme respectif $u_0$ et $v_0$ et :
\[ \forall n\in\N,\ 
\left\lbrace
\begin{array}{l}
u_{n+1}=au_n+bv_n+p\\
v_{n+1}=cu_n+dv_n+q
\end{array}
\right.\qquad , \qquad (a,b,c,d,p,q)\in\R^6
\]
On pose alors :
\[
X_n=\begin{pmatrix}u_n\\v_n\end{pmatrix}\quad,\quad A=\begin{pmatrix}a & b\\c & d\end{pmatrix}\quad,\quad B=\begin{pmatrix}p\\q\end{pmatrix}\quad,\quad I_2=\begin{pmatrix}1 & 0\\0 & 1\end{pmatrix}.
\]
Alors, l'écriture matricielle du système linéaire de suites récurrentes s'écrit :
\begin{align} \forall n\in\N,\quad X_{n+1}=AX_n+B. \end{align}
De plus, si $(I_2-A)$ est inversible alors, \[C=(I_2-A)^{-1}B\] est l'unique suite constante vérifiant la relation (1) d'inconnue $X_n$.\\
Alors, pour tout entier naturel $n$, la suite $U_n=X_n-C_n$ vérifie la relation de récurrence $U_{n+1}=AU_n$ et donc : \[X_n=A^n\left(X_0-C\right)+C.\]
\end{pasbox}

\begin{pasbox}[degrade,style=demo]
\begin{itemize}
\item \textbf{Commençons d'abord par vérifier que $C$ est l'unique suite constante vérifiant la relation (1).}\\
Posons alors $X_n=C$ une suite constante dans (1) et supposons que $(I_2-A)$ est inversible :
\begin{align*}
& C=AC+B\\
\Leftrightarrow\ & I_2C-AC=B\\
\Leftrightarrow\ & (I_2-A)C=B\\
\Leftrightarrow\ & C=(I_2-A)^{-1}B.
\end{align*}
Ainsi, $C=(I_2-A)^{-1}B$ est l'unique solution à la relation (1).
\end{itemize}
\breakbox
\begin{itemize}
\item \textbf{Montrons à présent que $\pmb{U_n=X_n-C}$ vérifie la relation de récurrence $\pmb{U_{n+1}=AU_n}$.}\\
Pour cela, calculons :
\begin{align*}
U_{n+1} & = X_{n+1}-C\\
& = AX_n+B-C\\
& = AX_n+B-(AC+B)\\
& = AX_n-AC\\
& = A(X_n-C)\\
& = AU_n
\end{align*}

\medskip

\item \textbf{Montrons maintenant que $\pmb{U_n=A^nU_0}$.}\\
Pour cela, raisonnons par récurrence sur $n$.
\begin{itemize}
\item \textbf{Initialisation.}\\
Nous avons : $A^0U_0=I_2U_0=U_0$. Donc la relation est vraie au premier rang.
\item \textbf{Hérédité.}\\
Supposons la relation vraie pour un entier naturel $k$ : $U_k=A^kU_0$.\\
Alors, d'après la relation démontrée au point précédent :
\begin{align*}
A_{k+1} & = AU_k\\
& = AA^kU_0\\
& = A^{k+1}U_0
\end{align*}

L'hérédité est alors vérifiée.\\
Par conséquent, la relation de récurrence est vraie pour tout entier naturel $n$.
\end{itemize}

\medskip

\item \textbf{Montrons le résultat final.}\\
Pour tout entier naturel $n$, on a :
\begin{align*}
U_n=X_n-C_n & \Leftrightarrow  X_n=U_n+C_n\\
& = A^nU_0+(I_2-A)^{-1}B.
\end{align*}
\end{itemize}
\end{pasbox}

\begin{pasbox}[degrade,style=ex]
Considérons les deux suites \suite{u}{n}{} et \suite{v}{n}{} telles que $u_0=v_0=1$ et :
\[ \forall n\in\N,\ 
\left\lbrace
\begin{array}{l}
u_{n+1}=-8u_n-6v_n+1\\
v_{n+1}=9u_n+13v_n-1
\end{array}
\right.
\]
\breakbox
D'après la propriété précédente, 
\begin{align*}
\forall n\in\N,\quad X_n& =
\begin{pmatrix}-8 & -6\\9 &13\end{pmatrix}^n
\left[
\begin{pmatrix}1\\1\end{pmatrix}
-
\begin{pmatrix}9 & 6\\-9 & -12\end{pmatrix}^{-1}\begin{pmatrix}1\\-1\end{pmatrix}
\right]
+\begin{pmatrix}9 & 6\\-9 & -12\end{pmatrix}^{-1}\begin{pmatrix}1\\-1\end{pmatrix}
\end{align*}
\`A l'aide de XCAS, on trouve
\[ \begin{pmatrix}-8 & -6\\9 & 13\end{pmatrix}=\begin{pmatrix}
2 & -1\\-1 & 3\end{pmatrix}\begin{pmatrix}-5 & 0\\0&10\end{pmatrix}
\begin{pmatrix}\frac{3}{5} & \frac{1}{5}\\\frac{1}{5} & \frac{2}{5}\end{pmatrix}\]
et
\[
\begin{pmatrix}9 & 6\\-9 & -12\end{pmatrix}^{-1} = \begin{pmatrix}\frac{2}{9} & \frac{1}{9}\\-\frac{1}{6}&-\frac{1}{6}\end{pmatrix}.
\]
Donc,
\begin{align*}
\begin{pmatrix}1\\1\end{pmatrix}
-
\begin{pmatrix}9 & 6\\-9 & -12\end{pmatrix}^{-1}\begin{pmatrix}1\\-1\end{pmatrix} & 
= \begin{pmatrix}1-\frac{1}{9}\\1\end{pmatrix}=\begin{pmatrix}\frac{8}{9}\\1\end{pmatrix}.
\end{align*}
Ainsi,\renewcommand{\arraystretch}{1.2}
\begin{align*}
\forall n\in\N,\quad X_n& =
\begin{pmatrix}2 & -1\\-1 & 3\end{pmatrix}
\begin{pmatrix}(-5)^n & 0\\0&10^n\end{pmatrix}
\begin{pmatrix}\frac{3}{5} & \frac{1}{5}\\\frac{1}{5} & \frac{2}{5}\end{pmatrix}
\begin{pmatrix}\frac{8}{9}\\1\end{pmatrix}+ 
\begin{pmatrix}\frac{2}{9} & \frac{1}{9}\\-\frac{1}{6}&-\frac{1}{6}\end{pmatrix}
\begin{pmatrix}1\\-1\end{pmatrix}\\
& = \begin{pmatrix}2(-5)^n & -10^n\\-(-5)^n & 3\times10^n\end{pmatrix}
\begin{pmatrix}\frac{3}{5} & \frac{1}{5}\\\frac{1}{5} & \frac{2}{5}\end{pmatrix}
\begin{pmatrix}\frac{8}{9}\\1\end{pmatrix}+
\begin{pmatrix}\frac{1}{9} \\ 0\end{pmatrix}\\
& = \begin{pmatrix}\frac{6}{5}(-5)^n-\frac{1}{5}\times10^n & \frac{2}{5}(-5)^n-\frac{2}{5}\times10^n \\ -\frac{3}{5}(-5)^n+\frac{3}{5}\times10^n & -\frac{1}{5}(-5)^n + \frac{6}{5}\times10^n\end{pmatrix}
\begin{pmatrix}\frac{8}{9}\\1\end{pmatrix}+\begin{pmatrix}\frac{1}{9} \\ 0\end{pmatrix}\\
& = \begin{pmatrix}\frac{22}{5}(-5)^n-\frac{26}{45}\times10^n+\frac{1}{9}\\
-\frac{11}{15}(-5)^n+\frac{26}{15}\times10^n \end{pmatrix}
\end{align*}
On en conclut alors que :
\[
\forall n\in\N,\qquad \left\lbrace\begin{array}{l}
u_n=\frac{22}{5}(-5)^n-\frac{26}{45}\times10^n+\frac{1}{9}\\
v_n=-\frac{11}{15}(-5)^n+\frac{26}{15}\times10^n
\end{array}\right.
\]
\end{pasbox}

\begin{pasbox}[degrade,style=rem]
On pourra toujours trouver les solutions d'un système linéaire de suites récurrentes du type $X_{n+1}=AX_n+B$ si $A$ peut se mettre :
\begin{itemize}
\item soit sous la forme $A=PDP^{-1}$, où $D$ est une matrice diagonale,
\item soit sous la forme $A=aI_2+bN$, où $N=\begin{pmatrix}0 & 0\\1 & 0\end{pmatrix}$ ou  $N=\begin{pmatrix}0 & 1\\0 & 0\end{pmatrix}$.
\end{itemize}
\end{pasbox}

%------------------ Modèle d'Ehrenfest

\begin{pasbox}[degrade,style=defi,name={Modèle d'Ehrenfest}]
Considérons 2 boîtes $B_1$ et $B_2$ séparées par une paroi trouée, $B_1$ étant rempli de $N$ particules de gaz et $B_2$ étant vide.\\
\`A chaque étape, un certains nombre de particules peut passer d'une boîte à l'autre.\\
Le modèle d'Ehrenfest permet d'étudier la proportion de particules à l'étape $n$, $n$ étant un entier naturel.
\end{pasbox}

Pour se donner une idée des démarches à suivre pour modéliser la répartition des particules, prenons d'abord $N=2$.

\medskip

Alors, à chaque étape, l'une des trois répartitions suivantes uniquement est envisageable :

\begin{itemize}
\item Répartition $r_1$ : 2 particules dans $B_1$ ;
\item Répartition $r_2$ : 1 particule dans $B_1$ et $B_2$ ;
\item Répartition $r_3$ : 2 particules dans $B_2$.
\end{itemize}

Notons alors pour $i\in\entInterv{1}{3}$ :

\begin{itemize}
\item $R_i$ l'événement : \og la répartition est $r_i$ \fg{} 
\end{itemize}

En convenant de noter, pour $\coord{i}{j}\in\entInterv{1}{3}\times\entInterv{1}{3}$, $p_{ij}=\probacond{R_j}{R_i}$, on a :

\[ p_{12}=p_{32}=1 \quad;\quad p_{21}=p_{23}=\frac{1}{2}\quad;\quad p_{11}=p_{22}=p_{33}=p{13}=p{31}=0\]
D'où la matrice de transition suivante :
\[ P=\begin{pmatrix}0 & 1 & 0\\ \frac{1}{2} & 0 & \frac{1}{2}\\0 & 1 & 0\end{pmatrix}\]

Alors, en convenant de noter $V_n$ la matrice ligne représentant la répartition des particules, $V_0=\begin{pmatrix}1 & 0 & 0\end{pmatrix}$, on, a :

\[ V_1=V_0P=\begin{pmatrix}1 & 0 & 0\end{pmatrix}\begin{pmatrix}0 & 1 & 0\\ \frac{1}{2} & 0 & \frac{1}{2}\\0 & 1 & 0\end{pmatrix}=\begin{pmatrix}
0 & 1 & 0\end{pmatrix}\]
et plus généralement, 
\[ V_n=V_{n-1}P=V_0P^n\]
Ainsi,
\[ V_2=\begin{pmatrix}0 & 1 & 0\end{pmatrix}\begin{pmatrix}0 & 1 & 0\\ \frac{1}{2} & 0 & \frac{1}{2}\\0 & 1 & 0\end{pmatrix}=\begin{pmatrix}
\frac{1}{2} & 0 & \frac{1}{2}\end{pmatrix}\]
En raisonnant par récurrence, on pourrait démontrer que :
\[ \forall n\in\N*,\quad P^{2n}=P^2\qquad\text{et}\qquad P^{2n+1}=P.\]
Donc, si $k\in\N*$, $V_{2k}=\begin{pmatrix}\frac{1}{2} & 0 & \frac{1}{2}\end{pmatrix}$, ce qui signifie que la répartition est soit $r_1$, soit $r3$ pour un instant pair, et $V_{2k+1}=\begin{pmatrix}0 & 1 & 0\end{pmatrix}$, ce qui signifie que la répartition est $r_2$ pour un instant impair.

\medskip

En notant $X_n$ le nombre de particules dans la boîte $B_1$ à l'instant $n>0$, on a :

\begin{itemize}
\item Si $n=2k$, $\esp{X$_n$}=2\times\dfrac{1}{2}+1\times0+0\times\dfrac{1}{2}=1$ ;
\item Si $n=2k+1$, $\esp{X$_n$}=2\times0+1\times1+0\times0=1$.
\end{itemize}

Ceci signifie que le nombre moyen de particules dans chaque boîte tend à s'équilibrer.

\medskip

Penchons-nous maintenant sur le nombre d'étapes moyen nécessaires pour revenir à l'état initial. Notons alors $T_p$, avec $N=2p$ particules, $p\in\N*$, la variable aléatoire représentant ce nombre.\\
D'après ce qui a été fait, on peut dire :

\begin{itemize}
\item $\probavar{T_p}{1}=\probavar{T_p}{3}=0$ et pour tout entier naturel $k$, $\probavar{T_p}{2k+1}=0$ ;
\item $\probavar{T_p}{2}=\dfrac{1}{2}$, $\probavar{T_p}{4}=\dfrac{1}{4}$ et pour tout entier naturel non nul $k$, $\probavar{T_p}{2k}=\dfrac{1}{2^k}$.
\end{itemize}

L'espérance de $T_p$ est donc  :

\begin{align*}
\esp{T$_p$} & = \sum_{k=1}^{2p} k\probavar{T_p}{k}\\
& = \sum_{k=1}^p \probavar{T_p}{2k}\\
& = \sum_{k=1}^p \dfrac{k}{2^{k-1}}
\end{align*}

Posons :
\[\forall x\neq 1,\qquad f(x)=\sum_{k=1}^p x^k=\sum_{k=0}^p x^k-1.\]
Alors, 
\[ \forall x\neq1,\qquad f'(x)=\sum_{k=1}^p kx^{k-1}.\]
Or, 
\[ \sum_{k=0}^p x^k=\frac{x^{p+1}-1}{x-1} \quad \text{(penser aux suites géométriques)}\]
donc :
\[ f(x)=\frac{x^{p+1}-1}{x-1}-1\]
et :
\begin{align*}
f'(x)&=\dfrac{(p+1)x^p(x-1)-(x^{p+1}-1)}{(x-1)^2}\\
&=\dfrac{px^{p+1}-(p+1)x^p+1}{(x-1)^2}
\end{align*}
Ainsi,
\[ \sum_{k=1}^p kx^{k-1}=\dfrac{px^{p+1}-(p+1)x^p+1}{(x-1)^2}.\]
En prenant $x=\dfrac{1}{2}$, cela donne :
\[ 
\sum_{k=1}^p\dfrac{k}{2^{k-1}}=\dfrac{\frac{p}{2^{p+1}}-\frac{p+1}{2^p}+1}{\frac{1}{4}}
\]
D'où :
\[ \limite{p}{+\infty}{\esp{T$_p$}}=4,\]
ce qui signifie qu'en moyenne, 4 étapes sont nécessaires pour revenir à l'état initial.
\end{document}	