Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
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
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: http://dx.doi.org/10.1090/S0025-5718-2012-02640-8
PII: S 0025-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.