On the geometry of polynomials and a theory of cost. I. (English) Zbl 0603.65027

Shub, Mike; Smale, Steve

Ann. Sci. Éc. Norm. Supér. (4) 18, 107-142 (1985).

The general field of the research reported here is the study of algorithms for polynomial root finding, and in particular an algorithm which the authors describe as an ”incremental” version of that of Euler for determining an approximate zero of a complex polynomial. The authors’ principal result is to show that the number of iterations of the algorithm is linearly related to the degree of the polynomial. Indeed their main theorem, which requires a somewhat lengthy proof, gives a good estimate of the number of iterations required.

Reviewer: J.Oliver

MSC:

65H05	Numerical computation of solutions to single equations
30C15	Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)

Keywords:

Euler method; polynomial root finding; complex polynomial; number of iterations

References:

[1]	K. ATKINSON , An Introduction to Numerical Analysis , Wiley, New York, 1978 . MR 80a:65001 | Zbl 0402.65001 · Zbl 0402.65001
[2]	E. DURAND , Solutions Numériques de Équations Algébriques , Masson, Paris, 1960 . · Zbl 0099.10801
[3]	P. DUREN , Coefficients of Univalent Functions (Bull. Amer. Math. Soc., Vol. 83, No. 5, 1977 , pp. 891-911). Article | MR 57 #9943 | Zbl 0372.30012 · Zbl 0372.30012 · doi:10.1090/S0002-9904-1977-14324-3
[4]	L. EULER , Institutiones Calculi Differentialis II , exp. IX. Opera Omnia, Serie I, Vol. X, pp. 422-455.
[5]	W. HAYMAN , Multivalent Functions , Cambridge Univ. Press : Cambridge, Eng., 1958 . Zbl 0082.06102 · Zbl 0082.06102
[6]	P. HENRICI , Applied and Computational Complex Analysis , Wiley, New York, 1977 . MR 56 #12235 · Zbl 0363.30001
[7]	E. HILLE , Analytic Function Theory , II Ginn, Boston, 1962 . MR 34 #1490 | Zbl 0102.29401 · Zbl 0102.29401
[8]	A. S. HOUSEHOLDER , The Numerical Treatment of a Single Nonlinear equation , McGraw-Hill, New York, 1970 . MR 52 #9593 | Zbl 0242.65047 · Zbl 0242.65047
[9]	S. LANG , Algebra , Addison-Wesley, Reading, Mass, 1965 . MR 33 #5416 | Zbl 0193.34701 · Zbl 0193.34701
[10]	A. OSTROWSKI , Solutions of equations in Euclidean and Banach Spaces , Academic Press, New York, 1973 . MR 50 #11760 | Zbl 0304.65002 · Zbl 0304.65002
[11]	G. SAUNDERS , Thesis , U. C. Berkeley, 1982 .
[12]	E. SCHRÖDER , Ueber unendlich viele Algorithmen zur Auflösing der Gleichungen (Math. Ann. 2, 1870 , pp. 317-365). Article | JFM 02.0042.02 · JFM 02.0042.02
[13]	S. SMALE , The Fundamental Theorem of Algebra and Complexity Theory (Bull, Amer. Math. Soc., Vol. 4, No. 1, 1981 , pp. 1-36. Article | MR 83i:65044 | Zbl 0456.12012 · Zbl 0456.12012 · doi:10.1090/S0273-0979-1981-14858-8