dimanche 11 décembre 2011

Boulanger: la saga continue (2/2)

 PART 2 Les mystères du monde continu


Je vous ai montré dans le billet précédent pourquoi en mélangeant de façon très méthodique une image faite de pixels (j’étale dans un sens, je replie et je recommence) on revient tôt ou tard à la l’image initiale. Mais aujourd’hui nous allons voir que cet éternel recommencement est un privilège réservé aux images numériques. Même si on savait répéter une telle transformation avec une précision parfaite sur une image réelle, faite d’un continuum de points, on ne retrouverait jamais l’image de départ. Plus fort encore: jamais le mélange ne produirait deux fois la même image…

Pétrissage décimal
Pour vous le montrer simplement, je vais modifier légèrement la méthode de pétrissage: le boulanger étire son carré de 10 fois sa longueur initiale (au lieu de deux) et il coupe les neuf morceaux qui dépassent afin de retrouver la  forme initiale du carré une fois empilés.

 

C’est un peu plus compliqué à première vue mais vous allez vite comprendre pourquoi ça simplifie les calculs…

Supposons que notre carré ait une longueur 1 de côté et divisons le verticalement en 10 bandes de largeur 0,1 chacune. Le point en rouge de coordonnées (0.375;0.405) est situé dans la troisième bande verticale en partant de la gauche.  Au premier étirement, notre point se retrouve dans le troisième bloc en partant de la gauche (son abscisse est multipliée par 10) et rabaissée (son ordonnées est divisée par 10) soit  (3.75;0.0405).  Après passage du couteau, le troisième bloc est empilée sur les deux premiers: l’abscisse du point est donc diminuée de 3 unités et son ordonnée augmentée de 3 décimales soit (0.75;0.3405).

Bilan:

 

La transformation d’un point s’obtient donc simplement en enlevant la première décimale de l’abscisse et en la glissant devant la première décimale de l’ordonnée. Une manière plus simple de faire l’opération consiste à écrire l’abscisse et l’ordonnées tête-bêche et de les séparer par un symbole par exemple « : » Dans ce formalisme, le point initial (0.375;0.405) s’écrit  573:405 et son image (0.57:0.345) s’écrit 57:3405!

La transformation consiste donc à simplement déplacer la séparation entre abscisse (écrite à l’envers) et ordonnée. A mesure que l’on itère les transformations, les lointaines décimales de l’abscisse initiale « remontent » près de la virgule et deviennent déterminantes sur l’abscisse avant de passer sur l’ordonnée. A l’inverse les décimales initiales de l’ordonnée sont reléguées en queue de développement décimale et ne comptent rapidement plus du tout.

Quand le destin est fonction de la naissance, pas de la valeur.
Nous voilà parés pour comparer les destins de trois points situés extraordinairement près les uns des autres avant que le boulanger ne commence à travailler son pétrin. Supposons qu’ils aient tous  la même ordonnée (mettons y=0,5) et comme abscisses respectivement:
– un nombre décimal  0.14159
– une fraction non décimale: 1/7=0,142 857 142 857…
– un nombre irrationnel: 3-pi=0.14159265… (suite de décimales non périodique)

1) Pour le point ayant une abscisse décimale, les choses se passent très mal: il se fait vite projeter contre le bord gauche de l’image avant de s’écrouler par terre, comme un mauvais cowboy dans une bagarre de saloon. Sa durée de vie est égale au nombre de ses décimales non nulle. Il est un peu nul et d’ailleurs tel est son destin, puisqu’il finit au point d’origine (0,0) en bas à gauche:

2) Le point d’abscisse rationnelle (non décimale) commence pareil que son jumeau décimal mais il s’en sort bien mieux.  Comme son développement décimal finit par être périodique, au bout d’un certain nombre de transformations l’abscisse du point devient elle-même cyclique. Et comme la première décimale de l’abscisse devient la première décimale de l’ordonnée lors de la transformation suivante, l’ordonnée entre à son tour dans un cycle en miroir. Le point entre dans un cycle fermé dont la longueur est celle de la période de ses décimales:


Les puristes auront remarqué  que l’ordonnée conserve toujours une queue de décimales qui lui est propre et ne peut donc être exactement cyclique. C’est exact, mais comme l’influence de cette « queue » décimale est divisée par 10 à chaque transformation, elle perd très rapidement toute influence.

3) Pour le point d’abscisse irrationnelle, c’est encore plus funky. Son développement décimal n’étant jamais périodique, les décimales que chaque transformation fait « remonter » en première position semblent parfaitement aléatoires. Et comme l’ordonnée se fait contaminer par les décimales de l’abscisse, le point se déplace de façon anarchique au fil des itérations.

