Dichotomies

Comme application de la proposition 2 (deux suites adjacentes convergent vers la même limite), nous présentons sur deux exemples une technique d'encadrement très efficace, la dichotomie (action de partager en deux). Le premier exemple est un résultat d'existence de point fixe.

Proposition 6   Soit $f$ une application continue de l'intervalle $[0,1]$ dans lui-même. Alors $f$ admet un point fixe :

$$\exists a\in [0,1]\;,\quad f(a)=a\;.$$

Démonstration : La démonstration que nous proposons est constructive : on peut la transformer en un algorithme pour calculer une valeur approchée du point fixe. Posons $u_0=0$ et $v_0=1$. Si $f(u_0)=u_0$, ou si $f(v_0)=v_0$, inutile d'aller plus loin, on a trouvé un point fixe. Sinon, on a forcément $f(0)>0$ et $f(1)<1$. Examinons le point $1/2$ : si $f(1/2)=1/2$, le point fixe est trouvé. Si $f(1/2)>1/2$, on pose $u_1=1/2$ et $v_1=v_0$. Si $f(1/2)<1/2$, on pose $u_1=u_0$ et $v_1=1/2$. On itère ensuite la construction. Supposons que $u_n$ et $v_n$ ont été construits de sorte que $f(u_n)>u_n$ et $f(v_n)<v_n$. On examine le point $x=(u_n+v_n)/2$ : si $f(x)=x$, le point fixe est trouvé. Si $f(x)>x$, on pose $u_{n+1}=x$ et $v_{n+1}=v_n$. Si $f(x)<x$, on pose $u_{n+1}=u_n$ et $v_{n+1}=x$. Plaçons nous dans le cas où la procédure se prolonge jusqu'à l'infini (on ne trouve jamais de point fixe). Vu la manière dont elles ont été construites, les suites $(u_n)$ et $(v_n)$ sont adjacentes : $(u_n)$ est croissante, $(v_n)$ est décroissante et $v_n-u_n=2^{-n}$. Donc elles convergent vers la même limite $a$. Comme $f$ est continue les suites $(f(u_n))$ et $(f(v_n))$ convergent vers $f(a)$. Par construction, $f(u_n)>u_n$, donc $f(a)\geqslant a$. De même, $f(v_n)<v_n$, donc $f(a)\leqslant a$. Donc $f(a)=a$ : $a$ est bien un point fixe.$\square$

Voici un résultat beaucoup plus important, démontré également par dichotomie : le théorème de Bolzano-Weierstrass.

Théorème 10   De toute suite bornée, on peut extraire une sous-suite convergente.

Démonstration : Soit $m$ un minorant et $M$ un majorant de la suite $(u_n)$ :

$$\forall n\in \mathbb{N}\;,\quad m\leqslant u_n\leqslant M\;.$$

Posons $a_0=m$ et $b_0=M$, et $\varphi(0)=0$. Divisons l'intervalle $[a_0,b_0]$ en deux, et considérons les deux moitiés : l'une au moins contient une infinité de termes de la suite $(u_n)$. Supposons que $[a_0,\frac{a_0+b_0}{2}]$ contienne une infinité de termes de la suite. On note $a_1=a_0$, $b_1=\frac{a_0+b_0}{2}$, et $\phi(1)>0$ un entier tel que $u_{\phi(1)}\in [a_1,b_1]$. Si la première moitié ne contient qu'un nombre fini de termes, on la remplace par l'autre moitié $[\frac{a_0+b_0}{2},b_0]$. On itère ensuite le procédé, de manière à construire des intervalles emboîtés $[a_k,b_k]$, de longueur $(M-m)/2^k$, et des valeurs extraites $u_{\phi(k)}\in [a_k,b_k]$. Les suites $(a_k)$ et $(b_k)$ sont adjacentes par construction, donc elles convergent vers la même limite. Par le théorème des gendarmes (corollaire 1) la suite $(u_{\varphi(k)})$ converge vers la même limite que $(a_n)$ et $(b_n)$. $\square$