Itérer une fonction : voilà un plaisir simple que l'on a tous fait dès lors que nous avons eu entre les mains notre première calculette ! On écrit un nombre, on écrit "+1", puis on martèle la touche [=] pour voir les nombres défiler. Le premier arrivé à 1000 sera prem's à la Master System !

Très vite, on essaye les autres touches de la calculatrice. Répéter la touche [X²] donne des nombres de plus en plus grands tandis que la touche [√X] donne des nombres de plus en plus proches de 1. Les touches [-x] et [1/x] ne sont vraiment pas amusantes, puisqu'elles alternent entre les deux mêmes nombres, alors que les touches [sin] et [cos] donnent des résultats bizarres. Comme on ne comprend pas vraiment le sens de toutes ces touches, on ne sait jamais ce que l'on va obtenir, la surprise est donc toujours au rendez-vous.

Toi aussi, lecteur, tambourine la touche [=] pour voir les nombres se transformer



La sagesse arrive avec l'âge et on arrête de taper bêtement sur sa calculatrice. On préfère inventer des théorèmes qui prédisent ce qui va arriver quand on le fera. Un tel théorème, c'est un théorème de point fixe, et c'est sans doute pour ça qu'il en existe autant (Wikipédia en recense 16, et c'est seulement ceux qui portent un nom particulier).

Le point fixe d'une fonction f est une solution de l'équation f(x)=x. Bien souvent, pour trouver cette solution, il suffit d'itérer la fonction f en partant de n'importe quel point de départ. Dans la théorie, un théorème de point fixe sert surtout à savoir si c'est une bonne idée a priori d'itérer la fonction. Dans la pratique, on commence par essayer de répéter la fonction, on ne regarde que dans un deuxième temps elle était bien k-lipschitzienne...

Itérons des fonctions 
Par exemple, que se passe-t-il si on itère la fonction cosinus ? Pour cela, on part d'un nombre, n'importe lequel (disons, 1), et on calcule son cosinus. On obtient :

cos(1) = 0.5403023058681398

Si maintenant, on applique à nouveau la fonction à son résultat, on trouve 

cos(0.5403023058681398) = 0.8575532158463934

On peut maintenant marteler la touche cos et observer ce qu'il se passe : 

cos(0.8575532158463934) = 0.6542897904977791
cos(0.6542897904977791) = 0.7934803587425656
...
après beaucoup trop d'itérations...
...
cos(0.7390851332151607) = 0.7390851332151607

La suite finit par se stabiliser autour du nombre 0.739, qui n'est autre que la solution de cos(x) = x. C'est en itérant la fonction que l'on a pu trouver une valeur (approchée) du point fixe de cos(x) ; c'est d'ailleurs la seule façon de le faire.

Itérons des opérateurs
Puisqu'il est amusant d'itérer des fonctions, on peut aussi itérer des fonctions de fonctions. Par exemple, que se passe-t-il si on itère la transformation ci-dessous en partant de la fonction f:x ↦ x ?

 OperateurBolzano

La réponse, c'est un point fixe de l'opérateur, une fonction particulièrement anguleuse :

Bolzano

La fonction que l'on obtient après une infinité d'étapes (bien que la cinquième itération en soit une bonne approximation), c'est la courbe de Bolzano-Lebesgue, un exemple de courbe continue partout mais dérivable nulle part.

I. F. S. 
Faisons encore mieux : itérons des transformations d'images, avec les IFS (Système de fonctions itérées). On part d'une image et on crée plusieurs sous-images identiques à la première.

Partons de la transformation suivante, où l'image est rapetissée et dédoublée :

Transfo_smiley

En la répétant suffisamment de fois (ici, 7 fois), on obtient une nébuleuse de smileys particulièrement esthétique !

Transfo_smileyneutre

Ces transformations sont surtout une excellente façon de produire des images fractales, puisque l'auto-similarité est au coeur de la procédure.

IFS
Cette fractale a été obtenue par itération de la transformation représentée à droite qui transforme le carré blanc en chacun des parallélogrammes rouges

Dans ce titre, on peut compter exactement vingt-neuf voyelles et quarante-cinq consonnes
Comment compléter la phrase "Cette phrase auto-référente compte ___ A, ___ B, ___ C, ___ D et ___ E" pour qu'elle soit vraie ? Encore une fois, les itérations vont nous sauver, bien qu'aucun théorème de point fixe ne peut nous garantir le résultat. Cette méthode est due à Douglas Hofstadter, auteur du célèbre Gödel, Escher, Bach.

Commençons donc par une phrase ostensiblement fausse :

Cette phrase auto-référente compte quarante-deux A, zéro B, quarante-deux C, quarante-deux D et quarante-deux E !

Puis, on remplace les nombres affichés par les nombres réels :

Cette phrase auto-référente compte onze A, un B, trois C, cinq D et dix-neuf E !

La phrase n'est toujours pas correcte, mais rien ne nous empêche de continuer :

Cette phrase auto-référente compte trois A, un B, quatre C, deux D et douze E !

Cette phrase auto-référente compte quatre A, un B, trois C, trois D et treize E !

Cette phrase auto-référente compte quatre A, un B, trois C, un D et treize E !

Cette phrase auto-référente compte quatre A, un B, trois C, un D et treize E !

Après quelques itérations, on finit par tomber sur une phrase authentique. Le mauvais côté de cette méthode, c'est que très souvent, elle finit par boucler sans trouver de point fixe... Et ça peut arriver alors même qu'il existe une solution :

Cette phrase auto-référente compte plusieurs A, un B, quelques C, un D et plein de E !
Cette phrase auto-référente compte trois A, un B, trois C, deux D et quinze E !
Cette phrase auto-référente compte trois A, un B, trois C, deux D et douze E !
Cette phrase auto-référente compte trois A, un B, trois C, trois D et douze E !
Cette phrase auto-référente compte trois A, un B, trois C, deux D et onze E !
Cette phrase auto-référente compte trois A, un B, trois C, deux D et douze E !

Avec cette méthode, on peut relativement facilement construire des phrases qui n'ont rien à cacher (à l'heure de la transparence...), comme celle-ci, œuvre de l'oulipo :

Huit a, un b, cinq c, six d, dix-huit e, trois f, six g, cinq h, vingt-six i, un j, un k, trois l, un m, vingt-quatre n, huit o, sept p, sept q, neuf r, quinze s, vingt-deux t, vingt u, six v, un w, dix x, un y, deux z, cinq traits d'union, une apostrophe, trente virgules, soixante-quatre espaces, et un point final.

I XKCD
En janvier 2012, xkcd publiait ceci :

self_description

Comment a-t-il obtenu cette image ? Avec des itérations, sans doute !... Le principe est toujours le même : on part d'une image qui n'a rien à voir, et décrit ce qu'il s'y passe pour fabriquer une nouvelle image. En réitérant le processus suffisament de fois, on arrive à une version publiable :

rien2
Première itération, obtenue à partir de l'image ci-dessus...

rien3
2 itérations

rien4
3 itérations

rien23

Après de nombreuses itérations, on obtient cette version un peu cheap du strip d'xkcd...


Sources :
Glito IFS fractals, pour dessiner des fractales par IFS
Ce titre contient quatre 'a', un 'b', [...] un 'y' et quatre 'z', de Jacques Pitrat [rtf]