L’absence de périodicité de ses déplacements garantit qu’il ne repasse jamais deux fois sur la même position. Si l’on poursuivait sans arrêt ces transformations, le point finirait par couvrir toute la surface de l’image.
Aussi proches soient-ils, nos trois points de départ ont des destins radicalement différents. Le point d’abscisse décimale converge vers l’origine, celui ayant une abscisse rationnelle suit une boucle cyclique et le point d’abscisse irrationnelle suit un parcours chaotique. Leur destin respectif ne dépend donc que de leur « statut » arithmétique, leur essence platonicienne pourrait-on dire, et non pas de leur valeur. Notre transformation du boulanger décimal s’avère être une extraordinaire trieuse de nombres!

Mais après tout, est-ce vraiment grave si ces dingos d’irrationnels sont incontrôlables? Du moment que les nombres rationnels tournent sagement en boucle, leur grand nombre n’assure-t-il pas que l’on retrouvera un système cyclique, comme pour l’image numérique? Hélas, il y a beaucoup beaucoup plus de nombre irrationnels que de nombres rationnels. Parmi tous les réels, ces derniers sont l’exception plutôt que la règle. A la différence d’une image ayant un nombre fini de pixels, notre  image « continue » sera donc irrémédiablement diluée par la transformation du boulanger, même si de ci de là quelques rares points suivront effectivement un cycle.

Déterminisme et prédictibilité
La transformation du boulanger illustre ainsi la différence qualitative entre fini et infini, mais elle est intéressante à plus d’un titre. Comme tout système chaotique, elle met aussi en évidence la différence entre déterminisme et prévisibilité. Certes l’équation de la trajectoire d’un point soumis à une série de transformations est parfaitement déterminée. Pourtant on vient de voir que deux points infiniment proches l’un de l’autre suivent des destins totalement différents selon la nature -décimale, rationnelle ou irrationnelle- de leur abscisse. L’imbrication infinie entre ces trois ensembles de nombres rend impossible toute prédiction concernant la trajectoire d’un point matériel donné: attraction vers O, oscillation périodique ou trajectoire chaotique. La transformation du boulanger est un joli exemple mélangeant déterminisme absolu et imprédictibilité totale.

Pour reprendre une thématique développée par Tom Roud, assimiler déterminisme et capacité prédictive ne vaut que tant que l’on est face à des phénomènes linéaires, pour lesquels une petite erreur de mesure initiale n’entraine qu’une petite erreur sur le résultat de la prédiction. Il se trouve que les lois physiques élémentaires soient justement linéaires, qu’il s’agisse de la gravité, de l’électromagnétisme ou des forces nucléaires faibles ou fortes. Et la « déraisonnable efficacité des mathématiques » acquise grâce à cette linéarité providentielle a sans doute largement contribué au succès de la méthode scientifique et son hégémonie dans le monde occidental.
Mais de même que les nombres rationnels sont « rares » parmi les nombres réels, les phénomènes linéaires sont probablement l’exception plutôt que la règle dès que l’on sort des régimes d’équilibre ou que l’on aborde des disciplines comme l’économie, la biologie ou l’écologie. On peut certes toujours modéliser des phénomènes non linéaires. Mais aucun modèle, aussi exact soit-il, n’aura la capacité de prédire leur évolution au-delà d’un temps très court, à l’image des prévisions météorologiques.

L’irréversibilité et la flèche du temps
La transformation du boulanger a aussi l’intérêt de mettre en évidence le lien entre irréversibilité et instabilité. Je m’explique: l’opération que l’on a décrite est entièrement réversible: pour revenir en arrière il suffit de découper le carré en deux (ou en dix) bandes horizontales, de les étaler les unes à côté des autres et de recomprimer le tout pour obtenir la forme initiale du carré. Simple non? En pratique pourtant, la très grande instabilité de la transformation détruit tout espoir de retour en arrière au-bout d’un certain temps. Il suffit qu’à l’aller, un des points bouge d’un angström (10-10m) sous l’influence gravitationnelle d’un électron situé aux confins de l’univers, pour que ce point perde tout espoir de revenir à sa position initiale après 10 transformations.
Pour illustrer le phénomène, prenons une image d’une tasse. Au bout de trois transformations du boulanger, l’image est complètement brouillée. En théorie, rien n’empêche de passer le film à l’envers en faisant trois transformations inverses et voilà notre tasse qui réapparaît comme si de rien n’était. Oui mais. Dans la vraie vie, si l’image mélangée bouge entre temps d’un micro-millième de chouïa, vous ne retombez plus du tout sur vos pieds. Voici ce qui se passe si on tourne la troisième image d’un degré avant de lui appliquer les transformations inverses. Adieu la tasse!

On retrouve de façon assez inattendue le deuxième principe de thermodynamique qui interdit l’évolution spontanés du désordre vers l’ordre. Mais dans cet exemple, la flèche du temps ne tient pas à une question de probabilité, au fait que l’état ordonné est infiniment moins probable qu’un quelconque état différent. Ici la flèche du temps naît de l’extraordinaire instabilité de l’évolution de chaque point…

Sources:
B Gréhant, Et si la science était de l’hébreu (le chapitre qui traite ce sujet est disponible en pdf)
I Prigogine et I Stenger, La fin des certitudes: temps, chaos et les lois de la nature.
La transformation de la tasse a été faite avec le logiciel libre de BouMaton (disponible ici si vous voulez vous amuser aussi)

