Chat d'Arnold

L'effet de l'opération modulo sur le parallélogramme.

On peut repérer les points sur le tore ${\displaystyle \mathbb {T} ^{2}}$ à l'aide de deux coordonnées x et y chacune dans l'intervalle [0, 1], cela revient à « déplier » ce tore pour obtenir un carré. L'application chat d'Arnold est définie par :

${\displaystyle \phi$ :{\begin{array}{lcl}\mathbb {T} ^{2}&\to &\mathbb {T} ^{2}\\P{\begin{pmatrix}x\\y\end{pmatrix}}&\mapsto &P'{\begin{pmatrix}(x+y)\mod 1\\(x+2y)\mod 1\end{pmatrix}}\end{array}}}

De façon intuitive, en raisonnant sur le carré [0,1]×[0, 1] représentant le tore déplié, cela revient d'abord à déformer le carré en un parallélogramme haut de 3 unités et large de 2. Ensuite, l'opération modulo remet les bouts qui dépassent du carré original dans ce carré (schéma ci-contre). Comme on travaille en réalité sur le tore et non dans le plan, l'opération modulo n'introduit pas de discontinuité.

L'application linéaire associée à l'application affine ${\displaystyle \phi }$ est une application linéaire bijective du tore dans lui-même (un automorphisme) dont la matrice est ${\displaystyle {\begin{pmatrix}1&1\\1&2\end{pmatrix}}}$.

Pour se faire une idée intuitive de l'effet d'ensemble de cette transformation, on peut ne plus raisonner sur un seul point, mais sur une image complète (illustration ci-dessus). On voit que l'image est « étirée » et « enroulée » sur le tore[2].

Le déterminant ${\displaystyle {\begin{vmatrix}1&1\\1&2\end{vmatrix}}}$ vaut 1, donc la fonction chat d'Arnold conserve les aires.

Si l'on calcule les valeurs propres, on trouve deux valeurs propres réelles, l'une plus grande que 1, l'autre plus petite que 1 :

${\displaystyle \lambda _{1}={\frac {3+{\sqrt {5}}}{2}}>1}$

${\displaystyle \lambda _{2}={\frac {3-{\sqrt {5}}}{2}}<1}$

${\displaystyle \lambda _{1}\lambda _{2}=1}$

Comme la matrice est symétrique, les espaces propres sont orthogonaux. Ces deux axes (schéma plus haut) sont globalement stables par la transformation. Sur l'un d'entre eux, l'image se dilate (valeur propre plus grande que 1) alors que sur l'autre, l'image se contracte (valeur propre plus petite que 1). Le seul point invariant est l'origine du repère.

Si l'on applique plusieurs fois de suite la transformation, l'image va toujours plus s'étirer, tout en conservant la même aire. Elle va tendre vers une hélice dense sur le tore. Bien que l'opération de base soit continue et dérivable, une petite différence dans la position d'un point va conduire à une énorme différence dans la position du point résultat après un grand nombre d'applications de la transformation : c'est le chaos.

Retour à l'image de départ au bout de 300 itérations.

On peut définir une fonction de manière très semblable, mais sur un ensemble discontinu de points. En pratique, on prend une image constituée de pixels disjoints. Ses points ont des coordonnées entières dans l'intervalle {0, … N-1}. On pose :

${\displaystyle \psi$ :{\begin{array}{lcl}I_{N,N}&\to &I_{N,N}\\P{\begin{pmatrix}x\\y\end{pmatrix}}&\mapsto &P'{\begin{pmatrix}(x+y)\mod N\\(x+2y)\mod N\end{pmatrix}}\end{array}}}

Si l'on applique cette transformation plusieurs fois de suite, on constate un comportement radicalement différent et surprenant. En effet, on retrouve au bout d'un nombre fini d'itérations l'image de départ (image ci-contre).

La différence de comportement provient du fait que la fonction continue du chat d'Arnold peut toujours plus enrouler l'image de départ, elle travaille avec des nombres réels et ne se heurte pas à une limite de précision. Le traitement informatique, au contraire, consiste à permuter les pixels sans perdre d'information ; les permutations possibles de l'image étant en nombre fini, il ne peut que tomber dans un cycle.

La période du cycle dépend de la taille N de l'image de façon très irrégulière[3]. Un majorant de la période du cycle est 3 N[4].