headlogo

L'ensemble de Mandelbrot

hd

Qu'est-ce que l'ensemble de Mandelbrot

Soit la suite définie par:

zn+1  = zn2 + c  avec  z0 = (0,0)

Cette suite dépend du paramètre c. Si ||zn|| reste borné pour tout n pour un c fixé, alors c appartient à l'ensemble de Mandelbrot.

Il y a quelques propriétés utiles pour calculer l'ensemble de Mandelbrot. Tout d'abord, tout point c tel que ||c|| est plus grand que 2 n'appartient pas à l'ensemble. Cela dérive de la propriété classique :

 | ||a||-||b|| | <= ||a+b||

qui vient de l'inégalité triangulaire.

||zn+1|| = ||zn2+c|| >= | ||zn2||-||c|| 

Supposons que ||c||=2+a, avec a>0 et que pour un n>0 nous avons

 ||zn||>2+na 

Alors:

||zn+1|| >= | ||zn2||-||c|| | > (2+na)2-2-a > 2+3na+(na)2 > 2+(n+1)a

Donc si la propriété est vraie pour n, elle est vraie pour n+1. Comme elle est vraie pour n=1, elle est vraie pour tout n, et ||zn|| n'est pas borné si ||c||>2.

De la même façon, il est facile de montrer que si pour c fixé, il existe k tel que ||zk||>2, alors c n'est pas dans l'ensemble de Mandelbrot.

Pour trouver les points de l'ensemble de Mandelbrot, il suffit de travailler sur les points à l'intérieur du cercle (O,R=2), et le calcul s'arrête dès que l'on trouve k tel que ||zk||>2.

A proprement parlé, l'ensemble de Mandelbrot devrait être représenté en noir et blanc, suivant que le point est, ou n'est pas, dans l'ensemble.

hd

Mais très vite, la première valeur k telle que ||zk||>2 fut utilisé comme un index de couleur. Il y a deux problèmes majeurs pour avoir des ensembles de Mandelbrot dont la représentation est plaisante.
D'une part, il faut choisir une borne supérieure d'arrêt de la recherche. En effet, le fait pour un point d'appartenir à l'ensemble de Mandelbrot est indécidable dans le cas général. Bien entendu si l'on trouve k tel que ||zk||>2 pour c fixé alors c n'appartient pas à l'ensemble. Il existe aussi des points pour lesquels il est possible de prouver qu'ils sont dans l'ensemble (le cas trivial est (0,0). Mais dans le cas général, il est impossible de déterminer l'appartenance ou la non appartenance, et il est impossible de calculer la suite ||zn|| jusqu'à l'infini. Il faut donc choisir une borne supérieur U d'arrêt du calcul. Cette borne supérieure détermine la qualité du détail de la représentation de l'ensemble, en particulier sur la frontière. Plus U est élevé, meilleure est la qualité, mais plus long est le temps de calcul.
D'autre part, il faut choisir une bonne table de couleurs. Ici, l'image suivante a été construite pour donner une bonne représentation de l'ensemble de Mandelbrot vu "de haut".

hd

Mais avec une telle représentation, il serait impossible de zoomer à l'intérieur de l'ensemble , car on a favorisé une différenciation des couleurs très forte, au détriment de la précision pour les valeurs de k élevés. En revanche la représentation suivante est elle adaptée à un zoom profond.

hd

On peut voir ce que cela donne lorsque l'on descend dans l'ensemble en gardant la même table de couleurs:

hd

Ce type de représentation est indispensable lorsque l'on doit réaliser un film zoomant dans l'ensemble, comme on peut en voir un à la fin de cette page. On comprendra d'ailleurs mieux en visionnant le film à quel point l'ensemble est complexe, et combien le choix de la table de couleurs est important.
Lorsque l'on zoome à l'intérieur de l'ensemble, choisir U (la borne sup) est aussi une des difficultés principales. Mais il y a d'autres problèmes, comme la précision numérique du processeur...

J'ai commencé à travailler sur les ensembles de Mandelbrot pendant mon stage de fin d'études en 1985 chez Jean-François Colonna au Lactamme à l'X. C'était les débuts des représentations des ensembles de Mandelbrot sous forme graphique et j'ai écrit les premières routines en assembleur sur calculateur Ridge RISC32 (vendu en France par Bull sous le nom de SPS9). Je continue à pratiquer cette activité comme un hobby, et je réécris régulièrement des petits bouts de programme en assembleur quand de nouveaux processeurs sont disponibles.

On trouvera dans le fichier suivant le code en assembleur utilisant le jeu d'instructions EMMX du Pentium3. C'est un jeu d'instruction SIMD qui permet de travailler simultanément sur des vecteurs de 4 éléments en simple précision (24 bits de mantisse, 8 bits d'exposant).

Il est intéressant d'estimer la performance de ce type de processeur. Sur un P-3 800Mhz, une image 1280x1024 avec U=256 est calculé 0.77 second. La routine en assembleur retourne le nombre de boucles réalisées et permet de calculer le nombre exact d'instructions effectuées. On sait que chaque boucle contient 15 instructions de calcul flottant vectorial (VFlop) et deux instructions de calcul entier. On exécute 21147490boucles, donc 317212350 VFlop sont réalisés. Cela donne 0.41 GVFlops, soit 1.6 GFlops. Sur un P-4 2.53Ghz, le même programme prend 0.29 s, soit 1.1GVflops ou 4.4GFlops. Sur un Athlon 2100+ (fréquence: 1.7Ghz), il faut 0.35s, pour une performance de 3.6GFlops.

Avec le Pentium4, on peut utiliser des vecteurs ayant deux éléments en double précision au lieu de 4 élements en simple précision. Le résultat est évidemment plus lent, mais bien plus précis. La routine en assembleur est ici . Sur un P-4 a 2.53Ghz, le programme exécute 41588101 boucle en 0.52s, pour une performance de 2.4GFlops.

En combinant plusieurs techniques (utilisation de routines vectorielles, connexité locale, parallélisation sur réseau avec pvm, utilisation de processeurs multi-coeurs), on arrive à calculer des films complets de voyage dans l'ensemble de Mandelbrot en un temps très raisonnable. On peut en voir un ci-dessous. Il a été réalisé "à la main" en utilisant des outils "home-made": un module de navigation en temps réel à la souris dans l'ensemble pour sélectionner les zones, un module de calcul rapide pour construire les frames une fois le schéma de déplacement choisi et un encoder vidéo standard (mencoder). La réalisation complète du film ne prend pas plus d'une heure. Attention, le débit de lecture est très élevé pour préserver la qualité de l'image. La première lecture sera certainement saccadée, sauf si vous disposez d'un très haut débit. Le mieux est donc de le lire une première fois pour le mettre en cache, puis de le repasser pour apprécier le zoom.


Retour à ma page principale

Le téléchargement ou la reproduction des documents et photographies présents sur ce site sont autorisés à condition que leur origine soit explicitement mentionnée et que leur utilisation se limite à des fins non commerciales, notamment de recherche, d'éducation et d'enseignement.
Tous droits réservés.

Dernière modification: 14:15, 09/01/2012 xhtml validation