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

摘要

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 [1.1d(log d)~2] points.