Julia
and Mandelbrot
|
Julia
and Mandelbrot |
1 Pour les débutants en mathématiques
Julia, Mandelbrot, Fractales, nain aux pommes - des noms et des expressions qu’on entend des fois, mais qui ou qu'est ce que c’est?
Alors: Gaston M. Julia et Benoît B. Mandelbrot sont ou étaient des professeurs de mathématique sur un domaine d’activité - disons - un peu exceptionnel. Ils s’occupaient d’une fonction qui ne donnait pas des résultats en sens traditionnel, mais qui quand-même montre un comportement raisonnable. En dessinant les résultats on arrive a un objet à trois dimensions : longueur et largeur que l'on peut tracer sur un plan alors que pour la hauteur on fait un détour par les couleurs. On représente les niveaux bas en brun, les niveaux moyens en vert et les niveaux élevés en blanc. Ce qui apparaît est une fractale ou un détail de fractale.
La formule derrière un fractale selon Julia ou Mandelbrot n’est pas trop compliquée:
M = M^2 + C
Il est aussi possible d'écrire la formule de cette façon:
M - M^n + C
Ici on traite les puissances de 2 jusqu'à 21.
La formule M = M^n + C est exécutée autant de fois dans une boucle. On prend le M, on l’élève à la puissance, on additionne le C et remplace le M initial par le résultat de ces opérations. On répète cette opération jusqu'à ce que on arrive à une valeur définie et on quitte la boucle. A chaque passage on augmente un compteur de 1.
Il y’a des régions de l'image où cette valeur n'est jamais atteinte. Pour ne pas bloquer l'ordinateur on effectue un test qui permet de quitter l'itération. Si le compteur dépasse une valeur définie d’avance, on sort de la boucle.
La valeur du compteur est utilisée pour déterminer la couleur du point. Je dis « est utilisée » car il faut faire quelques opérations jusqu’au numéro de couleur à appliquer.
Il faut alimenter la formule en données pour faire des calculs. Je parle de données simples mais en réalité il s'agit d'une paire de coordonnés en x et y.
1.3.1 Cas
des fractales de Julia
Dans le cas des fractales de Julia, il faut deux paires de coordonnées. D'abord les coordonnées du point à calculer et encore cette constante C (aussi une paire de coordonnées).
Vous êtes sans doute impatients de connaître l'origine de cette constante. Je pense, que vous la comprendrez vous-même en jouant un peu avec l'applet qu'on trouve en http://hem.passagen.se/gweronimo/juliet.html
1.3.2 Cas
des fractales de Mandelbrot
Dans le cas des fractales de Mandelbrot, il ne faut qu’une seule paire de coordonnées, celles du point à calculer.
1.4 Détermination
des couleurs
La valeur du numéroteur sert à la détermination des couleurs. Comme le nombre des itérations est bien plus grand que le nombre de couleurs (env. 200), le nombre doit être réduit. Et comme ce nombre n'augmente pas de manière linéaire, on utilise le logarithme.
Une autre astuce pour arriver à une coloration optimale est de chercher dans l’image calculée la valeur la plus basse et la plus élevée et de distribuer les couleurs entre ces deux.
1.5 Agrandir
un détail (Mandelbrot seulement)
En "explorant" une fractale de Mandelbrot on a la possibilité de sélectionner un détail de l'image et de l'agrandir. Je vais vous le démontrer avec les images qui suivent :
Je vais agrandir l'ensemble Mandelbrot :
Le détail à agrandir est déjà marqué :
L'agrandissement montre le détail à agrandir suivant :
On peut de nouveau marquer un détail et l'agrandir :
Zut! La dernière image montre un petit désastre: on a dépassé la limite maximale d'agrandissement.
Je me rappelle bien d'un commentaire d'un grand (?) expert en ordinateurs: il me recommandait d'acheter un ordinateur de meilleure qualité afin de pouvoir obtenir une meilleure réslution. Comme si la précision (nombre de chiffres significatifs) était un problème d'ordinateur. Mais non, c'est celui du traducteur (compiler/linker) de mon programme en langage de machine.
Vous ne me croyez pas? Alors voici une petite illustration.
Une fois, j'avais des ennuis avec des compilateurs pour Basic et pour Pascal sur le même ordinateur. Tout mes collègues s'extasiaient sur le langage Pascal. Basic c'est que pour les ballots. --- Eh bien, libre à vous de le penser. J'avais donc une petite routine écrite en Basic. Je la traduisit en Pascal et développai les logiciels avec les outils correspondants. Et alors? Basic calculait juste, contrairement à Pascal...
Pourquoi ça ? Basic utilisait des fractions décimales à 15 chiffres, Pascal n'en utilisait que 12. Et moi? J'en ai tiré ma leçon.
1.7 Quel
est la précision de mon système?
Sur mon ordinateur,
il y a une installation de "Linux release 9 (Shrike)". Les calculs
importants se font avec des fractions décimales à 19 chiffres
significatifs.
Pour la définition d’un seul des 1001 pixels sur une ligne de l'image
trois de ces chiffres sont à réserver ; on peut penser que 999
est suffisant, mais comme dans l'ordinateur on n'utilise pas le système
décimal, ces 3 chiffres suffisent.
Pour l'agrandissement
restent 16 chiffres, le maximum sera donc: 9'999999'999'999'999. Soyons gentils
et disons 10 billiards: 10'000'000'000'000'000, notre facteur pour agrandissements.
Sur mon écran une image fait environ 25 cm de largeur. Multiplié
par 10 billiards ça donne 25'000'000'000'000 km, 25 billions de km. A
l'aide, c'est vrai??!!!
Alors, faisons une excursion vers l'espace, où une telle feuille de papier pourrait être déployée. Au centre je met notre soleil, puis les planètes : Pluton se trouve à une distance moyenne de 6 milliards de km - pas de problèmes pour dessiner son orbite. Et l'étoile fixe la plus proche? Alpha du Centaure se trouve à une distance 4,3 années-lumière, environ 40 billions de km? Peut-être peut-elle trouver sa place dans un coin de ma feuille ? (Mais dites, je n'ai vraiment pas fait d'erreur?)
1.8 Où
se trouvent des belles images?
Les images représentent les bords de l'ensemble de Mandelbrot.
Mais c'est mince, un dixième d'un millimètre autour de l'ensemble. Pas juste, c'est géant. Multiplié par 10 billiards ça donne une "autoroute" d'une largeur de 1 milliard de km. Et les images se trouvent quelque part là-dessus. Mais où donc? Aucune idée. Et si on les cherche, on ne trouve rien. Mais si on flâne un peu par ci et par là, on peut avoir de la chance. Parfois.
Une fois j'avais dans l'idée de placer toute sorte d'informations sur le fichier dans son nom, mais quelque temps plus tard j'ai eu la conviction que ça ne servait à rien. Alors les noms commencent avec une lettre majuscule, un A veut dire 2. et T 21. puissance. Puis après un souligné, un numéro individuel écrit en 5 "chiffres" de a jusqu'à z. Après un autre souligné suit l'agrandissement arrondi à une chiffre et l'indication du nombre de zéro comme suit: 3E06 signifie un agrandissement par 3 millions.
Mes programmes (Julia ou Mandelbrot) produisent les images sous forme de bitmaps (*.bmp). Toutes les pixels y sont représentés par le numéro de leur couleur, il y a encore une liste qui définit 256 couleurs en donnant les valeurs pour rouge, vert et bleu.
Pour raisons esthétiques, je tourne une image de 90 ou 180 dégrés et je me permets de supprimer des taches gênantes. Rien dautre.
Les fichiers bitmap sont assez gros, il est préférable de les transformer en fichiers plus compacts. Moi je préfère le format 'CompuServe Graphics Interchange', c.a.d *.gif. Les fichiers peuvent être un peu plus gros que sous le format JPEG (*.jpg), mais on préserve bien les couleurs de l’original. JPEG fait de nouvelles couleurs, pas trop grave en cas de photos.
Si quelqu'un aimerait savoir plus sur mes logiciels, je lui présente volontiers quelques extraits de mes sources. Mes programmes sont écrit en langage C. En outre il y a la "run-time-library" du MGR, un logiciel pour construire une surface, ressemblant à Windows.
Je ne peux pas distribuer
le MGR. Mais je pense que ce qui est important ce sont les fonctions qui déterminent
les itérations pour les différentes puissances, alors je vais
essayer de les expliquer.
Pour ne pas surcharger cette page, j'offre de distribuer le module contenant
toutes ces 20 fonctions par ex. en pièce jointe à un mail. Le
module fait 40 kB environ.
2.1.1 Cas
les fractales de Mandelbrot
Pour calculer un point de Mandelbrot, on n’a besoin que des coordonnées (x, y) du point.
2.1.2 Cas
des fractales de Julia
Ces fonctions nécessitent deux paires de coordonnées: celles du point qui est à calculer et encore une deuxième qui reste constante pour le calcul de toute une fractale de Julia.
Ce deuxième point correspond normalement à un point du bord d'une fractale de Mandelbrot. J'ai donc fait un logiciel qui d'une part calcule une «Mandelbrot» et d'autre une « Julia ». Alors on choisit un point dans la fractale de Mandelbrot :
Puis on passe à la partie Julia et on calcule cette fractale:
Calcul fait, l'image peut être recalculée pour remplir le cadre.
La formule
M = M^2 + C
peut être écrite comme suit:
M = M^n + C
Chez nous le n va de 2 jusqu’à 21. M^2 génère le "nain aux pommes" comme figure de base, les autres n’ont pas un nom spécial.
Je continue donc jusqu'à la puissance 21 pour deux raisons (pas tellement fortes): d'abord ça donne vingt puissances, pour ainsi dire commutateurs de sélection, 4 fois cinq boutons, et encore à cause de l'effort important nécessaire pour faire des fonctions de puissances encore plus élevées. En outre, il ne faut pas espérer beaucoup de nouveauté.
2.3 Paramètres
pour les fonctions
Pour calculer le nombre d'itérations les fonctions sont les mêmes, il y a seulement des différences en ce qui concerne les quatre paramètres.
Dans le cas de Mandelbrot, on commence par deux fois 0.0, man_x et man_y sont les coordonnées du point à traiter:
counts[x][y] = point[idx](0.0, 0.0, man_x, man_y, b_loops);
Dans le cas de Julia on commence avec le point à traiter, les autres sont les constantes provenant de la figure de Mandelbrot :
counts[x][y] = point[idx](jul_x, jul_y, man_x, man_y, j_loops);
point[]() est un champ de fonctions pour faire les calculs pour une puissance donnée. b_loops et j_loops sont les limitations du nombre de boucles permises.
Pour calculer un point on a donc:
M = M^n + C
avec n de 2 jusqu'a (dans mon cas) 21. Mais M et aussi C sont des nombres complexes. M est en réalité de la forme (x + iy), la partie réelle étant x et la partie imaginaire y. x et y sont les coordinées (réelles) du point. Pour C, c'est la même chose.
L'ordinateur ne sait pas traiter les valeurs imaginaires, mais il est bien sûr possible de traiter les x et les y séparément, de même pour i. Une fois le calcul fait, on peut assembler les résultats des calculs.
Faisons un exemple avec n = 4 et calculons (x - y)^4. Ça donne :
x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4
Quand les valeurs se suivent sans rien entre elles, le mathématicien y voit une multiplication (par exemple : xy signifie x que multiplie y). Le signe ^ remplace une élévation à la puissance (par exemple : 2^3 signifie 2 à la puissance 3, soit 8). Une élévation à la puissance est prioritaire pour le compilateur par rapport à une multiplication. L'expression 4x^3y se lit donc : 4 fois (x élevée à la puissance trois) multiplié par y.
Les nombres 4, 6, 4 ou plutôt 1, 4, 6, 4, 1 devant les x et les y peuvent désorienter. Ce sont les coefficients du polynôme que l'on peut réduire en utilisant le triangle de Pascal :
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
et cetera.
Un autre problème se pose avec le i. On peut le voir comme chose intermédiaire entre le + (plus) et le - (minus). Comme règle on a:
i^1 =>
i
i^2 => -
i^3 => -i
i^4 => +
et on arrive à
x^4 + 4ix^3y - 6x^2y^2 - 4ixy^3 + y^4
On groupe les expressions avec et sans i et sort le i de la parenthèse:
(x^4 - 6x^2y^2 + y^4) + i(4x^3y - 4xy^3)
Le i et les signes influencés sont mis en évidence par la couleur rouge.
2.5 Source
pour calculer une puissance 4
Partie du programme Julia. Pour Mandelbrot double devient long double.
/****************************************************************
*
* c a l c u l a t e _ p o i n t _ C
*
****************************************************************/
int calculate_point_C(jul_x, jul_y, man_x, man_y, loops)
double jul_x, jul_y, man_x, man_y;
int loops; /* maximum loops */ {
double x01 = jul_x,
x02 = 0.0, x03 = 0.0, /* initialize x and y variables */
x04 = 0.0,
y01 = jul_y,
y02 = 0.0,
y03 = 0.0,
y04 = 0.0, size = 0.0; /* variable to hold absolute dimension */
int count = 0; /* loop counter */
while(size <= (double)4 && count <= loops)
{
x02 = x01 * x01; x03 = x01 * x02;
x04 = x01 * x03; y02 = y01 * y01; /* avoid calculation of potencies */
y03 = y01 * y02; /* to save calculation time */
y04 = y01 * y03; /* adding up real and imaginary values */
y01 = (double)4 * x03 * y01
-(double)4 * x01 * y03 + man_y;
x01 = x04
-(double)6 * x02 * y02
+ y04 + man_x; size = x01 * x01 + y01 * y01; /* absolute dimension */ count++; /* loop counter */ } /* jump to while statement */ return count; /* return number of loops executed */ }
Notez: la valeur retournée est au moins 1 et au maximum loops.
2.6 Du
nombre d’iteratios à la couleur
Plus haut j'ai dit qu’on a environ 240 couleurs à disposition et que le maximum de boucles est normalement de 2400 ; il se peut qu'il soit nécessaire d'augmenter ce maximum lorsque les bords des ensembles de Mandelbrot deviennent vagues.
Un ensemble de Mandelbrot est à une «hauteur» infinie. Comme on limite le nombre d'itérations, on évite un blocage de l'ordinateur, mais on ne peut pas calculer tous les points de l'ensemble, on s'en approche seulement. Mais ce n'est pas grave, car les flancs d'une telle "montagne de Mandelbrot" sont tellement raides qu'on arrive quand même à une image nettement délimitée.
Partiellement cette «raideur» peut être compensée en prenant le logarithme des itérations. Un simple logarithme ne suffit presque jamais, alors on prend le double: couleur = log(log(counts) + 1.0). L'addition de 1.0 évite de prendre le logarithme d'une valeur négative.
Puis il faut normaliser ces résultats: valeur 1 est mise au 16 (les couleurs 0 - 15 sont réservée pour la surface du logiciel), et la valeur la plus élevée est mise à 254 (couleur pour l'ensemble de Mandelbrot). La couleur 255 est par définition blanche.
Il faut quand même donner une "forme" aux palettes : par ex. la zone pour un changement de rouge à vert doit être plus petite vers les «hautes» valeurs que vers les basses.
Un «truc» assez avantageux, est de chercher la valeur la plus basse dans l'image et de distribuer les couleurs de la palette entre cette valeur et la valeur de l'ensemble de Mandelbrot.
3 Autocritique et possibilités
Le choix des objets et de leur coloration est personnel et je sais bien que tout le monde n'aurait pas fait les mêmes choix. Je vais continuer à chercher des objets intéressants et à les publier ici, sans aucune promesse de me corriger.
En ce qui concerne les couleurs, je sais que par ex. PaintShop Pro offre la possibilité de changer la palette d’une image, on n’arrive aussi à construire une autre. Je ne dis pas que c’est facile à faire, mais ça fonctionne.
En outre on peut modifier les proportions: tout est permis.
Ne tirez pas sur le pianiste, il fait de son mieux pour bien «fractaliser».
