A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton's method
Provides a more efficient universal starting set for finding all roots of complex polynomials via Newton's method, benefiting numerical analysis and computational mathematics.
The authors construct a set of O(d(log log d)^2) starting points that, with high probability, intersects the basins of attraction for all roots of any degree-d complex polynomial under Newton's method, improving upon the best known deterministic set of size ~1.1d(log d)^2.
We specify a small set, consisting of $O(d(\log\log d)^2)$ points, that intersects the basins under Newton's method of \emph{all} roots of \emph{all} (suitably normalized) complex polynomials of fixed degrees $d$, with arbitrarily high probability. This set is an efficient and universal \emph{probabilistic} set of starting points to find all roots of polynomials of degree $d$ using Newton's method; the best known \emph{deterministic} set of starting points consists of $\lceil 1.1d(\log d)^2\rceil$ points.