ITÉRATION, mathématique

Itérer signifie recommencer, faire à nouveau. Construire les nombres entiers peut être vu comme l'opération consistant à partir de zéro à itérer indéfiniment l'ajout d'une unité.

Plus généralement, en mathématiques, lorsqu'une fonction ou opération est disponible, il est fréquent d'en envisager l'itération, celle-ci conduisant soit à de nouvelles fonctions ou opérations, soit à des structures ou propriétés intéressantes.

La multiplication est le résultat de l'application itérée de l'addition : a.b = a + a + ... + a (a étant écrit b fois).

L'exponentiation est le résultat de l'application itérée de la multiplication : a^b = a × a × a × ... × a (a étant écrit b fois).

La notation fⁿ est souvent utilisée pour noter l'itération n fois d'une fonction f (ayant même ensemble de départ et d'arrivée), c'est-à-dire la composée n fois de suite de f avec elle-même : f¹(x) = f(x) ; fⁿ⁺¹(x) = f(f ⁿ(x)).

Une fonction f étant donnée, ainsi qu'un point de départ x(0), on définit la suite des itérées de x(0) par f, en posant pour tout entier n : x(n+1) = f(x(n)), ou, ce qui revient au même, en posant pour tout entier n : x(n) = fⁿ(x(0)). Il s'agit d'un cas particulier des suites définies par relations de récurrence.

L'étude de l'itération des fonctions et des suites itérées est pleine de surprises. Sous certaines conditions (par exemple : f de ℝ dans ℝ et continue, x(n) bornée, monotone) la suite x(n) converge vers une valeur limite a telle que a = f(a) (a est appelée point fixe de f). Le plus souvent cependant la suite x(n) aura un comportement plus complexe. Dans le cas où f est une application d'un ensemble fini dans lui-même, pour tout x(0), la suite x(n) aboutit sur un cycle de f, c'est-à-dire sur un point b = x(m) tel que f^k(b) = b et f^j(b) ≠ b pour j = 1, 2, ... k – 1.

Plus inattendu est le résultat suivant découvert au milieu du xx^e siècle : si f est une fonction continue de l'intervalle[a, b]dans lui-même (a et b étant deux nombres réels) et possède un cycle d'ordre 3, alors elle possède un cycle d'ordre n pour tout entier n > 1.

En algorithmique et en informatique, l'itération est une structure de contrôle essentielle offerte sous des formes diverses par tous les langages de programmation évolués et permettant de demander à un programme d'opérer un traitement répétitif sur les données.

Pour trouver le plus grand commun diviseur (pgcd) de deux nombres entiers A et B, la méthode la plus élémentaire consiste à itérer l'opération suivante tant que les deux nombres sont différents : soustraire le plus petit nombre du plus grand. Le pgcd de A et B est le nombre obtenu quand on s'arrête. Partant de (24 ; 18) l'itération donne (6 ; 18), (6 ; 12), (6 ; 6) ; le pgcd de 24 et 18 est donc 6.

Dans le langage de programmation Maple (largement utilisé en mathématiques), cette idée se transcrit de façon immédiate sous la forme :

while A<> do if A>B then A :=A-B else B :=B-A fi ; od ; résultat :=A ;

(fi repère la fin de l'instruction if... then... else ; od désigne la fin de l'action commencée par do).

On oppose programmation itérative et programmation récursive. Ce sont deux façons de concevoir la définition de certaines fonctions ou procédures. La première est bien sûr fondée sur l'idée d'itération. La seconde se fonde sur l'idée plus subtile qu'il suffit de décrire, premièrement le cas initial (le point de départ correspondant souvent à n = 0), secondement la façon de ramener le cas général à un cas plus simple. Les premiers langages de programmation ne permettaient pas les définitions récursives, mais aujourd'hui tous le prévoient.

Considérons l'exemple du calcul de la[...]