ITÉRATION, mathématique

Carte mentale

Élargissez votre recherche dans Universalis

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 étant écrit b fois).

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

La notation fn 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 : f1(x) = f(x) ; fn+1(x) = f(f n (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) = fn(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 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 x(m) tel que fk(b) = b et fj(b) ≠ b pour = 1, 2, ... k – 1.

Plus inattendu est le résultat suivant découvert au milieu du xxe siècle : si f est une fonction continue de l'intervalle [ab] 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 > 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 à = 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 somme des éléments d'une liste. La définition itérative consiste à ajouter dans une variable S les différents éléments de la liste L. En langage Maple, cela donne :

somme itérative := proc(L) local N, S, M ;

N :=0 ; S :=0 ; M :=nops(L) ;

while N < M do N :=N+1 ; S := S+L[N] ; od ;

résultat :=S ; end ;

(Le mot proc indique qu'on définit une procédure ; le mot local introduit les variables de la procédure ; le mot nops désigne la fonction qui calcule la longueur d'une liste.)

La définition récursive de la même fonction consiste à exprimer l'idée que la somme des éléments de L vaut 0 si L est la liste vide, et vaut le résultat de la somme de L[1] (le premier élément de L) et de la somme des éléments de la liste obtenue en supprimant le premier élément de L. En Maple, cela donne :

somme récursive := proc (L)

if nops(L)=0 then 0 else L[1] + somme récursive(L[2..nops(L)]) fi ; end ;

(La notation L[2..nops(L)] représente la liste L sans son premier élément.)

1  2  3  4  5
pour nos abonnés,
l’article se compose de 2 pages

Écrit par :

Classification

Autres références

«  ITÉRATION, mathématique  » est également traité dans :

BRAHMAGUPTA (598-apr. 665)

  • Écrit par 
  • Agathe KELLER
  •  • 1 168 mots
  •  • 1 média

L’astronome et mathématicien du sous-continent indien Brahmagupta nous est connu pour deux traités : le Brāhmasphu ṭ asiddhānta (« Traité théorique de la vraie école de Brahma », 628, abrégé BSS ) et un manuel plus pratique le Kha ṇḍ akādyaka (« Bouchées de douceurs », 665, abrégé KK ). Son œuvre, abondamment traduite et commentée, a largement dépassé les frontières du sous-continent indien. Com […] Lire la suite

CHAOS, physique

  • Écrit par 
  • Pierre BERGÉ, 
  • Monique DUBOIS
  •  • 3 387 mots
  •  • 6 médias

Dans le chapitre « Origine des phénomènes aléatoires »  : […] L'évolution temporelle d'un phénomène, une succession d'événements sont dites erratiques ou aléatoires si elles n'obéissent apparemment à aucune loi, à aucune régularité qui permettent de les prévoir. Dans ce sens, « aléatoire » est synonyme d'« imprédictible ». À titre d'exemple, la variation de la pression atmosphérique en un lieu donné est erratique et, de fait, imprédictible, tant il est vrai […] Lire la suite

FRACTALES

  • Écrit par 
  • Bernard PIRE
  •  • 794 mots
  •  • 2 médias

Certaines structures très irrégulières, souvent construites par itération, possèdent des symétries de dilatation caractéristiques : l'agrandissement d'une partie est semblable au tout . Le concept de fractalité unifie la description de nombreux objets mathématiques ou physiques et quantifie leur degré d'irrégularité. Il a été introduit en 1975 par Benoît Mandelbrot, mathématicien français qui a p […] Lire la suite

Pour citer l’article

Jean-Paul DELAHAYE, « ITÉRATION, mathématique », Encyclopædia Universalis [en ligne], consulté le 25 novembre 2021. URL : https://www.universalis.fr/encyclopedie/iteration-mathematique/