
%%% newton.tex

%Sem. Bourbaki / A. Marin / 1986
%The following is for Plain TeX 
%Save this Sweet-Write file as "Text only" file  ...'
%Then transcode to  Bourbaki/ Marin0-3.tex  using...'

\input newton.sty %% after export
%\input RESOURCESimple.occ %% during export

\magnification=1200 %adjust! %for print run only
\hsize=15truecm %for print
%\vsize=480 pt %for print
\nopagenumbers 


\headline{\ifnum \pageno>1  \hss\raise -5pt 
\hbox{\tenrm 
670-\folio}\hss\fi}
\widowpenalty=5000
\emergencystretch=20pt

\csname Francais\endcsname %%Ok of not there

\par \noindent S\'eminaire BOURBAKI\hfill                
Novembre 1986 \break
\Admin {19^{e}} ann\'ee, 1986-87, \Admin {n^{o} 670} 
\vskip 35pt plus 5pt minus 5pt

\Title 
---  G\'eom\'etrie  des  polyn\^omes ---\\
Co\^ut global moyen de la m\'ethode de Newton
\endTitle \medskip
\Author 
(d'apr\`es M. Shub et S. Smale)
\endAuthor \vskip 20pt  plus 5pt minus 5pt
\Author 
par Alexis MARIN
\endAuthor  \vskip 25pt  plus 5pt minus 5pt
%

   La suite $1,\enskip  3/2,\enskip  17/12,\enskip 
\dots{}\,\,$ d\'efinie par $x_{0}=1$ et la relation de 
r\'ecurrence $x_{n+1}={\textstyle {1\over 
2}}(x_{n}+2/x_{n})$ converge tr\`es rapidement vers 
$\sqrt 2 $.  Le troisi\`eme terme $x_{3}=577/408\sim 
1,414215\,\dots{}$ poss\`ede d\'ej\`a les six premiers 
chiffres du d\'eveloppement d\'ecimal de $\sqrt 2\sim 
1,414213\,\dots{}$ alors que  $x_{2}=17/12\sim 
1,416\,\dots{} $ n'en avait que trois.  Cette suite, 
connue des Babyloniens, est produite par la {\it 
m\'ethode de Newton\/}.  Pour approcher une solution 
d'une \'equation $f(x)=0$, o\`u $f$ est de classe 
$C^{2}$, Newton prend une {\it valeur initiale\/} 
$x_{0}$ et, it\'erant l'application $x\mapsto 
N_{f}(x)=x-f(x)/f'(x)$,  il engendre la suite $x_{n}= 
N_{f}^{n}(x_{0})$. (Notez que $N_{f}(x)={\textstyle 
{1\over 2}}(x+2/x)$ si $f(x)=x^{2}-2$.) Les points 
fixes de $N=N_{f}$ sont les z\'eros de $f$, et puisque 
$N'=ff''/(f')^{2}$, un {\it z\'ero simple\/} $w$ de 
$f$ (i.e. $f(w)=0\mathbin{\not =}f'(w))$ est un {\it 
point fixe superattractif\/} de $N$ (i.e. $N(w)=w$ et 
$N'(w)=0)$, en particulier il y a une constante $K$ et 
un voisinage $V$ de $w$ dont tout point $x$ v\'erifie 
$ \left \vert N(x)-w\right \vert \leq K \left \vert 
x-w\right \vert ^{2}$.  Cette {\it convergence 
quadratique\/}  explique le ``doublement de 
pr\'ecision'' \`a chaque it\'eration observ\'e 
ci-dessus. 

   Cependant, si $x_{0}$ n'est pas suffisamment proche 
d'une racine de $f$, la suite de Newton peut avoir un 
comportement chaotique ou s'accumuler sur un cycle, ce 
dernier ph\'enom\`ene se produisant dans un ouvert de 
l'espace $P_{d}$ des polyn\^omes de degr\'e $d$, d\`es 
le degr\'e 3, et ce pour un ouvert de valeurs 
initiales.  Pour trouver une bonne valeur initiale, on 
peut explorer syst\'ematiquement le domaine de $f $, 
mais le co\^ut d'un tel balayage est prohibitif; on 
pr\'ef\`ere {\it tirer au sort\/} une valeur initiale, 
et it\'erer quatre ou cinq fois l'application de 
Newton;  avec un peu de chance, la valeur de $f$ sur 
le dernier it\'er\'e est pratiquement nulle, sinon on 
relance les d\'es \dots{} . L'exp\'erience confirme 
que, sauf pour les polyn\^omes pathologiques et {\it 
rares\/}, les joueurs de d\'es sont gagnants.

   Pour justifier cette pratique, il faut munir les 
espaces de poly\-n\^omes et de valeurs initiales d'une 
mesure de probabilit\'e.  Smale consid\`ere l'espace 
$$
   P_{d}(1)=\left \lbrace 
p(v)=v^{d}+a_{d-1}v^{d-1}+\dots{}+a_{0}\enskip 
\bigMidvert \enskip a_{i}\in {\Bbd C}\,,\enskip  \left 
\vert a_{i}\right \vert \leq 1\right \rbrace 
$$
 muni de la mesure de Lebesgue  $\mu $ sur les 
coefficients, normalis\'ee par $\mu (P_{d}(1))=1$. On 
ne perd rien \`a se limiter \`a $P_{d}(1)$ car, pour 
tout polyn\^ome $q$ de degr\'e $d>1$, il existe $a$ et 
$b$ positifs avec $p(v)=aq(bv)$ dans $P_{d}(1)$; 
d'autre part (voir 5.4), les racines de $p\in 
P_{d}(1)$ sont de module inf\'erieur \`a  2.  
Connaissant $p(v_{0})$ et $p'(v_{0})$, Smale a un 
crit\`ere pour savoir si, partant de $v_{0}$, la 
m\'ethode de Newton converge quadratiquement  
(\Cite{Sm5}, cf. {\S }6).  Il vient de montrer  
(\Cite{Sm6}) que, si pour un polyn\^ome $p$ de 
$P_{d}(1)$ la moyenne du nombre de tirages dans le 
disque $\lbrace  \left \vert v\right \vert \leq 
3\rbrace $ pour obtenir une valeur initiale $v_{0}$ 
v\'erifiant son crit\`ere est sup\'erieur \`a $n$  
alors $p$ se trouve dans un ensemble exceptionnel 
${\Cal E}_{n,d}$ de mesure born\'ee par $(\Rm 
{constante})(d^{5}/n)$.  Dans  \Cite{ShSm1}, il y 
avait un r\'esultat dans le m\^eme sens, mais sans 
crit\`ere permettant de savoir si on a gagn\'e  (cf. 
2.3).

   D\`es 1976, lors de ses travaux d'\'economie 
math\'ematique  (\Cite{Sm1}), puis avec Hirsch 
(\Cite{HiSm}), Smale avait introduit des {\it 
m\'ethodes de Newton glo\-bales\/} (cf. {\S }{\S }3 et 
5) n'ayant qu'une convergence lin\'eaire mais dont le 
co\^ut global peut \^etre estim\'e plus finement.  En 
1981, il d\'egageait une jolie d\'emonstration du 
th\'eor\`eme de d'Alembert-Gauss  (\Cite{Sm2} et {\S 
}3)  et prouvait le r\'esultat suivant:  {\it Pour 
tout  $0<\mu <1$, il y a un ensemble exceptionnel   
$U_{d}(\mu )$ de mesure  $\mu $  dans   $P_{d}(1)$ tel 
que, pour tout  $p$ hors de   $U_{d}(\mu )$, une 
m\'ethode de Newton glo\-bale partant de   $v_{0}=0$ 
fournit en moins de  $(100(d+2))^{9}/\mu ^{7}$  
it\'erations\/}  une valeur \`a partir de laquelle le 
``doublement de pr\'ecision'' \`a chaque it\'eration 
de Newton se produit.  En 1983 avec Shub (\Cite{ShSm1} 
et \Cite{ShSm2}), il introduit des m\'ethodes d'ordre 
sup\'erieur (dont chaque it\'eration n\'ecessite le 
calcul de $\log{d}$  d\'eriv\'ees de $p$ si $p\in 
P_{d}(1)$).  Partant d'un point $v_{0}$ pris au hasard 
sur un cercle de grand rayon, Shub et Smale obtiennent 
un bon z\'ero approch\'e en $N_{d}(\mu )$ it\'erations 
o\`u $N_{d}(\mu )$ cro\^\i t lin\'eairement en $d$ : 
$$
     N_{d}(\mu ) = L_{1}d\,( \left \vert \log\mu 
\right \vert /\mu )^{1+1/\log{d}}+ L_{2}\enskip 
\enskip \Rm {avec}\enskip \enskip 
20>L_{1}>L_{2}\enskip \enskip ,
$$
et ils estiment le nombre d'op\'erations 
arithm\'etiques n\'ecessaires.  En 1984, dans un 
survol  (\Cite{Sm4}) o\`u, {\it sans pr\'etendre 
produire des algorithmes rivalisant avec ceux 
couramment utilis\'es\/}, il cherche \`a expliquer 
pourquoi {\it les algorithmes efficaces de l'analyse 
sont rapides en moyenne\/}  bien qu'ils pi\'etinent 
sur des cas d\'eg\'en\'er\'es, et il d\'ecrit une 
m\'ethode glo\-bale du premier ordre qui permet de 
retrouver avec de meilleures bornes la plupart des 
r\'esultats de \Cite{ShSm1} et \Cite{ShSm2}  en 
n'ayant besoin \`a chaque it\'eration de n'\'evaluer 
que $p$ et $p'$ (cf. {\S }4).

   Le grand avantage de la m\'ethode de Newton sur les 
autres proc\'ed\'es de r\'esolution approch\'ee d'une 
\'equation d'une variable r\'eelle (dichotomie, 
s\'ecante, \dots{}) est qu'elle s'applique en toute 
dimension et m\^eme dans un Banach, ce qui permet de 
traiter des \'equations fonctionnelles  (\Cite{KA}, 
chap. 18).  Renegar a \'etendu aux syst\`emes de $n$ 
\'equations polynomiales en $n$ inconnues complexes 
les r\'esultats de Shub-Smale \Cite{R1}, et \Cite{Sm6} 
contient des r\'esultats valables dans un Banach.

   Dans le cas d'un polyn\^ome d'une variable complexe, 
l'application de Newton a une extension rationnelle 
$(x,p)\mapsto N_{p}(x)$ \`a la sph\`ere de Gauss $S$~: 
 La m\'ethode de Newton est un algorithme {\it 
purement it\'eratif rationnel\/} et l'on peut se 
demander s'il existe un autre algorithme purement 
it\'eratif rationnel  $G : S\times P_{d} 
\llongrightarrow         S$  qui soit de plus 
\Bi{g\'en\'eriquement convergent },  i.e.
$$
     \lbrace (x,p)\in S\times P_{d}\enskip \bigMidvert 
\enskip G_{p}^{n}(x)\enskip \,\Rm {ne converge pas 
vers une racine de}\,\enskip p\rbrace 
$$
est de mesure nulle.  Pour  $d>3$, la th\`ese de 
McMullen (\Cite{McM}) r\'epond: ``non''.  Ceci 
n'arr\^eta pas Shub et Smale: avec la conjugaison 
complexe en plus des op\'erations arithm\'etiques, ils 
ont construit un algorithme purement it\'eratif 
g\'en\'eriquement convergent pour les syst\`emes de 
$n$ polyn\^omes en $n$variables complexes, et, pour 
$n=1$, un tel algorithme qui, pr\`es des racines, est 
la m\'ethode de Newton (\Cite{ShSm3} et {\S }7).

   D'autre part, Dantzig (cf. \Cite{Sm3}) avait 
conjectur\'e que: $\rho (m,n)$ {\it le nombre moyen 
d'it\'erations  n\'ecessaires pour r\'esoudre par la 
m\'e\-thode du simplexe un probl\`eme lin\'eaire \`a  
$m$ contraintes et $n$ variables est, pour  $m$ 
fix\'e, lin\'eaire en\/} $n$.  En 1982, Smale 
r\'esolvait par les m\^emes m\'ethodes ce fameux 
probl\`eme; il donne une fonction $K(\varepsilon ,m)$ 
telle que, pour tout $\varepsilon >0$,\enskip  $\rho 
(m,n)\leq Kn^{\varepsilon }$ (\Cite{Sm3}).  Depuis, 
des algorithmes polynomiaux en $m$ et $n$ ont \'et\'e 
trouv\'es  (\Cite{R2}, \Cite{Sm6}).

   Tous ces r\'esultats illustrent l'int\'er\^et de 
l'introduction d'id\'ees \'el\'ementaires de topologie 
et de r\'esultats g\'en\'eraux comme le th\'eor\`eme 
de la vari\'et\'e stable dans les probl\`emes concrets 
de calcul (cf. \Cite{Sh} et {\S }7).

   Dans cet expos\'e, je me limiterai aux polyn\^omes 
d'une variable complexe.

   Mes remerciements vont \`a J.J.~Risler qui m'a 
convaincu d'\'etudier les travaux de Smale pour son 
s\'eminaire, ainsi qu'\`a L. Guillou pour ses 
commentaires perspicaces sur ce texte.


\Subheading {1.  M\'ethode de Newton, chaos, et non 
convergence g\'en\'erique}  
%
   Si un polyn\^ome r\'eel  $f(t) = \prod _{i=1}^{d}  
(t-x_{i})$ a toutes ses racines r\'eelles et 
distinctes, il en est de m\^eme de sa d\'eriv\'ee  
$f'(t)=d\prod _{j=1}^{d-1}(t-c_{j})$, et z\'eros et 
points critiques alternent 
$x_{1}<c_{1}<x_{2}<\dots{}<x_{d}$ dans ${\Bbd R}$.  
Soit  $f$ un tel polyn\^ome de degr\'e  $d\geq 3$ et 
notons  $N=N_{f}$.  Pour l'orbite $\lbrace 
t_{n}=N^{n}(t)\rbrace $ d'un point $t$, il y a trois 
possibilit\'es:
\Item {1)}    $t_{n}$ converge vers un point fixe de 
$N$ (un z\'ero de $f$);
\Item {2)}    $t_{n}$ n'est pas d\'efini pour 
$n>n_{0}$ car $t_{n_{0}}$  est un point critique;
\Item {3)}    $t_{n}$ est d\'efini pour tout $n$, mais 
ne converge pas.
\medskip\nobreak 
   Soit $S_{1}$, $S_{2}$, $S_{3}$ la partition 
correspondante de  ${\Bbd R}$.  Comme les points fixes 
$x_{i}$ de $N$ sont attractifs  ($ \left \vert 
N'(x_{i})\right \vert =0<1$), $S_{1}$ est ouvert.  
Soient  $b_{1},\dots{},b_{d}$ les bandes 
$]c_{i-1},c_{i}[$ \enskip (ici $c_{0}=-\infty $ et 
$c_{d}=+\infty $). Un coup d'oeil \`a la figure~1 nous 
assure que $N$ envoie des points proches des $c_{i}$ 
dans $b_{1}$ ou $b_{d}$ et que $S_{1}$ contient ces 
deux bandes, donc $S_{2}$ est disjoint de $\overline 
S_{3}$, et $S_{3}$ est un ferm\'e invariant par $N$ 
inclus dans $b_{2}\cup \dots{}\cup b_{d-1}$.



\Diagram {{140}\hfill \raise 0 pt \hbox{Figure 1} 
\hfill \hfill        Figure 2\hfill } 

   Soit  $\Omega $ l'espace des suites infinies en les 
symboles $b_{2},\dots{},b_{d-1}$ muni de la topologie 
produit; le d\'ecalage $D$ agit sur $\Omega $.  
L'application $h:S_{3}\rightarrow \Omega $ d\'efinie 
par $N^{n}(x)\in h(b)_{n}$ est continue et envoie le 
syst\`eme dynamique $(S_{3},N)$ dans $(\Omega ,D)$.

\Theorem {Th\'eor\`eme 1.1 \Rm {(Barna, Saari et 
Urenho \Cite{Ba}, \Cite{SU})}}    Si le polyn\^ome  
$f$ de degr\'e  $d\geq 3$ a tous ses z\'eros r\'eels 
et distincts, alors  $S_{3}$ est un Cantor de mesure 
nulle, l'application  $h$ est surjective et toute 
orbite p\'eriodique non constante de  $D$ se rel\`eve 
en une orbite de  $h$ de m\^eme p\'eriode, les orbites 
constantes se relevant en des orbites de p\'eriode  
2.\endTheorem 

\Proof {D\'emonstration}    Pour $1<i<d$, soit $\beta 
_{i}=\,\,]e_{i},f_{i}[$ la composante connexe de 
$x_{i}$ dans $S_{1}$, alors $S_{3}\subset B = \bigcup  
\left \lbrace b_{i}\setminus \beta _{i} \bigMidvert  
1<i<d\right \rbrace $ et $N$ \'echange $e_{i}$ et 
$f_{i}$ (cf. Figure~2).  
             
   Comme $\Lim_{t\rightarrow c_{i}}N'(t) = -\infty $  et 
 $N'(x_{i})=0$,  l'\'equation 
      $$N'(x)=-a^{2}             \Eqno (*)$$
a au moins une solution dans chacun des $2d-2$ 
intervalles de $B$ et il n'y a qu'une solution par 
intervalle car \Admin {(*)} est de degr\'e $2d-2$, 
donc $N'$ est strictement monotone sur chaque 
intervalle sur lequel elle est n\'egative, en 
particulier croissante sur $]c_{i-1},e_{i}]$ et 
d\'ecroissante sur $[f_{i},c_{i}[$.  Par un calcul 
astucieux (\Cite{Ba}, p.202-206), Barna obtient 
$N'(e_{i})<-1$ et $N'(f_{i})<-1$; donc $N$ est 
dilatante sur $B$, et a fortiori sur $S_{3}\subset B$. 
Comme $S_{3}$ est invariant, sa mesure doit \^etre 
nulle.  Le reste du th\'eor\`eme est facile.  
\endProof 

   Dans \Cite{SU} et \Cite{HM}, on trouvera d'autres 
informations sur la dynamique de $N$.  Hurley et 
Martin ont aussi observ\'e que si $T_{f}$ est une 
application $C^{2}$ d\'efinie dans le compl\'ementaire 
d'un ensemble fini $J$, tendant vers l'infini pr\`es 
de $J$ et dont les points fixes sont attractifs, alors 
deux points fixes cons\'ecutifs sont s\'epar\'es par 
une asymptote du graphe de $T_{f}$, et $T_{f}$ 
pr\'esente le m\^eme chaos que $N_{f}$.

   Le th\'eor\`eme de Barna reste vrai s'il y a des 
racines multiples. En ce cas, comme $S_{2}$ est 
d\'enombrable, la mesure de ${\Bbd R}\setminus S_{1}$ 
est nulle, ce qui semble donner raison aux joueurs.  
Cependant, pour tout $d>2$, il y a des polyn\^omes $p$ 
de degr\'e $d$ avec $p''(0)=0$ et 
$p(0)=-p'(0)\mathbin{\not =}0\mathbin{\not 
=}p(1)=p'(1)$ et donc pour lesquels $\lbrace 
0,1\rbrace $ est un cycle superattractif d'ordre 2 de 
$N$ (par exemple \hskip 1pt \Footnote{(\dag 
)}{D'apr\`es le th\'eor\`eme de Barna, un tel 
polyn\^ome a des racines complexes.} le polyn\^ome 
$p(z)={\textstyle {1\over 2}}z^{3}-z+1$).  Tout 
polyn\^ome  $q$  proche de  $p$  poss\`ede un cycle 
attractif d'ordre $2$. Il s'en suit que {\it la 
m\'ethode de Newton n'est pas un algorithme 
g\'en\'eriquement convergent\/}.

   La dynamique holomorphe donne d'autres informations 
sur les orbites de $N$ (voir  \Cite{Sm4}, \Cite{DH} et 
\Cite{F}).





\Subheading {2.  Les m\'ethodes d'Euler-Newton, un 
crit\`ere au but de convergence}  
%
   Soient  $p : {\Bbd C}\rightarrow {\Bbd C}$ un 
polyn\^ome et $v$ un point r\'egulier de $p$ (i.e. 
$p'(v)\mathbin{\not =}0$); il y a, d\'efini au 
voisinage de $z=p(v)$, un unique inverse \`a droite de 
$p$ envoyant $z$ sur $v$, notons le $p_{v}^{-1}$, de 
rayon de convergence $r_{v}$ en $v$.  Notons 
$D_{v}=D(z,r_{v})$.  Si  $r_{v}> \left \vert z\right 
\vert $, Euler calcule une racine $w$ de $p$ gr\^ace 
au d\'eveloppement de Taylor de $p_{v}^{-1}$ en $z$ : 
$$
   w = p_{v}^{-1}(0) = p_{v}^{-1}(z-z) 
   = \displaystyle \sum _{n=0}^{\infty } {1\over n!}\, 
\left \lbrace {d^{n}\over dz^{n}}p_{v}^{-1 }\right 
\rbrace _{z}\,(-z)^{n }   \Eqno (2.1)
$$
   Le calcul des termes de (2.1) co\^utant de plus en 
plus cher, Euler pr\'ef\`ere tronquer cette s\'erie 
\`a l'ordre $k$ et it\'erer l'application $v\mapsto 
E_{k}(v)$ ainsi obtenue.  Remarquons que 
$E_{1}(v)=v-p(v)/p'(v)$ est l'application de Newton.

\Theorem {Proposition 2.1 \Rm {(\Cite{ShSm1}, 
\Cite{Sm4})}}    Pour chaque  $k$, il y a une 
constante  $c_{k}<1$ telle que si  $w$ est une racine 
simple de  $p$ et  $v_{0}\in p_{w}^{-1}(c_{k}D_{w})$, 
alors pour tout  $n$ l'it\'er\'e  
$v_{n}=E_{k}^{n}(v_{0})$ est dans  
$p_{w}^{-1}(D_{w})$, la suite  $v_{n}$ converge vers  
$w$, et 
$$
 \left \vert p(v_{n})\right \vert  \leq  
b^{(k+1)^{n}-1} \left \vert p(v_{0})\right \vert 
\enskip \enskip ,\enskip \enskip \Rm {o\`u }\enskip 
\enskip \enskip b=  \left \vert p(v_{0})\right \vert  
/c_{k}r_{w}<1\enskip . 
$$
La suite  $c_{k}$ est croissante, tend vers  $(2-\sqrt 
2)/4$ quand  $k\rightarrow \infty $, et 
$$
  c_{1} = 1/9 < c_{2} < 1/8 < c_{3} < 1/7 < c_{4} < 
(2-\sqrt 2)/4 < 1/6\enskip \enskip .
$$\endTheorem 
   Un \Bi{bon z\'ero approch\'e  } (pour la m\'ethode 
d'Euler d'ordre $k$) est un $v_{0}$ auquel on peut 
appliquer la proposition 2.1.  Nous ne d\'emontrerons 
et n'utiliserons 2.1 qu'avec $k=1$.  Pour $k>1$, voir 
\Cite{ShSm1, \Rm {p.115-121}}.

\Remark {Remarque 2.2}  La connaissance de  $r_{w}$ 
est inaccessible \`a un observateur en $v=v_{0}$; {\it 
on peut cependant minorer  $r_{w}$ par  $\rho _{p}$ le 
module de la plus petite valeur critique\/},  qui peut 
s'estimer \`a l'aide du discri\-mi\-nant.  Le 
crit\`ere obtenu a peu d'int\'er\^et du point de vue 
num\'erique, car le calcul du discriminant co\^ute 
trop cher; il sera cependant utile pour donner des 
estim\'ees probabilistes.\endRemark 

\Theorem {Proposition 2.3 \Rm {(\Cite{ShSm1})}}  Soit  
$D$ le disque unit\'e; la probabilit\'e dans  $D\times 
P_{d}(1)$ pour que  $v_{0}$ dans  $D$ soit un bon 
z\'ero approch\'e d'un polyn\^ome  $p$ de $P_{d}(1)$ 
est minor\'ee par  $c/d^{5}$ avec  $c>4\cdot 
10^{-4}$.\endTheorem 

\Proof {Preuve de 2.3}  Un point $z$ est une valeur 
critique de $p$ si et seulement si le polyn\^ome $p-z$ 
est de discriminant z\'ero.  Comme le discriminant 
${\Cal D} : P_{d}\rightarrow {\Bbd C}$ est de degr\'e 
$d-1$  en le terme constant, on a, en posant ${\Cal 
E}_{d}(\rho )=\lbrace p\in P_{d}(1)\bigMidvert \rho 
_{p}<\rho \rbrace $, le lemme suivant:

\Theorem {Lemme 2.4} La mesure de  ${\Cal E}_{d}(\rho 
)$ est major\'ee par  $(d-1)\rho ^{2}$. \endProof 
\endTheorem 

   Comme le produit des racines de $p$ est $a_{0}$, un 
polyn\^ome $p$ de $P_{d}(1)$ (qui v\'erifie $ \left 
\vert a_{0}\right \vert \leq 1$) a une racine $w$ dans 
$D$.  Si de plus $p$ est hors de ${\Cal E}_{d}(\rho )$ 
pour un $\rho >0$, $w$ est un z\'ero simple et $ \left 
\vert p'(w)\right \vert \leq 1+2+\dots{}+d 
={\textstyle {1\over 2}} d(d+1)$; donc, gr\^ace au 
th\'eor\`eme du quart (cf. \Cite{O},~p.\,\,3), le 
disque $D'$ centr\'e en $w$ et de rayon $r=\rho 
/18d(d+1)$ est inclus dans $ p_{w}^{-1}(1/9D_{w})$, et 
donc constitu\'e de bons z\'eros approch\'es.  L'aire 
de $D\cap D'$ est sup\'erieure \`a $\sigma =r^{2}\sqrt 
{1-r^{2}/4}$\enskip \enskip (cf. Figure~3).  Soit  
$0<\mu <1$. En prenant  $\rho =\sqrt {\mu /(d-1)}$ 
dans 2.4, la probabilit\'e cherch\'ee est minor\'ee 
par 
${1\over \raise .5pt\hbox{$\pi $}}\int _{0}^{1}\sigma 
(\mu )d\mu \geq c/d^{5}$.  \endProof 



\vDiagram{ {75}\hskip\parindent Figure 3} 



\Remark {Notations 2.5}   Le polyn\^ome $p$ \'etant 
fix\'e et $v$ r\'egulier pour $p$, on pose: $\beta 
(v)= \left \vert p(v)/p'(v)\right \vert $, $\gamma 
(v)= \left \vert p^{(k)}(v)/k!\,p'(v)\right \vert 
^{1/k-1}$ et $\alpha (v)=\beta (v)\gamma (v)$.  Si 
l'on a besoin de pr\'eciser $p$, on \'ecrit $\beta 
(v,p)$, $\gamma (v,p)$, $\alpha (v,p)$.\endRemark 

\Proof {D\'emonstration de 2.1 lorsque  $k=1$}    
Calculons $p(v_{1})$ par la s\'erie de Taylor de $p$ 
en $v=v_{0}$; comme $k=1$, $v_{1}-v=\beta (v)$ et les 
deux premiers termes s'annulent, les autres \'etant 
major\'es par $ \left \vert p(v)\right \vert (\alpha 
(v))^{k-1}$ d'o\`u le

\Theorem {Lemme 2.6}  Si   $v$ est r\'egulier pour  
$p$ et  $\alpha (v)<\alpha $, alors  $ \left \vert 
p(v_{1})\right \vert <{\alpha \over 1-\alpha } \left 
\vert p(v)\right \vert $.  \endProof \endTheorem 

\Theorem {Lemme 2.7}  Si  $v$ est r\'egulier pour  
$p$, alors  $\alpha (v)<4 \left \vert p(v)\right \vert 
/r_{v}$.\endTheorem 

\Proof {D\'emonstration de 2.7}    Comme $p$ est 
l'inverse de la fonction univalente 
$p_{v}^{-1}:D_{v}\rightarrow {\Bbd C}$, les 
coefficients $a_{k}$ de son d\'eveloppement de Taylor 
en $v$ sont born\'es par un th\'eor\`eme de L{\"o}wner 
(\Cite{H},~p.\,\,137):
 $$ 
 \left \vert a_{k}\right \vert  \leq  B_{k} \left 
\vert a_{i}\right \vert ^{k}r_{v}^{k-1} \enskip 
\enskip \enskip \enskip \Rm {o\`u}
   \enskip \enskip \enskip \enskip B_{k} =  2^{k 
}{1\cdot 3\,\dots{}(2k-1) \over  1\cdot 
2\,\dots{}k\cdot (k+1)} \leq  4^{k-1} 
$$
d'o\`u le lemme.  \endProof 

   Sous les hypoth\`eses de 2.1, comme  $r_{v}>r_{w}- 
\left \vert p(v)\right \vert $, on d\'eduit de ces 
deux lemmes $ \left \vert p(v)\right \vert \leq A 
\left \vert p(v)\right \vert ^{2}$ o\`u $A \left \vert 
p(v)\right \vert <b$.  D'autre part, comme sur 
$D(0,r_{w}/9)$ les inverses $p_{v}^{-1}$ et 
$p_{w}^{-1}$ co\"\i ncident, et $$
 \left \vert v_{1}-v\right \vert = \left \vert 
p(v)/p'(v)\right \vert \leq r_{w}\,/\,9 \left \vert 
p'(v)\right \vert \leq r_{v}\,/\,8 \left \vert 
p'(v)\right \vert <r_{v}\,/\,4 \left \vert p'(v)\right 
\vert \enskip \enskip ,
$$
le th\'eor\`eme du quart assure que $v_{1}$ est dans 
$p_{w}^{-1}(D_{w})$.  Donc, par r\'ecurrence, $ \left 
\vert p(v_{n+1})\right \vert ^{2}<A \left \vert 
p(v_{n})\right \vert ^{2}$ avec  $A \left \vert 
p(v_{0})\right \vert <b$, d'o\`u la proposition.  
\endProof 


\Subheading {3.  Le th\'eor\`eme de d'Alembert-Gauss, 
une m\'ethode de Newton globale}  
%
   L'ensemble $\Sigma $ des valeurs critiques d'un 
polyn\^ome $p$ de degr\'e $d>0$ est fini  ($ \left 
\vert \Sigma \right \vert \leq d-1$); comme $p$ est 
une application ouverte, il y a un $v$ tel que le 
rayon $R_{z}=\lbrace tz\enskip \vert \enskip 0<t\leq 
1\rbrace $ ($z=p(v)$) \'evite $\Sigma $ (cf. 
Figure~4); le point $v$ est donc r\'egulier, 
$p_{v}^{-1}$ se prolonge analytiquement \`a un 
voisinage de $R_{z}$ et $w=\Lim_{t\rightarrow 0}  
p_{v}^{-1}(tz)$
est une racine de $p$.  Par des majorations faciles, 
on peut obtenir un ensemble de $d$ points de grand 
module contenant un tel $v$: cette d\'emonstration est 
constructive.  Elle conduisit Smale (\Cite{Sm2}) \`a 
\'etendre $p_{v}^{-1}$ \`a des secteurs angulaires.



\vDiagram{ {50}Figure 4 \hfill    Figure 5  } 




   L'\Bi{\'etroitesse } $e(v)$ (relativement \`a $p$) 
d'un point $v$ non racine de $p$ est le plus grand 
$\theta \geq 0$ tel que $p_{v}^{-1}$ se prolonge au 
secteur:
            $$ W(z,\theta ) = \lbrace z'\in {\Bbd 
C}\enskip \bigMidvert \enskip  \left \vert \Rm 
{Arg}(z'/z)\right \vert <\theta \rbrace $$
(rappelons que $z=p(v)$ et convenons que 
$W(z,0)=\lbrace z\rbrace $ (cf. \Cite{G})).

\Theorem {Th\'eor\`eme 3.1}    Il y a des constantes  
$M$ et  $L$ d\'ependant de $\theta $ ($L>0<M<1$) 
telles que, pour  $1-M\leq K<1$ et  $v_{0}$ un point 
d'\'etroitesse  $\theta >0$ relativement \`a un 
polyn\^ome non constant  $p$, et si l'on note  
$t_{i}=K^{i}p(v_{0})$ la suite  $v_{i}$ d\'efinie par:
$$
   v_{i} = N_{p-t_{i}}(v_{i-1}) = 
v_{i-1}-{p(v_{i-1})-t_{i} \over  p'(v_{i-1})}     
\Eqno ({\Sharp})
$$
converge vers une racine de  $p$.  De plus:
$$
    \left \vert p(v_{n})\right \vert \leq K^{n}(1+L) 
\left \vert p(v_{0})\right \vert             \Eqno 
({\Sharp}{\Sharp})
$$
$M=\sin\theta /(24+\sin\theta )$ et  $L={2\over 3}M$ 
conviennent.\endTheorem 
\penalty -1000  
\Theorem {Corollaire 3.2}   Soit  $p$ un polyn\^ome de 
 $P_{d}(1)$ et  $\varepsilon >0$.  Si  $v_{0}$ est un 
point d'\'etroitesse  $\theta >0$ et de module  $R>1$, 
et  $v_{n}$ est la suite d\'efinie par  ({\Sharp}) 
avec  $K=1-M$, alors, si  $n\geq N(d,\theta 
,R,\varepsilon )$, on a  $ \left \vert p(v_{n})\right 
\vert \leq \varepsilon $, o\`u $N(d,\theta 
,R,\varepsilon )=K_{1}d+K_{2}+K_{3}\log(1/\varepsilon 
)$ avec  $K_{1}=K_{3}\log{R}$,\,\, 
$K_{2}=K_{3}\log{R(1+L)\over R-1}$ et  $K_{3} = 
{1\over  \left \vert \log(1-M)\right \vert }<{1\over 
M}$.
\endProof \endTheorem 

\Proof {D\'emonstration de 3.1}    Posons 
$z_{n}=p(v_{n})$, $r_{n}=r_{v_{n}}$ et 
$D_{n}=D(t_{n},t_{n}\sin\theta )$.  Comme $t_{n}=K^{n} 
\left \vert p(v_{0})\right \vert $, l'in\'egalit\'e 
({\Sharp}{\Sharp}) suit de:
\medskip\nobreak 
\Item {{\bf (a_{n})} }      $ \left \vert 
z_{n}-t_{n}\right \vert \leq L \left \vert t_{n}\right 
\vert  $.
\medskip\nobreak 
   \Admin {(a_{0})} est vraie car $t_{0}=z_{0}$.  De 
\Admin {(a_{n})}, il vient: 
\medskip\nobreak       
\Item {{\bf (b_{n})}}       $ \left \vert 
z_{n}-t_{n+1}\right \vert \leq  \left \vert 
z_{n}-t_{n}\right \vert + \left \vert 
t_{n}-t_{n+1}\right \vert \leq (L+M) \left \vert 
t_{n}\right \vert  $.
\medskip\nobreak 
   Comme $D_{n}$ est inclus dans $W(t_{0},\theta )$ (cf. 
Figure~5), on tire de \Admin {(a_{n})} et \Admin 
{(b_{n})} :
$$
 r_{n}\geq  \left \vert t_{n}\right \vert \sin\theta - 
\left \vert z_{n}-t_{n}\right \vert  \geq  (\sin\theta 
-L) \left \vert t_{n}\right \vert  \geq  J \left \vert 
z_{n}-t_{n+1}\right \vert  \enskip \enskip ,  
$$ 
o\`u $J = (\sin\theta -L)/(L+M)$.  Supposons
$$
      J>4  \enskip \enskip .               \Eqno (*)
$$
Les lemmes 2.6 et 2.7 appliqu\'es au polyn\^ome 
$p-t_{n+1}$ donnent:
$$ 
      \left \vert z_{n+1}-t_{n+1}\right \vert  \leq 
{ 4 \left \vert z_{n}-t_{n+1}\right \vert ^{2} \over  
r_{n}-4 \left \vert z_{n}-t_{n+1}\right \vert  } \leq  
I \left \vert t_{n+1}\right \vert \enskip \enskip ,
$$
o\`u $I=4(L+M)/M(J-4)$.  Donc, si de plus
$$
       I<\sin\theta \enskip \enskip ,                \Eqno (*')
$$
le point $z_{n+1}$ est dans $W(z_{0},\theta )$, et si 
enfin
$$
      I<L\enskip \enskip ,               \Eqno (*'')
$$
la condition \Admin {(a_{n+1})} est v\'erifi\'ee.  Que 
les valeurs de $M$ et $L$ donn\'ees dans 3.1 
v\'erifient les hypoth\`eses (*) n'est plus qu'un 
exercice de calcul.~\endProof 
%\input RESOURCE% for test run
%\input Bourbaki/Marin0-3% for final run    

\Subheading {4.  Les algorithmes probabilistes}  
%
   Soit $S_{R}$ le cercle $\lbrace v\,\,\bigMidvert \,\, 
\left \vert v\right \vert =R\rbrace $ muni de la 
mesure de Lebesgue normalis\'ee par $\mu (S_{R})=1$.  
Soit $p$ un polyn\^ome de $P_{d}(1)$ et posons 
$E_{R}(\theta )=\lbrace v\in S_{R}\bigMidvert e(v)\leq 
\theta \rbrace $; on \'etablira au {\S }5 la:

\Theorem {Proposition 4.1} L'ensemble $E_{R}(\theta )$ 
est inclus dans la r\'eunion de  $2(d-1)$ arcs de  
$S_{R}$ chacun de mesure:  ${1\over \pi d}\left 
\lbrack \theta +2\arcsin{1\over R-1}\right \rbrack 
$.\endTheorem 

On notera $\mu _{\theta ,R}$ la somme de leur mesure.

\Theorem {Algorithme $ {\Cal A}(\theta ,R)$ 4.2 \Rm 
{(\Cite{Sm4})}}   {\rm 
Soit $p$ un polyn\^ome de $P_{d}(1)$ et $\varepsilon 
>0$.  Les constantes $M$,\enskip \enskip  $K=1-M$, et 
$N$ (d\'ependant de $d$, $\theta $, $R$, et 
$\varepsilon $) \'etant celles de 3.2, proc\'eder 
comme suit:}
\Item {1^{\circ }}   Choisir au hasard un  $v_{0}$ sur 
 $S_{R}$.
\Item {2^{\circ }}   Calculer  $v_{N}$ en it\'erant  
$N$ fois (3.1).
\Item {3^{\circ }}    Si   $ \left \vert 
p(v_{N})\right \vert \leq \varepsilon $ fin; sinon 
retourner au  \Admin {1^{\circ }}.

\par \noindent {\rm La moyenne du nombre de cycles 
dans cet algorithme est major\'ee par} $t = t_{\theta 
,R} = 1/(1-\mu _{\theta ,R})$.  \qed \endTheorem 


\Subheading {Quelques valeurs num\'eriques}  
\vskip-12pt
$$\matrix{ 
   &   &   &    M&     t&   tK_{1}&   tK_{2}&   tK_{3}   \Endphase \cr 
  R = 3,&  \theta  = \pi /12&   : &   1/94&     6&   615&   
231&   560    \Endphase \cr 
R = 6,&  \theta  = \pi /6&   : &   1/49&   2,44&   212&   24&   
119     \Endphase \cr 
}$$

   Lorsque, pour $R$ donn\'e, on cherche \`a minorer 
$tK_{1}$, l'optimum semble \^etre autour de $R=8$ et 
$\theta =7\pi /36$ et est assez stable (Pour $6\leq 
R\leq 16$,\enskip  $tK_{1}$ varie entre 206 et 223.)  
Assez paradoxalement, il est plus \'economique de 
partir d'une grande valeur initiale (cf. {\S }5).

   Si vous ne faites pas confiance au hasard, soit 
$k=2(d-1)\,\ell \,\,t_{\theta ,R}$ un entier avec 
$\ell >1$.  Placez alors $k$ points \'egalement 
r\'epartis sur $S_{R}$.  Comme $E_{k}(\theta )$ est 
dans une r\'eunion de $2(d-1)$ arcs, il ne peut 
contenir plus de $T_{k}=2(d-1)+k\mu _{\theta ,R}$ de 
ces points.  Tirant au sort les valeurs initiales dans 
cette urne de $k$ points, on est s\^ur que 
l'algorithme 4.2 n'a pas plus de $T_{k}$ cycles; la 
moyenne du nombre de tirages est major\'ee par 
$t_{k}=t_{\theta ,k}\,\ell /(\ell -1)$.  Le choix de 
$\ell $ est affaire de go\^ut: un grand $\ell $ 
am\'eliore la moyenne, mais recule la barri\`ere de 
s\'ecurit\'e $T_{k}$.


\Theorem {Th\'eor\`eme 4.3}    Soit  $0<\mu <1$.  Il y 
a une fonction  $N(\mu ,d)$ telle que, si  
$R=1+4d^{\,2}/\pi \mu $ et  $(v_{0},p)$ est hors d'un 
ensemble exceptionnel de mesure  $\mu $ dans  
$S_{R}\times P_{d}(1)$, il suffit, partant de  $v_{0}$ 
et fixant  $\theta ={\textstyle {1\over 2}}\pi \mu $ 
de  $N(\mu ,d)$ it\'erations de la formule  \Admin 
{3.1({\Sharp})} pour obtenir un bon z\'ero approch\'e 
de  $p$. On a :
$$    
     N(\mu ,d) = K_{1}(\mu )(d+{\textstyle {\textstyle 
{1\over 2}}}) {\log(1/\mu )+ K_{2}( d) \over  \mu  } + 
K_{3}(d) 
$$
o\`u  $K_{1}$ est croissante, 
$$
   15,2\leq K_{1}(\mu )\leq 25\enskip \enskip , 
\enskip \enskip \enskip \enskip \enskip 
K_{1}(1/4)<15,5<K_{1}(1/2)<18\enskip \enskip ,
$$$$
   (d+{\textstyle {1\over 
2}})K_{2}=3\log{d}+\log(36/\pi )\enskip ,\enskip 
\enskip \Rm { {\it et\/}}
            \enskip \enskip K_{3}(d)=2/3+K_{1}\pi 
/4d^{2}\enskip \enskip .
$$\endTheorem   

\Proof {D\'emonstration de 4.3}   La mesure des 
$(v_{0},p)$ tels que, soit $\rho _{p}<\rho $, soit 
$e_{p}(v_{0})<\theta $, est major\'ee par 
$$
  \mu  = (d-1)\rho ^{2}+{2(d-1)\over \pi d} \left 
\lbrack \theta +2\arcsin{1\over R-1}\right \rbrack 
\enskip \enskip .
$$
{\smc }Il suffit de poser $\rho =\sqrt \mu /d$  et 
d'appliquer 3.2 avec $\varepsilon =\rho /9$, et, pour 
$\theta $ et $R$, les valeurs donn\'ees dans 4.3.  
\endProof 



\Subheading {5.  La g\'eom\'etrie des polyn\^omes \Rm 
{(cf. \Cite{ShSm1})}}   
%
   Une id\'ee naturelle pour trouver un z\'ero d'un 
polyn\^ome $p$ est de minimiser la fonction r\'eelle 
$g(v)={\textstyle {1\over 2}} \left \vert p(v)\right 
\vert ^{2}$ en descendant le long des lignes de 
gradient.  Or, $X(v)=\Rm {grad}g(v)=\overline 
{p'(v)}p(v)$ est colin\'eaire au champ de Newton 
$n(v)=p(v)/p'(v)$ ($X(v)= \left \vert p'(v)\right 
\vert ^{2}n(v)$) et donc $X$ a m\^emes courbes 
int\'egrales que l'\'equation diff\'erentielle de 
Newton $v'=-n(v)$.  La m\'ethode d'Euler, avec le pas 
1 pour r\'esoudre cette \'equation diff\'erentielle, 
produit la m\^eme it\'eration que la m\'ethode de 
Newton.  Remarquons aussi que, comme 
$p'(v)n(v)=p(v)=z$, le polyn\^ome $p$ envoie son champ 
de Newton sur le champ radial du but. Donc les lignes 
de gradient que nous cherchons \`a descendre sont 
aussi les feuilles du feuilletage ${\Cal F}_{p}$, 
pr\'eimage par $p$ des rayons de ${\Bbd C}$ \`a savoir 
les courbes que Smale suivait dans sa d\'emonstration 
du th\'eor\`eme fondamental de l'alg\`ebre.  Dans 
\Cite{Sm2} (et aussi \Cite{ShSm1}), Smale avait suivi 
ces lignes de gradient de plus pr\`es en relaxant le 
pas de la m\'ethode d'Euler, i.e. en it\'erant 
$v\mapsto v-hp(v)/p'(v)$ o\`u $0<h<1$.

   De mani\`ere imag\'ee, si le graphe de $g$ est une 
montagne que l'on cherche \`a descendre, au lieu \`a 
chaque pas de viser le refuge attendu, Smale 
\Cite{Sm2} vise une \'etape interm\'ediaire, disons 
\`a mi-distance.  La m\'ethode du {\S }3 (\Cite{Sm4}) 
est plus s\^ure: avant de partir, on d\'etermine 
toutes ses \'etapes, ce qui permet d'\'eviter de 
mauvais embranchements aux cols.  Pour expliquer le 
paradoxe du {\S }4, on peut dire que, de plus haut, la 
vue permet de distinguer la vall\'ee principale des 
vall\'ees secondaires et donc on peut faire un 
meilleur plan de route.

   Le feuilletage ${\Cal F}_{p}$, orient\'e par $X$, a 
des singularit\'es de deux types (cf. Figure~6): des 
sources aux racines de $p$ et des selles de singe \`a 
$m-1$ pattes aux points critiques de multiplicit\'e 
$m$ et de valeur critique non nulle 
($0=p'(c)=\dots{}=p^{(m-1)}(c)$ et 
$p(c)p^{(m)}(c)\mathbin{\not =}0$).   Soit $\Gamma 
(p)$ la r\'eunion des vari\'et\'es instables des 
points critiques de ${\Cal F}_{p}$; c'est un arbre 
plong\'e dans ${\Bbd C}$, \Bi{l' arbre de Shub-Smale 
du polyn\^ome  }  $p$.   Posons $\Gamma (p)^{+}$ 
l'union de $\Gamma (p)$ et des vari\'et\'es stables 
des singularit\'es de type selle (\'eventuellement 
multiples) de ${\Cal F}_{p}$.  Les composantes  de  
$\Gamma (p)^{+}/\Gamma (p)$ {\it sont en nombre 
inf\'erieur ou \'egal \`a\/} $2(d-1)$ (ce maximum est 
atteint quand les racines de $p$ sont simples, les 
points critiques sont de multiplicit\'e 2 et n'ont pas 
de liaisons entre eux dans ${\Cal F}_{p}$).



\vDiagram{ {66}Figure 6} 




\Remark {Remarque 5.1}  Les arbres plong\'es dans 
${\Bbd C}$ qui peuvent se r\'ealiser comme arbres de 
Shub-Smale d'un polyn\^ome peuvent \^etre facilement 
d\'etermin\'es et, \`a l'aide des arbres de 
Shub-Smale, on peut {\it param\'etrer les polyn\^omes 
par leurs valeurs critiques\/} (cf. \Cite{M} et 
\Cite{STW}).\endRemark 

\Theorem {Lemme 5.2 \Rm {(Gauss)}}    Soit  $p$ un 
polyn\^ome dont toutes les racines sont \`a 
l'int\'erieur d'un cercle  $S$, alors le champ de 
Newton est transverse \`a  $S$.\endTheorem 

\Theorem {Corollaire 5.3}    Soit  $S$ un cercle 
contenant dans son int\'erieur tous les z\'eros d'un 
polyn\^ome  $p$, alors:
\Item {(i)}   l'arbre  $\Gamma (p)$ est dans 
l'int\'erieur de  $S$;
\Item {(ii)}   $\Gamma (p)^{+}\cap S$ contient au plus 
 $2(d-1)$ points.  \endProof \endTheorem   

\Theorem {Lemme 5.4}  Soit  $p$ un polyn\^ome de  
$P_{d}(1)$, $R\geq 2$, $S_{R}$ le cercle  $ \left 
\vert v\right \vert =R$ et  $v_{1}$, $v_{2}$ deux 
points de $S_{R}$.  Alors :
\medskip
\Item {(i)}   $p(v_{i})$ est non nul;
\medskip
\Item {(ii)}  $\displaystyle d \left \vert \Rm 
{Arg}{v_{1}\over v_{2}}\right \vert  - 2\Rm 
{arcsin}{1\over R-1}\leq   \left \vert \Rm 
{Arg}{p(v_{1})\over p(v_{2})}\right \vert  \leq $
   $$\leq  d \left \vert \Rm {Arg}{v_{1}\over 
v_{2}}\right \vert  + 2\Rm {arcsin}{1\over R-1}\enskip 
\enskip .$$
\endTheorem 
\Proof {D\'emonstration de 4.1}    Soit $R\geq 2$ et 
$p$ dans $P_{d}(1)$; remarquons qu'un point $v_{0}$ de 
$S_{R}$ est dans $E_{R}(\theta )$ si et seulement s'il 
y a un $v'$ dans $S_{R}\cap \Gamma (p)^{+}$ avec $~ 
\left \vert \Rm {Arg}(p(v)/p(v')\right \vert <\theta 
$.  D'apr\`es 5.4(i) et 5.2, ${\Cal F}_{p}$ est 
transverse \`a $S_{R}$ et l'un des arcs limit\'es par 
$v$ et $v'$ sur $S_{R}$ a tous ses points $u$ 
v\'erifiant $ \left \vert \Rm {Arg}(p(u)/p(v')\right 
\vert <\theta $.  La proposition~4.1 suit alors de 
l'in\'egalit\'e de gauche dans 5.4~(ii).  \endProof 







\Diagram {{75}\hfill    Figure 7 \hfill \hfill    Figure 8 
\hfill  } 
\Proof {D\'emonstration de 5.2 (voir Figure 7)}   
Soient  $w_{i}$ les racines de $p$ et soit $v$ sur 
$S$. On a:
$$
    \left \vert n(v)\right \vert ^{^{-2}}v\overline n(v) 
= v\,{p'(v)\over p(v)} = \sum _{i=1}^{d }{v\over 
v-w_{i}}\enskip \enskip .
$$
Or, comme $w_{i}$ est int\'erieur \`a $S$, on a $\Rm 
{Re}(v(\overline {v-w_{i}}))>0$; donc $\Rm {Re}( 
v/(v-w_{i}))>0$ et $\Rm {Re}( v\,\,\overline n(v))>0$. 
 \endProof  

\Proof {D\'emonstration de 5.4 (voir Figure 8)} Soit 
$p(v)=v^{d}+a_{1}v^{d-1}+\dots{}+a_{d}$ pour $ \left 
\vert v_{j}\right \vert =R$.  On a:
$$
    \left \vert 1-{p(v_{j})\over v_{j}^{d}}\right 
\vert  \leq  \sum _{i=1}^{d  }{ \left \vert 
a_{i}\right \vert \over  \left \vert v_{j}\right \vert 
^{d}} < {1\over  \left \vert v_{j}\right \vert 
}\,\,{1\over 1-1/ \left \vert v_{j}\right \vert } 
        = {1\over R-1} \leq  1
$$
car $R\geq 2$, d'o\`u (i);  et pour (ii):
$$
     \left \vert \Rm {Arg}{p(v_{1})\over p(v_{2})} - 
\Rm {Arg}\left({v_{1}\over v_{2}}\right)^{d} \right 
\vert  
      = \Rm {Arg} \left \vert {p(v_{1})\over 
v_{1}^{d}}\,{v_{2}^{d}\over p(v_{2})}\right \vert  
\leq  
$$$$
\hfil       \leq   \left \vert \Rm {Arg}{p(v_{1})\over 
v_{1}^{d}}\right \vert  +  \left \vert \Rm 
{Arg}{p(v_{2})\over v_{2}^{d}}\right \vert  
      \leq 2\Rm {arcsin}{1\over R-1}\enskip \enskip 
\enskip .
$$                             \endProof 


\Subheading {6.  Un crit\`ere de convergence 
calculable en $\Headingfont v_{0}$}
%
   Soit $v$ un point r\'egulier d'un polyn\^ome $p$.  En 
2.5, on a d\'efini     $\alpha (v,p)=\beta (v,p)\gamma 
(v,p)$ o\`u $\beta (v,p)$ est la norme du vecteur de 
Newton $p(v)/p'(v)$, alors que le calcul de $\gamma 
(v)$ n\'ecessite la connaissance de toutes les 
d\'eriv\'ees de $p$ en $v$.  La proposition suivante 
permet de majorer $\gamma (v)$ (et donc $\alpha (v)$) 
en n'ayant \`a \'evaluer que $p$ et $p'$ en $v$:

\Theorem {Proposition 6.1 \Rm {(\Cite{Sm5}, 
\Cite{Sm6})}}    Soit  $\varphi (r)=1+\dots{}+r^{d}$ 
et  $p(v)=a_{0}+a_{1}v+\dots{}+a_{d}v^{d}$ un 
polyn\^ome de degr\'e  $d$, alors :
$$
\gamma (v,p) \leq  {\left \Vert p\right \Vert (\varphi 
'( \left \vert v\right \vert ))^{2}\over  \left \vert 
p'(v)\right \vert \varphi ( \left \vert v\right \vert 
)}\enskip \enskip ,\enskip \enskip \enskip \Rm {o\`u 
}\enskip \enskip \enskip \left \Vert p\right \Vert  = 
\Rm {Max} \left \vert a_{i}\right \vert \enskip 
\enskip .
$$\endTheorem 

\Theorem {Th\'eor\`eme 6.2 \Rm {(\Cite{Sm5})}}  Soit  
$p$ un polyn\^ome et  $v_{0}$ un point r\'egulier tel 
que  $\alpha (v_{0},p)<3-2\sqrt 2$, alors la suite de 
Newton  $v_{n+1}=v_{n}-p(v_{n})/p'(v_{n})$ converge 
vers une racine de  $p$.  De plus, il y a une 
bijection croissante  $K:\left \lbrack \right 
.0,3-2\sqrt 2\left \lbrack \right . \llongrightarrow   
      [0,1[$ telle que: \enskip Si  $\alpha 
(v_{0},p)<\alpha $, alors  $\left \Vert 
v_{n+1}-v_{n}\right \Vert \leq K(\alpha 
)^{2^{n}-1}\left \Vert v_{1}-v_{0}\right \Vert $ et  
$\alpha _{0}=K^{-1}({\textstyle {1\over 
2}})>0,14$.\endTheorem 

   Pour $p$ dans $P_{d}(1)$, le nombre $\alpha (0,p)$ 
est major\'e par $ \left \vert a_{0}\right \vert / 
\left \vert a_{1}\right \vert ^{2}$ qui est 
ind\'ependant de $d$. Ainsi, {\it l'ensemble des 
polyn\^omes de  $P_{d}(1)$, dont la suite de Newton 
partant de z\'ero converge, a une mesure minor\'ee 
ind\'ependamment de\/} $d$.


\Proof {D\'emonstration de 6.1}  En majorant les 
coefficients de $p$ par $\left \Vert p\right \Vert $, 
on obtient $ \left \vert p^{(k)}(v)/k!\right \vert 
\leq \left \Vert p\right \Vert \varphi ^{(k)}( \left 
\vert v\right \vert )/k!$, d'o\`u en faisant $k=1$ on 
obtient $\left \Vert p\right \Vert \varphi '( \left 
\vert v\right \vert )/ \left \vert p'(v)\right \vert 
\geq 1$.  Un jeu sur les coefficients du bin\^ome 
(\Cite{Sm6}, p.12-14) permet d'\'etablir que $\alpha 
(r,\varphi )\leq 1$ pour tout $r\geq 0$, d'o\`u
$$
 \left \vert p^{(k)}(v)/k!\right \vert  \leq  \left 
\Vert p\right \Vert \varphi ^{(k)}( \left \vert 
v\right \vert )/k! \leq   \left \Vert p\right \Vert 
(\varphi '( \left \vert v\right \vert ))^{k}/(\varphi 
( \left \vert v\right \vert ))^{k-1}\enskip \enskip 
,\enskip \Rm {et}
$$$$
    \gamma (v,p) \leq   \sup _{k>1}\left \lbrack  
\left \Vert p\right \Vert (\varphi '( \left \vert 
v\right \vert ))^{k}\over  \left \vert p'(v)\right 
\vert (\varphi ( \left \vert v\right \vert ))^{k-1} 
\right \rbrack ^{1/k-1}\leq  \,{\varphi '\over \varphi 
} \,\,\sup _{k>1}\left \lbrack \left \Vert p\right 
\Vert \varphi '\over  \left \vert p'\right \vert 
\right \rbrack ^{1/k-1}\enskip \enskip .
$$
\par \noindent Le dernier supr\'emum est atteint pour 
$k=2$, d'o\`u la proposition.  \endProof 

\Proof {D\'emonstration de 6.2}   Pour $0\leq t<\gamma 
^{-1}$, soit $\psi $ la fonction $\psi (t)={1\over 
1-\gamma t}-2\gamma t+\alpha -1$; comme en 2.6, on 
\'etablit que, pour $\left \Vert v-v_{0}\right \Vert 
\leq t\gamma ^{-1} $ on a:
   $$ \left \vert p(v_{0})\over p'(v_{0})\right \vert  
\leq  {\psi (0)\over -\psi '(0)}\enskip \enskip 
\enskip ,\enskip \enskip \enskip \Rm {et}\enskip 
\enskip \enskip  
      \left \vert p''(v)\over p'(v_{0})\right \vert  
\leq  {\psi ''(t)\over -\psi '(0)}\enskip \enskip 
\enskip .$$


   Kantorovitch (\Cite{KA}, th\'eor\`eme 3, p.234) nous 
dit que, si  $\psi (t)=0$  a une racine dans $\left 
[0,\gamma ^{-1}\right [\,$, alors la suite $v_{n}$ 
converge vers une racine $w$ de $p$, que la suite de 
Newton $t_{n}$ de $\psi $ partant de $t_{0}=0$ 
converge vers la plus petite racine $t_{*}$ de $\psi 
(t)=0$ et $ \left \vert v_{n+1}-v_{n}\right \vert \leq 
t_{n+1}-t_{n}$.

   Il ne reste plus qu'\`a estimer $t_{n+1}-t_{n}$ pour 
obtenir les majorations du th\'eor\`eme 6.2.  
\endProof 

\Remark {Remarques} 
% 
\par \noindent Comme Kantorovitch \'enonce son 
th\'eor\`eme dans un Banach, le th\'eor\`eme~6.2 est 
valable pour une fonction analytique d\'efinie sur un 
Banach (il en est bien s\^ur de m\^eme pour 6.1).

\par \noindent Smale d\'emontre 6.2 plus directement 
en majorant \`a chaque it\'eration de Newton les 
quantit\'es $\beta $ et $\gamma $.  N'utilisant pas le 
th\'eor\`eme de Kantorovitch, cette approche se 
g\'en\'eralise aux m\'ethodes d'ordre sup\'erieur 
(\Cite{C}).\endRemark 



\Subheading {7.  Un algorithme g\'en\'eriquement 
convergent \Rm {(\Cite{ShSm3})}}
%
   Soit $G_{d}$ l'ouvert de $P_{d}$ form\'e des 
polyn\^omes $p(v)=a_{0}+a_{1}v+\dots{} +a_{d}v^{d}$ 
ayant leurs racines et leurs points critiques 
distincts: $P_{d}\setminus G_{d}$ \'etant 
alg\'ebrique, $G_{d}$ est un ouvert dense de mesure 
pleine.  Soient $p$ dans $G_{d}$ et $v$ dans la 
sph\`ere de Gauss $S={\Bbd C}\cup \infty $.  
D\'efinissons alors:
$$ 
k_{p}(v)={\varphi ( \left \vert v\right \vert ) \left 
\vert p'(v)\right \vert ^{2}\over 2(\varphi '( \left 
\vert v\right \vert ))^{2} \left \vert p(v)\right 
\vert \left \Vert p\right \Vert }\enskip \enskip ,  
h_{p}(v)=\Rm {Min}(1,k_{p}(v))\enskip \enskip ,  $$
et $T_{p}(v)=v-h_{p}(v)p(v)/p'(v)$  \enskip (o\`u 
$\varphi $ et $\left \Vert p\right \Vert $ sont 
d\'efinis au {\S }6).

   Les points fixes de $T_{p}$ sont les racines et les 
points critiques de $p$.  L'application $\widetilde  T 
: S\times G_{d}\rightarrow S$ ainsi d\'efinie est 
continue et $C^{\infty }$ pr\`es des points critiques 
de $p$.  Quand $p$ est fix\'e par le contexte, nous 
\'ecrirons $T$ au lieu de $T_{p}$.

\Remark {Remarque}  Les formules ci-dessus 
d\'efinissent une application continue $S\times 
P_{d}\rightarrow S$, mais si $p$ a des racines 
multiples, cette application n'est pas lisse pr\`es 
des racines multiples.  Remarquons d'autre part que 
l'application de Newton  $\widetilde  N : S\times 
P_{d}\rightarrow S$ n'est pas continue (en $P_{d}$) 
aux racines multiples, car quand le polyn\^ome varie, 
un point critique se rapprochant d'une racine voit son 
image passer brusquement de l'infini \`a cette 
racine.\endRemark 

{\bf }\Theorem {Th\'eor\`eme 7.1}  Pour tout  $p$ de  
$G_{d}$, il y a un ferm\'e  $V_{p}$ de mesure nulle 
dans  $S$ tel que, pour tout  $v$ hors de  $V_{p}$ la 
suite des it\'er\'es  $T^{k}(v)$, $k\geq 0$, converge 
vers un z\'ero de  $p$.

   De plus,  $T$ est la m\'ethode de Newton dans un 
voisinage de chaque racine de  $p$.\endTheorem 

\Theorem {Proposition 7.2}  Soit  $p$ dans  $G_{d}$ et 
 $c$ un point critique de  $p$, alors  
      $$V^{s}(c)=\lbrace v\bigMidvert T^{k}(v)\rightarrow 
c\enskip \enskip \Rm {quand}\enskip \enskip 
k\rightarrow \infty \rbrace $$
est un ferm\'e de mesure nulle dans  $S$.\endTheorem 

\Proof {D\'emonstration de 7.2}  Comme le jacobien de 
$T$ est presque partout non nul, il suffit de montrer 
qu'un voisinage de $c$ dans $V^{s}(c)$ est de mesure 
nulle.  Comme $T$ est lisse au voisinage de $c$, il 
suffit, selon le th\'eor\`eme de la vari\'et\'e stable 
(\Cite{HPS}), de prouver que $T'(c)$ est hyperbolique 
(en effet ce th\'eor\`eme impliquera alors que 
$V^{s}(c)$ est, pr\`es de $c$, un arc lisse).  On a 
$$T'(c)(V) = V-\lambda \overline V\enskip \enskip 
\enskip ,\enskip \enskip \enskip \Rm {o\`u}\enskip 
\enskip \enskip 
      \lambda  = {p(c)\,\overline p''(c)\,\varphi ( \left 
\vert c\right \vert )\over 2\left(\varphi '( \left 
\vert c\right \vert )\right)^{2}\left \Vert p\right 
\Vert  \left \vert p(c)\right \vert }\enskip \enskip 
\enskip .$$
Les valeurs propres de $T'(c)$ sont donc $1\pm  \left 
\vert \lambda \right \vert $; or, comme on a 
\break$\varphi (r)\varphi ''(r)\leq 2(\varphi 
'(r))^{2}$,
      $$ \left \vert \lambda \right \vert  \leq  { \left 
\vert p''(c)\right \vert \over \left \Vert p\right 
\Vert }\,\,{1\over \varphi ''( \left \vert c\right 
\vert )} \leq  1\enskip \enskip .$$
\endProof 

\Proof {D\'emonstration de 7.1}  Posons $V_{p}=\bigcup 
\left \lbrace V^{s}(c)\bigMidvert p'(c)=0\right 
\rbrace $. Soit $v$ hors de $V_{p}$ et 
$v_{n}=T^{n}(v)$, alors $p'(v)\mathbin{\not =}0$ et 
comme, d'apr\`es 6.1, $k(v)<{\textstyle {1\over 
2}}\alpha (v)$, on obtient par une majoration analogue 
\`a celle de 2.6~:
   $$    \left \vert p(v_{n+1})\right \vert  \leq  
h(v_{n}) \left \vert p(v_{n})\right \vert  <  \left 
\vert p(v_{n})\right \vert \enskip \enskip \enskip ,      
$$
o\`u l'application continue $h : {\Bbd C}\rightarrow 
[0,1]$ n'est nulle qu'aux points critiques de $p$.

   Comme $v$ n'est dans aucun des $V^{s}(c)$, cela 
implique que la suite d\'ecroissante $ \left \vert 
p(v_{n})\right \vert $ tend vers z\'ero et $v_{n}$ 
tend vers une racine de $p$ (deux racines de $p$ ne 
peuvent \^etre adh\'erentes \`a $v_{n}$ puisque, comme 
$T$ co\"\i ncide avec l'application de Newton pr\`es 
des racines de $p$, ces derni\`eres sont des points 
fixes attractifs de $T$).\endProof 


\References {
Bibliographie
}
%
\Benchmark 
\Cite{Ba}   {\smc B. Barna}, {\it Uber Divergenzpunkte 
des Newtonshe Verfahrens zur Bestimmung von 
W{\"u}rzeln algebraischer Gleichungen III\/}{\smc ,}  
Publ. Math. Debrecen {\bf 8} (1961), 193-207.
\Benchmark 
\Cite{C}   {\smc J. Curry}, {\it On zero finding methods 
of higher order from data at one point\/}, MSRI 
Berkeley (1986).
\Benchmark 
\Cite{DH}   {\smc A. Douady and J.H. Hubbard}, {\it On 
the dynamics of polynomial like mappings\/},  Ann. 
Sci. E.N.S., 4e s\'erie, {\bf t.18} (1985), 287-343.
\Benchmark 
\Cite{F}   {\smc J.-P. Francoise}, {\it Estimations 
uniformes pour les domaines de convergence de la 
m\'ethode de Newton\/},  S\'eminaire de G\'eom\'etrie 
Alg\'ebrique R\'eelle (J.J. Risler), Publ. Univ. Paris 
VII, {\bf 24} (1986).
\Benchmark 
\Cite{G}   {\smc O. Gabber}, {\it Diverses interventions 
au S\'eminaire Bourbaki\/},  tradition orale.
\Benchmark 
\Cite{H}   {\smc W. Hayman},  ``Multivalent functions'', 
Cambridge Univ. Press, Cambridge, 1958.
\Benchmark 
\Cite{HPS}   {\smc M. Hirsch, C. Pugh and M. Shub}, {\it 
Invariant manifolds\/},  Lectures Notes in Math. {\bf 
583} (1977), Springer, New-York.
\Benchmark 
\Cite{HM}   {\smc M. Hurley and C. Martin}, {\it 
Newton's algorithm and chaotic dynamical systems\/},  
SIAM J. Math. Anal. {\bf 15} (1984), 238-252.
\Benchmark 
\Cite{Ka}   {\smc L. Kantorovich et G. Akilov},  Analyse 
fonctionnelle, {\bf t.2}, Editions MIR, Moscou, 1981.
\Benchmark 
\Cite{McM}   {\smc C. McMullen},  ``Families of 
Rationals Maps and Iterative Root-Finding 
Algorithms'', Ph. D., Harvard Univ., Mai 1985, \`a 
para\^\i tre.
\Benchmark 
\Cite{M}   {\smc A. Marin}, {\it Les arbres de 
Shub-Smale\/},  S\'eminaire de G\'eom\'etrie 
alg\'ebrique r\'eelle (J.J. Risler), Publ. Univ. Paris 
VII {\bf 24} (1986).
\Benchmark 
\Cite{O}   {\smc J. Oesterl\'e}, {\it D\'emonstration de 
la conjecture de Bieberbach\/},  expos\'e \Admin 
{n^{o}649} du S\'eminaire Bourbaki (juin 1985).
\Benchmark 
\Cite{R1}   {\smc J. Renegar}, {\it On the efficiency of 
Newton's method in approximating all zeros of a system 
of complex polynomials\/},  \`a para\^\i tre dans 
Mathematics of Operations Research.
\Benchmark 
\Cite{R2}   {\smc J. Renegar}, {\it A polynomial-time 
algorithm based on Newton's method for linear 
programming\/},  MSRI Berkeley (1986).
\Benchmark 
\Cite{SU}   {\smc D. Saari and J. Urenko}, {\it Newton's 
method, circle maps and chaotic motions\/},  Amer. 
Math. Monthly {\bf 91} (1984), 3-17.
\Benchmark 
\Cite{Sh}   {\smc M. Shub}, {\it The geometry and 
topology of dynamical systems, and algorithms for 
numerical problems\/},  notes pr\'epar\'ees pour des 
conf\'erences donn\'ees \`a D.D.A, Universit\'e de 
Peking, Bejing, Chine, Ao\^ut-Septembre 1983.
\Benchmark 
\Cite{{\bf ShSm1\&2}} {\smc M. Shub and S. Smale}, 
{\it Computational complexity on the geometry of 
polynomials and a theory of cost\/},  PartI, Ann. Sci. 
E.N.S. ({\bf 4}) {\bf t.18} (1985), 107-161; Part II, 
SIAM J. Computing {\bf 15} (1986), 145-161.
\Benchmark 
\Cite{ShSm3} {\smc M. Shub and S. Smale}, {\it On the 
existence of generally convergent algorithms\/},  
Jour. of Complexity {\bf 2} (1986), 2-11.
\Benchmark 
\Cite{STW}   {\smc M. Shub, D. Tischler and R. 
Williams}, {\it The Newtonian graph of a complex 
polynomial\/},  soumis \`a SIAM J. of  Math. Analysis.
\Benchmark 
\Cite{Sm1}   {\smc S. Smale}, {\it A Convergent process 
of price adjustment and global Newton methods\/},  J. 
Math. Econom. {\bf 3} (1976), 107-120.
\Benchmark 
\Cite{Sm2}   {\smc S. Smale}, {\it The fundamental 
theorem of algebra and complexity theory\/},  Bull. 
Amer. Math. Soc. {\bf 4} (1981), 107-120.
\Benchmark 
\Cite{Sm3}   {\smc S. Smale}, {\it The Problem of the 
average speed of the simplex method\/},  in 
``Mathematical Programming: the state of the Art, Bonn 
1982'' (editors Bachem et al.), Springer, 1983.
\Benchmark 
\Cite{Sm4}   {\smc S. Smale}, {\it On the efficiency of 
algorithms of analysis\/},  Bull. Amer. Math. Soc. 
{\bf 13} (1985), 87-121.
\Benchmark 
\Cite{Sm5}   {\smc S. Smale}, {\it Newton's method 
estimates from data at one point\/}, \`a para\^\i tre 
dans: Proceedings of a Conference at Laramie in Honor 
of Gail S. Young, Springer New York (1986).
\Benchmark 
\Cite{Sm6}   {\smc S. Smale}, {\it Algorithms for 
solving equations\/},  MSRI Berkeley, 1986  (texte 
\'ecrit pour le congr\`es mondial de Berkeley).
\endReferences 
\bigskip
\goodbreak


   Vous trouverez de nombreuses autres r\'ef\'erences 
dans les bibliographies de \Cite{Sm2}, \Cite{Sm4}, 
\Cite{Sm6}; en plus, \Cite{Sm6} contient une 
discussion de l'\'etat actuel des probl\`emes pos\'es 
dans \Cite{Sm2} et \Cite{Sm4}.



\medskip
\vfill
\leftskip = .55 \hsize 
\parindent=0pt \parskip=0pt
\def \Par{\nobreak\par}
            Alexis MARIN  
 \nobreak\vskip 1.5pt \nobreak\Par
            UA 1169 du CNRS\Par  
            Universit\'e Paris-Sud\Par  
            Math\'ematiques, b\^at 425\Par  
            91405 ORSAY\Par  
          
\vfill
\vfill
\eject
\end
