Fractal Generator Project

De la génération des fractales
Théorie et Applications

John Bonobo
PhD Applied Mathematics
Bonobo Future Systems Inc. - Nancy, Berlin, 2000-2004.


Table des matières


Notations

1. Introduction


2. Construction d'un ensemble fractal par itération d'une fonction complexe

2.1. Construction théorique, définitions et propriétés élémentaires
2.1.1. Orbites et ensemble fractal
2.1.2. Stabilité des orbites
2.2. Quelques exemples
2.2.1. Les fractales de Mandelbrot et de Julia
2.2.2. Les fractales de Mandelbrot et Julia généralisées
2.2.3. Les fractales de Newton
2.3. Algorithmes de représentation
2.3.1. Premier temps de sortie
2.3.2. Estimateurs de distance
2.3.3. Temps d'entrée (ou pièges à orbites)
2.3.4. Angle de sortie, courbure
2.3.5. Statistiques
2.3.6. Suites de Cauchy et orbites périodiques
2.3.7. Densité des orbites

3. Les fractales de Lyapunov

3.1. Formule d'itération
3.2. Exposant de Lyapunov

4. Transformations du plan

4.1. Effet de loupe gaussienne
4.2. Inversion du plan complexe
4.3. Projection sur la sphère de Riemann

Références


Notations

L'emploi du HTML rend problématique l'affichage de certains symboles mathématiques, par simplicité nous utiliserons les notations suivantes :

N Ensemble des entiers naturels : 0,1,2,3,...
R Ensemble des nombres réels
Rd Espace euclidien à d dimensions
C Ensemble des nombres complexes (de la forme z = x + iy, avec x et y dans R et i2= −1)
  
Dans tout ce texte on ne fera pas la distinction entre l'ensemble R2 et le plan complexe C, autrement dit on assimile tout couple (x,y) ∈ R2 au nombre complexe z = x + iy ∈ C correspondant. On ne refera pas la théorie des nombres complexes, qui permettent ici une écriture plus naturelle et plus simple des formules.

 x 
Racine carrée de x
||(x,y)|| Norme du vecteur (x,y)∈R2, autrement dit la distance entre (x,y) et l'origine (0,0). 
Par le théorème de Pythagore, ||(x,y)|| =  √  x2 + y2 .
z Complexe conjugué de z : si z = x + iy alors z = x − iy.
|z| Module du nombre complexe z : si z = x + iy alors |z|=||(x,y)||.
Infini
f(n)(x)  f itérée n fois : f(n)(x)=f(f(f(...f(x)...)))
  
F Ensemble fractal générique
M Ensemble fractal de Mandelbrot
J(C) Ensemble fractal de Julia "plein" (de paramètre C dans C)
N(P) Ensemble fractal de Newton (associé au polynome complexe P)

Rappels sur les nombres complexes :
On introduit le nombre "imaginaire" i tel que i2= −1.

Forme cartésienne :
z = x + i y avec x et y dans R.
x est la partie réelle de z et y la partie imaginaire de z.

