IFS, fractales & jeu du chaos

Algorithme IFS


Vitesse de convergence vers l'attracteur


Si $M$ est un point de l'attracteur $S$ alors $F(M)\subset S$, et on calcule et trace donc directement des points de $S$.
Maintenant, si $M$ n'est pas un point de $S$, en notant $M_n$ la suite des points obtenus avec la suite récurrente $M_0=M$ et $M_{n+1}=F\left( M_n\rp$ et $S$ l'ensemble limite, on a, comme $S=F\left( S\rp$:
\[\begin{array}{ll} \|S-M_n\|&=\left\| F\left( S\rp-F\left( M_{n-1}\rp\right\| \\[.8em] &\leqslant k \left\| S- M_{n-1}\right\| \\[.8em] &=k\left\| F\left( S\rp-F\left( M_{n-2}\rp\right\| \\[.8em] &\leqslant k\times k \left\| S- M_{n-2}\right\| \\[.8em] &=k^2\left\| F\left( S\rp-F\left( M_{n-3}\rp\right\| \\[.8em] &\leqslant k^2\times k \left\| S- M_{n-3}\right\| \\[.8em] &\dots \\[.8em] &\leqslant k^n \left\| S- M_0\right\| \enar\]

ce qui montre que la distance entre $M_n$ et $S$ décroît exponentiellement (il s'agit en fait ici d'une distance entre ensembles de points, voir les paragraphes sur les distances et la distance de Hausdorff).
Ainsi, au bout de $n$ itérations, la distance entre l'ensemble de points $M_n$ calculé par et l'attracteur est la distance initiale entre $M_0$ et l'attracteur multipliée par $k^n$.
Pour un rapport de contraction par exemple $k=0,5$, et $n=10$ itérations, on a $k^n=0,5^{10}\simeq 10^{-3}$: la distance a été divisée par mille.
Pour une figure de 1000 pixels sur 1000 pixels, soit une résolution d'un million de pixels (1 méga-pixel), la distance initiale est au pire d'environ 1000 pixels, et donc au bout de 10 itérations $M_n$ et $S$ sont à une distance inférieure à 1 pixel: numériquement, la suite récurrente a convergé.
Cela signifie en d'autres termes que l'algorithme converge rapidement, en quelques itérations, donc efficacement vers l'image fractale limite.

D'autres considérations sont par contre moins opimistes quant à cette efficacité, en pratique.


Approche de la complexité et temps de calcul


Si la convergence vers l'attracteur à partir d'un point quelconque est rapide, il ne faut pas négliger pour autant le calcul des itérations de l'opérateur de Hutchinson: pour $M$ un point du plan, $M_1=F(M)$ contient $N$ points,
\[M_1=F(M)=\bigcup_{i=1}^N f_i(M) =\Bigl\{ f_1(M)\,; f_2(M)\,; \dots\,; f_N(M) \Bigr\} \]

puis $M_2=F\left( M_1\rp=F(F(M))$ contient $N^2$ points
\[\begin{array}{ll} M_2=F(F(M)) &\dsp=\bigcup_{i=1}^N f_i(F(M)) \\[1.4em] &=\Bigl\{ f_1(F(M))\,; f_2(F(M))\,; \dots\,; f_N(F(M)) \Bigr\} \\[1em] &=\begin{array}[t]{ll} \Bigl\{ f_1(f_1(M))\,; f_1(f_2(M))\,; \dots\,; f_1(f_N(M))\,; \\[.6em] f_2(f_1(M))\,; f_2(f_2(M))\,; \dots\,; f_2(f_N(M))\,; \\[.6em] \dots \\[.6em] f_N(f_1(M))\,; f_N(f_2(M))\,; \dots\,; f_N(f_N(M)) \Bigr\} \end{array} \enar\]

et ainsi de suite.
À la n-ième itération, $M_n=F(F(\dots F(M)))$ contient $N^n$ points.
Pour un IFS défini par exemple par 3 fonctions $f_1$, $f_2$ et $f_3$, après $n=10$ itérations, $M_n$ contient $3^{10}=59\,049$ points, après $n=20$ itérations, $3^{20}\simeq 3,5.10^{9}$ de points, et pour $n=30$ itérations $3^{30}\simeq 2.10^{14}$ points.

Comme ces nombres ne sont pas forcément parlants: cela fait beaucoup, certes, mais pour un ordinateur moderne... il est intéressant de préciser quelques détails techniques.
Suposons que le calcul de l'image d'un point par une fonctions $f_i$ de l'IFS, soit $f_i(M)$ se fasse en $10^{-9}$ seconde (soit 1 milliard de ces calculs par seconde), alors les $n=20$ itérations nécessiteraient $3,5$ secondes, et les $n=30$ itérations environ $2.10^5$ secondes, soit environ 55 heures...

Encore plus remarquable est de ces données la taille pour un ordinateur. Un point est représenté par 2 coordonnées, soit deux nombres réels. En python par exemple un tel nombre nécessite basiquement 24 octets.
Ainsi, pour $n=20$ itérations, le stockage en mémoire de ces points nécessite quelques 3,5 milliards d'octets, ou 3,5 gigaoctets (Go) !
Plus vertigineux: pour $n=30$ itérations, il faut $2.10^{14}$ octets ou 200 000 Go soit aussi 200 teraoctets (To) !!!

Il vaut mieux réflechir un peu avant de lancer ce type de calcul, et augmenter timidement le nombre $N$ d'itérations…


Algorithme IFS


On calcule récursivement $M=F\left( M\rp=\Bigl\{f_1\left( M\rp\,;f_2\left( M\rp\,;\dots\,;f_N\left( M\rp\Bigr\}$ à partir d'un point $M$ pris au hasard, par exemple:

Algorithme
Entrer n
M est un point au hasard
Pour i de 1 à n
   T={}
   Pour j de 1 à N
      T={ T ; fj(M) }
   Fin
   M=T
Fin


Par exemple, en python:

Programme Python

def f(i,x,y):
    # definition de i-ème fonction 
    # de l'IFS
    return M
def F(M):
    Mr=[];
    for i in range(len(M)):
        x=M[i][0]
        y=M[i][1]
        for j in range(N):
            [xr,yr]=f(j,x,y)
            Mr=Mr+[(xr,yr)];
    return Mr

M=[(0,0)]
for i in range(n):
    M=F(M)
    
for i in range(len(M)):
    Point(M[i]) # Trace les points avec libxy
On peut utiliser une bibliothèque graphique python telle que libxy ou matplotlib.

Voir un exemple de programme en javascript: triangle ou fractale de Sierpiński ou en python et plus généralement dans un polygone régulier
.

Jeu du chaos


Lien


LongPage: h2: 2 - h3: 3