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(loglog d)^2)$ points, thatintersects the basins under Newton's method of emph{all} roots of emph{all}(suitably normalized) complex polynomials of fixed degrees $d$, witharbitrarily high probability. This set is an efficient and universalemph{probabilistic} set of starting points to find all roots of polynomials ofdegree $d$ using Newton's method; the best known emph{deterministic} set ofstarting points consists of $lceil 1.1d(log d)^2ceil$ points.