Fonction itérée

En mathématiques, une fonction itérée est une fonction obtenue par composition répétée d’une autre fonction avec elle-même un certain nombre de fois. La procédure consistant à appliquer la même fonction à plusieurs reprises s’appelle itération. Les fonctions itérées apparaissent en informatique, dans les systèmes dynamiques, les groupes de renormalisation et sont à la base des fractales. L’itérée, plus précisément la deuxième itérée, d’une fonction f , définie sur un ensemble X et à valeurs dans ce même ensemble X, est la fonction où note la composition de fonctions. Autrement dit, pour tout élément x de X Plus généralement, n étant un entier positif ou nul, la n-ième itérée d’une fonction f , définie sur un ensemble X et à valeurs dans ce même ensemble X, se définit par récurrence via la relation Par convention, pour n = 0, , où est la fonction identité sur X. La notation peut être ambiguë, car elle est employée non seulement pour l’itération, mais aussi pour l’élévation à la puissance. Pour cette raison, certains mathématiciens notent la n-ième itération d’une fonction f. Les identités suivantes sont vérifiées pour tous les entiers positifs ou nuls m et n : Pour un élément x de X, la suite des valeurs est l’orbite de x. Si pour un entier m non nul, on a alors (pour tout n), l’orbite est dite périodique et le plus petit entier m pour un x donné est la période de l’orbite correspondante ; le point x lui-même est un point dit périodique. En informatique, le problème de détection de cycles est le problème algorithmique qui consiste à trouver le premier point périodique d’une orbite et la période de l’orbite. Si f(x) = x pour un élément x de X (autrement dit, la période de l’orbite de x est 1), alors x est un point fixe de la suite itérée. L’ensemble des points fixes se note Fix(f). Divers théorèmes garantissent l’existence de points fixes dans certaines situations, comme le théorème du point fixe de Banach ou le théorème du point fixe de Brouwer. Plusieurs techniques permettent par ailleurs d’accélérer la convergence des suites produites par l’itération de points fixes.