\section{Introduction}

Newton's root-finding method is as old as analysis, but still not
well understood, even in the fundamental case of finding all roots of
a polynomial in a single variable. Its local convergence properties
are well known; near simple roots convergence is quadratic and thus
extremely rapid. However, the global dynamical properties are
insufficiently understood so that numerical analysis algorithms often
use different global methods, and resort to Newton's method for a
final local ``polishing'' of the roots.

This article is a contribution towards a better understanding of the
global properties of Newton's method, applied to polynomials in a
single complex variable. Even for polynomials over the reals, and
even if all the roots are real, it is often preferable to use complex
methods; see Figure~\ref{Fig:NewtonDynamics}.

\begin{figure}
\includegraphics[width=0.49\textwidth]{NewtonDeg7Plane.pdf}
\includegraphics[width=0.49\textwidth]{NewtonDeg4Real.pdf}
\caption{Dynamical planes of Newton maps of two complex polynomials.
Different colors illustrate basins of attraction of different roots;
shades of color illustrate different speeds of convergence. It is
clearly visible that all immediate basins are unbounded and have one
or several channels to $\infty$ of different widths. Left: a
polynomial of degree $7$. Right: a polynomial of degree $11$ with all
roots real. Some of the roots are very close to each other; however, away
from the disk containing all the roots, the basins and their channels
all have almost uniform width, so that finding the real roots using
complex methods is much easier.}
\label{Fig:NewtonDynamics}
\end{figure}

\begin{figure}
\includegraphics[width=0.51\textwidth,trim=0 130 0 60,clip]{NewtonDeg11ThinRoots.pdf}
\caption{The dynamical plane of the polynomial $p(z)=z(z^{10}-1)$: the ten roots of unity each have one ``thick'' channel, while the root $z=0$ has 10 channels (red) which are all rather ``thin''. The deterministic method from \cite{HSS} would search for the individual thin channels and thus requires more points, while our method searches for the union of all thin channels, which together are much bigger.}
\label{Fig:NewtonDynamicsThinChannels}
\end{figure}

Among the difficulties with Newton's method are the following:
\begin{itemize}
\item
if an orbit under iteration comes close to a critical point of the
polynomial, the Newton map sends the orbit far away near $\infty$, so
that control of the dynamics is lost, and in any case a large number
of iterations are required until the orbit comes back to where the
roots are;
\item
there are polynomials with open sets of starting points that do not
converge to any root (Smale~\cite{Smale} asked, in 1984, for a
classification of such polynomials; an answer has recently been given by
Mikulich in current work \cite{ZhenyaThesis});
\item
the boundary of the basins of convergence for the roots may have
positive planar Lebesgue measure (this follows from recent work by
Buff and Ch\'eritat on the existence of Julia sets with positive
measure \cite{BuffCheritat}, combined with Douady and Hubbard's
renormalization theory \cite{PolyLike});
\item
even if almost every point in $\C$ converges to some root under the
Newton iteration, our goal is to find \emph{all} roots of the
polynomial, and with bounded complexity. Finding some roots and
deflating is usually not an option, because deflation is in general
numerically unstable (unless the roots are found in a specific
order), and because deflation might not be compatible with the way
the polynomial may be specified, or evaluated efficiently (for
instance, if the polynomial itself is given by an efficient iteration
procedure).
\end{itemize}
See \cite{Johannes} for a recent survey of known results on Newton's method.

