# Les suites et séries/Les suites récurrentes k-contractantes

Il existe quelques cas particuliers de fonctions pour lesquelles on peut prouver qu'une suite récurrente associée converge systématiquement. Un cas particulier bien connu, souvent introduit dans les cours de mathématiques du supérieur, est celui des fonctions dites K-contractantes.
* Les fonctions K-contractantes sont celles qui respectent la propriété suivante :
* Une fonction est dite K-contractante si, pour tout x et tout y :
* $|f(x)-f(y)|\leq K\cdot |x-y|$, avec $K\in [0,1[$.
* On peut réécrire la formule précédente comme suit :
* ${\frac {|f(x)-f(y)|}{|x-y|}}\leq K$
* Cette formule ressemble à s'y méprendre à la formule d'une dérivée, et nous verrons que ce n'est pas un hasard : diverses propriétés impliquant la dérivée de f sont liées au caractère K-contractant de la fonction. Tel est le cas du théorème suivant :
* Prenons une fonction f dérivable sur un intervalle I. Si $\max _{x\in I}{|f'(x)|}=K<1$, alors la fonction f est strictement contractante sur l'intervalle I.

## Le théorème du point fixe de Picard et Banach

Cette propriété implique, sous certaines conditions, que la suite récurrente associée à f converge. Ces conditions sont les suivantes :
* f est K-contractante.
* I est un intervalle stable par f.
* f admet un unique point fixe $x_{0}$.
    On peut démontrer que les deux premières conditions impliquent la troisième, mais cette démonstration aurait plus sa place dans un cours sur les fonctions que dans un cours sur les suites, aussi nous la mettons de côté pour le moment.
Si ces conditions sont remplies, la suite récurrente associée à f converge vers le point fixe $x_{0}$. Ce résultat est un théorème qui porte le doux nom de Théorème du point fixe de Picard et Banach. Le démontrer est assez aisé et demande de procéder comme indiqué plus haut : d'abord on prouve que la suite associée converge, avant de montrer que le point fixe est bien celui qui sert de limite. Ici, nous allons procéder dans l'ordre inverse : nous allons d'abord démontrer que le point fixe en question est unique, avant de montrer que la suite associée converge. La raison à cela est que la démonstration de l'unicité du point fixe est particulièrement simple : c'est un simple raisonnement par l'absurde qui ne demande que quelques manipulations algébriques triviales. Par contre, démontrer que la suite converge vers le point fixe est plus compliqué et demande un raisonnement mathématique à plusieurs étapes assez longues.

### Démonstration de l'unicité de la limite

Commençons par démontrer l'unicité par l'absurde.
* Démonstration
* Supposons que la fonction accepte deux points fixes différents nommés $x_{0}$ et $x_{1}$. Par définition, on a :
* $x_{0}=f(x_{0})$
* $x_{1}=f(x_{1})$
* En soustrayant les deux équations, on trouve alors :
* $|x_{0}-x_{1}|=|f(x_{0})-f(x_{1})|$
* Dire que f est K-contractante signifie, par définition, que $|f(x_{0})-f(x_{1})|\leq K\cdot |x_{0}-x_{1}|$, ce qui donne :
* $|x_{0}-x_{1}|\leq K\cdot |x_{0}-x_{1}|$
* Et vu que, d'après l'énoncé, $K\in [0,1[\implies K<1$, on a :
* $|x_{0}-x_{1}|<|x_{0}-x_{1}|$
* Ce qui est absurde.

### Démonstration de la convergence de la suite

Il existe deux démonstrations différentes du fait que la suite converge.
* Démonstration
* Une première démonstration montre que la suite est une suite de Cauchy, à savoir une suite telle que $\lim _{(p,q)\rightarrow \infty }u_{n}-u_{p}=0$, qui converge donc forcément (dans R ou C, du moins).
* Du fait que la fonction g est K-contractante, on a immédiatement:
* $|u_{n+1}-u_{n}|\leq |g(u_{n})-g(u_{n-1})|\leq K\left[|g(u_{n-1})-g(u_{n-2})|\right]\leq ...\leq K^{n}\left[|g(u_{1})-g(u_{0})|\right]$
* On a aussi, par définition :
* $u_{n}-u_{p}=(u_{n}-u_{n-1})-(u_{n-1}-u_{n-2})-(u_{n-2}-u_{n-3})-...-(u_{1}-u_{0})$
* En combinant les deux équations précédentes, on a :
* $|u_{n}-u_{p}|\leq \sum _{0}^{n-1}K^{n+1}(|u_{1}-u_{0}|)\leq {\frac {K^{n}}{1-K}}(|u_{1}-u_{0}|)$
* En prenant la limite vers l'infini de l'expression précédente, on trouve bien que :
* $\lim _{(p,q)\rightarrow \infty }|u_{n}-u_{p}|=0$
* Démonstration
* Une autre démonstration utilise le théorème de Boltzano-Weistrass.
* La suite est bornée :
* En premier lieu, la démonstration prouve que la suite K-contractante est bornée.
* En effet, on a :
* $|u_{n+1}-u_{n}|=|f(u_{n})-f(u_{n-1})|<K\cdot |f(u_{n-1})-f(u_{n-2})|<K^{2}\cdot |f(u_{n-2})-f(u_{n-3})|<K^{3}\cdot |f(u_{n-3})-f(u_{n-4})|<...<K^{n}\cdot |f(u_{1})-f(u_{0})|$
* On peut alors démontrer que :
* $|u_{n}-u_{0}|<{\frac {1-K^{n}}{1-K}}\cdot |u_{1}-u_{0}|$
* Vu que $K\in {[0,1]}$, on a :
* $|u_{n}-u_{0}|<{\frac {1-K^{n}}{1-K}}\cdot |u_{1}-u_{0}|<{\frac {1}{1-K}}\cdot |u_{1}-u_{0}|$
* Inégalité qu'on peut reformuler comme suit :
* $-{\frac {1}{1-K}}\cdot |u_{1}-u_{0}|\leq |u_{n}-u_{0}|\leq {\frac {1}{1-K}}\cdot |u_{1}-u_{0}|$
* Les termes de la suite $(u_{n})$ sont donc bornés dans l'intervalle :
* $\left[u_{0}-{\frac {|u_{1}-u_{0}|}{1-K}},u_{0}+{\frac {|u_{1}-u_{0}|}{1-K}}\right]$
* Application de Boltzano-Weirstrass :
* Vu que la suite est bornée, on peut en extraire une suite convergente, que l'on notera $u_{\Sigma (n)}$.
* Sa limite sera notée L dans ce qui suit.
* Prouver que $L$ est un point fixe de f :
* Il faut ensuite prouver que L est un point fixe de f, ce qui est fait par le développement suivant.
* On sait que, par définition de la limite L :
* $\lim _{n\rightarrow \infty }|u_{\Sigma (n)}-L|\rightarrow 0$
* On a alors :
* $|f(L)-L|=|f(L)-f(u_{\Sigma (n)})+f(u_{\Sigma (n)})-u_{\Sigma (n)}+u_{\Sigma (n)}-L|$
* $|f(L)-L|\leq |f(L)-f\left(u_{\Sigma (n)}\right)|+|f\left(u_{\Sigma (n)}\right)-u_{\Sigma (n)}|+|u_{\Sigma (n)}-L|$
* $|f(L)-L|\leq K\cdot |L-\left(u_{\Sigma (n)}\right)|+|u_{\Sigma (n)+1}-u_{\Sigma (n)}|+|u_{\Sigma (n)}-L|$
* $|f(L)-L|\leq (K+1)\cdot |\left(u_{\Sigma (n)}\right)-L|+K^{\Sigma (n)+1}|u_{1}-u_{0}|$
* On a alors :
* $\lim _{n\rightarrow \infty }u_{\Sigma (n)}\rightarrow 0$
* $\lim _{n\rightarrow \infty }K^{\Sigma (n)}\rightarrow 0$
* Le second terme tend donc vers zéro, ce qui donne :
* $|f(L)-L|\leq 0$
* En clair, on la limite L est bien un point fixe de la fonction f.
* Prouver que $L$ est la limite de $u_{\Sigma (n)}$ :
* Enfin, il reste à prouver que :
* $|u_{n}-L|\leq K^{n}\cdot |u_{0}-L|$
* La démonstration est une simple démonstration par récurrence.
* Pour n = 1, la propriété est évidente.
* $|u_{1}-L|=|f(u_{0})-f(L)|\leq K\cdot |u_{0}-L|$
* Ensuite, il reste à prouver que si la propriété est vraie pour n, elle l'est aussi pour n+1 :
* $|u_{n+1}-L|=|f(u_{n})-f(L)|\leq K\cdot |u_{n}-L|\leq K\times K^{n}|u_{0}-L|=K^{n+1}|u_{n}-L|$