\documentclass[12pt]{article}
\usepackage[active]{srcltx}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
\usepackage{array}
\usepackage{epsfig}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{verbatim}

\topmargin 0cm
\headsep 5.mm
\textheight 22cm
\textwidth 16cm
\oddsidemargin -0.6cm
\evensidemargin -0.6cm
\parskip 0.24cm

\pagestyle{myheadings}

\def\ds{\displaystyle }
\begin{document}

\begin{center} {\large M\'ethode de Newton et son fractale}

\end{center}

\begin{center}Tan Lei

\end{center}

Dans la vie courante, des probl\`emes math\'ematiques
se repr\'esentent souvent sous forme d'\'equations. Ainsi,
r\'esoudre ces probl\`emes revient \`a trouver des solutions
de ces \'equations.

Voici un exemple\ : prenons une feuille de papier A4 standard. Sa largeur
est de 21cm, un nombre entier tout rond. Par contre sa longueur se mesure 
entre 29cm et 30cm. Pourquoi cela? Pourquoi ne pas l'arrondir \`a un nombre entier?
En effet, pour des raisons \'economiques et esth\'etiques, cette longueur
a \'et\'e choisie pour qu'apr\`es \^etre repli\'e en deux, le papier
reprend la m\^eme forme, c'est-\`a-dire le m\^eme 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\`es le pliage, la nouvelle
longueur est 21cm, et la nouvelle largeur x/2, avec donc comme rapport 21/(x/2).
La valeur $x$ est donc solution de $x/21=21/(x/2)$, soit $x^2=2\times 21^2$,
ou encore $x^2-882 =0$. 

Calculons \`a pr\'esent $\sqrt{882}$ \`a l'aide
d'une calculatrice, vous trouverez, $29,698485$, d'o\`u la longueur en centim\`etre de
notre feuille A4. 

Cependant, cette valeur en d\'ecimale n'est qu'une approximation de $\sqrt{882}$.
Comme beaucoup d'autres probl\`emes math\'ematiques, on ne peut pas
donner une valeur exacte en d\'ecimale de $\sqrt{882}$. 

Imaginons un jour que la touche $\sqrt{\ }$ ne fonctionne pas? Ou qu'on a besoin 
d'une valeur approch\'ee avec bien plus de pr\'ecision? Ou bien on tombe sur
un autre probl\`eme o\`u aucune touche d'une calculatrice ne nous fournise une
r\'eponse? 

Heureusement le g\'enie math\'ematician Issac Newton (1642-1727) avait invent\'e un algorithme it\'eratif qui nous founit toujours des solutions approch\'ees de nos \'equations,
et ce avec autant de pr\'ecision que n\'ecessaire.

Qu'est-ce qu'un algorithme it\'eratif? Il s'agit tout simplement 
de r\'ep\'eter une grande quantit\'e de fois la
m\^eme op\'eration math\'ematique. Taper par exemple un nombre au hazard, 
disons $5$, dans une calculatrice. Puis appuyer, disons une trentaine de fois, la touche $\sqrt{\ }$ (esp\'erons qu'elle fonctionne cette fameuse touche!).
Vous allez voir d\'efiler sur l'\'ecran une succession de nombres d\'ecimaux, et ces nombres s'approchent de plus en plus vers $1$.
Essayons cette fois-ci $0,001$ \`a la place de $5$, qu'observez vous?

Ce que vous \^etes en train de faire est d'it\'erer l'op\'eration ``racine carr\'ee''. Et cette it\'eration
nous founit au fur et \`a mesure  une suite d'approximations de la valeur $1$ (pas tr\`es int\'eressant en soi). 

Vous pouvez bien s\^ur it\'erer d'autres op\'erations comme $x^2$, $\sin$ ou $\cos$ si votre
calculatrice le permet, tout en variant le choix de la valeur initiale. Vous allez constater qu'it\'erer 
$x^2$ pour $1,05$ ou $0,95$ donnerait des r\'esultats tr\`es diff\'erents, tandis qu'it\'erer
$\sin$ (ou $\cos$) donnerait toujours le m\^eme r\'esultat au final.
 Curieux ph\'enom\`enes... 


Revenons maintenant \`a la m\'ethode de Newton. Notons $P(x)=x^2-882$. Nous nous int\'eressons
\`a trouver des solutions approch\'ees de l'\'equation $P(x)=0$, autrement dit des racines
du polyn\^ome $P(x)$.
Newton s'est dit que pour cela, 
il suffit d'it\'erer l'op\'eration
 \begin{center}
 \fbox{\quad$\ds x-\frac{P(x)}{P'(x)}$\quad} 
 \end{center}
(o\`u $P'(x)$ d\'esigne la d\'eriv\'ee de $P$), soit $\ds x-\frac{x^2-882}{2x}$, ou encore
$\ds \frac12 (x+ \frac{882}{x})$.

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

Apr\`es seulement plusieurs coups d'essaie, on est d\'ej\`a tr\`es proche
 de la vraie solution $\sqrt{882}\approx 29,698485$.  Voil\`a une m\'ethode bien efficace...

On pourrait montrer que pour tout choix de la  valeur initiale proche de $\sqrt{882}$
(\`a la place de $x=1$ ici),
 la suite des valeurs it\'eratives  va 
toujours s'approcher de $\sqrt{882}$. Cette valeur initiale pourrait m\^eme \^etre prise sous la forme 
d'un nombre complexe.

Or si
 l'on prenait au hazard notre valeur initiale, la magie de Newton risque de
 perdre toute sa puissance \ :
Prenons par exemple $\sqrt{-1}=i$, le nombre imaginaire pur dont le carr\'e est $-1$. 
It\'erer l'op\'eration $\ds \frac12 (x+ \frac{882}{x})$ \`a partir de $i$ nous donnera une suite de nombres
imaginaires purs, soit\ : $$\frac12(i+\frac{882}{i})=\frac12(i+\frac{882}{i\times i}i)\underset{i^2=-1}{\overset{\text{puisque}}{=}}\frac12(i-882\,i)=  -440,5\,i,$$
puis $ -219,25\,i, \quad -251,227\,i;\quad \cdots$, et ainsi de suite. Ces valeurs ne se rapprocheront jamais
 de nos racines $\pm \sqrt{882}$. 

Que se passerait-il si nous prenons comme valeur initiale un autre nombre complexe $x+iy$?
Un peu de r\'eflection nous convaincra que si $x$ est positive, nous allons nous rapprocher
de $\sqrt{882}$, et si au contraire $x$ est n\'egative, nous allons nous rapprocher
de $-\sqrt{882}$. La droite des nombres complexes imaginaires purs est \`a la fois
la bissectrice des deux racines, et la ligne de s\'eparation de deux comportements
diff\'erents des suites de valeurs it\'eratives.

\begin{center}
\includegraphics[width=8cm]{degreetwo.jpg}
\end{center}

Essayons maintenant  la m\'ethode de Newton $\ds z-\frac{P(z)}{P'(z)}$ pour un polyn\^ome un peu plus compliqu\'e\ \ :
$\ds P(z)=(z-a+\frac12)(z+a+\frac12)(z-1)$, ici $z$ d\'esigne un nombre complexe inconnu et $a=-0,00508+0,33136\,i$.

Les racines de $P(z)$ sont $1$, $\ds-\frac12+a$ et $\ds \frac12-a$. On aurait pu croire na\"{\i}vement que,
comme dans le cas pr\'ec\'edent, le graphe s\'eparateur
passant par le centre de gravit\'e des trois racines (ici $0$) jouerait le r\^ole de la bissectrice \ :
ce graphe s\'eparerait le plan en trois r\'egions, et qu'une valeur initiale prise dans une 
r\'egion nous donnerait des approximations de la racine de sa r\'egion.

\begin{center}
\includegraphics[width=8cm]{champnewton.pdf}
\end{center}

Faisons donc une exp\'erience num\'erique, mais cette fois-ci sur un vrai ordinateur \ : 

Pla\c{c}ons-nous dans une fen\^etre carr\'ee du plan, disons $-1,4<x<1,6$, $-1,5<y<1,5$. 
D\'ecoupez ce carr\'e en $400\times 400$ pixels. Pour chaque pixel (sous forme d'un
nombre complexe $z=x+iy$), on demande notre ordinateur d'it\'erer l'op\'eration  $\ds z-\frac{P(z)}{P'(z)}$ un grand nombre de fois (par exemple mille fois), 
et on colorie le pixel $z$ bleu, respectivement  vert, rouge, si le r\'esultat nous donne une valeur proche de $1$,
respectivement proche de $\ds-\frac12+a$, $\ds \frac12-a$. Enfin  on colorie le pixel noir si
rien de tout cela se produit. Un petit programme d'une vingtaine de lignes ferait tr\`es bien
l'affaire.

Voici ce que notre ordinateur nous dessine\ :  le deuxi\`eme \'etant un agrandissement du premier dans la fen\^etre
$-0,22<x,y<0,22$.

%\begin{figure}[htbp]
\begin{center}
\includegraphics[width=8cm]{newtonrabbit.jpg}
\includegraphics[width=8cm]{newtonzoom.jpg}

\end{center}
%\caption{\footnotesize Tableau}\label{tableau}
%\end{figure}

Au lieu de voir appara\^{\i}tre le graphe s\'eparateur, on voit un joli fractale qui d\'ecoupe
le carr\'e en plein de petits lacs de toutes les couleurs, puis trois grand lac, un autour de chaque 
racine. Ces lacs sembleraient s'entremeler de mani\`ere
tr\`es compliqu\'ee...


La couleur noire repr\'esente le lieu des mauvaises valeurs de test initiales. 
M\^eme si ce lieu est relativement petit, on y voit tout de m\^eme des taches dans son int\'erieur.
Autrement dit si on a la malchance de tomber sur une valeur initiale au sein de ces taches noires,
la m\'ethode de Newton, m\^eme
en comptant les erreurs num\'eriques, ne nous am\`enera jamais vers une racine.

Le fait que ces lacs de couleurs diff\'erentes s'entrem\`elent illustre le ph\'enom\`ene ``chaotique''
de cette m\'ethode it\'erative\ : lorsqu'on est \`a la fronti\`ere de ces lacs, la moindre erreur num\'erique
nous bascule d'une racine vers une autre, ou vers un pi\`ege de couleur noir.

On peut bien s\^ur op\'erer la m\'ethode de Newton sur d'autres polyn\^omes, en changeant
la valeur de $a$ par exemple. 

Il existe des r\'esultats math\'ematiques  qui permettent de pr\'edire  pour quelle valeur de $a$ 
le lieu noir pr\'esente des taches pi\`eges dans son int\'erieur.

Lorsque le lieu noir n'a pas de tache \`a l'int\'erieur, peut-t-on pour autant affirmer que la m\'ethode
de Newton est globalement efficace?
 Pas si simple que \c{c}a. De nos jours il existe des logiciels qui produisent des valeurs al\'eatoires,
 c'est-\`a-dire compl\`etement au hazard. On aurait voulu
 dire que la m\'ethode de Newton est efficace partout si la chance de tomber sur une
 valeur noire par un tel logiciel est minime (en terme math\'ematique, si ce lieu 
 noir est de mesure de Lebesgue nulle). Or ce n'est pas toujours le cas, comme montr\'e  r\'ecemment
par deux jeunes math\'ematiciens \`a Toulouse, Xavier Buff et Arnaud Ch\'eritat. Ils
ont trouv\'e des valeurs de $a$ pour lesquelles la chance de tomber sur une valeur
initiale noire est vraiment non-n\'egligeable.

Essayons maintenant de comprendre un peu plus la structure de ce fractale de Newton.

La premi\`ere observation est que les taches noires sont pr\'esentes \`a peu pr\`es partout
\`a la fronti\`ere des lacs color\'es, de taille tr\`es diff\'erentes les unes des autres.
La deuxi\`eme est que ces taches ont toutes une belle forme,
qui ressemblent \`a un lapin \`a deux oreilles. 

Adrien Douady (1935-2006) fait partie des premiers math\'ematiciens \`a avoir observ\'e cela. Il a tr\`es vite compris 
que ces lapins proviennent de l'it\'eration d'une autre op\'eration, 
plus simple cette fois-ci, celle de $z^2+ (-0,12+0,75i) $. Faisons-nous l'exp\'erience comme lui. en colorant un pixel rouge
si ses valeurs it\'eratives par cette op\'eration s'\'echappent de l'\'ecran, et noir sinon.

Voici le r\'esultat\ : 

\begin{center}
\includegraphics[width=8cm]{rabbit.jpg}


\end{center}


Une ressemblance frappante n'est ce pas? D'ailleurs ce fractale s'appelle le lapin de Douady.

Cette observation n'explique pas encore toute la structure de notre lieu noir. Il fallait
encore comprendre comment ces multiples de lapins se sont reli\'es les uns et les autres. 

En fait, bien que ce ne soit pas du tout \'evident \`a l'oeil nu,  il y a moyen de  voir ce fractale comme deux fractales plus simples recousus ensemble. Voici l'illustration\ :

D'abord  le premier fractal, provenant de l'it\'eration de $z^3+(1,503-0,8046\,i)z^2$. Vous remarquerez que les multiples de
lapins y sont d\'ej\`a pr\'esents.
 \begin{center}
\includegraphics[width=8cm]{cubicrabbit.jpg}
\end{center}

 
Et voici le deuxi\`eme, 
provenant de l'it\'eration de $z^3+(2,12i)z^2$. 
\begin{center}
\includegraphics[width=8cm]{lemon.jpg}
\end{center}

Puis tournons notre fractale de Newton de $90^\circ$ pour mieux visualiser la couture\ :

\begin{center}
\includegraphics[width=8cm]{newtonrabbit90.jpg}
\end{center}

Et enfin la vid\'eo de la couture, film r\'ealis\'e par  A. Ch\'eritat\ :
d'abord sur le plan\ :

\bigskip

puis sur une sph\`ere, appel\'ee la sph\`ere de Riemann (cette sph\`ere est li\'ee avec le plan par
une projection st\'er\'eographique) \ :

\bigskip

 Ce proc\'ed\'e de couture 
a \'et\'e appel\'e ironiquement ``accouplement'' par Adrien Douady. 

Un petit peu de math\'ematique tout de m\^eme\ : Pourquoi la m\'ethode de Newton se
stabilise \`a une certaine racine $r$ du polyn\^ome $P(z)$?

Il suffit de mettre  $r$ \`a la place de $z$ dans $z-\frac{P(z)}{P'(z)}$, pour observer que
$r-\frac{P(r)}{P'(r)}=r-\frac{0}{P'(r)}=r$. Cela veut dire que faire op\'erer la m\'ethode de Newton 
ne changera pas la  valeur $r$. En terme math\'ematique, $r$  est 
un point fixe. Cela repr\'esente un principe assez courant
en math\'ematique\ : on transforme la r\'esolution d'une \'equation en la recherche
d'un point fixe d'un op\'erateur appropri\'e. 

Mais pour ce but on aurait pu prendre un op\'erateur plus simple, par exemple $z-P(z)$. Alors pourquoi
se fatiquer avec la division par la d\'eriv\'ee? En fait c'est pour approcher 
$P(z)$ par une \'equation lin\'eaire (la tangente) $f(z)=(z-z_0)P'(z_0)+P(z_0)$.
Cette $f(z)$ admet la m\^eme valeur et la m\^eme d\'eriv\'ee en $z_0$ que $P(z)$.
On pourrait donc imaginer que la solution de $f(z)=0$ est proche de celle de $P(z)=0$. L'\'equation $f(z)=0$
est tellement simple qu'on peut la r\'esoudre directement, soit $z=z_0-\frac{P(z_0)}{P'(z_0)}$, 
d'o\`u l'apparaition du facteur $\frac1{P'(z_0)}$.

Poussons-nous un peu plus loin dans notre compr\'ehension\ : Pourquoi l'it\'eration de la m\'ethode de Newton
nous donne des valeurs de plus en plus proches d'une racine $r$ (lorsqu'on
part d'une valeur suffisament proche), et ce de mani\`ere extr\^ement rapide? 

Pour comprendre cela nous allons mettre  $r$
dans la formule de la d\'eriv\'ee de notre op\'eration $z-\frac{P(z)}{P'(z)}$, soit $\frac{P(z)P''(z)}{P'(z)^2}$.
On constate alors que non seulement la m\'ethode de Newton laisse la valeur $r$ invariante,
elle y admet aussi une d\'eriv\'ee nulle. En terme math\'ematique, la valeur $r$ 
est un point fixe super-attractif. Cela veut dire que $r$ agit comme un puits
qui attire de toutes ses forces les valeurs voisines
vers elle. En plus \ :  la vitesse d'approximation vers $r$ est aussi rapide que
celle vers $0$ lorsque'on it\`ere l'op\'eration $x^2$ (constatons que $x^2$
laisse $0$ invariant tout en y admettant une d\'eriv\'ee nulle).

Pour avoir une id\'ee de la grandeur de cette vitesse, prenons par exemple une valeur $0,5$, puis appuyer r\'ep\'etitivement la touche $x^2$ d'une
calculatrice, on obtient\ :
\\
$0,5;\quad 0,25;\quad 0,0625;\quad 0,00390625;\quad 0,00001525878; \quad 0,00000000023283;$
\\
$0,00000000000000000005421;\quad\cdots$

En gros le nombre de z\'eros apr\`es la virgule se d\'edouble \`a chaque coup. Rapide, n'est ce pas?! Vous pouvez par exemple le comparer avec l'it\'eration de l'op\'eration ``diviser un nombre par $100$''.
Qui est-ce qui va emporter en fin de compte?

Et le graphe s\'eparateur des trois racines dans tout cela? Ce graphe est tellement naturel qu'il doit bien
jouer un r\^ole quelque part! En effet vous n'avez pas tort de penser \`a cela \ :
il suffit de ralentir le pas de la m\'ethode de Newton en y rajoutant un
facteur $h$ devant le terme $\frac{P(z)}{P'(z)}$, soit $z-h\frac{P(z)}{P'(z)}$. 
Lorsque $h$ devient infiniment petit, on a en fait affaire avec le champ de vecteurs de Newton\ :
\`a chaque point du plan on plante  le vecteur directionnel $-\frac{P(z)}{P'(z)}$. En suivant
les directions indiqu\'ees par ces vecteurs on obtient trois flots d'eau  coulant chacun vers
une racine. Et la fronti\`ere des trois bassins n'est rien d'autre que,
le graphe s\'eparateur!

\begin{center}
\includegraphics[width=8cm]{graphe.pdf}
\end{center}

Terminons par un peu d'histoire\ : Cette branche de math\'ematiques s'appelle it\'eration
des fractions rationnelles, une th\'eorie fond\'ee dans les ann\'ees 1920 par Gaston Julia (1893-1978)
et Pierre Fatou (1878-1929). Ces fractales sont d'ailleurs appel\'es ensembles de Julia.
Cette th\'eorie a connu un d\'eveloppement florissant depuis 1980, d\^ue en partie \`a l'arriv\'ee
des ordinateurs et de puissants outils math\'ematiques modernes.
 
Les premi\`eres
images des fractales de Newton datent tr\`es probablement vers le printemps 1977, selon le r\'ecit
de J. H. Hubbard (voir ci-dessous). Gaston Julia est mort un an apr\`es, \`a Paris.
 Mais je ne crois pas qu'il a eu la chance de voir ses propres cr\'eatures sous les yeux.

 
R\'ef\'erences math\'ematiques\ : 

J. H. Hubbard, Pr\'eface pour {\it The Mandelbrot Set, Theme and Variations},
 Tan Lei (Editeur), Cambridge University Press, 2000. 
 
Pour des images et r\'esultats historiques, voir par exemples\ :
James H. Curry, Lucy Garnett et Dennis Sullivan, {\it 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'apparaition du lapin dans un fractale de Newton,
voir A. Douady et J. H. Hubbard, {\it On the dynamics of polynomial-like mappings},
Annales scientifiques de l'\'Ecole normale sup\'erieure,
1985, vol. 18, n$^\circ$2, pages 287-343.


Pour les ensembles de Julia de mesures positives\ : voir Xavier Buff et Arnaud Ch\'eritat,
{\it Ensembles de Julia quadratiques de mesure de Lebesgue strictement positive}, 
Comptes Rendus Math\'ematiques, 2005, n$^\circ$341/11, pages 669-674.  

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

Pour aller plus loins\ : voir Pascale Roesch, 
{\it 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 la projection st\'er\'eographique et bien d'autres informations\ : voir  \\ http\ ://www.dimensions-math.org/.

Pour d'autres animations du m\^eme genre\ : voir \\ http\ ://www.math.univ-toulouse.fr/$\sim$cheritat/MatMovies/ .

Les ensembles de Julia ici ont \'et\'e trac\'es \`a l'aide du logiciel It de
Christian Mannes, http\ ://www.mannes-tech.com.

Le champ de vecteur et le graphe s\'eparateur ont \'et\'e trac\'es \`a l'aide du logiciel 
 Scilab.
\end{document}
