Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

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 $ O(d(\log \log d)^2)$ points, that intersects the basins under Newton's method of all roots of all (suitably normalized) complex polynomials of fixed degrees $ d$, with arbitrarily high probability. This set is an efficient and universal probabilistic set of starting points to find all roots of polynomials of degree $ d$ using Newton's method; the best known deterministic set of starting points consists of $ \lceil 1.1d(\log d)^2\rceil $ points.


References [Enhancements On Off] (What's this?)

  • [A] Lars Ahlfors, Lectures on quasiconformal mappings, Second edition. University Lecture Series 38. American Mathematical Society, Providence, RI, 2006. MR 2241787 (2009d:30001)
  • [ABS] Magnus Aspenberg, Todor Bilarev, Dierk Schleicher: On the speed of convergence of Newton's method for complex polynomials. Manuscript, submitted.
  • [BC] Xavier Buff, Arnaud Chéritat, Ensembles de Julia quadratiques de mesure de Lebesgue strictement positive. C. R. Acad. Sci. Paris 341 11 (2005), 669-674. MR 2183346 (2006k:37133)
  • [DH] Adrien Douady, John Hubbard, On the dynamics of polynomial-like maps. Ann. Sci. Ec. Norm. (4) 18 2 (1985), 277-343. MR 816367 (87f:58083)
  • [HLP] Godfrey H. Hardy, John E. Littlewood, George Pólya, Inequalities, Second edition. Cambridge University Press, Cambridge 1952. MR 0046395 (13:727e)
  • [HSS] John Hubbard, Dierk Schleicher, Scott Sutherland, How to find all roots of complex polynomials by Newton's method. Inventiones Mathematicae 146 (2001), 1-33. MR 1859017 (2002i:37059)
  • [Mi] Yauhen Mikulich, Newton's Method as a Dynamical System. Thesis, Jacobs University Bremen, 2011.
  • [M] John Milnor, Dynamics in one complex variable, third edition. Annals of Mathematics Studies 160, Princeton University Press, Princeton, NJ, 2006. MR 2193309 (2006g:37070)
  • [Pr] Feliks Przytycki, Remarks on the simple connectedness of basins of sinks for iterations of rational maps. In: Dynamical Systems and Ergodic Theory, ed. by K. Krzyzewski, Polish Scientific Publishers, Warszawa (1989), 229-235. MR 1102717 (92e:58180)
  • [Rü] Johannes Rückert, Rational and transcendental Newton maps. In: Holomorphic dynamics and renormalization, Fields Inst. Commun. 53, Amer. Math. Soc., Providence, RI, 2008, pp. 197-211. MR 2477424 (2010c:37096)
  • [Sch1] Dierk Schleicher, Newton's method as a dynamical system: efficient root finding of polynomials and the Riemann $ \zeta $ function. In: Holomorphic dynamics and renormalization, M. Lyubich and M. Yampolski (eds,) Fields Inst. Commun. 53, Amer. Math. Soc., Providence, RI, 2008, pp. 213-224. MR 2477425 (2010c:37097)
  • [Sch2] Dierk Schleicher, On the efficient global dynamics of Newton's method for complex polynomials. Manuscript, submitted.
  • [S1] Stephen Smale, On the efficiency of algorithms of analysis. Bulletin of the American Mathematical Society (New Series) 13 2 (1985), 87-121. MR 799791 (86m:65061)
  • [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.

Similar Articles

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.

American Mathematical Society