%%% 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}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 $12$, 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 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 000$ 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 $$ I0$. 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,50$; 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