Fonction itérée
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/Confusion_colour.svg/20px-Confusion_colour.svg.png)
Ne doit pas être confondu avec Fonction récursive.
En mathématiques, itérer une fonction ou effectuer son itération consiste à la composer avec elle‑même un certain nombre de fois, ou bien indéfiniment.
Les fonctions itérées apparaissent en informatique, dans les systèmes dynamiques, les groupes de renormalisation et sont à la base des fractales.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f2/It%C3%A9rer_une_soustraction_de_d_jusque_modulo_d.svg/335px-It%C3%A9rer_une_soustraction_de_d_jusque_modulo_d.svg.png)
le reste de la division euclidienne de n par d.
Par exemple si n = 95 et d = 20, la fonction
f itérée est définie par f ( x ) = x – 20, sur
l’ensemble ℕ des entiers naturels. La variable
r prend les valeurs 95 ↦ 75 ↦ 55 ↦ 35 ↦ 15,
en quatre parcours de la boucle. L’algorithme
conclut : 95 modulo 20 = 95 – 4 × 20 = 15.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/06/An_iterated_direct_similarity_yields_spirals.svg/403px-An_iterated_direct_similarity_yields_spirals.svg.png)
de son agrandissement par la similitude directe F.
Le point invariant de F est le centre S des
pentagones réguliers. Par la composition de F
à l’infini avec elle‑même, les images d’un point
distinct de S sont les sommets d’une spirale infinie.
Une spirale qui part de K passe par L = F ( K ),
puis M = F ( F ( K )) = F ○ F ( K ) = F 2 ( K ), etc.
Définition, conventions, énonciations
À la première itération d’une fonction f d’un ensemble X dans lui‑même, pour tout élément x de X, où se lit “ au carré ”. Car la composition de fonctions symbolisée est une opération multiplicative.
Quand est un nombre, son carré s’entend différemment du précédent Quand f ne peut pas être itérée, son itération est alors exclue de l’interprétation d’une expression qui comporte f . Par exemple, une fonction trigonométrique transforme un angle en un rapport qui n’est plus un angle, donc n’est pas itérée. Alors dans certains cas, peut représenter le carré de Par exemple, la formule pourrait s’écrire
De la même façon, se lit “ au cube ”, ou “ puissance 3 ”, bien que la composition ○ ne soit pas une multiplication de nombres.
Après une construction rigoureuse par des axiomes, de l’ensemble ℕ des entiers naturels, la n‑ième itérée de f se définirait par la relation de récurrence :
où n est un entier naturel, et f une fonction définie sur un ensemble X, et à valeurs dans le même ensemble X.
L’interprétation peut être ambiguë entre deux itérations différentes, celle d’une multiplication par un nombre constant, ou bien l’itération d’une autre fonction. Alors parfois certains auteurs précisent l’itération en inscrivant ○ juste après la fonction, ce symbole de composition de fonctions en début d’exposant
Par convention pour n = 0, , où est la fonction identité sur X. Ainsi la formule est valable quels que soient les entiers naturels n et p.
Suites d’itération
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.
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[1].
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[2]. 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 f est une fonction g telle que . Cette fonction g peut s’écrire avec une notation exponentielle . De même, est la fonction telle que , et peut être définie comme , et ainsi de suite, à partir du principe que L’idée peut se généraliser au cas où le nombre d’itérations n 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, est la réciproque usuelle de la fonction f, 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, est définie de telle sorte que .
![Graphes des itérées de la fonction sinus depuis la 1/2e itérée jusqu'à la 1/64e et de la 2e à la 64e, ainsi qu'un graphe de la fonction arc sin qui est la fonction itérée -1](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4d/Sine_iterations.svg/440px-Sine_iterations.svg.png)
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.
- Déterminer un point fixe a de la fonction, autrement dit un point a tel que .
- Fixer , pour tout n appartenant aux réels. Ceci correspond à la condition supplémentaire la plus naturelle à imposer aux itérées.
- Écrire au voisinage du point fixe a comme une série de Taylor :
- Développer :
- En utilisant la condition fixée à l’étape 2 , pour tout k, on obtient :
- Simplifier à l’aide de la progression géométrique :
- Un cas particulier est celui où ; dans ce cas :
- Si n n’est pas entier, on utilise la formule .
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 f(x) = Cx+D , avec C ≠ 1, a un point fixe a = ‘’D/(1-C).
Le procédé expliqué ci-dessus donne :
Exemple 2
Il s’agit de trouver la valeur de , pour n itérations. La fonction est ici définie par f(x)=√2x. Un point fixe est .
En développant f n (x) comme expliqué plus haut au voisinage de 2, et en posant x=1, on obtient,
Pour n entier positif, les trois premiers termes donnent la première décimale correcte : fn(1) = n√2.
(On remarque que si on utilise à la place du point fixe 2 l’autre point fixe a = f(4) = 4, la série diverge.)
Pour n = −1, la série calcule la fonction réciproque, .
Exemple 3
En développant au voisinage du point fixe 1 la fonction f(x) = xb, on obtient la série
qui est simplement la série de Taylor de x(bn) au voisinage de 1.
Conjugaison
Si f et g sont deux fonctions itérées, et s’il existe un homéomorphisme h tel que , on dit que f et g sont conjuguées topologiquement.
L’itération préserve la conjugaison topologique : en effet, . 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 f(x) = x+1, qui donne comme itération de
pour n’importe quelle fonction h.
En faisant la substitution , on obtient
- , autrement dit l’équation d’Abel.
En l’absence d’un véritable homéomorphisme global, il est souvent possible de résoudre[3] l’équation de Schröder au voisinage d’un point fixe pour une fonction Ψ. En prenant par exemple x = 0, f(0) = 0, f(x) est localement conjugué à une dilation, g(x) = f '(0) x, autrement dit
L’orbite d’itération, ou flot, sous des conditions adéquates (par exemple f '(0) ≠ 1), devient la conjuguée de l’orbite du monôme :
où n dans cette expression est un exposant ordinaire : autrement dit, l’itération fonctionnelle a été réduite à une simple multiplication. L’exposant n peut n’être ni positif, ni entier ; il correspond alors à un temps continu d’évolution pour l’orbite[4].
L'exemple 2 ci-dessus revient par exemple à , pour tout n (pas nécessairement entier), où Ψ est la solution de l'équation de Schröder correspondante, . Cette solution est aussi la limite, pour m tendant vers l'infini, de .
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[5] a étudié en 1870 des cas particuliers de la suite logistique :
- (cas chaotique) : donne , d’où .
- (cas non chaotique) : donne , et donc .
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 ne itérée. La table ci-dessous liste quelques fonctions[5] pour lesquelles une telle expression existe. Toutes ces expressions sont valides pour des n, négatifs ou fractionnaires, aussi bien que des entiers positifs.
où : | |
| où : |
[6] | où : |
(équation d’Abel générique) | |
(polynôme de Tchebychev d'ordre m) |
Note : les deux exemples de ax2 + bx + c 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[7].
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 :
et le produit par :
Dérivée fonctionnelle
La dérivée fonctionnelle d’une fonction itérée est donnée par la formule de récurrence :
Références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Iterated function » (voir la liste des auteurs).
- ↑ (en) L. Carleson et T. D. W. Gamelin, Complex dynamics, Berlin/New York, Springer-Verlag, coll. « Universitext: Tracts in Mathematics », , 174 p. (ISBN 0-387-97942-5).
- ↑ Vasile Istratescu, Fixed Point Theory, An Introduction, D. Reidel, (ISBN 90-277-1224-7).
- ↑ Tosihusa Kimura, « On the Iteration of Analytic Functions », Funkcialaj Ekvacioj, vol. 14, , p. 197-238 (lire en ligne).
- ↑ Thomas Curtright et Cosmas Zachos, « Evolution Profiles and Functional Equations », Journal of Physics A, vol. 42, no 48, , p. 485208 (DOI 10.1088/1751-8113/42/48/485208, Bibcode 2009JPhA…42V5208C, arXiv 0909.2424).
- ↑ a et b (de) Ernst Schröder, « Ueber iterirte Functionen », Mathematische Annalen, vol. 3, no 2, , p. 296-322 (DOI 10.1007/BF01443992).
- ↑ Louis Brand, « A sequence defined by a difference equation », American Mathematical Monthly, vol. 62, , p. 489–492 (lire en ligne).
- ↑ Pour d’autres exemples, essentiellement des conjugués des exemples de Schröter, voir S. Katsura et W. Fukuda, « Exactly solvable models showing chaotic behavior », Physica A: Statistical Mechanics and its Applications, vol. 130, no 3, , p. 597 (DOI 10.1016/0378-4371(85)90048-2).
Portail des mathématiques
Portail de l'informatique théorique