summaryrefslogtreecommitdiff
path: root/macros/generic/occam/PlainEx1/newton.tex
blob: 5e5e0845237d5a48e3083ce5d6985ea6ed8e7d8d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281

%%% 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