recevoir les news :: signaler une erreur :: statistiques visiteurs :: imprimer

ALGORITHMES | FRACTALS | ALGEBRE DE BOOLE | CRYPTOGRAPHIE | INFORMATIQUE QUANTIQUE

Les fractals sont des figures invariantes par changement d'échelle (nous parlons aussi de structures "autosimilaires") et représentées graphiquement par des suites récurrentes développées après un raisonnement ou un peu au hasard. Pour le commun des mortels, les fractals servent à faire joli. Mais ils ont des applications plus sérieuses:

Nous avons vu dans ce site que certaines de ces "séduisantes" images reproduisaient des phénomènes physiques (dynamique des populations pour le fractal de Feigenbaum, turbulences dans un fluide pour l'attracteur de Lorentz, dispositions des galaxies L-Fractals, amas et super-amas de galaxies,…). Les fractals ont également trouvé des application en musique (avec des logiciels générant de la musique fractale). Enfin, dans le domaine de l'infographie, les fractals permettent de compresser très efficacement les images, avec un qualité constante quel que soit le zoom, ils permettent de créer des textures réalistes, et peuvent permettre de tramer une image avec de bons résultats. Et bien d'autres choses encore…

Cette géométrie fractale se différencie de la géométrie euclidienne par leur définition d'une part: les figures de la géométrie euclidienne sont en général déterminées par des relations algébriques, alors que les courbes fractales sont définies de façon récursive. D'autre part, il ne faut pas non plus négliger leur aspect autosemblable: chaque partie d'un fractal peut être observé à n'importe quelle échelle: chaque partie est (sensiblement) une copie de l'ensemble. Finalement, autre propriété des fractals, ceux-ci ont des dimensions non entières (voir le chapitre de géométrie plane dans la section de géométrie).

Plusieurs méthodes ont été proposées pour construire des images fractales, nous nous intéresserons aux méthodes dites "d'échappement":

On se place dans le plan complexe formé des points M de coordonnées  d'affixe  où i représente le nombre complexe tel que .

On considère une suite complexe définie par  et ,  étant une fonction continue complexe. On suppose que  à un point fixe , c'est-à-dire qu'il existe  tel que  (il s'agit du "théorème du point fixe" démontré dans la section d'algèbre du site au chapitre sur les suites et séries). Sous certaines conditions sur  et sur , on constate que la suite des points ne divergent pas. Cette méthode est à la base de la construction des ensembles de Mandelbrot et de Julia.

Construire une image fractale à partir d'un ensemble de suites ainsi définies, revient à étudier pour chaque couple  du plan le comportement de la suite. On associe alors une couleur à chaque suite (c'est-à-dire à chaque couple ) représentant la "rapidité" de divergence de la suite.

Pour étudier la convergence d'une suite, on regarde ses n premiers éléments, si on détecte que les conditions de divergence sont vérifiées alors on peut dire que cette suite diverge, sinon, cette suite est potentiellement convergente. On remarque que plus n est grand plus les résultats seront précis (mais plus le temps de calcul sera grand).

Algorithme de base est le suivant:

Fractal=proc(x,y)

            z:= valeur de z0;
            j:=nombre max itérations

            Tant que condition_de_divergence non vérifiée(z) et j non atteint faire
                        z:=formule_iteration(z)
                        changer de couleur;
            Fin Tant que
            Renvoyer couleur finale

Fin Fractal

ENSEMBLE DE MANDELBROT

On construit l'ensemble de Mandelbrot grâce à des itérations dans le plan complexe. La fonction est de la forme:

où c est un paramètre constant tel que . Le premier terme de la suite est nul. On la donc la suite U définie par:

 et

Pourquoi commence-t-on avec ? Car zéro est le point critique de , c'est-à-dire le point qui satisfait à l'extremum:

Pour chaque point d'affixe  du plan, on étudie la suite U pour . Si la suite diverge, on dit que le point testé n'appartient pas à l'ensemble M, si la suite converge, on dit que le point appartient à M.

Pour reproduire l'ensemble de Mandelbrot, on associe à c des valeurs du plan complexe. On considère généralement la portion du plan complexe ayant comme partie réelle, les valeurs entre -2.5 et 1.5 et comme partie imaginaire, les valeurs entre -1.5 et 1.5. Cette portion du plan complexe est subdivisée de façon à former une grille dont les éléments seront associés à des valeurs de C. Pour chaque valeur de C, on obtient une suite dont les modules peuvent converger ou diverger. En pratique, on considère que la suite des modules converge si les 30 premiers modules sont inférieurs à 2. Lorsque la suite des modules converge, on colorie en noir le point de la grille. Après avoir considéré tous les points de la grille, on obtient un ensemble de points noircis: l'ensemble de Mandelbrot.

La liste des  générés par l'itération s'appelle "l'orbite" de .

On peut colorer les points à l'extérieur de l'ensemble de Mandelbrot en utilisant des couleurs qui dépendent du nombre de termes calculés avant d'obtenir un module supérieur ou égal à 2. Les points d'une même couleur peuvent être interprétés comme étant des points s'éloignant à la même vitesse de l'ensemble de Mandelbrot.

On peut aussi faire une incursion dans l'ensemble de Mandelbrot en utilisant MapleV (disponible habituellement au collège). Il suffit de copier le programme ci-dessous sur une feuille de travail du logiciel et d'indiquer à la place de -2 .. 1, -1.5 .. 1.5 de la dernière ligne, l'étendue des parties réelles et imaginaires de c que l'on désire visualiser:

restart: with(plots):
couleur:=proc(a,b)
local x,y,xi,yi,n;
x:=a;
y:=b;
for n from 0 to 30 while evalf(x^2+y^2) < 4 do;
xi:=evalf(x^2-y^2+a);
yi:=evalf(2*x*y+b);
x:=xi;
y:=yi;
od;
n;
end:

plot3d(0,-2..1,-1.5..1.5,orientation=[-90,0],style=patchnogrid, scaling=constrained,axes=framed,numpoints=20000,color=couleur);

Vous obtiendrez dès lors le résultat ci-dessous:

ENSEMBLES DE JULIA

L'ensemble de Julia se construit presque de la même façon que l'ensemble de Mandelbrot. Dans l'ensemble de Mandelbrot, c balaye le plan. Pour l'ensemble de Julia, c est fixé pendant tout le calcul de l'image. A chaque c correspond donc un ensemble particulier que l'on notera . Ce qui varie, c'est , qui prend la valeur du point à tester. C'est donc  qui balaie le plan.

Le point A de coordonnées et d'affixe  appartient à  si et seulement si la suite définie par:

 et

converge.

En fait, l'ensemble de Mandelbrot est l'ensemble des points c tels que l'ensemble de Julia de paramètre c soit connexe. Si à nouveau on développe l'algorithme, on obtient à un facteur d'échelle près donné, le fractal représenté ci-dessous:

ENSEMBLES DE NEWTON

Les ensembles de Newton sont ainsi appelés car ils découlent de la résolution de problème de la recherche des zéros d'une fonction par la méthode de Newton.

Soit une fonction  à valeur dans , et dérivable dans , on prend  dans  tel que:

Il y a alors deux manière de procéder: soit on s'intéresse à  et alors on fait comme précédemment, soit on se demande vers quel zéro  la suite converge et on s'intéresse à . Si à nouveau on développe l'algorithme, on obtient à un facteur d'échelle près donné, le fractal représenté ci-dessous: