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

Bollobás, Béla; Lackmann, Malte; Schleicher, Dierk

doi:10.1090/S0025-5718-2012-02640-8

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.