Suites itérées et convergence géométrique

La suite des itérées

Étant donné $f$ et un point de départ $u_0$, la suite des itérées est définie par récurrence :

$$u_{n+1} = f(u_n)$$

Si cette suite converge vers un réel $c$ et si $f$ est continue, alors en passant à la limite dans la relation de récurrence on obtient $f(c) = c$ : la limite est nécessairement un point fixe. Toute la question est donc de garantir la convergence.

Décroissance géométrique de l'erreur

Supposons $f$ $k$-contractante et admettant un point fixe $c$. En appliquant la définition au couple $\left(u_n, c\right)$, et puisque $f(c) = c$ :

$$\lvert u_{n+1} - c \rvert = \lvert f(u_n) - f(c) \rvert \leq k\,\lvert u_n - c \rvert$$

Une récurrence immédiate donne alors la majoration fondamentale :

$$\lvert u_n - c \rvert \leq k^n\,\lvert u_0 - c \rvert$$

Comme $0 \leq k < 1$, on a $k^n \to 0$, donc $u_n \to c$ : la convergence est géométrique, et elle a lieu quel que soit le point de départ.

Un exemple à suivre pas à pas

Itérons $f(x) = \cos x$ à partir de $u_0 = 0$. Le point fixe, appelé nombre de Dottie, vaut $c \approx 0{,}739085$.

$n$	$u_n$	$\lvert u_n - c \rvert$
$0$	$0$	$0{,}7391$
$2$	$0{,}540302$	$0{,}1988$
$4$	$0{,}654290$	$0{,}0848$
$6$	$0{,}701369$	$0{,}0377$
$8$	$0{,}722102$	$0{,}0170$
$10$	$0{,}731404$	$0{,}0077$

L'erreur est divisée par un peu plus de $2$ toutes les deux étapes, ce qui correspond bien à $k^2 \approx 0{,}71$ par itération de rang pair :

Estimations d'erreur utilisables

En pratique on ne connaît pas $c$, donc la majoration en $\lvert u_0 - c \rvert$ ne sert à rien telle quelle. Deux variantes se calculent, elles, à partir des seules valeurs observées :

$$\lvert u_n - c \rvert \leq \frac{k^n}{1 - k}\,\lvert u_1 - u_0 \rvert \qquad \text{et} \qquad \lvert u_n - c \rvert \leq \frac{k}{1 - k}\,\lvert u_n - u_{n-1} \rvert$$

La première, dite a priori, permet de fixer à l'avance le nombre d'itérations nécessaires ; la seconde, dite a posteriori, transforme l'écart entre deux termes consécutifs en majoration de l'erreur réelle. C'est le critère d'arrêt utilisé dans les algorithmes.

Piège classique

Croire qu'une suite définie par $u_{n+1} = f(u_n)$ converge dès que $f$ possède un point fixe. Pour $f(x) = -2x$, le point fixe est $0$, et pourtant la suite issue de $u_0 = 1$ vaut $1, -2, 4, -8, \ldots$ : elle diverge, car $\lvert f' \rvert = 2 > 1$. Le point fixe est alors dit répulsif. Seule la contraction garantit qu'il est attractif.