18 avril 2009

4 commentaires — commenter cet article

La méthode de Newton et son fractal

Tan Lei

Professeur à l'Université d'Angers. (page web)

Dans la vie courante, des problèmes mathématiques se modélisent souvent sous forme d’équations. Résoudre ces problèmes revient alors à trouver des solutions à ces équations.

Les dimensions d’une feuille de papier

Voici un exemple : prenons une feuille de papier A4 standard. Sa largeur est de $21$ cm (nous l’avons un peu arrondie pour simplifier le calcul [1]). Sa longueur mesure entre $29$ cm et $30$ cm. Comment expliquer ce rapport « étrange »
entre longueur et largeur ?

En effet, pour des raisons économiques et esthétiques, ce rapport a été choisi pour qu’après avoir été plié en deux, le papier reprenne la même forme, c’est-à-dire le même rapport longueur/largeur. Ainsi, en notant $x$ la longueur de notre feuille A4, le rapport longueur/largeur avant le pliage est de $x/21$. Après le pliage, la nouvelle
longueur est $21$cm, et la nouvelle largeur $x/2$, avec donc comme rapport $21/(x/2)$.
La longueur $x$ de la feuille A4 est donc solution de l’équation
\[x/21=21/(x/2),\]
soit $x^2=2\times 21^2$, ou encore $x=\sqrt{882}$.

Calculez à présent $\sqrt{882}$ à l’aide d’une calculatrice, vous trouverez $29,\!698485$, d’où la longueur en centimètres de notre feuille A4 (et voilà pourquoi A4 est aussi $21\times 29,\!7$) !

Cependant, cette valeur avec toutes ses décimales n’est qu’une
approximation de $\sqrt{882}$, puisque ce nombre réel n’est pas un nombre
décimal [2], de même que $1/3=0,333333333...$, $\pi$, $\sqrt{2}$ ne sont
pas des nombres décimaux. Une des questions est alors de trouver une
bonne approximation de ces nombres par des nombres décimaux, en
fonction de la façon dont ils sont définis. Cette question n’a
pas grand
intérêt pour les nombres qui sont des fractions (comme $1/3$), car le
développement décimal d’un tel nombre est toujours périodique
(comme celui de $1/3$ où le chiffre $3$ se répète indéfiniment dans le développement).

La touche « racine carrée » est en panne

Imaginons qu’un jour la touche $\sqrt{\ }$ ne fonctionne pas. Ou qu’on ait besoin d’une valeur approchée avec beaucoup plus de précision. Ou encore que l’on tombe sur un autre problème dont aucune touche de la calculatrice ne nous fournisse de réponse.

Heureusement, après avoir transformé ces problèmes
en équations, nous pouvons utiliser un algorithme itératif inventé par le génial mathématicien et physicien Isaac Newton (1642-1727).
Cette méthode de Newton fournit toujours des solutions approchées des équations, et ce avec autant de précision que nécessaire (voir l’article original de Newton, ajouté à la fin de cet article).

Qu’est-ce qu’un « algorithme itératif » ? C’est tout simplement l’opération consistant à répéter un grand nombre de fois la même opération mathématique. Tapez par exemple un nombre au hasard, disons $5$, sur une calculatrice. Puis appuyez, disons une trentaine de fois, sur la touche $\sqrt{\ }$ (en espérant qu’elle fonctionne, cette fameuse touche !).

Vous allez voir défiler sur l’écran une succession de nombres décimaux, et ces nombres s’approchent de plus en plus de $1$.
Essayez cette fois-ci $0,\!001$ à la place de $5$, qu’observez vous ?

Ce que vous êtes en train de faire, c’est d’itérer l’opération « racine carrée ». Et cette itération vous fournit au fur et à mesure des approximations de plus en plus précises du nombre $1$ (ce qui n’est pas très intéressant en soi).

