Fonction itérée

Modèle:Confusion Modèle:À recycler En mathématiques, une fonction itérée est une fonction obtenue par composition répétée d’une fonction de départ donnée avec elle-même un certain nombre de fois.

On dit encore que la fonction est obtenue par itération de la fonction de départ, ou que l'on a itérer cette fonction. 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, sont à la base des fractales…

Définition, conventions, énonciations

La fonction Modèle:Mvar à itérer est supposée définie définie sur un ensemble Modèle:Mvar et à valeurs dans ce même ensemble Modèle:Mvar. La composition de fonctions se note « ○ » et, par définition, pour Modèle:Math :

$(f\circ f)(x)=f(f(x))$

c'est-à-dire que cette valeur est obtenue en itérant deux fois Modèle:Mvar sur Modèle:Mvar. La fonction Modèle:Mvar est la fonction Modèle:Mvar itérée Modèle:Nobr et se note également :

$f\circ f=f^2.$

Plus généralement, n étant un entier positif ou nul, la n-ième itérée de Modèle:Mvar, se définit par récurrence par :

$f^0={\mathrm{id}}_X;f^{n+1}=f\circ f^n(n\in \mathbb{N}).$

où ${\mathrm{id}}_X$ est la fonction identité sur Modèle:Mvar. Ainsi :

$f^0={\mathrm{id}}_X;f^1=f;f^2=f\circ f;f^3=f\circ f\circ f;\dots$

(l'opération de composition est associative, il est inutile de parenthéser).

La notation Modèle:Mvar peut être ambiguë, car elle est parfois aussi employée pour l’élévation à la puissance, en particulier en trigonométrie. Ainsi l'identité trigonométrique fondamentale :

${\cos }^{2}x+{\sin }^{2}x=1$

s'interprète par :

$(\cos x{)}^2+(\sin x{)}^2=1.$

Le contexte doit permettre de lever l'ambiguïté.

Suites d’itération

Les identités suivantes sont vérifiées pour tous les entiers positifs ou nuls Modèle:Mvar et Modèle:Mvar :

$f^m\circ f^n=f^n\circ f^m=f^{m+n}.$

$(f^m{)}^n(x)=(f^n{)}^m(x)=f^{mn}(x).$

Pour un élément Modèle:Mvar de Modèle:Mvar, la suite des valeurs $f^n(x)$ est nommée l'orbite de Modèle:MvarModèle:Refsou.

Si $x=f^m(x)$ pour un entier Modèle:Mvar non nul, on a alors $f^n(x)=f^{n+m}(x)$ (pour tout Modèle:Mvar), l’orbite est dite périodique et le plus petit entier Modèle:Mvar pour un Modèle:Mvar donné est la période de l’orbite correspondante ; le point Modèle:Mvar 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.

Points fixes

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.

Au cours de l’itération, il peut y avoir des ensembles qui se contractent et convergent vers un seul point : dans ce cas, ce point est un point fixe attractif. L’itération peut aussi donner l’apparence de points s’éloignant d’un point fixe, qui est alors appelé point fixe instable. D’autres comportements limites sont aussi possibles. Quand les points de l’orbite convergent vers une ou plusieurs limites, l’ensemble des points d’accumulation de l’orbite est appelé l’ensemble limite ou l’ensemble ω-limite.

Les idées d’attraction et de répulsion se généralisent : on peut catégoriser les ensembles stables et instables selon le comportement de petits voisinages sous l’itération.

Mesure invariante

Si l’on s’intéresse à l’évolution d’une distribution à densité, au lieu d’une distribution discrète ou d’un point individuel, le comportement limite est donné par la mesure invariante. Elle peut être visualisée comme le comportement d’un nuage de points ou de poussière sous une itération. La mesure invariante est un vecteur propre de l’opérateur de Ruelle-Frobenius-Perron ou opérateur de transfert, correspondant à la valeur propre 1. De plus petites valeurs propres correspondent à des états instables, contractants.

En général, puisque l’itération correspond à un décalage, l’opérateur de transfert et son adjoint, l’opérateur de Koopman, peuvent être interprétés tous deux comme l’action d’un opérateur de décalage sur un système dynamique symbolique. La théorie des systèmes dynamiques symboliques fournit un cadre pour comprendre de nombreuses fonctions itérées, en particulier celles conduisant au chaos.

Itérées fractionnaires et négatives

Sous certaines hypothèses, il est possible de définir une itérée fractionnaire d’une fonction. Par exemple, la demi-itérée d’une fonction Modèle:Mvar est une fonction Modèle:Mvar telle que $g(g(x))=f(x)$. Cette fonction Modèle:Mvar peut s’écrire avec une notation exponentielle $f^{\frac{1}{2}}(x)$. De même, $f^{\frac{1}{3}}(x)$ est la fonction telle que $f^{\frac{1}{3}}(f^{\frac{1}{3}}(f^{\frac{1}{3}}(x)))=f(x)$, et $f^{\frac{2}{3}}(x)$ peut être définie comme $f^{\frac{1}{3}}(f^{\frac{1}{3}}(x))$, et ainsi de suite, à partir du principe que $f^m\circ f^n=f^n\circ f^m=f^{m+n}.$ L’idée peut se généraliser au cas où le nombre d’itérations Modèle:Mvar devient un paramètre continu ; le système est alors un flot lié à une équation de Schröder.

Les itérées négatives correspondent aux réciproques de fonctions et à leurs compositions. Par exemple, $f^{-1}(x)$ est la réciproque usuelle de la fonction Modèle:Mvar, $f^{-2}(x)$ est la réciproque composée avec elle-même, etc. Les itérées fractionnaires négatives sont définies de manière analogue aux fractionnaires positives. Par exemple, $f^{-\frac{1}{2}}(x)$ est définie de telle sorte que $f^{-\frac{1}{2}}(f^{-\frac{1}{2}}(x))=f^{-1}(x)$.

Itérations de la fonction sinus (en bleu) sur une demi-période : la 1/Modèle:2e itérée est en jaune, les itérées fractionnaires suivantes (jusqu'à 1/64) au-dessus en noir ; la Modèle:2e itérée est en rouge, les suivantes (Modèle:4e, Modèle:8e, etc., jusqu'à la 6'Modèle:E) en-dessous en noir ; l'itérée -1, c'est-à-dire la fonction réciproque arc sin, est en pointillé

Formules pour l’itération fractionnaire

Il existe plusieurs méthodes pour déterminer les itérées fractionnaires. Celle qui suit repose sur l’utilisation d’un point fixe.

1. Déterminer un point fixe a de la fonction, autrement dit un point a tel que $f(a)=a$.
2. Fixer $f^n(a)=a$, pour tout n appartenant aux réels. Ceci correspond à la condition supplémentaire la plus naturelle à imposer aux itérées.
3. Écrire $f^n(x)$ au voisinage du point fixe a comme une série de Taylor :

   $f^n(x)=f^n(a)+(x-a)\frac{d}{dx}{f}^n(x){|}_{x=a}+\frac{(x-a{)}^2}{2}\frac{d^2}{d{x}^2}{f}^n(x){|}_{x=a}+\cdots$

4. Développer :

   $f^n\left(x\right)=f^n(a)+(x-a)f^{\prime }(a)f^{\prime }(f(a))f^{\prime }(f^2(a))\cdots f^{\prime }(f^{n-1}(a))+\cdots$

5. En utilisant la condition fixée à l’étape 2 $f^k(a)=a$, pour tout k, on obtient :

   $f^n\left(x\right)=a+(x-a)f^{\prime }(a{)}^n+\frac{(x-a{)}^2}{2}(f^{″}(a)f^{\prime }(a{)}^{n-1})(1+f^{\prime }(a)+\cdots +f^{\prime }(a{)}^{n-1})+\cdots$

6. Simplifier à l’aide de la progression géométrique :

   $f^n\left(x\right)=a+(x-a)f^{\prime }(a{)}^n+\frac{(x-a{)}^2}{2}(f^{″}(a)f^{\prime }(a{)}^{n-1})\frac{f^{\prime }(a{)}^n-1}{f^{\prime }(a)-1}+\cdots$

7. Un cas particulier est celui où $f^{\prime }(a)=1$ ; dans ce cas :

   $f^n\left(x\right)=x+\frac{(x-a{)}^2}{2}(n{f}^{″}(a))+\frac{(x-a{)}^3}{6}(\frac{3}{2}n(n-1)f^{″}(a{)}^2+n{f}^{‴}(a))+\cdots$

8. Si n n’est pas entier, on utilise la formule $y^n=\exp (n\ln (y))$.

Ce procédé peut être poursuivi indéfiniment, mais il n’est en général pas efficace, car les termes deviennent de plus en plus compliqués.

Exemple 1

La fonction f est définie par Modèle:Math , avec C ≠ 1, a un point fixe Modèle:Math.

Le procédé expliqué ci-dessus donne :

$f^n(x)=\frac{D}{1-C}+(x-\frac{D}{1-C})C^n=C^{n}x+\frac{1-C^n}{1-C}D.$

Exemple 2

Modèle:Article détaillé Il s’agit de trouver la valeur de ${\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{\cdots }}}$, pour Modèle:Mvar itérations. La fonction est ici définie par Modèle:Math. Un point fixe est $a=f(2)=2$.

En développant Modèle:Math comme expliqué plus haut au voisinage de 2, et en posant Modèle:Math, on obtient,

${\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{\cdots }}}=f^n(1)=2-(\ln 2{)}^n+\frac{(\ln 2{)}^{n+1}((\ln 2{)}^n-1)}{4(\ln 2-1)}\cdots .$

Pour n entier positif, les trois premiers termes donnent la première décimale correcte : Modèle:Math.

(On remarque que si on utilise à la place du point fixe 2 l’autre point fixe Modèle:Math, la série diverge.)

Pour Modèle:Math, la série calcule la fonction réciproque, $2\ln x/\ln 2$.

Exemple 3

En développant au voisinage du point fixe 1 la fonction Modèle:Math, on obtient la série

$f^n(x)=1+b^n(x-1)+\frac{1}{2}{b}^n(b^n-1)(x-1{)}^2+\frac{1}{3!}{b}^n(b^n-1)(b^n-2)(x-1{)}^3+\cdots ,$

qui est simplement la série de Taylor de x^(bn) au voisinage de 1.

Conjugaison

Modèle:Article détaillé Si Modèle:Mvar et Modèle:Mvar sont deux fonctions itérées, et s’il existe un homéomorphisme Modèle:Mvar tel que $g=h^{-1}\circ f\circ h$, on dit que Modèle:Mvar et Modèle:Mvar sont conjuguées topologiquement.

L’itération préserve la conjugaison topologique : en effet, $g^n=h^{-1}\circ f^n\circ h$. Donc, si on sait déterminer un système de fonctions itérées, on sait aussi déterminer tous les systèmes topologiquement conjugués.

Par exemple, la fonction triangulaire est topologiquement conjuguée à la suite logistique. Un cas particulier est Modèle:Math, qui donne comme itération de $g(x)=h^{-1}(h(x)+1)$

$g^n(x)=h^{-1}(h(x)+n),$

pour n’importe quelle fonction Modèle:Mvar.

En faisant la substitution $x=h^{-1}(y)=\varphi (y)$, on obtient

$g(\varphi (y))=\varphi (y+1)$, autrement dit l’équation d’Abel.

En l’absence d’un véritable homéomorphisme global, il est souvent possible de résoudre l’équation de Schröder au voisinage d’un point fixe pour une fonction Modèle:Mvar. En prenant par exemple Modèle:Mvar = 0, Modèle:Mvar(0) = 0, Modèle:Math est localement conjugué à une dilation, Modèle:Math, autrement dit

$f(x)={\psi }^{-1}(f(0)\psi (x)).$

L’orbite d’itération, ou flot, sous des conditions adéquates (par exemple Modèle:Math), devient la conjuguée de l’orbite du monôme :

${\psi }^{-1}(f^{\prime }(0{)}^n\psi (x)),$

où Modèle:Mvar dans cette expression est un exposant ordinaire : autrement dit, l’itération fonctionnelle a été réduite à une simple multiplication. L’exposant Modèle:Mvar peut n’être ni positif, ni entier ; il correspond alors à un temps continu d’évolution pour l’orbite.

L'exemple 2 ci-dessus revient par exemple à $f^n(x)={\psi }^{-1}((\ln 2{)}^n\psi (x))$, pour tout n (pas nécessairement entier), où Modèle:Mvar est la solution de l'équation de Schröder correspondante, $\psi ({\sqrt{2}}^x)=\ln 2\psi (x)$. Cette solution est aussi la limite, pour m tendant vers l'infini, de $\frac{f^m(x)-2}{(\ln 2{)}^m}$.

Cette méthode est équivalente à l'algorithme décrit dans la section précédente, mais plus puissante et systématique en pratique.

Exemples

Pour des exemples de fonctions itérées, voir aussi l’ensemble de Mandelbrot et les systèmes de fonctions itérées.

Ernst Schröder a étudié en 1870 des cas particuliers de la suite logistique :

• (cas chaotique) : $f(x)=4x(1-x)$ donne $\psi (x)={\arcsin }^2(\sqrt{x})$, d’où $f^n(x)={\sin }^2(2^n\arcsin (\sqrt{x}))$.

• (cas non chaotique) : $f(x)=2x(1-x)$ donne $\psi (x)=-\frac{1}{2}\ln (1-2x)$, et donc $f^n(x)=-\frac{1}{2}((1-2x{)}^{2^n}-1)$.

Itérées de fonctions ayant une expression fermée

Pour la plupart des fonctions, il n’y a pas d’expression fermée pour la nModèle:E itérée. La table ci-dessous liste quelques fonctions pour lesquelles une telle expression existe. Toutes ces expressions sont valides pour des n, négatifs ou fractionnaires, aussi bien que des entiers positifs.

$f(x)$	$f^n(x)$
$x+b$	$x+nb$
$ax+b(a\ne 1)$	$a^{n}x+\frac{a^n-1}{a-1}b$
$a{x}^b(b\ne 1)$	$a^{\frac{b^n-1}{b-1}}{x}^{b^n}$
$a{x}^2+bx+\frac{b^2-2b}{4a}$	$\frac{2{\alpha }^{2^n}-b}{2a}$ où : $\alpha =\frac{2ax+b}{2}$
$a{x}^2+bx+\frac{b^2-2b-8}{4a}$	$\frac{2{\alpha }^{2^n}+2{\alpha }^{-2^n}-b}{2a}$ où : $\alpha =\frac{2ax+b\pm \sqrt{(2ax+b{)}^2-16}}{4}$
$\frac{ax+b}{cx+d}$	$\frac{a}{c}+\frac{bc-ad}{c}\left[\frac{(cx-a+\alpha ){\alpha }^{n-1}-(cx-a+\beta ){\beta }^{n-1}}{(cx-a+\alpha ){\alpha }^n-(cx-a+\beta ){\beta }^n}\right]$ où : $\alpha =\frac{a+d+\sqrt{(a-d{)}^2+4bc}}{2}$ $\beta =\frac{a+d-\sqrt{(a-d{)}^2+4bc}}{2}$
$\sqrt{x^2+b}$	$\sqrt{x^2+bn}$
$\sqrt{a{x}^2+b}(a\ne 1)$	$\sqrt{a^n{x}^2+\frac{a^n-1}{a-1}b}$
$g^{-1}\left(f\right(g(x)\left)\right)$	$g^{-1}\left(f^n\right(g(x)\left)\right)$
$g^{-1}(g(x)+b)$   (équation d’Abel générique)	$g^{-1}(g(x)+nb)$
$g^{-1}(ag(x)+b)(a\ne 1)$	$g^{-1}(a^{n}g(x)+\frac{a^n-1}{a-1}b)$
$T_m(x)=\cos (m\arccos x)$ (polynôme de Tchebychev d'ordre m)	$T_{m^n}=\cos (m^n\arccos x)$

Note : les deux exemples de Modèle:Math sont les seuls cas qui ont une solution sous forme fermée. En choisissant respectivement b = 2 = –a and b = 4 = –a, ils se réduisent d’ailleurs aux cas non-chaotique et chaotique discutés plus haut.

Certains de ces exemples sont liés entre eux par des conjugaisons simples.

Chaînes de Markov

Si la fonction est linéaire et peut être décrite par une matrice stochastique, c’est-à-dire une matrice où la somme des entrées d’une ligne (ou d’une colonne) est toujours égale à 1, alors le système des itérées est appelé une chaîne de Markov.

En informatique

En informatique, les fonctions itérées apparaissent comme des cas particuliers de fonctions récursives et interviennent dans le lambda calcul, ou dans des sujets plus spécialisés, comme la sémantique dénotationnelle des programmes informatiques.

Définitions basées sur des fonctions itérées

Deux fonctionnelles importantes, la sommation et le produit correspondant, peuvent être définies en termes de fonctions itérées. La sommation est définie par :

$\{b+1,\sum _{i=a}^{b}g(i)\}\equiv {(\{i,x\}\to \{i+1,x+g(i)\})}^{b-a+1}\{a,0\}$

et le produit par :

$\{b+1,\prod _{i=a}^{b}g(i)\}\equiv {(\{i,x\}\to \{i+1,xg(i)\})}^{b-a+1}\{a,1\}.$

Dérivée fonctionnelle

La dérivée fonctionnelle d’une fonction itérée est donnée par la formule de récurrence :

$\frac{\delta f^N(x)}{\delta f(y)}=f^{\prime }(f^{N-1}(x))\frac{\delta f^{N-1}(x)}{\delta f(y)}+\delta (f^{N-1}(x)-y).$