Algorithme IFS, fractales & jeu du chaos
Algorithme IFS
Vitesse de convergence vers l'attracteur
Si




Maintenant, si







![\[\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\]](fich-chaos-IMG/38.png)
ce qui montre que la distance entre


Ainsi, au bout de




Pour un rapport de contraction par exemple



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


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_1=F(M)=\bigcup_{i=1}^N f_i(M)
=\Bigl\{ f_1(M)\,; f_2(M)\,; \dots\,; f_N(M) \Bigr\}
\]](fich-chaos-IMG/53.png)
puis


![\[\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\]](fich-chaos-IMG/56.png)
et ainsi de suite.
À la n-ième itération,


Pour un IFS défini par exemple par 3 fonctions










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







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

Plus vertigineux: pour


Il vaut mieux réflechir un peu avant de lancer ce type de calcul, et augmenter timidement le nombre

Algorithme IFS
On calcule récursivement


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


