A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton’s method
Open Access
- 20 August 2012
- journal article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 82 (281) , 443-457
Abstract
We specify a small set, consisting of O ( d ( log log d ) 2 ) 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 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 d using Newton’s method; the best known deterministic set of starting points consists of ⌈ 1.1 d ( log d ) 2 ⌉ \lceil 1.1d(\log d)^2\rceil points.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Dynamics in One Complex Variable. (AM-160)2011
- Newton’s method as a dynamical system: Efficient root finding of polynomials and the Riemann 𝜁 function2008
- Rational and transcendental Newton maps2008
- Lectures on Quasiconformal Mappings2006
- Ensembles de Julia quadratiques de mesure de Lebesgue strictement positiveComptes Rendus Mathematique, 2005
- How to find all roots of complex polynomials by Newton’s methodInventiones Mathematicae, 2001
- Remarks on the simple connectedness of basins of sinks for iterations of rational mapsBanach Center Publications, 1989
- Newton’s Method Estimates from Data at One Point1986
- On the efficiency of algorithms of analysisBulletin of the American Mathematical Society, 1985
- On the dynamics of polynomial-like mappingsAnnales Scientifiques de lʼÉcole Normale Supérieure, 1985