Forme polaire : (on mesure ici les angles en radians, on rappelle que π radians = 180 degrés)
z = r e avec r > 0 et θ∈[0;2π[.
r est le module ou la norme de z (notée |z|) et θ l'argument de z.

Passage d'une forme à l'autre :
On a e = cos(θ) + i sin(θ) (formule d'Euler), d'où
x = r cos θ et y = r sin θ.
D'autre part, grâce au théorème de Pythagore,
r = |z| =  √  x2 + y2 
et, dans un triangle rectangle la tangente est le rapport entre le coté adjacent et le coté opposé à l'angle droit, autrement dit tg(θ)=y/x, donc en tenant compte de l'orientation et en traitant à part le cas x=0,
si x ≠ 0 :     θ = arctg (y/x) si x > 0
θ = arctg (y/x) +π     si x < 0
 
si x = 0 : θ = π/2 si y > 0
θ = 3π/2 si y < 0.


Représentation cartésienne et polaire d'un nombre complexe

Représentation cartésienne et polaire d'un nombre complexe z
Règles de calcul :
Soient z = x + i y = r e et z′ = x′ + i y′ = r′ eiθ′.

Addition : z + z′ = (x + x′) + i(y + y′)
Multiplication : z z′ = (x x′ − y y′) + i(x y′ + x′ y) = r r′ ⋅ ei(θ + θ′)
Division : z/z′ = (x x′ + y y′)/(x′2 + y′2) + i(&minus x y′ + x′ y)/(x′2 + y′2) = r/r′ ⋅ ei(θ - θ′)
Puissance : zz′ = e z′(log r + iθ) = e x′ log r − y′ θ [ cos (x′ θ + y′ log r ) + i sin (x′ θ + y′ log r ) ]


De la gnration des fractales
Thorie et applications

Par le docteur John Bonobo


Table des matires

Avant-propos
Preface
Notations
Introduction

1. Construction d'un ensemble fractal par itration d'une fonction complexe

1.1. Construction thorique, dfinitions et proprits lmentaires
1.1.1. Orbites et ensemble fractal
1.1.2. Stabilit des orbites
1.2. Quelques exemples
1.1.1. Les fractales de Mandelbrot et de Julia
1.1.1.1. Un lien entre Mandelbrot et Julia
1.1.1.2. Description fine du Mandelbrot
1.1.1.3. Un premier algorithme pour tracer les Julia : La mthode d'itration inverse
1.1.2. Les fractales de Mandelbrot et Julia gnralises
1.1.3. Les fractales de Newton
1.2. Algorithmes de reprsentation
1.2.1. Premier temps de sortie
1.2.2. Suites de Cauchy et orbites priodiques

2. Les fractales de Lyapunov

2.1. Formule d'itration
2.2. Exposant de Lyapunov

3. Transformations du plan

3.1. Loupe gaussienne
3.2. Inversion du plan
3.3. Projection sur la sphre de Riemann

Rfrences


Sommaire rapide




Au sujet de l'exp, c'etait sur en fait, mais c'est hyper long (et en fait on a l'impression que ca donne un dessin qui n'est fractal qu'au voisinage d'un point... pas tres interessant). ca serait sans doute avantageusement remplac par une approximation polynomiale de l'exponentielle. z+z2/2+z3/6+...+z^n/(n!) pour un n pas trop trop grand non plus (5).

2. Les fractales de Lyapunov

Alexander Markus Lyapunov, 1857-1918

2.1. Formule d'itration


On part d'un P0 donn entre 0 et 1, en general 0.5. On construit ensuite l'orbite (Pn), contrairement Mandelbrot-Julia-Newton, c'est une suite de dimension 1 et pas 2.

Pn+1 = k * Pn * (1−Pn) = f (Pn)      avec f(x)=kx(1−x).

Cette quation peut etre vue comme une equation simpliste d'evolution d'une population, ou plutot une densit de population car Pn est une proportion (entre 0 et 1), genre le pourcentage de la population maximale supporte par le territoire.
la ou ca devient joli, c'est quand on choisit 2 valeurs pour k, appelons les k1 et k2.
Ensuite on choisit une sequence (une facon d'alterner k_1 et k_2 lors des iterations), par exemple

k1, k2, k1, k2, k1, k2, k1, k2 ... (ab)
k1, k2, k2, k1, k1, k2, k2, k1 ... (abba)
etc.
Plus c'est compliqu plus c'est beau, par exemple aaabbaabbba ou aaaaabbabbbaaaaaaabaaaabbbbb ca doit etre tres joli.

2.2. Exposant de Lyapunov


On reprsente une fractale bimensionnelle en fonction de l'abcisse k1 et de l'ordonne k2 :
On itre la formule donnant (Pn(k1,k2)) un grand nombre NITER de fois et, on colorie le point (k1,k2) en fonction de l'exposant de Lyapunov associ a la suite (Pn) c'est a dire

A(k1,k2) = limn → ∞ (1/n) * ( log(f '(P1)) + log(f '(P2)) + ... + log(f '(Pn)) )       avec ici f '(x)=k(1−2x).

Comme on s'arrete a NITER, on calcule donc
A(k1,k2) = (1/NITER) * ( log(k(1−2P1)) + log(k(1−2P2)) + ... + log(k(1−2PNITER)) ).

En clair, pour chaque point (k1,k2) de la portion de plan reprsente, on part de A=0 et a chaque iteration on ajoute log(k(1−2Pn)) a A. Souvent on ignore les premieres valeurs de Pn (par exemple si on fait 1000 iterations, on touche pas a A jusque n=500) , c'est la fin de la suite qui determine tout.
Quand A est negatif, la suite (Pn) converge, quand A est positif, elle est chaotique. c'est donc les coins ou A est positif qui sont jolis, et fractals (parfois on met juste deux couleurs, noir ou blanc en fonction du signe de A, c'est deja pas mal pour commencer).
j'ai jou un peu avec fractal explorer 2 sinon, (le truc qui manque chez eux c'est pouvoir taper la fonction, si on fait pas ca on apporte presque rien en fait a part le java) t'as essay les "filtres" ? ca donne des resultats magnifiques. et c'est une facon de colorier l'interieur noir des fractales. le truc est simple : tu calcules comme avant le nombre d'iteration avant de sortir d'une boule (essaie aussi avec un carr, d'ailleurs c'est plus rapide de tester −2<x<2 ou −2<y<2 (ou bien |x|+ |y|<2) que x*x+y*y<4 ) et a ce nombre tu ajoutes un truc, par exemple l'exposant de lyapunov de la suite x_n ou y_n. donc pour chaque point (x,y), pour l'instant tu calcules N(x,y) qui est le premier entier n tel que (x_n,y_n) sorte d'un certain domaine. et jusque la, tu mets une couleur en fonction de n, ou de cos(n). ben c'est simple ce qu'ils appellent filtre (enfin ce que j'ai cru comprendre est simple ;-) ) a la place de mettre la couleur en fonction de N(x,y), tu fais la meme chose mais en fonction de N(x,y)+A(x,y). ou A est une autre quantit calcule lors de l'iteration, par exemple l'exposant de Lyapunov de la suite (x_n) ou (y_n) ou (x_n/y_n), etc (il faut une suite reelle unidimensionnelle). par exemple A = une petite constante (genre de l'ordre de 1/n) * somme de 1 n de log(f′(x_n,y_n)) l'entier n c'est cens etre le nombre max d'iterations. la fonction f c'est celle qui definit l'iteration, par exemple x_n+1=f(x_n,y_n) (si on s'interesse a x, on considere y constant, on va juste deriver par rapport a x) dans mandelbrot f=x2+y2 donc f′=2x pour la suite x_n. donc A = constante * somme de 1 a n de log(x_n) ca doit etre pas mal. A est un nombre qui sera tres negatif au voisinage de points peu chaotiques (par exemple (0,0) qui est stable) il y a des points tels que z_n+2=z_n (en fait 4, on peut meme resoudre cette equation), A y sera un peu moins negatif. encore un peu moins negatif pres des points tels que z_n+3=z_n. etc. et il finira par etre positif la ou il ya chaos, c'est a dire pres de la frontiere. A decrit la stabilit de l'orbite. l'orbite en fait c'est pas autre chose que la suite (x_n,y_n), c'est comment bouge le point de depart quand on itere. ce que je disais avant c'est : il y a des orbites periodiques, de periode 1,2,3, etc. C'est interessant d'etudier les orbites. je t'en reparlerai. (notamment, dans fractal explorer, quand tu ouvres la fenetre julia, le julia correspondant au point ou est la souris est automatiquement dessin, et ca c'est classe. on pourrait dessiner les orbites en temps reel de la meme facon.) essaie les fractales de Lyapunov, c'est rigolo. Et aussi, faudrait que tu m'explique en dtail ces histoires de projections sur la sphre de Riemann.

Transformations du plan

ca c'est tres simple. tu fais une boucle sur des entiers (i,j) qui representent les points de la fenetre d'affichage. jusque la, tu calcules les points "reels" (x,y) de facon lineaire, c'est a dire x= gauche + largeur/taille * i l'idee ici est de pas prendre une fonction lineaire. si ta fractale etait une grille rectiligne, ben ca donnerait une grille deforme, non rectiligne.

La loupe gaussienne

on va commencer par un exemple simple : une "loupe gaussienne" centr en (0,0) : plutot que d'ecrire une formule complique a partir de (i,j), on a autant a partir de (x,y). donc tu fais ta boucle sur (i,j), tu calcules (x,y), et au lieu de faire les iterations avec x_0=x et y_0=y tu prends : x'= x * (1+K_1*exp(−K_2*y*y) ) y'= y * (1+K_1*exp(−K_2*x*x) ) o K_1 est un coefficient de grossissement (0 change rien, 1 ca va jusqu 'a une taille double) et K_2 c'est, en tres gros, le diametre de la loupe. (0 ca donne un zoom lineaire (tout est zoom avec le facteur 1+K_1 jusqu'a l'infini quoi), 1000 ca changera presque rien sauf tres pres de (0,0). K_2 est a fixer en fonction de la taille de la fenetre, pour le carr [−1,1]^2 je prendrais K_1=1 et K_2=1) (remarquons que faire des zooms a la souris n'est plus trop possible, ou alors il faudrait afficher le rectangle dform par la transformation : c'est donc plus un rectangle)

La projection sur la sphre de Riemann

La sphere de Riemann, c'est un peu plus compliqu parcequ'au final on dessine tout dans un disque. L'idee c'est de considerer la fractale dessine sur le plan comme un papier peint (mais tres tres elastique), qu'on plaque sur la sphere. le disque de rayon 1 devient l'hemisphere nord, le point (0,0) devient le pole nord. le cercle de rayon 1 devient l'equateur l'exterieur du disque est donc plaqu sur l'hemisphere sud, le point "infini" devient le pole sud. donc, il faut deja parametrer une sphere. c'est ca qui est compliqu a ecrire en fait. pour chaque (i,j) dans un disque sur l'ecran, on calcule longitude a (de 0 a 360) et latitude b (de −90 a 90) b>0 c'est le nord b=0 l'equateur et b<0 le sud. disons qu'on ne fait pas de rotation et qu'on dessine un disque de diametre [−100,100], ... plus clairement : boucle sur l'ordonne j de −100 a 100 puis boucle sur l'abcisse i de − racine carre de (100*100−j*j) jusqu'a + racine carre de (100*100−j*j) ca donne, par bricolage a partir de la formule des coordonnes spheriques : a= arcsin ( i / racine{i*i + j*j}) + 90 (si on prend l'arcsin en degr; c'est plus clair a ecrire) b= arcsin ( j / racine{i*i + j*j}) (si jamais i=0 et j=0, alors a=0 et b=0, ca evite de diviser par 0) Pour faire une rotation, rien de plus simple maintenant qu'on bosse avec des angles, il suffit d'ajouter. la a va de 0 a 180 et b de −90 90. on a bien une demishpere avec le pole nord en haut et le pole sud en bas, l'intersection entre le meridien 0 et l'equateur est le point gauche du disque. pour faire une rotation de 37 degres en x et de 48 degres en y, il suffit de prendre a'= a + 37 b'= b + 48 ensuite, on applique la transformation de riemann : si b est positif x=1/90 * (90−b) *cos(a) y=1/90 * (90−b) *sin(a) 1/90 * (90−b) est la distance au pole nord (donc au point 0,0), a est l'angle. si b est negatif x=90/(90+b)*cos(a) y=90/(90+b)*sin(a) on a juste invers : 90/90+b est la distance a l'infini (si b tend vers −90 alors x et y tendent vers l'infini, c'est bien ce qu'on voulait) tout ca se recolle bien a l'equateur, on est contents. et on fait l'iteration (x_n,y_n) comme d'hab en partant de x,y. evidemment il faut toujours faire des tests supplementaires quand on fait un programme. par exemple si jamais b=−90 ca va faire division par 0 (donc on fait rien en ce point, on choisit de le mettre en noir ou en rouge mais y'a rien a calculer).
Tiens voil un lien interessant sur les fractales, ou plutot un site partir du quel il y a des liens interessants ( mais souvent en anglais ) : http://fractals.iut.u-bordeaux1.fr/jpl/jpl01.html En particulier, il y a pas mal de lien sur cette page http://fractals.iut.u-bordeaux1.fr/jpl/couleurs.html Bonne idee, cultivons nous. Le site dont tu parles est excellent pour la coloration. une bonne idee aussi la, mettre une image a la place de la couleur : http://www.xmission.com/~legalize/fractals/textured-mandel.html Moi de mon cot ce que j'aimerais retrouver... (en fait un jour j'tais tomb sur un bouquin fabuleux sur les fractales "the Beauty of Fractals " by Peitgen et al. un enorme bouquin grand format avec des images... indescriptibles et plein de formules gniales et d'explications, avec meme des bouts de demonstrations, mais hyper cher. A part ca j'ai lu... "le" bouquin de mandelbrot dont je ne suis sur du titre, la est toute ma culture litteraire en fractale.)

Potentiel continu et lignes de champ

les lignes de champs de M. (nous appelerons maintenant M l'ensemble de Mandelbrot) c'est un truc qui marche pour n'importe quelle fractales de type iteration de polynome (donc a priori pas les lyapunov) on les voit la. http://www.xmission.com/~legalize/fractals/field-lines.html il ne file pas la formule helas.
Voila ce que l'on sait dessiner facilement par l'algorithme que tu connais. Imaginons maintenant que je ne veuille pas dessiner la ligne de potentiel 1Volt ni 2V ni 3V, mais la ligne 1.5V ou 2.79V ? zut, comment faire pi itrations ? evidemment on peut pas. Mais, il y a une formule. la formule du potentiel continu. Que j'ai oubli. Ca ressemble a l'exposant de Lyapunov, on fait toujours l'itration de la suite complexe (z_n), mais il faut la faire jusqu'au bout (toujours jusque 1000 par exemple), meme quand (z_n) sort du domaine. Et on fait une somme et y'a du log. donc forcement tout a un prix c'est plus long. Ca permet de faire vraiment un continuum lisse autour du mandelbrot. En 24bits de couleurs, c'est merveilleux ce truc. Et il y avait une autre formule, pour le meme prix. Les lignes de champs. que tu vois sur le site que je te montre. C'est simplement les perpendiculaires aux L_n. Physiquement ca represente la direction dans laquelle le clou est attir vers M.

Certains filtres comme |x|,|y| peut-etre de Fractal Explorer (FE), font apparaitre en transparence des motifs qui ressemblent aux lignes de champ. ou a certaines. elles sont en general perpendiculaires a la frontiere (t'as vu que tu peux augmenter l'intensit ? je t'enverrai une image que j'ai fait hier soir ou il y a un effet d'arbre sur M. Les spirales complexes ressemblent a des buissons de feuilles et les traces du filtres foncent aux milieu comme des branches. ca ressemble vraiment a n(z)+A(z), n nombre d'iteration (potentiel) et A ... un truc comme la drive du potentiel continu. le champ (la perpendiculaire, ou normale) est la derive (le gradient) du potentiel. dans lyapunov ya de la somme de log de derives. ca ressemble trop. donc... il faut vraiment essayer un truc comme ca. chez FE ils ne donnent pas les formules des filtres, si ? wouhou regarde en bas http://linas.org/art-gallery/escape/ray.html voila j'ai bien fait de te parler j'ai clarifi mes ides et j'ai trouv. C'est trop classe les images d'en bas hein ? ne trouves tu pas que la derniere "lanfing rays" fait penser aux motifs des filtres FE ? Douady je crois qu'il est coauteur du bouquin dont je te parlais avec Peitgen. Je regarde les formules et je te suggererai des algos precis. Dis moi si y'a des trucs pas clairs par exemple pour la projection sur la sphere de Riemann. Veux tu plus de details sur l'algo ?


Haut de page - Page précédente : - Page suivante : - - Sommaire - Notations

Références

Livres et articles

[Bar88] "Fractals Everywhere", Michael Barnsley, Academic Press, San Diego, 1988.

[CEJ91] "Fractals and chaos", A. J. Crilly, R. A. Earnshaw, H. Jones, editors, Springer-Verlag, New York, 1991.

[CM89] "Complex Universality" de Cvitanovic et Myrheim, Comm. Math. Phys. 121, 225-254 (1989)

[Dev89] "An Introduction to Chaotic Dynamical Systems", R. Devaney, Addison-Wesley, 1989.

[DK89] "Chaos and fractals: the mathematics behind the computer graphics", Robert L. Devaney, and Linda Keen, editors, American Mathematical Society, Providence, RI, 1989.

[Fei80] "Universal Behavior in Nonlinear Systems" Feigenbaum M.J., Los Alamos Science 1, 4-27 (1980)

[FR92] "A Generalized Mandelbrot Set and the Role of Critical Points", M. Frame and J. Robertson, Computers and Graphics 16,No. 1 (1992), pages 35-40.

[Gle87] "La théorie du chaos : vers une nouvelle science" de James Gleick, traduit par Christian Jeanmougin (1999) (original : "Chaos : Making a New Science", Viking Press, New York, 1987)

[Jul18] "Mémoire sur l'itération des fractions rationnelles" de Gaston Julia, Journal de Mathématiques Pures et Appliquées, No. 8 (1918), pages 47-245

[JPS92] "Chaos and Fractals: New Frontiers of Science", H. Jürgens, H.-O. Peitgen, and D. Saupe, Springer, New York, 1992.

[Man75] "Les objets fractals : forme, hasard et dimension, survol du langage fractal" de Benoît Mandelbrot (1975)

[Man77] "The Fractal Geometry of Nature", B. B. Mandelbrot, Freeman, New York, 1977, 1982, 1983.

[PR86] "Beauty of Fractals: Images of Complex Dynamical Systems" de Heinz-Otto Peitgen et Peter H. Richter Springer, Berlin, New York, Tokyo (1986)

[PS89] "The Science of Fractal Images", H.-O. Peitgen and D. Saupe, Springer, Berlin, New York, 1989.

[H94]"A First Course in Discrete Dynamical Systems", R. Homlgren, Springer-Verlag, 1994.

Pages web

Un magnifique PDF sur la génération des fractales
Sur la coloration
Sur la coloration (nombreux liens)
Sur la coloration avec une texture
Lina's Art Gallery - Images et considérations mathématiques
Sur les lignes de champs
Benoît Mandelbrot
Benoît Mandelbrot (autre)
Gaston Julia
The Mandelbrot Set and Julia Sets
An introduction to fractals
Complex Analysis
A virtual investigation with interactive pictures : The Mandelbrot and Julia sets Anatomy and Chaotic dynamics (autre lien), références.
Fractal Frequently Asked Questions and Answers
A short walk through the Mandelbrot Set
Vocabulaire combinatoire de l'imagerie fractale (PDF)


Last modification : John Bonobo @ Tue 10 Dec 2013, 12:12:50.
Cette page respecte les standards définis par le W3C.