Small set of initial points for Newton’s method to find all roots of polynomials

Analysis 1 Minute

You need to know: Set {\mathbb C} of complex numbers, absolute value of a complex number, polynomials in complex variable, convergence, derivative, natural logarithm \ln.

Background:  Let P_d be the set of polynomials of degree d in one complex variable, such that all their roots have absolute values less than 1. For P \in P_d and z_0 \in {\mathbb C}, consider sequence z_0, z_1=f_P(z_0), z_2=f_P(z_1), \dots, where f_P(z) = z - \frac{P(z)}{P'(z)}. If this sequence converges to a root z^* of P, we say that z_0 is in the basin of z^*. This is called the Newton’s method for finding roots.

The Theorem: On 24th February 2000 John Hubbard, Dierk Schleicher, and Scott Sutherland submitted to Inventiones mathematicae a paper in which they proved that, for every d \geq 2, there is a set S_d consisting of at most 1.11 d \cdot \ln^2 d points in {\mathbb C} with the property that for every polynomial P \in P_d and every root z^* of P, there is a point s \in S_d in the basin of z^*.

Short context: Finding roots of polynomials is one of the basic problems in mathematics, with Newton’s method being one of the most popular methods for its numerical solution. However, its convergence depends on the choice of initial point z_0. The Theorem guarantees that, if we start Newton’s method from all points of S_d, we are guaranteed to find all the roots of any polynomial P \in P_d.

Links: The original paper is available here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment