Fonction itérée

En mathématiques , une fonction itérée est une fonction obtenue en composant une autre fonction avec elle-même deux ou plusieurs fois. Le processus consistant à appliquer de manière répétée la même fonction est appelé itération . Dans ce processus, à partir d'un objet initial, le résultat de l'application d'une fonction donnée est réintroduit dans la fonction en tant qu'entrée, et ce processus est répété.

Par exemple, sur l'image de droite :

Les fonctions itérées sont étudiées en informatique , en fractales , en systèmes dynamiques , en mathématiques et en physique du groupe de renormalisation .

La définition formelle d’une fonction itérée sur un ensemble X suit.

Soit X un ensemble et f : X → X une fonction .

Définition de f ⁿ comme la n -ième itération de f , où n est un entier non négatif, par : et

où id _X est la fonction identité sur X et ( f g )( x ) = f ( g ( x )) désigne la composition de fonctions . Cette notation a été attribuée à John Frederick William Herschel en 1813. Herschel en a attribué le mérite à Hans Heinrich Bürmann , mais sans donner de référence spécifique au travail de Bürmann, qui reste inconnu.

Étant donné que la notation f ⁿ peut désigner à la fois l'itération (composition) de la fonction f ou l'exponentiation de la fonction f (cette dernière est couramment utilisée en trigonométrie ), certains mathématiciens choisissent d'utiliser ∘ pour désigner la signification compositionnelle, en écrivant f ^{∘ n} ( x ) pour la n -ième itération de la fonction f ( x ) , comme dans, par exemple, f ^∘3 ( x ) signifiant f ( f ( f ( x ))) . Dans le même but, f ^{[ n ]} ( x ) a été utilisé par Benjamin Peirce tandis qu'Alfred Pringsheim et Jules Molk ont ​​suggéré ⁿ f ( x ) à la place.

En général, l'identité suivante est valable pour tous les entiers non négatifs m et n ,

Ceci est structurellement identique à la propriété d' exponentiation selon laquelle a ^m a ⁿ = a ^{m + n} .

En général, pour des indices généraux arbitraires (négatifs, non entiers, etc.) m et n , cette relation est appelée équation fonctionnelle de translation , cf. équation de Schröder et équation d'Abel . Sur une échelle logarithmique, cela se réduit à la propriété d'imbrication des polynômes de Tchebychev , T _m ( T _n ( x )) = T _{m n} ( x ) , puisque T _n ( x ) = cos( n arccos( x )) .

La relation ( f ^m ) ⁿ ( x ) = ( f ⁿ ) ^m ( x ) = f ^mn ( x ) est également vraie, de manière analogue à la propriété d'exponentiation selon laquelle ( a ^m ) ⁿ = ( a ⁿ ) ^m = a ^mn .

La séquence de fonctions f ⁿ est appelée suite de Picard , du nom de Charles Émile Picard .

Pour un x donné dans X , la séquence de valeurs f ⁿ ( x ) est appelée l' orbite de x .

Si f ⁿ ( x ) = f ^{n + m} ( x ) pour un entier m > 0 , l'orbite est appelée orbite périodique . La plus petite valeur de m pour un x donné est appelée période de l'orbite . Le point x lui-même est appelé point périodique . Le problème de détection de cycle en informatique est le problème algorithmique de recherche du premier point périodique d'une orbite et de la période de l'orbite.

Si x = f ( x ) pour un x dans X (c'est-à-dire que la période de l'orbite de x est 1 ), alors x est appelé un point fixe de la séquence itérée. L'ensemble des points fixes est souvent noté Fix ( f ) . Il existe un certain nombre de théorèmes de point fixe qui garantissent l'existence de points fixes dans diverses situations, notamment le théorème de point fixe de Banach et le théorème de point fixe de Brouwer .

Il existe plusieurs techniques d' accélération de la convergence des séquences produites par itération à point fixe . Par exemple, la méthode d'Aitken appliquée à un point fixe itéré est connue sous le nom de méthode de Steffensen et produit une convergence quadratique.

Lors de l'itération, on peut constater qu'il existe des ensembles qui se rétrécissent et convergent vers un seul point. Dans un tel cas, le point vers lequel convergent les ensembles est appelé point fixe attractif . Inversement, l'itération peut donner l'impression que des points s'éloignent d'un seul point ; ce serait le cas pour un point fixe instable .

Lorsque les points de l'orbite convergent vers une ou plusieurs limites, l'ensemble des points d'accumulation de l'orbite est appelé ensemble limite ou ensemble ω-limite .

Les idées d'attraction et de répulsion se généralisent de la même manière ; on peut classer les itérations en ensembles stables et en ensembles instables , selon le comportement des petits voisinages sous itération. Voir aussi compositions infinies de fonctions analytiques .

D'autres comportements limitatifs sont possibles ; par exemple, les points errants sont des points qui s'éloignent et ne reviennent jamais, même près de leur point de départ.

Si l'on considère l'évolution d'une distribution de densité, plutôt que celle de la dynamique de points individuels, alors le comportement limite est donné par la mesure invariante . Elle peut être visualisée comme le comportement d'un nuage de points ou d'un nuage de poussière sous itération répétée. La mesure invariante est un état propre de l'opérateur de Ruelle-Frobenius-Perron ou de l'opérateur de transfert , correspondant à une valeur propre de 1. Les valeurs propres plus petites correspondent à des états instables et en déclin.

En général, comme l'itération répétée correspond à un décalage, l'opérateur de transfert et son adjoint, l' opérateur de Koopman , peuvent tous deux être interprétés comme des opérateurs de décalage agissant sur un espace de décalage . La théorie des sous-décalages de type fini fournit un aperçu général de nombreuses fonctions itérées, en particulier celles qui conduisent au chaos.

La notion f ^{1/ n} doit être utilisée avec précaution lorsque l'équation g ⁿ ( x ) = f ( x ) a plusieurs solutions, ce qui est normalement le cas, comme dans l'équation de Babbage des racines fonctionnelles de l'application identité. Par exemple, pour n = 2 et f ( x ) = 4 x − 6 , g ( x ) = 6 − 2 x et g ( x ) = 2 x − 2 sont toutes deux des solutions ; l'expression f ^1/2 ( x ) ne désigne donc pas une fonction unique, tout comme les nombres ont plusieurs racines algébriques. Une racine triviale de f peut toujours être obtenue si le domaine de f peut être suffisamment étendu, cf. image. Les racines choisies sont normalement celles appartenant à l'orbite étudiée.

L'itération fractionnaire d'une fonction peut être définie : par exemple, une demi-itération d'une fonction f est une fonction g telle que g ( g ( x ))= f ( x ) . Cette fonction g ( x ) peut être écrite en utilisant la notation d'indice comme f1 ^/2 ( x ) . De même, f1 ^/3 ( x ) est la fonction définie telle que f1 ^/3 ( f1 ^/3 ( f1 ^{/ 3} ( x )))= f ( x ) , tandis que f2 ^/3 ( x ) peut être définie comme égale à f1 ^/3 ( f1 /3 ( x )) , et ainsi de suite, le tout basé sur le principe, mentionné précédemment, que fm ^○ fn = fm ^{+ n} . Cette idée peut être généralisée de sorte que le nombre d'itérations ⁿ devienne un paramètre continu , une sorte de « temps » continu d' une orbite continue . ^[

Dans de tels cas, on parle de système de flux (cf. section sur la conjugaison ci-dessous).

Si une fonction est bijective (et possède donc une fonction inverse), alors les itérations négatives correspondent aux inverses de fonctions et à leurs compositions. Par exemple, f ⁻¹ ( x ) est l'inverse normal de f , tandis que f ⁻² ( x ) est l'inverse composé avec lui-même, c'est-à-dire f ⁻² ( x ) = f ⁻¹ ( f ⁻¹ ( x )) . Les itérations négatives fractionnaires sont définies de manière analogue aux itérations positives fractionnaires ; par exemple, f ^−1/2 ( x ) est définie de telle sorte que f ^−1/2 ( f ^−1/2 ( x )) = f ⁻¹ ( x ) , ou, de manière équivalente, de telle sorte que f ^−1/2 ( f ^1/2 ( x )) = f ⁰ ( x ) = x .

L’une des nombreuses méthodes permettant de trouver une formule de série pour une itération fractionnaire, en utilisant un point fixe, est la suivante.

1. Déterminez d’abord un point fixe pour la fonction tel que f ( a ) = a .
2. Définissons f ⁿ ( a ) = a pour tout n appartenant aux réels. C'est, d'une certaine manière, la condition supplémentaire la plus naturelle à imposer aux itérations fractionnaires.
3. Développons f ⁿ ( x ) autour du point fixe a comme une série de Taylor ,
4. Développer
5. Remplacer par f ^k ( a ) = a , pour tout k ,
6. Utilisez la progression géométrique pour simplifier les termes. Il existe un cas particulier lorsque f '(a) = 1 ,

Cette procédure peut être poursuivie indéfiniment, bien que de manière inefficace, car les termes de la convention deviennent de plus en plus complexes. Une procédure plus systématique est décrite dans la section suivante sur la conjugaison .

Par exemple, si l'on définit f ( x ) = Cx + D, on obtient le point fixe a = D /(1 − C ) , donc la formule ci-dessus se termine par ce qui est facile à vérifier.

Trouver la valeur de où ceci est fait n fois (et éventuellement les valeurs interpolées lorsque n n'est pas un entier). Nous avons f ( x ) = √ 2 ^x . Un point fixe est a = f (2) = 2 .

Ainsi, si x = 1 et f ⁿ (1) développé autour de la valeur du point fixe 2 est alors une série infinie, qui, en prenant seulement les trois premiers termes, est correcte à la première décimale lorsque n est positif. Voir aussi Tétration : f ⁿ (1) = ⁿ √ 2 . L'utilisation de l'autre point fixe a = f (4) = 4 fait diverger la série.

Pour n = −1 , la série calcule la fonction inverse ⁠2+ln x/en 2⁠ .

Avec la fonction f ( x ) = x ^b , développez autour du point fixe 1 pour obtenir la série qui est simplement la série de Taylor de x ^{( b n )} développée autour de 1.

Si f et g sont deux fonctions itérées, et qu'il existe un homéomorphisme h tel que g = h ⁻¹ ○ f ○ h , alors f et g sont dites topologiquement conjuguées .

De toute évidence, la conjugaison topologique est préservée lors de l'itération, car g ⁿ = h ⁻¹ ○ f ⁿ ○ h . Ainsi, si l'on peut résoudre un système de fonctions itérées, on a également des solutions pour tous les systèmes topologiquement conjugués. Par exemple, la carte de tentes est topologiquement conjuguée à la carte logistique . Comme cas particulier, en prenant f ( x ) = x + 1 , on a l'itération de g ( x ) = h ⁻¹ ( h ( x ) + 1) comme

g ⁿ ( x ) = h ⁻¹ ( h ( x ) + n ) , pour toute fonction h .

En effectuant la substitution x = h ⁻¹ ( y ) = ϕ ( y ) on obtient

g ( ϕ ( y )) = ϕ ( y +1) , une forme connue sous le nom d' équation d'Abel .

Même en l'absence d'un homéomorphisme strict, près d'un point fixe, ici pris à x = 0, f (0) = 0, on peut souvent résoudre l'équation de Schröder pour une fonction Ψ, ce qui rend f ( x ) localement conjugué à une simple dilatation, g ( x ) = f '(0) x , c'est-à-dire

f ( X ) = Ψ ⁻¹ ( f '(0) Ψ( X )) .

Ainsi, son orbite d'itération, ou son flux, sous des dispositions appropriées (par exemple, f '(0) ≠ 1 ), équivaut au conjugué de l'orbite du monôme,

Ψ ⁻¹ ( f '(0) ⁿ Ψ( x )) ,

où n dans cette expression sert d'exposant simple : l'itération fonctionnelle a été réduite à la multiplication ! Ici, cependant, l'exposant n n'a plus besoin d'être entier ou positif, et est un « temps » continu d'évolution pour l'orbite complète : le monoïde de la suite de Picard (cf. semi-groupe de transformation ) s'est généralisé à un groupe complet continu .

Cette méthode (détermination perturbative de la fonction propre principale Ψ, cf. matrice de Carleman ) est équivalente à l'algorithme de la section précédente, quoique, en pratique, plus puissante et systématique.

Si la fonction est linéaire et peut être décrite par une matrice stochastique , c'est-à-dire une matrice dont la somme des lignes ou des colonnes est égale à un, alors le système itéré est appelé chaîne de Markov .

Il existe de nombreuses applications chaotiques . Parmi les fonctions itérées les plus connues, on trouve l' ensemble de Mandelbrot et les systèmes de fonctions itérées .

Ernst Schröder , en 1870, a élaboré des cas particuliers de la carte logistique , tels que le cas chaotique f ( x ) = 4 x (1 − x ) , de sorte que Ψ( x ) = arcsin( √ x ) ² , donc f ⁿ ( x ) = sin(2 ⁿ arcsin( √ x )) ² .

Un cas non chaotique que Schröder a également illustré avec sa méthode, f ( x ) = 2 x (1 − x ) , a donné Ψ( x ) = − ⁠1/2⁠ ln(1 − 2 x ) , et donc f ⁿ ( x ) = − ⁠1/2((1 − 2 x ) 2 ^{n −} 1) .

Si f est l' action d'un élément du groupe sur un ensemble, alors la fonction itérée correspond à un groupe libre .

La plupart des fonctions n'ont pas d'expressions explicites générales sous forme fermée pour la n -ième itération. Le tableau ci-dessous en répertorie quelques-unes nombres n non entiers et négatifs , ainsi que pour les nombres n non négatifs .

Remarque : ces deux cas particuliers de ax ² + bx + c sont les seuls cas qui ont une solution sous forme fermée. Le choix de b = 2 = – a et b = 4 = – a , respectivement, les réduit encore davantage aux cas logistiques non chaotiques et chaotiques discutés avant le tableau.

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

Les fonctions itérées peuvent être étudiées avec la fonction zêta d'Artin-Mazur et avec les opérateurs de transfert .

En informatique , les fonctions itérées constituent un cas particulier de fonctions récursives , qui à leur tour ancrent l'étude de sujets aussi vastes que le calcul lambda , ou plus restreints, tels que la sémantique dénotationnelle des programmes informatiques.

Deux fonctions importantes peuvent être définies en termes de fonctions itérées. Il s'agit de la sommation :

et le produit équivalent :

La dérivée fonctionnelle d'une fonction itérée est donnée par la formule récursive :

Les fonctions itérées apparaissent dans le développement en série de fonctions combinées, telles que g ( f ( x )) .

Étant donné la vitesse d'itération , ou fonction bêta (physique) ,

pour la n ^-ième itération de la fonction f , nous avons

Par exemple, pour une advection rigide, si f ( x ) = x + t , alors v ( x ) = t . Par conséquent, g ( x + t ) = exp( t ∂/∂ x ) g ( x ) , action par un opérateur de décalage simple .

Inversement, on peut spécifier f ( x ) étant donné un v ( x ) arbitraire , à travers l' équation d'Abel générique discutée ci-dessus,

où

Ceci est évident en notant que

Pour un indice d'itération continue t , alors, maintenant écrit sous forme d'indice, cela équivaut à la célèbre réalisation exponentielle de Lie d'un groupe continu,

La vitesse initiale d'écoulement v suffit à déterminer l'écoulement entier, étant donné cette réalisation exponentielle qui fournit automatiquement la solution générale à l' équation fonctionnelle de translation ,