Vous pouvez bien sûr itérer d’autres opérations comme $x^2$, $\sin x$ ou $\cos x$ si votre calculatrice le permet, tout en variant le choix du nombre de départ. Vous allez constater qu’itérer $x^2$ en commençant par $1,\!05$ ou $0,\!95$ donne des résultats très différents, tandis qu’itérer $\sin$ (ou $\cos$) donne toujours le même résultat final.

Personnellement j’ai été très étonnée
lors de la découverte de ces curieux phénomènes. Pas vous ?

La « touche » méthode de Newton

Alors quelle est la méthode de Newton pour trouver des solutions approchées de l’équation $x^2-882=0$ ? Notons $P(x)=x^2-882$ pour simplifier la présentation (cela rend également la méthode plus conceptuelle).

Newton a réalisé que pour cela, il suffisait d’itérer l’opération
\[ x-\frac{P(x)}{P'(x)}\]
(où $P'$ désigne la dérivée de $P$), soit
\[x-\frac{x^2-882}{2x},\]
ou encore
\[ \frac12 \left(x+ \frac{882}{x}\right),\]
un peu comme si la calculatrice avait une touche « $x-P(x)/P'(x)$ » et qu’on appuie un grand nombre de fois sur cette touche.

Nous allons voir un peu plus tard, dans le paragraphe « Solutions et points fixes », la raison
mathématique d’utiliser la formule précise
$ x-P(x)/P'(x)$ plutôt qu’une autre. A présent contentons nous de faire quelques expériences numériques.

Essayons avec $x=1$. On obtient, successivement : \[1;\quad \frac12 \left(1+ \frac{882}{1}\right)=441,\!5;\quad \frac12 \left(441,5 + \frac{882}{441,\!5}\right)=221,\!749;\] puis $112,\!8632; \quad 60,\!339;\quad 37,\!4782;\quad 30,\!50594;\quad 29,\!70917;\quad 29,\!69849,\quad 29,\!69848,\ \ldots\ .$

Après seulement quelques coups d’essai, on est déjà très près de la vraie solution $\sqrt{882}\approx 29,\!698485$. Voilà une méthode bien efficace... [3]
 [4]

On pourrait montrer que, en commençant par n’importe quel nombre proche de $\sqrt{882}$ (à la place de $x=1$ ici), les valeurs obtenues en itérant le procédé vont toujours s’approcher de $\sqrt{882}$.

Nous allons maintenant tester cette méthode avec des nombres complexes
(nous expliquerons pourquoi à la fin de ce paragraphe), c’est-à-dire
des nombres sous la forme $x+iy$, avec $i$ un nombre (imaginaire) dont le carré est $-1$,
et $x,y$ deux nombres réels habituels (voir le film Dimensions mentionné ci-dessous pour une explication animée et détaillée des nombres complexes). Le nombre $x$ est appelé la partie réelle, et
$y$ la partie imaginaire.

Un tel nombre serait proche de $\sqrt{882}$ si $x$ est proche de $\sqrt{882}$ et
$y$ est proche de $0$. En particulier les nombres imaginaires purs, c’est-à-dire
ceux dont la partie réelle est nulle, ceux la forme $0+iy$, sont très loin de $\sqrt{882}$.

Faisons le test avec $i$ comme valeur initiale, cette fois-ci avec un crayon sur une feuille de
papier (A4 par exemple !) au lieu d’une calculatrice.

Mettons $i$ (à la place de $x$) dans la formule de Newton \[\frac12 \left(x+ \frac{882}{x}\right),\]
nous obtenons \[\frac12\left(i+\frac{882}{i}\right)=\frac12\left(i+\frac{882}{i\times i}i\right)\\]
et, comme $i^2=-1$, c’est aussi
\[\frac12(i-882\,i)= -440,\!5\,i.\]
Remettons ce dernier terme (toujours à la place de $x$) dans la formule de Newton, et ainsi de suite, cela nous donne
$ -219,\!25\,i$, puis $ -251,\!227\,i$... On voit que ces valeurs
restent imaginaires pures et donc ne se rapprocheront jamais de nos solutions $\pm \sqrt{882}$.

Que se passerait-il si nous prenions comme valeur initiale un autre nombre complexe $x+iy$ ?
Il n’est pas très difficile de démontrer que, si $x$ est positif, nous allons nous rapprocher de $\sqrt{882}$, et si au contraire $x$ est négatif, nous allons nous rapprocher de $-\sqrt{882}$. La droite des nombres complexes imaginaires purs, qui n’est rien d’autre que l’axe des $y$, est à la fois la médiatrice des deux solutions, et la ligne de séparation de deux comportements différents des suites de valeurs itératives. À sa gauche, c’est le « bassin » d’attraction de la solution $-\sqrt{882}$ ;
et à sa droite, celui de $\sqrt{882}$.

GIF - 7.6 ko
Bassin d’attraction de la méthode de Newton pour un polynôme de degré 2

Alors pourquoi partir d’un nombre complexe alors qu’un réel suffisait ? En effet, dans d’autres problèmes plus compliqués, on risque de tomber sur une équation dont la solution recherchée n’est pas réelle.
Tester sur des valeurs initiales qui sont des nombres complexes permet donc de repérer également ce genre de solutions. Ce n’est pas tout. Aller des réels vers les complexes nous permet à la fois d’élargir
notre champ de vision (comme illustré par de nombreux dessins ci-dessous), et
d’avoir accès à de puissants outils mathématiques relevant de l’analyse complexe. Il y a d’ailleurs des problèmes
mathématiques purement réels qui n’ont pu être résolus que grâce à l’utilisation des
nombres complexes, c’est ce qu’on appelle encore « complexifier » le
problème.

Avec un polynôme de degré 3

Essayons maintenant la méthode de Newton $ z-P(z)/P'(z)$ pour un polynôme un peu plus compliqué :
\[ P(z)=\left(z-a+\frac12\right)\left(z+a+\frac12\right)(z-1),\]
ici $z$ désigne un nombre complexe inconnu et $a$ est le nombre complexe $-0,\!00508+0,\!33136\,i$. (En fait on aurait pu prendre n’importe quel
nombre complexe pour $a$, mais celui-ci
a été choisi spécifiquement pour illustrer par la
suite l’apparition du fameux lapin de Douady. Voir le paragraphe
« Choix de $a$ » ci-dessous. )

Les solutions de l’équation $P(z)=0$ sont 1, $-\frac12+a$ et $ -\frac12-a$. On pourrait croire naïvement qu’une sorte de graphe séparateur jouerait le rôle de la médiatrice (comme dans le cas précédent) :
ce graphe séparerait le plan en trois régions, et une valeur initiale (qui
est un nombre complexe) prise dans une région donnée nous donnerait
des approximations de la racine du polynôme située dans cette région. Par exemple :

GIF - 2.6 ko
Un graphe séparateur ?

Arthur Cayley (1821-1895) avait tenté en vain de justifier cette intuition (voir
son article, ajouté à la fin de cet article). Nous allons tout de
suite comprendre pourquoi.

Une expérience numérique

Faisons une nouvelle expérience numérique, en remplaçant cette fois la calculette par un ordinateur :

Plaçons-nous dans une fenêtre carrée du plan, disons $-1,\!4

  • le pixel $z$ en bleu si le résultat est un nombre complexe proche de $1$,
  • en vert s’il est proche de $-\frac12+a$,
  • en rouge, s’il est proche de $ -\frac12-a$...

Enfin colorions le pixel en noir si rien de tout cela se produit.

Voici ce que notre ordinateur dessine :

GIF - 25.3 ko
Le fractal de Newton

Ainsi, plutôt qu’un simple graphe séparateur, on voit apparaître un surprenant
« fractal » qui partage le carré en trois grands lacs, un autour de chaque solution,
mais également en beaucoup de petits lacs rouges, verts ou bleus, qui s’entremêlent de manière très compliquée...

Ah ! Si Cayley avait vu cela !

Observons ce fractal de plus près. Voici un agrandissement dans la fenêtre
$-0,\!22

GIF - 32.2 ko
Zoom

La couleur noire indique le lieu des « mauvaises » valeurs de test initiales :
si l’on choisit au départ un nombre complexe au sein de cette partie, la méthode de Newton n’approchera jamais d’une solution de $P=0$.

Même si ce lieu est relativement petit, on voit tout de même des taches piégées
dans son intérieur,
des sortes de lacs noirs (en termes mathématiques, l’intérieur de cet ensemble n’est pas vide). La présence de ces lacs
met en doute l’efficacité globale de la méthode de Newton.

En plus, ces lacs noirs ne sont pas dans une partie isolée, bien délimitée, du plan. Au contraire ils s’entremêlent partout avec les lacs rouges, verts ou bleus.

Ceci illustre le phénomène « chaotique » de cette méthode itérative : en partant d’un point de la frontière d’un de ces lacs, la moindre erreur numérique nous fait basculer soit d’une solution vers une autre, soit vers un piège de couleur noire.

Il faut dire que la présence de ces taches noires est due à notre
choix spécifique du nombre complexe $a$.

En choisissant un autre nombre pour $a$, le fractal engendré peut très bien ne plus avoir de taches noires. On peut
même prédire à peu de choses près tous les choix de $a$ pour lesquels cela se
produit.

Une question se pose alors : dans ces cas-là, peut-on affirmer que la méthode de Newton est enfin globalement efficace ? Eh bien, ce n’est pas si simple que ça.

Il existe aujourd’hui des logiciels qui produisent des valeurs « aléatoires », c’est-à-dire imitant le hasard. On aimerait
dire que la chance qu’un tel logiciel produise un nombre complexe noir est minime, lorsqu’il n’y a pas de tache noire à l’intérieur [5]. Or ce n’est pas toujours le cas : pour certains choix de $a$, il n’y a pas de taches noires (l’intérieur de l’ensemble noir est vide), pourtant la probabilité pour qu’un point choisi au hasard soit noir n’est pas nulle [6].

Lapins

Essayons maintenant de comprendre un peu mieux la structure du fractal de Newton présenté ci-dessus, donc
calculé avec le nombre $a$ que nous avons choisi ci-dessus.

  • La première observation est qu’il y a des taches noires un peu partout à la frontière des lacs colorés, et que ces taches ont des tailles très variées.
  • La deuxième est que ces taches ont toutes une drôle de forme : elles ressemblent un peu à un lapin à deux oreilles.

Adrien Douady (1935-2006) fait partie des premiers mathématiciens à avoir observé cela. Il a très vite compris que ces lapins proviennent de l’itération d’une autre opération, plus simple cette fois-ci, celle de
\[z^2+ (-0,\!12+0,\!75i).\]

Faisons l’expérience comme lui, en colorant un pixel dans le carré
$-1,45\le x,y\le 1,45$

  • en rouge si ses itérés par cette opération s’échappent du carré,
  • et en noir sinon.

Voici le résultat :

GIF - 39.4 ko
Le lapin de Douady

Une ressemblance frappante avec le lieu noir que nous avons appelé « lapin », n’est ce pas ? D’ailleurs ce fractal s’appelle le lapin de Douady.

Choix de $a$


Alors pour quelle raison le fractal produit par l’itération
du polynôme quadratique ci-dessus apparaît-il dans notre fractal de Newton ?

C’est dû à un phénomène de renormalisation, démontré par Douady et Hubbard : pour des bons choix de $a$, et pour la méthode de Newton associée au polynôme
\[ P(z)=\left(z-a+\frac12\right)\left(z+a+\frac12\right)(z-1)\] (qui dépend
de $a$), itérer un nombre pair de fois, par exemple $2n$ fois, cette méthode
dans une région proche de $0$, revient à itérer $n$ fois un polynôme quadratique
de la forme $z^2+c$ (où $c$ dépend de $a$). Donc si l’on veut voir apparaître
le fractal engendré par un $c$ spécifique, par exemple le lapin
de Douady, il ne reste plus qu’à ajuster le nombre $a$.

Alors comment procéder précisément ?
Pour cela, il faut d’abord savoir comment produire le lapin de Douady. Nous allons voir que
le choix de $c$, tout comme celui de $a$, est relativement flexible.

Commençons par itérer $z^2+c$ à partir de $z=0$.
Nous obtenons, successivement,

$0^2+c= c\,;\quad\$ puis $\quad c^2+c\,;\quad (c^2+c)^2+c\,;\quad ((c^2+c)^2+c)^2+c\,;\quad \cdots \quad$ etc.

D’après la théorie de Douady et Hubbard, pour obtenir un fractal qui ressemble à un lapin,
il faut choisir un $c$ parmi ceux qui rendent le troisième terme ci-dessus relativement petit,
donc un $c$ proche d’une solution de l’équation $(c^2+c)^2+c=0$.

Essayons donc de résoudre cette équation. En divisant par $c$,
elle devient : $c(c+1)^2+1=0$. Cette nouvelle équation a trois solutions, et celle qui nous convient
est approximativement $-0,\!1225612+0,\!7448618i$. Notons la par $c_0$.
Ainsi pour tout choix de $c$ proche
de $c_0$, le troixième terme ci-dessus est proche de $0$, et itérer $z^2+c$ devrait
nous donner un lapin. Nous en avons choisi un au hasard, notamment $c=-0,\!12+0,\!75i$,
et ça marche !

Revenons à la méthode de Newton. Cette fois-ci il faut choisir un $a$ tel que le sixième
itéré de $0$ par cette méthode soit proche de $0$. Il existe $18$ valeurs de $a$ rendant ce
terme du
sixième
itéré nul, et celle qui nous convient est approximativement $-0,\!0051054+0,\!3313825i$. Notons la par $a_0$.
Ainsi n’importe quel choix de $a$ proche de $a_0$ devrait nous donner un fractal de Newton avec
des lapins sautillant dedans. Là encore nous en avons choisi un au hasard, notamment
$a=-0,\!00508+0,\!33136i$. Et des beaux lapins apparaissent bel et bien dans notre fractal.

(A titre d’information, le sixième
itéré de $0$ pour ce choix de $a$ est $-0,\!0001958-0,\!0005808i$.)

Coutures et accouplements

Cette relation avec les lapins n’explique pas encore toute la structure du lieu noir. Il faut encore comprendre comment ces multiples lapins se sont reliés les uns et les autres.

En fait, bien que ce ne soit pas du tout évident à l’œil nu,
ce fractal est obtenu en recousant ensemble deux fractals plus simples,
et donc plus facils à comprendre. Mais nous n’allons pas
entrer dans les détails ici. Nous nous contentons juste d’illustrer
ces deux fractals ainsi que la couture.

Voici le premier fractal, provenant de l’itération de
\[Q(z)=z^3+(1,\!503-0,\!8046\,i)z^2.\]
Ce fractal est appelé « ensemble de Julia » de $Q$.
Vous remarquerez que de multiples lapins y sont déjà présents.

GIF - 7.5 ko
Ensemble de Julia d’un polynôme de degré 3, avec lapin

Et voici le deuxième, provenant de l’itération de
\[z^3+(2,\!12i)z^2.\]

GIF - 4.6 ko
Citron

Faisons maintenant tourner notre fractal de Newton de $90^\circ$ pour mieux visualiser la couture :

GIF - 22 ko
Le fractal de Newton

Voici enfin la couture en vidéo (film réalisé par Arnaud Chéritat),
d’abord dans le plan :

puis sur une sphère [7]) :

La théorie derière cette couture a été connue depuis 1997 (voir les
références mathématiques ci-dessous). Mais l’illustration
en film présente de grandes difficultés techniques,
de nature à la fois informatique et mathématique.
Arnaud Chéritat a du surmonter toutes ces difficultés
afin de réaliser ces remarquables vidéos pour nous.
Je lui en suis très reconnaissante.

Au passage ce procédé de couture a été appelé « accouplement » avec humour par Adrien Douady.

Solutions et points fixes

Essayons maintenant de comprendre pourquoi la méthode de Newton se stabilise à une certaine solution $r$ de l’équation $P(z)=0$ (pour un $P$ quelconque).

Pour cela remplaçons $z$ par une telle solution $r$ dans $z-P(z)/P'(z)$. Nous observons que
\[r-\frac{P(r)}{P'(r)}=r-\frac{0}{P'(r)}=r.\]

Cela veut dire que faire opérer la méthode de Newton ne change pas la valeur $r$ : si vous avez tapé $r$ comme valeur initiale, vous pouvez appuyer tant que vous voulez sur la touche « méthode de Newton », vous obtiendrez toujours $r$.

En termes mathématiques, $r$ est un point fixe. Ce que nous avons fait est un exemple d’une méthode assez courante en mathématique : on transforme la résolution d’une équation en la recherche d’un point fixe d’une opération appropriée.

Mais on aurait pu choisir une opération plus simple. Par exemple la touche « $z-P(z)$ », qui remplace $z$ par $z-P(z)$ : bien sûr si $r$ est une solution de $P(z)=0$, appuyer sur cette touche produira toujours $r$. Alors pourquoi choisir une opération aussi compliquée que celle de Newton, avec la division par la dérivée ?

Eh bien, c’est pour approcher le graphe du polynôme $P$ par une droite (une tangente) $f(z)=(z-z_0)P'(z_0)+P(z_0)$.

Cette fonction $f$ admet la même valeur et la même dérivée en $z_0$ que le polynôme $P$.
On peut donc imaginer que la solution de $f(z)=0$ est proche de celle de $P(z)=0$. L’équation $f(z)=0$ est tellement simple qu’on peut la résoudre directement, soit
\[z=z_0-\frac{P(z_0)}{P'(z_0)},\]
et voilà d’où vient la division par la dérivée !

La relation entre la solution de $P=0$ et celle de $f=0$ se voit facilement sur une figure (ici dans le cas réel) :

GIF - 1.9 ko
Relation avec la tangente

Poussons-nous un peu plus loin dans notre compréhension : pourquoi l’itération de la méthode de Newton donne-t-elle des valeurs s’approchant de plus en plus d’une solution $r$ (si l’on est parti d’une valeur assez proche), et ce de manière extrêmement rapide ?

Pour comprendre cela

  • calculons la dérivée de l’opération \[z-\frac{P(z)}{P'(z)}.\] Nous trouvons \[\frac{P(z)P''(z)}{P'(z)^2}.\]
  • remplaçons $z$ par la solution $r$ dans cette expression : la dérivée s’annule elle aussi en $r$.

Non seulement la méthode de Newton laisse la valeur $r$ invariante, mais en plus elle y admet une dérivée nulle. On dit que $r$ est un point fixe super-attractif. Cette terminologie illustre le fait que la solution $r$ attire vers elle, de toutes ses forces, les valeurs voisines.

Alors pourquoi la vitesse de convergence a-t-elle un quelconque lien
avec le fait que la dérivée s’annule en $r$ ?

Nous pouvons essayer de comprendre cela en considérant un exemple plus simple, mais typique de ce genre de situation.
Prenons l’opération « élever un nombre au carré », c’est-à-dire « $x^2$ ». La valeur $0$ est fixe ($0^2=0$ !), et la dérivée ($2x$) est nulle en $0$.
La valeur $0$ est donc bel et bien un point fixe super-attractif.

Faisons ensuite un test (sur une calculatrice par exemple) de la vitesse de convergence en prenant
$0,\!5$ comme valeur initiale. Nous obtenons :

\[0,\!5;\quad 0,\!25;\quad 0,\!0625;\quad 0,\!00390625;\quad 0,\!00001525878;\]
\[0,\!00000000023283;\quad 0,\!00000000000000000005421; \quad\ldots\]

En gros le nombre de zéros après la virgule double à chaque itération. Rapide, n’est ce pas ?! Vous pouvez par exemple le comparer avec l’itération de l’opération « diviser un nombre par $100$ », c’est-à-dire « $x/100$ »
(avec donc une dérivée $1/100$ qui n’est pas nulle).
Qui est-ce qui va l’emporter en fin de compte ?

Graphe séparateur

Et l’histoire d’un graphe séparant les trois solutions d’un polynôme (quelconque) $P(z)$ de degré 3, dans tout cela ? Une idée si naturelle... vous n’avez peut-être pas envie de l’abandonner complètement.

Eh bien, vous avez raison. Pour le voir, rajoutons un facteur $h$ devant le terme $P(z)/P’(z)$, notre « touche méthode de Newton » devient
\[z-h\frac{P(z)}{P’(z)}.\]
Ce facteur va modifier la vitesse à laquelle la méthode de Newton permet de s’approcher d’une
racine de $P$. Plus $h$ est petit, moindre est la vitesse.

Nous fabriquons ainsi toute une famille de « fractals de Newton », un pour chaque valeur de $h$.
Quand $h$ décroît, devenant de plus en plus petit, ces fractals se transforment
progressivement en un graphe. Ce graphe sépare le plan en trois
régions, contenant chacune une solution de $P(z)=0$. Et nous avons enfin trouvé le graphe séparateur que Cayley cherchait !

Voici ce qui se passe avec notre $P(z)$ spécifique, c’est-à-dire
\[ P(z)=\left(z-a+\frac12\right)\left(z+a+\frac12\right)(z-1),\]
avec $a=-0,\!00508+0,\!33136\,i$ :

Ce qui est surprenant, c’est que ce graphe n’a pas tout à fait l’allure qu’on imaginait, c’est-à-dire un graphe avec trois branches se rencontrant en un point.

C’est dû au fait que le nombre complexe $a$ que nous avons choisi a une partie réelle non nulle. Si l’on supprimait cette partie réelle, on trouverait bien un graphe avec trois branches se rencontrant en un point. En revanche on n’aurait
pas obtenu les multiples lapins du départ.

Le champ de Newton

Mais... l’algorithme de Newton a-t-il encore un sens lorsque $h$ devient infiniment petit ?

Eh bien oui. Mais cette fois-ci, il faut considérer le champ de vecteurs de Newton : en chaque point $z$ du plan, on plante un vecteur de direction $ -P(z)/P’(z)$. En suivant les directions indiquées par ces vecteurs on obtient trois flots (comme des flots d’eau), coulant chacun vers une solution. Et la frontière entre ces trois bassins n’est rien d’autre que le graphe séparateur.

Ce fait est valable pour n’importe quel choix du nombre $a$. Voici une illustration pour notre
$a$ spécifique :

Un peu d’histoire

Terminons par un peu d’histoire : Cette branche des mathématiques s’appelle l’itération des fractions rationnelles, une théorie fondée (bien après Newton) dans les années 1900-1920 par Pierre Fatou (1878-1929) et Gaston Julia (1893-1978). Ces fractals « de Newton » sont d’ailleurs appelés ensembles de Julia.

Cette théorie a connu un développement florissant depuis 1980, grâce en partie à l’arrivée de puissants outils informatiques et mathématiques. Ces deux types d’outils interagissent parfois de manière très compliquée pour permettre tour à tour d’observer, de démontrer et
d’illustrer des phénomènes mathématiques.

Les premières images des fractals de Newton réalisés par des ordinateurs datent très probablement du printemps 1977, un an avant la mort de Julia [8]. Michèle Audin m’a signalé que Julia avait dessiné, dès 1917, un ensemble
de Julia, ressemblant au citron présenté ici [9].

Ci-joints deux documents historiques :

  • le premier est de Newton (en français, traduit par Buffon !) : la première équation de l’histoire traitée par la méthode de Newton est une équation de degré 3 : \[y^3-2y-5=0,\]
  • l’autre est de Cayley, où il explique qu’il ne sait pas couper le plan en trois parties qui seraient les domaines d’attraction des trois solutions.
JPEG - 239.9 ko
JPEG - 158.6 ko

Références mathématiques

Tan Lei (Editor), The Mandelbrot Set, Theme and Variations,
Cambridge University Press, 2000.

Pour des images et résultats historiques, voir par exemple :
J. H. Curry, L. Garnett et D. Sullivan, On the iteration of a rational function : Computer experiments with Newton’s method,
Communications in Mathematical Physics, Volume 91, Number 2 / June, 1983, pages 267-277.

Pour l’apparition du lapin dans un fractal de Newton,
voir A. Douady et J. H. Hubbard, On the dynamics of polynomial-like mappings,
Annales scientifiques de l’École normale supérieure,
1985, vol. 18, no. 2, pages 287-343.

Pour les coutures et accouplements : voir Tan L., Branched coverings and cubic Newton maps, Fundamenta Mathematicae, 154 (1997), pages 207-260.

Pour aller plus loin : voir P. Roesch,
On local connectivity for the Julia set of rational maps : Newton’s famous example,
Annals of Mathematics. Second Series , Vol. 168, N. 1, pages 127-174 (2008).

Pour le lien avec le graphe séparateur et le champ de vecteurs de Newton, voir
M. Flexor et P. Sentenac, Algorithmes de Newton généralisés,
CRAS 308, no.14, 1989, pages 445-448.

Pour d’autres animations d’accouplements de polynômes : voir [la page web d’Arnaud Chéritat->http://www.math.univ-toulouse.fr/ cheritat/MatMovies/].

Les ensembles de Julia présentés dans cet article ont été dessinés à l’aide du logiciel It de
Christian Mannes, http://www.mannes-tech.com.

Notes

[1Toutes les feuilles de papier, de format A0, A1, A2, A3, A4,... ont la même forme (leurs longueurs et
largeurs sont dans le même rapport) et la feuille A0 a une surface d’un mètre carré.

[2C’est-à-dire : il faut, pour l’écrire, une infinité de chiffres après la virgule.

[3En fait dans ce cas particulier, le calcul de la racine carrée de $a$, la méthode était connue des Babyloniens : itérer
\[x\mapsto \frac{1}{2}\left(x+\frac{a}{x}\right).\]

[4Il existe d’autres méthodes itératives pour trouver
la racine carrée d’un nombre. Voir par exemple l’article de
Hodgson.

[5En termes mathématiques, ce serait dire que le lieu noir est de mesure de Lebesgue nulle.

[6D’après Xavier Buff et Arnaud Chéritat, Ensembles de Julia quadratiques de mesure de Lebesgue strictement positive, Comptes Rendus Mathématiques, 2005, no. 341/11, pages 669-674.

[7La sphère est liée au plan par une projection stéréographique, voir une belle image de projection stéréographique (sur ce site). Pour la projection stéréographique, les nombres complexes et bien d’autres informations, voir le film Dimensions de Jos Leys, Étienne Ghys et Aurélien Alvarez.

[8Selon le récit de J. H. Hubbard, dans sa préface au livre édité par l’auteur sur l’ensemble de Mandelbrot (voir les références mathématiques).

Affiliation de l'auteur

Commentaires sur l'article

Pour citer cet article : Tan Lei, « La méthode de Newton et son fractal »Images des Mathématiques, CNRS, 2009.

En ligne, URL : http://images.math.cnrs.fr/La-methode-de-Newton-et-son.html

Si vous avez aimé cet article, voici quelques suggestions automatiques qui pourraient vous intéresser :