Les suites définies par itération : méthodes, convergence et pièges à éviter en prépa

Définitions fondamentales et premiers exemples

La suite récurrente du premier ordre

Une suite (u_n) est dite définie par récurrence du premier ordre si elle vérifie une relation de la forme u_{n+1} = f(u_n) pour tout entier n, où f est une fonction donnée et u_0 est la valeur initiale. La fonction f s'appelle la fonction d'itération. L'ensemble de définition de la suite est l'ensemble des n pour lesquels les itérés restent dans le domaine de f : si I est un intervalle stable par f, c'est-à-dire tel que f(I) est inclus dans I, et si u_0 appartient à I, alors tous les termes de la suite restent dans I. Cette notion de stabilité est fondamentale : on ne peut étudier le comportement d'une suite récurrente sans d'abord s'assurer que tous ses termes sont bien définis.

L'exemple le plus classique est la suite définie par u_{n+1} = (u_n + a/u_n) / 2 pour a positif donné et u_0 positif. C'est l'algorithme babylonien de calcul de la racine carrée de a, l'un des plus anciens algorithmes numériques connus. La fonction d'itération est f(x) = (x + a/x) / 2, et si u_0 > 0, tous les termes restent positifs car f(x) > 0 pour x > 0 par l'inégalité arithmético-géométrique. On vérifie facilement que la suite est décroissante pour n supérieur ou égal à 1 et bornée inférieurement par zéro, donc convergente, et que sa limite vérifie l = f(l), soit l = (l + a/l) / 2, ce qui donne l² = a, c'est-à-dire l = racine de a. La convergence est de plus extrêmement rapide, quadratique, ce qui signifie que le nombre de décimales correctes double à chaque itération.

Points fixes et leur rôle central

Un point fixe de la fonction f est un réel l tel que f(l) = l. Ce concept est central dans l'étude des suites itérées : si une suite u_{n+1} = f(u_n) converge vers une limite l, alors en passant à la limite dans la relation de récurrence, on obtient l = f(l), c'est-à-dire que la limite est nécessairement un point fixe de f. La recherche des points fixes de f est donc toujours la première étape de l'étude d'une suite récurrente : ce sont les seuls candidats possibles pour la limite de la suite, si elle converge.

Attention : l'existence d'un point fixe ne garantit pas la convergence de la suite vers ce point fixe. Tout dépend de la valeur initiale et de la nature du point fixe (attracteur ou répulseur). Un point fixe l est dit attracteur si pour des valeurs initiales proches de l, la suite converge vers l. Il est dit répulseur si pour des valeurs initiales proches de l, la suite s'en éloigne. Le critère qui gouverne cette distinction est la valeur de |f'(l)| : si |f'(l)| est strictement inférieur à 1, le point fixe est attracteur ; si |f'(l)| est strictement supérieur à 1, il est répulseur. C'est l'un des résultats les plus importants et les plus utiles du chapitre.

L'étude graphique : la toile d'araignée

Construire et interpréter le graphe de la toile

L'étude graphique des suites itérées repose sur une représentation appelée diagramme de la toile d'araignée ou escalier de Feigenbaum, qui permet de visualiser le comportement qualitatif de la suite sans effectuer de calculs. Le principe est le suivant : on trace dans un repère la courbe représentative de f et la droite y = x (la première bissectrice). Les points d'intersection de ces deux courbes sont précisément les points fixes de f. On construit alors la suite géométriquement en partant de u_0 sur l'axe des abscisses, en montant verticalement jusqu'à la courbe de f pour atteindre le point (u_0, f(u_0)) = (u_0, u_1), puis en se déplaçant horizontalement jusqu'à la droite y = x pour atteindre le point (u_1, u_1), puis à nouveau verticalement jusqu'à la courbe, et ainsi de suite.

