A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton's method

Authors:
Béla Bollobás, Malte Lackmann and Dierk Schleicher

Journal:
Math. Comp. **82** (2013), 443-457

MSC (2010):
Primary 37F10, 49M15

DOI:
https://doi.org/10.1090/S0025-5718-2012-02640-8

Published electronically:
August 20, 2012

MathSciNet review:
2983031

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We specify a small set, consisting of points, that intersects the basins under Newton's method of *all* roots of *all* (suitably normalized) complex polynomials of fixed degrees , with arbitrarily high probability. This set is an efficient and universal *probabilistic* set of starting points to find all roots of polynomials of degree using Newton's method; the best known *deterministic* set of starting points consists of points.

**[A]**Lars V. Ahlfors,*Lectures on quasiconformal mappings*, 2nd ed., University Lecture Series, vol. 38, American Mathematical Society, Providence, RI, 2006. With supplemental chapters by C. J. Earle, I. Kra, M. Shishikura and J. H. Hubbard. MR**2241787****[ABS]**Magnus Aspenberg, Todor Bilarev, Dierk Schleicher:*On the speed of convergence of Newton's method for complex polynomials*. Manuscript, submitted.**[BC]**Xavier Buff and Arnaud Chéritat,*Ensembles de Julia quadratiques de mesure de Lebesgue strictement positive*, C. R. Math. Acad. Sci. Paris**341**(2005), no. 11, 669–674 (French, with English and French summaries). MR**2183346**, https://doi.org/10.1016/j.crma.2005.10.001**[DH]**Adrien Douady and John Hamal Hubbard,*On the dynamics of polynomial-like mappings*, Ann. Sci. École Norm. Sup. (4)**18**(1985), no. 2, 287–343. MR**816367****[HLP]**G. H. Hardy, J. E. Littlewood, and G. Pólya,*Inequalities*, Cambridge, at the University Press, 1952. 2d ed. MR**0046395****[HSS]**John Hubbard, Dierk Schleicher, and Scott Sutherland,*How to find all roots of complex polynomials by Newton’s method*, Invent. Math.**146**(2001), no. 1, 1–33. MR**1859017**, https://doi.org/10.1007/s002220100149**[Mi]**Yauhen Mikulich,*Newton's Method as a Dynamical System*. Thesis, Jacobs University Bremen, 2011.**[M]**John Milnor,*Dynamics in one complex variable*, 3rd ed., Annals of Mathematics Studies, vol. 160, Princeton University Press, Princeton, NJ, 2006. MR**2193309****[Pr]**Feliks Przytycki,*Remarks on the simple connectedness of basins of sinks for iterations of rational maps*, Dynamical systems and ergodic theory (Warsaw, 1986) Banach Center Publ., vol. 23, PWN, Warsaw, 1989, pp. 229–235. MR**1102717****[Rü]**Johannes Rückert,*Rational and transcendental Newton maps*, Holomorphic dynamics and renormalization, Fields Inst. Commun., vol. 53, Amer. Math. Soc., Providence, RI, 2008, pp. 197–211. MR**2477424****[Sch1]**Dierk Schleicher,*Newton’s method as a dynamical system: efficient root finding of polynomials and the Riemann 𝜁 function*, Holomorphic dynamics and renormalization, Fields Inst. Commun., vol. 53, Amer. Math. Soc., Providence, RI, 2008, pp. 213–224. MR**2477425****[Sch2]**Dierk Schleicher,*On the efficient global dynamics of Newton's method for complex polynomials*. Manuscript, submitted.**[S1]**Steve Smale,*On the efficiency of algorithms of analysis*, Bull. Amer. Math. Soc. (N.S.)**13**(1985), no. 2, 87–121. MR**799791**, https://doi.org/10.1090/S0273-0979-1985-15391-1**[S2]**Stephen Smale,*Newton's method estimates from data at one point*, in: The Merging Disciplines: New Directions in Pure, Applied and Computational Mathematics, Springer-Verlag, Berlin, New York (1986), 185-196.

Retrieve articles in *Mathematics of Computation*
with MSC (2010):
37F10,
49M15

Retrieve articles in all journals with MSC (2010): 37F10, 49M15

Additional Information

**Béla Bollobás**

Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WB, UK; and Department of Mathematical Sciences, University of Memphis, Memphis Tennessee 38152

Email:
B.Bollobas@dpmms.cam.ac.uk

**Malte Lackmann**

Affiliation:
Immenkorv 13, D-24582 Bordesholm, Germany

Email:
malte.lackmann@web.de

**Dierk Schleicher**

Affiliation:
Research I, Jacobs University Bremen, Postfach 750 561, D-28725 Bremen, Germany

Email:
dierk@jacobs-university.de

DOI:
https://doi.org/10.1090/S0025-5718-2012-02640-8

Received by editor(s):
September 10, 2010

Received by editor(s) in revised form:
August 28, 2011

Published electronically:
August 20, 2012

Article copyright:
© Copyright 2012
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.