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.
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".
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.
On peut voir ce que cela donne lorsque l'on descend dans l'ensemble en gardant la même table de couleurs:
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.
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: 09:48, 22/02/2024