Fractales de Newton et sensibilité aux conditions initiales

Ce projet a été réalisé en Python sur PyScripter

Définition

Les fractales de Newton sont une représentation graphique des racines associées à chaque point complexe z d'un plan.
La fractale de Newton est définie dans le plan complexe et caractérisée par l'application de la méthode de Newton à un polynôme complexe.

Construction

On utilise la méthode de Newton qui associe z_n+1 à z-f(z)/f'(z).
Cette règle mène ensuite à une suite de points z₁,z₂,etc.. Si la suite converge vers une racine k du polynôme, alors z₀ appartient à la région k.
Cette région est appelée "bassin d'attraction de la racine k".

Remarque

On remarque rapidement en regardant les fractales de Newton que des similarités se distinguent à toutes échelle.


Cependant il existe aux frontières de ces bassins d’attraction des points pour lequel on ne trouve aucune convergence.
Ces frontières très minces tendent à montrer une sensibilité très élevée aux condition initiales : trois points très proches peuvent avoir une racine distincte.
Ici un décalage de +0.5i a été appliqué a chacun des points et ils ont tous une racine associée différente.

Programme

Ce programme a donc pour but de calculer puis dessiner une fractale à partir d'un polynôme complexe donné en paramètre.
Il nécessite les bibliothèque scipy et PIL :

from scipy.misc import derivative
from PIL import Image

Initialisation

J’ai créé une classe Fractale pour diminuer le nombre de paramètres de chaque fonction et rendre certaines variables globales. On défini en tout 6 choses :

 -	f : le polynôme complexe dont on veut la représentation

 -	N : le nombre maximal d’itérations que peut faire une suite avant d’être dite « non-convergente »

 -	R : la liste des racines du polynôme

 -	L : la liste des z obtenu au terme de la suite de la méthode de Newton

 -	I : le nombre d’itérations nécessaire à chaque z pour atteindre une racine

 -	Palette : n’est autre que la palette de couleur utilisée pour dessiner les fractales

Ce qui donne ceci :

class Fractale:

    def __init__(self,f,N=50):
        self.f = f  #Polynôme
        self.N = N  #Nombre maximal d'itération avant la "non-convergence"
        self.R = [] #Liste des racines
        self.L = [] #Liste des z finaux des points
        self.I = [] #Liste du nombre d'iteration
        self.palette = [(0,0,0),(255,255,255),(23, 49, 144),(174, 10, 10),(73, 53, 72),(38, 161, 0),(226, 219, 190),(134, 187, 216),(238, 66, 102),(184, 59, 21),(60, 187, 177),(64, 64, 64),(122, 122, 122),(192, 192, 192)]

Main

La fonction main est celle qui appellera toutes les autres pour assurer le bon fonctionnement du programme.

def main(self):
        """Programme principal"""
            #Initialisation des variables
        taille_img_x = int(input("Taille x de votre image (une taille impair est préférable pour que le 0,0 soit centré)"))
        taille_img_y = int(input("Taille y de votre image"))
        im = Image.new('RGB', (taille_img_x, taille_img_y), (255, 255, 255)) #Crée une image blanche de la taille souhaitée
        npix = 0 
        compteur = 0       
        pix_tot = taille_img_x*taille_img_y

            #Set des coordonnées pour la création de z
        for pix_x in range(taille_img_x):
            for pix_y in range(taille_img_y):
                coord = Fractale.coordonees(pix_x,pix_y,taille_img_x,taille_img_y)
                x = coord[0]
                y = coord[1]
                z = complex(x,y)

                    #Recuperation des resultats de calcul_racine()
                z_f = Fractale.calcul_racine(self,z) #Theoriquement proche d'une racine


                    #Definition de la racine
                Fractale.set_racine(self,z_f)

                compteur +=1
            print((compteur/pix_tot*100)/2)


            #Creation de l'image

        for i in range(taille_img_x):
            for j in range(taille_img_y):
                im.putpixel((i,j), Fractale.set_color_pix(self,npix))
                npix += 1

            print(50+(npix/pix_tot*100)/2)


        im.save("Images\\Finale_pres\\z^5-1.jpg","JPEG")
        print("Votre image est prête")

Variables

Pour que le programme s'execute correctement il faut commencer par initialiser quelques variables:

 -  La taille de l'image (en x et en y)
 -  im : Une toile blanche de la taille souhaitée sur laquelle "dessiner" notre fractale
 -  npix : ou numéro pixel qui servira plus tard pour le dessin
 -  compteur et pix_tot servent a l'affichage en pourcentage de la progression du programme

Coordonnées

Pour avoir le résultat souhaité on travaille avec des z de petite taille (généralement entre 2+2i et -2-2i).
Pour ça il nous faut transformer les coordonnées pixels en coordonnées réelles. En effet les coordonnées d'un image et d'un plan ne sont pas traitée de la même façon :

En résolvant un petit système :

    def coordonees(pix_x,pix_y,taille_x,taille_y):
        """Transforme les coordonnées pixel en coordonnées réelles."""
        x_hi = 2
        x_lo = -2
        y_hi = -2
        y_lo = 2
        x = (((x_hi-x_lo)/taille_x)*pix_x) + x_lo
        y = (((y_hi-y_lo)/taille_y)*pix_y) + y_lo
        return (x,y)

on obtient une équation et nous voilà avec des coordonnées utilisables pour nos calculs. On crée donc notre z complexe à partir du x et du y déduis de ce calcul.

Calculs

Mon programme utilise la méthode de Newton, c'est un programme plutôt lent qui possède une complexité quadratique.

Avec le z calculé précédemment dans la fonction coord on peut donc effectuer la méthode Newton afin de trouver vers quelle racine il converge.
Pour cela j’ai eu besoin du module scipy et de sa fonction derivative qui renvoi le résultat de la dérivée de notre fonction.
On défini donc Zn+1 comme étant z – f(z)/f’(z).

Compteur est le nombre d’itération effectuées jusqu’à ce que z trouve une racine.

On stop donc la boucle de calcul si le nombre d’itérations dépasse N (un nombre arbitraire défini dans le init) ou si Zn+1 – Z est inferieur a 1*10-6 (la suite n’évolue plus).Théoriquement lorsque la suite ce stabilise c’est que l’on se trouve proche d’une racine.

Une fois sortis de la boucle on ajoute à la variable globale I le nombre d’itérations effectuée pour ce z et on renvoi le z final obtenu.

    def calcul_racine(self,z):
        """Compte le nombre d'itérations necéssaire pour trouver une racine et s'arrete après N itérations."""
        Zn_plus_1 = z - (self.f(z) / derivative(self.f,z,1e-12))
        compteur = 0

        while compteur < self.N and abs(Zn_plus_1 - z) >= 1e-6:
            z = Zn_plus_1
            Zn_plus_1 = z - (self.f(z) / derivative(self.f,z,1e-12))
            compteur += 1

        self.I.append(compteur)
        return z

Différentes méthodes

Cependant, il existe d’autre méthodes ayant des résultats similaires avec des complexité moindre ou non.
On peut notamment citer la méthode de la sécante avec une complexité linéaire de 1.618 qui approxime la dérivée au lieu de la calculer mais qui a donc un résultat moins précis.
Je ne présenterai ici que la méthode de Newton.