|
 Finding
roots of polynomials is an ancient
problem, going back to the Sumerians.
The Newton-Raphson method of finding
approximate zeros of a function
proceeds as follows...
Let $f$ be a differentiable
function with a zero at $r$, and
suppose $x_1$ is a starting estimate of
$r$. Then the line tangent to the graph
of $f$ at $(x_1,f(x_1))$ has the
equation $y = f(x_1) + f'(x_1)
(x-x_1)$. We may suppose that the zero
of $f$, which is $r$, and the zero of
the preceding equation, which is $x_2 =
x_1 - f(x_1)/f'(x_1)$, would be closer
than $r$ and our original estimate,
$x_1$. From $x_2$ we can find a still
better estimate by defining $x_3 = x_2
- f(x_2)/f'(x_2)$ $\ldots$ and so on.
(See the diagram.) 
Under certain assumptions,
this is indeed what happens. Even for
functions in a complex variable.
However, the dynamics of the Newton
method is a complex matter. For
example, even for cubic polynmials
there may be open sets of initial
points which do not lead to iterations
converging to a root, but instead to an
attracting cycle of length greater than
one.
So we are lead to consider
the following question:
Is there a finite (small
and constructible) set of initial
values which we can be sure will
converge to all of the roots of a
polynomial?
The answer - yes - comes from a recent
paper, How to find all roots of a
complex polynomial by Newton's
method by J. Hubbard, D.
Schleicher and S.
Sutherland.
Theorem. For every $d
\ge 2$ there is a set $S_d$ consisting
of at most $1.11 d \log^2 d$ points in
$\mathbb{C}$ with the property that for
every polynomial $p \in \mathcal{P}_d$
and each of its roots, there is a point
$s \in S_d$ such that the iteration
associated by Newton's method with $s$
converges to the chosen
root.
The idea of the proof can be
seen from diagram 1. The diagram
shows the Julia set of a polynomial of
degree $50$. Each point in this square
in the complex plane is colour-coded
according to which root the Newton
method iteration converges to (call
points with the same colour, the
basin of the root). The roots are
shown by the red dots. There are $47$
roots near the unit circle, and three
more much closer to $0$.
Key is the fact that each basin has
channels which extend all the way out
to infinity. Then it can be shown that
there is a lower bound on the width of
one channel for each root. Thus we can
choose $S_d$ to be a ring of points on
the unit disc sufficiently close
together that at least one will fall
into each channel.
|
