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
ou en python et plus généralement dans un polygone régulier