DOSSIER
L'intelligence des Maths

Méthode de Newton et fractales

Sous le polynôme, l’étrange

La méthode de Newton pour rechercher les solutions d’équations polynomiales permet de décrire des objets fascinants : les fractales.
par LEI Tan, Professeur, chercheur au Larema, Laboratoire de recherche en mathématiques de l’Université d’Angers. http://math.univ-angers.fr/

Le rapport r entre la longueur (29,7 cm) et la largeur (21 cm) d’une feuille de papier A4 a été choisi pour rester inchangé lorsqu’on plie la feuille en deux. Ainsi, en notant x la longueur, r vaut x/21 avant pliage ; après pliage, il devient 21/(x/2). x est donc solution de l’équation

x/21 = 21/(x/2)

ou

x2 = 2×212 = 882.

Avec une calculatrice, on obtient racine carrée de 882 = 29,698485 (dont 29,7 est proche), mais cette valeur n’est qu’une approximation de racine carrée de 882 qui, comme 1/3 ou pi, possède une infinité de décimales. D’autres problèmes pratiques conduisent à résoudre des équations plus compliquées que x2 - 882 = 0, dont aucune touche de calculatrice ne peut fournir de solution approchée. Pourtant, Isaac Newton (1642-1727) a inventé un « algorithme itératif » capable de faire cela avec autant de précision que nécessaire.

La méthode de Newton

Un algorithme itératif consiste à répéter plusieurs fois la même opération mathématique sur le dernier résultat obtenu. Par exemple, tapez 5 sur une calculatrice, puis appuyez une trentaine de fois sur la touche « racine carrée » ; vous observerez une succession de nombres décimaux s’approchant de plus en plus de 1. La même expérience avec 0,01 à la place de 5 donne une autre suite d’approximations de 1. Cela n’est pas très intéressant en soi, mais le choix de la valeur initiale n’est cependant pas anodin. Par exemple, « itérer » x2 donne des résultats très différents selon qu’on commence par 1,01 ou par 0,99.

Revenons maintenant à Newton. Pour trouver des approximations de solutions de l’équation P(x) = 0 (ou « racines » de P, P étant un polynôme quelconque), Newton a remarqué qu’il peut suffire d’itérer l’opération x - P(x)/P’(x) où P’ désigne la dérivée de P.

Si P(x) = x2 - 882, alors P’(x) = 2x, et x - P(x)/P’(x) vaut dans ce cas (x + 882/x)/2. Essayons cette méthode avec la valeur initiale x = 1. On obtient successivement (à peu près) : 221,749 ; 112,8632 ; 60,339 ; 37,4782 ; 30,50594 ; 29,70917 ; 29,69849 ; 29,69848, etc. Voilà une méthode efficace pour trouver une valeur approchée de racine carrée de 882.

Maintenant, que se passe-t-il si nous commençons par un nombre complexe ? Un tel nombre est de la forme x+yi, où i est un nombre « imaginaire » dont le carré vaut -1 et où x et y sont deux nombres réels habituels. Il est alors facile de montrer que si la valeur initiale de x est positive, alors les itérations approchent racine carrée de 882 ; si elle est négative, nous approchons - racine carrée de 882, l’autre racine de P. La droite d’équation x = 0 est à la fois bissectrice des deux racines et ligne de séparation de deux « bassins d’attraction » des itérations.

Du chaos numérique

Appliquons maintenant la méthode de Newton au polynôme

P(z) = (z - a + 1/2)(z - a + 1/2)(z - 1)

où z désigne une variable complexe et où a est la constante complexe - 0,00508 + 0,33136 i. P a trois racines : 1, -1/2 + a et -1/2 - a. On pourrait penser que, comme dans le cas précédent, des lignes médiatrices partagent le plan en trois régions telles qu’une valeur initiale (complexe) prise dans l’une de ces régions conduise à une approximation de la racine située dans cette même région. Arthur Cayley (1821-1895) avait tenté de justifier cette intuition, mais en vain. Voici pourquoi.

Faisons l’expérience numérique suivante sur un ordinateur.