Billets connexes:
Votre boulanger est-il discret, le billet précédent

dimanche 4 décembre 2011

Votre boulanger est-il discret? (1/2)

Quelle différence faites-vous entre l’infini et le « très très grand »? Comment vous représentez-vous l’ensemble des nombres rationnels contenus dans l’intervalle [0,1]? Bon, je ne vous sens pas franchement emballés par mes questions métaphysiques, mais ne zappez pas tout de suite! Pour y répondre, je vous propose un phénomène bluffant qui non seulement prend vos intuitions à contre-pied, mais qui illustre également la différence qualitative entre fini et infini, discret et continu. Et si au pire vous n’y comprenez rien, l’effet spectaculaire en vaut la peine, promis!

PART1: quelle différence entre fini et infini?

Pour bien mélanger son pétrin, le boulanger prend un carré de pâte, l’étire dans un sens puis le replie pour retomber sur son carré initial et il recommence: il étire puis replie pendant une bonne demi-heure (ça muscle!):

La transformation du boulanger

Si au lieu de faire ça avec une pâte à pain, on s’amuse à faire la même chose avec une image numérique, l’image se brouille très vite:Assez rapidement l’image se brouille…

Evidemment, comme on ne peut pas étirer chaque pixel on a un tout petit peu triché: pour étirer une ligne, on est obligé d’interpénétrer chaque ligne paire avec la ligne impaire suivante avant de replier le tout.

Les mystères de l’éternel retour

L’avantage sur la pâte à pain, c’est que c’est moins fatigant à faire et surtout ça va beaucoup plus vite. Au lieu de s’arrêter au bout d’une dizaine de mélanges comme ce feignant de boulanger, on peut laisser le logiciel tourner des milliers de fois. C’est le miracle de la technique. Mais le plus miraculeux c’est surtout qu’au bout d’un moment, l’image du départ revient comme par magie!

Magique!

Cette transformation très simple aurait-elle des propriétés spéciales? Même pas: on trouve sur internet plein d’autres transformations très différentes qui bouclent sur elles-mêmes de la même façon. Par exemple celle du photomaton qui « disperse » l’image initiale dans les quatre quarts du carré avant de recommencer:

La transformation du photomaton appliquée à l’image de la Joconde

Je me disais qu’il devait être affreusement compliqué de démontrer que « ça boucle », d’autant que le nombre d’itérations nécessaires pour retomber sur ses pieds est très sensible au nombre de pixels de l’image. La démonstration que propose JP Delahaye [1] est pourtant incroyablement simple.

Numérotons les pixels de l’image de 1 à N en fonction de leur position. La  transformation du boulanger envoie le pixel en position X1 à une position X2 qui lui est exclusivement réservée. La transformation du boulanger est donc une bijection entre les N pixels de l’image.  Appliquons  itérativement  cette transformation bijective à notre pixel situé  initialement en position X1, il devient:
X1->X2->X3->X4->….->XN
Puisque la transformation est bijective et qu’il n’y a que N pixels possibles, un peu de réflexion vous convaincra que notre point reviendra fatalement à sa position d’origine en X1 au bout d’un certain nombre d’itérations. Ansi à chaque pixel de l’image correspond un cycle de longueur inférieure à N, cycle au terme duquel il revient à sa position de départ. Tous les pixels appartenant à un cycle de longueur 10, reviennent à leur position initiale au bout de 10 transformations, 20, 30, 40 etc.
Evidemment deux pixels différents peuvent appartenir à des cycles de  longueurs différentes l1 et l2, mais ils seront tous les deux revenus à leur position initiale au bout de l1*l2 cycles.
On peut en principe connaître la liste de toutes les longueurs de cycles correspondant aux pixels d’une image. Supposons par exemple qu’il n’y ait que trois cycles possibles, de longueur 3, 7 et 10. L’image reviendra identique à elle-même au bout de 3*7*10=210 itérations.
De façon générale, si l’on connaît toutes les longueurs de cycle d’une image, le « temps de retour » de l’image sera égal au plus petit commun multiple de toutes les longueurs de cycles. Dans le pire des cas (si chaque point appartient à un cycle de longueur différente) l’image initiale revient au bout de N! cycles. Ca peut être long, mais ça marche à tous les coups!

Tout s’explique!
Ce raisonnement est valable quelle que soit la nature de la transformation (Boulanger, photomaton ou autre), il suffit juste qu’elle soit bijective. Rigolo non? Au passage, cette démonstration aide à comprendre pourquoi au cours des itérations on voit de temps en temps apparaître  l’image initiale un peu brouillée: c’est le cas chaque fois que le nombre d’itérations est un multiple des longueurs de cycles les plus fréquentes. Les très nombreux pixels correspondant à ces cycles sont alors revenus à leur position initiale – c’est ce qui fait qu’on reconnaît l’image- mais pas les autres -c’est ce qui fait que l’image est floue: