Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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
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?)

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

Malte Lackmann
Affiliation: Immenkorv 13, D-24582 Bordesholm, Germany

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

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