Plaçons-nous dans une fenêtre carrée du plan, définie par -1,4 < x < 1,6 et -1,5 < y < 1,5, par exemple ; découpons-la en 400×400 pixels puis, avec une valeur initiale appartenant à chacun de ces pixels (donnée par un nombre complexe z = x + yi), faisons itérer par l’ordinateur z - P(z)/P’(z) un millier de fois et colorions ce pixel

en bleu si le résultat est un nombre complexe proche de 1,

en vert s’il est proche de -1/2 + a,

en rouge s’il est proche de -1/2 - a,

en noir si rien de tout cela ne se produit (les itérations ne « convergent » vers aucune racine).

L’ordinateur dessine alors la figure 1. Plutôt qu’un simple graphe séparateur, il apparaît une « fractale » qui partage non seulement le carré en trois grands « lacs » autour de chaque racine mais aussi en une infinité de petits lacs rouges, verts, bleus ou noirs entremêlés de manière compliquée.

Cette complexité illustre le caractère « chaotique » de la méthode de Newton : aux frontières de ces lacs, le moindre changement de valeur initiale peut faire basculer les itérations d’une racine vers une autre ou vers un « piège noir ».

Une fois découverte cette « fractale de Newton », les mathématiciens ont cherché à mieux comprendre sa structure, par des moyens divers. Par exemple, nous avons démontré qu’elle est une combinaison (ou « couture », ou encore « accouplement », selon Adrien Douady) de deux fractales plus simples, qui proviennent des itérations de z3 + (1,503 - 0,8046 i)z2 puis de z3 + (2,12 i)z2.

Tangente à l’appui

Il apparaît que les itérations de la méthode de Newton n’évoluent pas si la valeur initiale est une solution z* de P(z) = 0. En effet, remplacer z par z* dans z - P(z)/P’(z) a pour résultat z*. z* est un « point fixe » de la méthode. Il est un principe courant en mathématiques de transformer la résolution d’une équation en la recherche d’un point fixe d’un opérateur approprié. Nous aurions donc pu utiliser un opérateur plus simple, par exemple z - P(z), pour lequel z* est aussi un point fixe. Alors pourquoi Newton a-t-il choisi une opération compliquée, avec la division par la dérivée ? C’est pour approcher le graphe du polynôme P par la droite d’équation f(z) = (z - z0)P’(z0) + P(z0) (où f(z) et z jouent les rôles de y et x dans une droite d’équation y = ax + b). Cette droite est la tangente de P au point quelconque z0 (la fonction f admet en effet la même valeur et la même dérivée en z0 que P). La solution de f(z) = 0 est proche de celle de P(z) = 0 ; elle vaut z0 - P(z0)/P’(z0). Voilà d’où vient la division par la dérivée : la méthode de Newton utilise la pente du graphe P (donnée par la dérivée de P) pour approcher une racine.

Afin de justifier l'intuition naturelle du graphe séparateur, nous avons « ralenti » la méthode de Newton en ajoutant un facteur h < 1 au terme P(z)/P’(z) : l’opérateur devient alors z - hP(z)/P’(z). En faisant varier h, nous fabriquons toute une famille de fractales de Newton ; lorsque h décroît vers 0, celles-ci tendent à séparer le plan en seulement trois régions contenant chacune une racine de P.

Nous avons enfin trouvé le graphe séparateur que Cayley cherchait ! Celui-ci n’a cependant pas tout à fait l’allure imaginée auparavant, avec trois branches qui se rencontrent en un point (sauf si la partie réelle x de a est choisie nulle).

Les ensembles de Julia

Cette branche des mathématiques, nommée « Itération des fractions rationnelles », est une théorie fondée dans les années 1920 par Gaston Julia (1893-1978) et Pierre Fatou (1878-1929) ; les fractales qu’elle décrit sont d’ailleurs appelées ensembles de Julia. Elle a connu un développement florissant depuis 1980, non seulement grâce à des avancées mathématiques mais aussi grâce au développement d’outils informatiques qui permettent de visualiser les objets fractals et d’alimenter ainsi les questionnements des mathématiciens.

© Larema

Têtes chercheuses ©2007 | mentions légales | contactez nous | page d'accueil | Réalisation : Intelliance 2007