A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton’s method
HTML articles powered by AMS MathViewer
- by Béla Bollobás, Malte Lackmann and Dierk Schleicher PDF
- Math. Comp. 82 (2013), 443-457 Request permission
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
- 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, DOI 10.1090/ulect/038
- Magnus Aspenberg, Todor Bilarev, Dierk Schleicher: On the speed of convergence of Newton’s method for complex polynomials. Manuscript, submitted.
- 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, DOI 10.1016/j.crma.2005.10.001
- 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
- G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, Cambridge, at the University Press, 1952. 2d ed. MR 0046395
- 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, DOI 10.1007/s002220100149
- Yauhen Mikulich, Newton’s Method as a Dynamical System. Thesis, Jacobs University Bremen, 2011.
- John Milnor, Dynamics in one complex variable, 3rd ed., Annals of Mathematics Studies, vol. 160, Princeton University Press, Princeton, NJ, 2006. MR 2193309
- 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
- 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
- Dierk Schleicher, Newton’s method as a dynamical system: efficient root finding of polynomials and the Riemann $\zeta$ function, Holomorphic dynamics and renormalization, Fields Inst. Commun., vol. 53, Amer. Math. Soc., Providence, RI, 2008, pp. 213–224. MR 2477425
- Dierk Schleicher, On the efficient global dynamics of Newton’s method for complex polynomials. Manuscript, submitted.
- Steve Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 2, 87–121. MR 799791, DOI 10.1090/S0273-0979-1985-15391-1
- 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.
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
- MR Author ID: 38980
- 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
- MR Author ID: 359328
- Email: dierk@jacobs-university.de
- Received by editor(s): September 10, 2010
- Received by editor(s) in revised form: August 28, 2011
- Published electronically: August 20, 2012
- © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 82 (2013), 443-457
- MSC (2010): Primary 37F10, 49M15
- DOI: https://doi.org/10.1090/S0025-5718-2012-02640-8
- MathSciNet review: 2983031