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
|