Ce procédé graphique permet de distinguer immédiatement plusieurs types de comportements. Si la courbe de f est moins inclinée que la droite y = x au voisinage du point fixe (c'est-à-dire si |f'(l)| < 1), la toile converge en spirale vers le point fixe : la suite converge. Si la courbe est plus inclinée (|f'(l)| > 1), la toile s'échappe du point fixe : la suite diverge localement. Si la courbe coupe la première bissectrice avec une pente négative de valeur absolue inférieure à 1 (c'est-à-dire -1 < f'(l) < 0), la toile prend la forme d'une spirale convergente qui alterne de part et d'autre du point fixe : la suite converge en oscillant. Cette visualisation est extrêmement puissante pour anticiper la nature du comportement avant tout calcul.

Les cas de convergence monotone et oscillante

Quand f'(l) est positif et inférieur à 1, la suite converge de façon monotone vers l : tous les termes restent du même côté du point fixe, soit tous supérieurs, soit tous inférieurs, et la suite est monotone. Le graphe de la toile prend alors la forme d'un escalier qui monte ou descend en se rapprochant du point fixe. C'est le cas le plus simple à analyser et à démontrer rigoureusement, car on peut souvent montrer que la suite est à la fois monotone et bornée par le point fixe, ce qui suffit pour conclure à la convergence par le théorème des suites monotones bornées.

Quand f'(l) est négatif et supérieur à -1 en valeur absolue (c'est-à-dire -1 < f'(l) < 0), la suite converge en oscillant autour du point fixe, alternant entre des valeurs au-dessus et en dessous de l. Ce cas est plus délicat à traiter rigoureusement, car la suite n'est plus monotone. Une stratégie efficace consiste alors à étudier la suite des termes pairs (u_{2n}) et la suite des termes impairs (u_{2n+1}) séparément, en remarquant que u_{n+2} = f(f(u_n)) = g(u_n) où g = f composé avec f est la composée de f avec elle-même. Les suites (u_{2n}) et (u_{2n+1}) vérifient une nouvelle relation de récurrence avec la fonction g, et elles peuvent être monotones, ce qui permet d'appliquer les théorèmes habituels.

Les théorèmes fondamentaux de convergence

Le théorème du point fixe de Banach

Le théorème du point fixe de Banach, aussi appelé théorème de l'application contractante, est l'un des résultats les plus puissants et les plus utiles pour étudier les suites itérées. Il affirme que si f est une application de [a, b] dans [a, b] (c'est-à-dire que f est stable sur l'intervalle [a, b]) et si f est k-lipschitzienne sur [a, b] avec k strictement inférieur à 1 (c'est-à-dire qu'il existe k dans [0, 1[ tel que |f(x) - f(y)| est inférieur ou égal à k|x - y| pour tous x, y dans [a, b]), alors f admet un unique point fixe l dans [a, b] et la suite définie par u_{n+1} = f(u_n) converge vers l pour toute valeur initiale u_0 dans [a, b].

Ce théorème fournit en outre une majoration de l'erreur à l'étape n : |u_n - l| est inférieur ou égal à k^n / (1 - k) * |u_1 - u_0|. Cette majoration est précieuse en pratique car elle permet de quantifier la précision de l'approximation numérique obtenue après n itérations. En concours, le théorème de Banach est souvent mobilisé pour justifier l'existence et l'unicité d'un point fixe et la convergence de la suite, en vérifiant que f est bien contractante sur un intervalle stable. La vérification de la propriété contractante passe souvent par la majoration de |f'|, car si f est dérivable sur [a, b] avec |f'| majoré par k < 1, alors f est k-lipschitzienne sur [a, b] par le théorème des accroissements finis.

Utiliser le théorème des accroissements finis dans les suites itérées

Le théorème des accroissements finis est un outil récurrent dans l'étude des suites récurrentes, souvent utilisé pour majorer la distance entre deux termes consécutifs ou entre un terme et le point fixe. Si l est un point fixe de f et si f est dérivable sur un intervalle contenant l et u_n, on a : |u_{n+1} - l| = |f(u_n) - f(l)| est inférieur ou égal à sup|f'| * |u_n - l|, où la borne supérieure de |f'| est prise sur l'intervalle entre u_n et l.

Si l'on peut montrer que sup|f'| est inférieur à un certain k < 1 sur un intervalle contenant tous les termes de la suite, on en déduit que |u_n - l| est inférieur ou égal à k^n * |u_0 - l|, ce qui établit la convergence de la suite vers l et donne une vitesse de convergence géométrique de raison k. C'est une méthode très efficace pour les suites où f est dérivable et de dérivée contrôlable. En pratique, l'exercice consiste souvent à montrer d'abord que la suite reste dans un certain intervalle (par récurrence), puis à majorer |f'| sur cet intervalle pour conclure.

Suites monotones et convergence par encadrement

Lorsque la suite est monotone et bornée, le théorème des suites monotones bornées garantit la convergence sans qu'il soit nécessaire de faire appel au théorème de Banach. La démonstration de la monotonie par récurrence est souvent le coeur de l'argument : on montre que u_{n+1} supérieur ou égal à u_n (ou l'inégalité inverse) est vraie pour tout n en supposant qu'elle l'est pour un certain n et en utilisant la relation de récurrence et les propriétés de f (notamment sa monotonie). La démonstration de la borne procède de même par récurrence : on montre que u_n reste dans un intervalle [a, b] pour tout n.

Une fois la convergence établie, la limite l vérifie l = f(l), ce qui permet de la calculer en résolvant cette équation de point fixe. Si l'équation admet plusieurs solutions, il faut utiliser les informations sur la monotonie et les bornes de la suite pour identifier laquelle est la limite. Par exemple, si la suite est croissante et bornée supérieurement par b, et si f admet deux points fixes l_1 < l_2 = b, la limite est nécessairement l_1 (la suite, étant croissante et bornée par b, converge vers le plus petit point fixe accessible depuis u_0).

Les méthodes numériques d'itération : applications concrètes

La méthode de Newton-Raphson

La méthode de Newton-Raphson est l'exemple le plus célèbre et le plus utilisé de méthode itérative pour résoudre une équation f(x) = 0. Le principe est le suivant : partant d'une valeur initiale x_0 proche d'un zéro de f, on approxime la courbe de f par sa tangente en x_0 et on prend le zéro de cette tangente comme nouvelle approximation x_1. La tangente à la courbe de f en (x_0, f(x_0)) a pour équation y - f(x_0) = f'(x_0)(x - x_0) et s'annule en x = x_0 - f(x_0) / f'(x_0). On obtient ainsi la relation de récurrence x_{n+1} = x_n - f(x_n) / f'(x_n), ce qui définit bien une suite itérée de fonction d'itération g(x) = x - f(x) / f'(x).

La méthode de Newton présente une propriété remarquable : sa convergence est quadratique au voisinage d'un zéro simple de f, c'est-à-dire que l'erreur est essentiellement élevée au carré à chaque étape. Si e_n = |x_n - l| désigne l'erreur à l'étape n, on montre que e_{n+1} est de l'ordre de e_n² : le nombre de décimales correctes double à chaque itération. Cette propriété explique la popularité de la méthode dans les applications numériques. En concours, la méthode de Newton est souvent présentée comme la suite itérée associée à une fonction g donnée, et l'on demande d'identifier la fonction f dont on cherche un zéro, de montrer la convergence par le critère de contraction, et d'estimer le nombre d'itérations nécessaires pour atteindre une précision donnée.

Les méthodes de point fixe en général

De nombreuses équations de la forme f(x) = 0 peuvent être réécrites sous la forme x = g(x) pour une fonction g bien choisie, et la méthode de point fixe consiste à itérer la fonction g pour approcher la solution. Il y a souvent plusieurs façons de réécrire l'équation sous cette forme, et le choix de g détermine la vitesse et même la réussite de la convergence. Par exemple, pour résoudre x³ - x - 1 = 0, on peut réécrire l'équation comme x = x³ - 1 (méthode g_1(x) = x³ - 1), comme x = (x + 1)^{1/3} (méthode g_2(x) = (x+1)^{1/3}), ou encore comme x = 1 / (x² - 1) (si cela a un sens). Toutes ces méthodes ont la même racine comme point fixe, mais leurs propriétés de convergence sont radicalement différentes selon la valeur de |g'| au voisinage de la racine.

C'est précisément le critère |g'(l)| < 1 qui détermine si la méthode converge localement. Pour l'exemple ci-dessus, la racine réelle de x³ - x - 1 = 0 est environ 1,3247. On calcule g_1'(x) = 3x², donc g_1'(1,3247) est environ 5,26 : la méthode g_1 diverge. En revanche, g_2'(x) = (1/3)(x+1)^{-2/3}, donc g_2'(1,3247) est environ 0,16 : la méthode g_2 converge rapidement. Ce type d'analyse comparative entre différentes méthodes itératives est un exercice classique de concours.

Les erreurs classiques et les pièges des concours

Conclure à la convergence sans vérifier la stabilité

L'erreur la plus fréquente dans l'étude des suites récurrentes est de supposer implicitement que tous les termes de la suite sont bien définis et restent dans un domaine convenable, sans le vérifier. Si la fonction f n'est pas définie sur tout R, ou si elle peut envoyer certains points hors de son domaine de définition, il faut impérativement montrer par récurrence que tous les u_n appartiennent bien à un intervalle sur lequel f est définie et stable. Sauter cette étape conduit à des raisonnements faux, même si la conclusion finale se trouve être correcte par chance.

Par exemple, pour la suite définie par u_{n+1} = 1 / (2 - u_n) avec u_0 = 0, la fonction f(x) = 1 / (2 - x) n'est pas définie en x = 2. Il faut d'abord montrer que u_n est inférieur à 2 pour tout n (par récurrence : si u_n < 2 alors u_{n+1} = 1/(2 - u_n) > 0, et on doit aussi borner u_n par dessus pour rester loin de 2), puis seulement ensuite étudier la monotonie et la convergence.

Oublier de vérifier les hypothèses des théorèmes

Le théorème de Banach exige que f soit définie de I dans I (stabilité), et que f soit contractante sur I avec une constante de contraction k strictement inférieure à 1. L'oubli d'une seule de ces conditions invalide le théorème. En particulier, une fonction peut être contractante en un point (au sens où |f'(l)| < 1) sans être contractante sur tout un intervalle (la constante de contraction globale doit être strictement inférieure à 1, pas seulement localement). Les concours testent précisément cette distinction en proposant des exemples où la contraction locale ne suffit pas.

De même, le théorème des suites monotones bornées exige que la suite soit à la fois monotone et bornée : il faut montrer les deux propriétés séparément et rigoureusement. Dire simplement que la suite est décroissante et positive suffit à conclure à la convergence, mais il faut avoir vraiment montré ces deux points, et non simplement les supposer à partir du comportement de la suite pour les premières valeurs.

Confondre la limite de la suite et le point fixe de f

Si la suite converge, sa limite est un point fixe de f. Mais la réciproque est fausse : un point fixe de f n'est pas nécessairement la limite de la suite. Il peut exister plusieurs points fixes, et la limite dépend de la valeur initiale u_0. Il peut aussi arriver qu'un point fixe soit répulseur : la suite converge vers le point fixe seulement si elle part exactement de ce point, ce qui est une situation dégénérée sans intérêt pratique. Dans un sujet de concours, dès qu'il existe plusieurs points fixes, il faut identifier lequel est la limite de la suite en utilisant les propriétés de monotonie, les bornes de la suite, ou le critère |f'(l)| < 1 pour déterminer lequel est attracteur.

Négliger la vitesse de convergence

Les sujets de concours demandent souvent d'estimer le nombre d'itérations nécessaires pour approcher la limite avec une précision donnée (par exemple, à 10^{-6} près). C'est une question qui mobilise la majoration de l'erreur fournie par le théorème de Banach : |u_n - l| est inférieur ou égal à k^n / (1-k) * |u_1 - u_0|. Pour trouver le nombre minimum d'itérations, on résout l'inégalité k^n * C inférieur à epsilon, ce qui donne n supérieur ou égal à log(epsilon/C) / log(k). Cette manipulation des inégalités logarithmiques est souvent mal maîtrisée et source d'erreurs de signe ou de direction d'inégalité.

Méthode complète pour traiter une suite itérée en concours

Les étapes incontournables

Face à une suite définie par u_{n+1} = f(u_n), voici la démarche à suivre sans exception. La première étape est d'identifier le domaine de définition de f et de montrer qu'il existe un intervalle I, stable par f, contenant u_0. Cette étape se fait le plus souvent par récurrence : on montre que si u_n appartient à I alors u_{n+1} = f(u_n) appartient aussi à I. Cela garantit que tous les termes de la suite sont bien définis.

La deuxième étape est de chercher les points fixes de f, c'est-à-dire de résoudre l'équation f(l) = l. Ce sont les seuls candidats possibles pour la limite. La troisième étape est d'étudier la monotonie de la suite. On étudie le signe de u_{n+1} - u_n = f(u_n) - u_n en fonction de la position de u_n par rapport aux points fixes et aux éventuels points où f(x) - x change de signe. Si la fonction x -> f(x) - x est de signe constant sur I, la suite est monotone sur I. La quatrième étape est de conclure à la convergence : si la suite est monotone et bornée, elle converge. Sinon, on peut utiliser le théorème de Banach si f est contractante, ou étudier les suites de rangs pairs et impairs séparément.

La cinquième étape est d'identifier la limite parmi les points fixes, en utilisant les propriétés de monotonie et de bornes établies précédemment. La sixième étape, souvent oubliée, est d'étudier la vitesse de convergence si le sujet le demande, en utilisant la majoration fournie par le théorème des accroissements finis ou le théorème de Banach.

Un exemple complet traité pas à pas

Traitons l'exemple f(x) = (x² + 2) / (2x) = x/2 + 1/x pour x > 0, et u_0 = 2. La fonction f est définie et strictement positive pour tout x > 0. Montrons que u_n > 0 pour tout n par récurrence : u_0 = 2 > 0, et si u_n> 0 alors u_{n+1} = u_n/2 + 1/u_n > 0. Donc la suite est bien définie et positive.

Points fixes : f(l) = l donne l/2 + 1/l = l, soit 1/l = l/2, soit l² = 2, soit l = racine de 2 (en prenant la racine positive puisque l > 0). Il y a un unique point fixe positif.

Monotonie : u_{n+1} - u_n = u_n/2 + 1/u_n - u_n = 1/u_n - u_n/2 = (2 - u_n²) / (2u_n). Ce signe est celui de 2 - u_n² : positif si u_n < racine de 2, négatif si u_n > racine de 2. Montrons par récurrence que u_n est supérieur ou égal à racine de 2 pour tout n supérieur ou égal à 1 : par l'inégalité arithmético-géométrique, u_{n+1} = u_n/2 + 1/u_n est supérieur ou égal à la racine de 2 * (1/u_n), ce qui donne u_{n+1} supérieur ou égal à racine de 2 dès que u_n > 0, en fait u_{n+1} = (u_n/2 + 1/u_n) est supérieur ou égal à racine de (u_n/2 * 1/u_n * 4) = racine de 2 par AM-GM. Donc u_n est supérieur ou égal à racine de 2 pour n supérieur ou égal à 1, ce qui implique que la suite est décroissante pour n supérieur ou égal à 1 et bornée inférieurement par racine de 2. La suite converge donc vers un point fixe, qui est racine de 2.