On the Convergence of Newton’s Method

Joel Friedman University of California, Berkeley

0. Abstract

Let P_{d} be the set of polynomials over the complex numbers of degree d with all its roots in the unit ball. For f ∈ P_{d}, let Γ_{f} be the set of points for which Newton’s method converges to a root, and let A_{f} ≡ |Γ_{f} ∩ B_{2}(0)|/|B_{2}(0)|, i.e. the density of Γ_{f} in the ball of radius 2 (where | | denotes Lebesgue measure on C viewed as R^{2}). For each d we consider A_{d}, the worst-case density (i.e. infimum) of A_{f} for f ∈ P_{d}. In [S], S. Smale conjectured that A_{d} > 0 for all d ≥ 3 (it was well-known that A_{1} = A_{2} = 1). In this paper we prove that

(\frac{1}{d})^{cd^{2} log d} ≤ A_{d}

for some constant c. In particular, A_{d} > 0 for all d.

Remark: Our definition of A_{d} differs slightly from that in [S], but the conclusions hold for A_{d} as defined in [S] as well.

1. Introduction

Newton’s method is a method for finding the zeros of a function, f. One starts with an initial guess, z_{0}, of a zero of f, and then generates a sequence of successive guesses according to the rule

z_{i+1} ⟵ z_{i} − \frac{f(z_{i})}{f′(z_{i})}.  (1.1)

Intuitively, using the value of f and f′, we locate the unique zero of the tangent line to f at z_{i}; this is the next guess, z_{i+1}.

It is known that for any differentiable function, f, and any root, r, of f, the sequence {z_{i}} converges to r if our first guess, z_{0}, is close enough to r. We define the basin of r to be the set of points in C for which Newton’s method converges to r.

There are various forms of Newton’s method. We will assume that f is a polynomial

f(z) = a_{0}z^{n} + ⋯ + a_{n},  a_{i} ∈ C,  (1.2)

so that f and f′ are easy to compute. We will view equation (1.1) as a map

T_{f}(z) = z − \frac{f(z)}{f′(z)},

from C ∪ {∞} to itself. In this paper we will study the set Γ_{f}, defined to be the set of points, z_{0}, for which Newton’s method works, i.e. {z_{i}} converges to a root of f.

In this paper we will use a geometric interpretation of Newton’s method, involving a relation that goes back at least 100 years–

Theorem 1.1 (Lucas, 1874): Let f(z) be a polynomial with coefficients in C. Then the zeros of f′ lie in the convex hull of the roots of f.

Proof: For a set S ⊂ C, we denote its closed convex hull by ⟨S⟩. It is easy to check that

f′(z) = f(z) ∑_{i=1}^{d} \frac{1}{z − r_{i}} ,  (1.3)

where r_{1},…, r_{n} are the roots of f. Assume that f′ has a root, z, outside ⟨r_{j}⟩, the convex hull of the roots. Then the vectors from z to the r_{i}’s all lie in one side of a half-plane through z. Then the vectors z − r_{i} all lie to one side of a half-plane. Hence the \frac{1}{z−r_{i}} ’s lie to one side of a half-plane (not the same half-plane, rather the one you get by reflecting through the x-axis). Hence the sum of the \frac{1}{z−r_{i}} ’s cannot vanish, which is a contradiction.

Given a polynomial, f, the Newton map for f,

T_{f}(z) = z − \frac{f(z)}{f′(z)},  (1.4)

has a geometric interpretation in terms of f’s roots. For a polynomial f(z) = (z−r_{1}) … (z− r_{d}), we can write T_{f} as

z + \frac{1}{∑{d \atop i=1} \frac{1}{r_{i}−z}} .  (1.5)

For example, if z = 0,

T_{f}(0) = \frac{1}{∑{d \atop i=1} \frac{1}{r_{i}}} .  (1.6)

This is sometimes called the harmonic sum of the r_{i}’s. Looking at equation (1.5) we see that T_{f}(z) looks like T_{f}(0) with z as the origin. From equation (1.5) we can also see that if we change z and the roots of f, by a translation, rotation, and/or dialation, (i.e. a linear map az + b, with a, b ∈ C), then the new T_{f}(z) is just the old T_{f}(z) transformed in the same way.

We will give an example of the geometric point of view. By a wedge, W, we mean a subset of C of the form

W = {z : θ_{1} ≤ arg(z − r) ≤ θ_{2}},  (1.7)

where arg(z) is the angle z makes with the positive x-axis; r is called the vertex of the wedge, and θ_{2} − θ_{1} its angle. A wedge is convex iff its angle is ≤ π.

Theorem 1.2: If W is a convex wedge at z containing the {r_{i}}’s, then T_{f}(z) is contained in W.

Proof: The r_{i} − z’s lie in a wedge V = W − z about the origin; by W − z we mean the points \{w − z : w ∈ W \}. Thus the \frac{1}{r_{i}−z} ’s lie in the wedge V′, the reflection of V through the x-axis. Since V′ is a convex wedge, then it also contains their sum ∑ \frac{1}{r_{i}−z}. Its reciprocal is contained in the original wedge, V, and hence T_{f} is contained in W = V + z (= {v + z : v ∈ V }).

Returning to the study of Γ_{f}, we would like to know how likely a randomly chosen point in C will lie in Γ_{f}.

Let P_{d} denote the polynomials of degree d with roots in the unit ball. For a function f, let A_{f} denote the density of Γ_{f} in the ball or radius 2, i.e.

A_{f} ≡ \frac{|Γ_{f} ∩ B_{2}(0)|}{|B_{2}(0)|},  (1.8)

where |C| denotes the area of C. For a positive integer d, let

A_{d} ≡ inf{A_{f} : f ∈ P_{d}}.  (1.9)

In this paper we will prove that A_{d} > 0 for all d.

There are several reasons why we study A_{d}:

(1) It is easy to ensure f ∈ P_{d}.

Fact: If f(z) = a_{0}z^{d} + ⋯ and |a_{0}| > ∑_{i=1}^{d} |a_{i}|, then f ∈ P_{d}.

Proof: If |z| > 1, then a_{0}z^{d} is larger in absolute value than the sum of all the lower order terms of f. Hence if |z| > 1, then z cannot be a root of f.

(2) By rescaling we can assume that (1) holds. Since

f(zc) = (a_{0}c^{d})z^{d} + (a_{1}c^{d−1})z^{d−1} + ⋯,  (1.10)

the a_{0}c^{d} will dominate if we take c large enough.

(3) We need some restriction on f to prove a density theorem. It is well known that for any d ≥ 3 there is a polynomial f for which Newton’s method does not converge on some open set in C (see, for example, [S]). It follows that for any bounded set we can find a polynomial of degree d for which Newton’s method does not converge anywhere on this bounded set, simply by taking an appropriate translation and dilation of f. The main theorem of the paper is Theorem 1.4: A_{d} > 0 for d ≥ 3. More precisely, there is a constant c_{1} such that

(\frac{1}{d})^{c_{1}d^{2} log d} ≤ A_{d}.  (1.11)

We caution the reader to note that A_{f} is not continuous in f’s coefficients or its roots. For example, for f(z) = z^{3} Newton’s method works for any initial guess. Yet one can show that there exists a constant c < 1 such that there exist polynomials g, arbitrary close to f, with A_{g} ≤ c.

We will introduce some useful notations for the rest of the paper.

Let E be a subset of C. By sE, s ∈ R, we mean the set E dilated by s, i.e.

sE ≡ {s · e : e ∈ E}.

By sE_{z} we mean sE with z viewed as the origin, i.e.

sE_{z} ≡ {z + s(e − z) : e ∈ E}.

In particular sE_{0} = sE.

Given a convex polygon, P, and a vertex, v, of the polygon, the interior angle at v is the angle determined by the two line segments of the boundary of P meeting v; the exterior angle at v it the angle opposite the interior angle (see figure 1).

Figure 1

The exterior wedge at v is the wedge bounded by the exterior angle at v. If P is a degenerate polygon, that is to say a line segment, then the exterior wedge is the ray from v to ∞ which is colinear and opposite the line segment.

In this paper we use many different constants. Rather that give each one a different name, we will denote them all by c (unless some confusion will occur).

In §2 we describe some regions in which Newton’s method converges. In §3 we estimate the area of one of these regions, yielding the lower bound on A_{d}. Some of the calculations used in these sections are postponed until appendix A.

We remark that as we send this paper for publication, A. Manning proved that Γ_{f} has density 1/(d^{2} log^{2} d) in the ball of radius d, see [M]; one can use this to improve our density bound to 1/d^{cd log d}. Also, an earlier version of this paper, [F], appeared in a conference.

The author would like to thank Steve Smale for many helpful discussions.

2. Invariant Curves

For background, let us begin with the question of how fast does Newton’s method converge. One can do both local and assymptotic analysis as follows—

Let f be a polynomial of degree d, and let r be a root of f of multiplicity k. An easy calculation shows

T′_{f}(z) = \frac{f(z)f′′(z)}{(f′(z))^{2}}.  (2.1)

It follows that at r we have

T′_{f}(r) = 1 − \frac{1}{k} .  (2.2)

Hence if r is a simple root of f we get T′_{f}(r) = 0 so that

T_{f}(r + ϵ) = r + aϵ^{2} + · · · .  (2.3)

In other words, Newton’s method is quadratically convergent. For a root of multiplicity > 1, Newton’s method is linearly convergent. That is

T_{f}(r + ϵ) = r + (1 − \frac{1}{k} )ϵ + …,  (2.4)

and so

T^{n}(r + ϵ) = r + (1 − \frac{1}{k} )^{n}ϵ + · · · .  (2.5)

Assymptotically, for |z| ≫ r’s, we have

\begin{aligned}T_{f}(z) & = z + \frac{1}{∑ \frac{1}{r_{i}−z}} \\ & ≈ z + \frac{1}{∑ \frac{1}{−z}} \\ & = z + \frac{1}{−d/z} = z(1 − \frac{1}{d}). \end{aligned}  (2.6)

Notice the similarity in the right-hand side of (2.4) with that of (2.6); geometrically a d-tuple root and |z| ≫ r’s look similar.

We would like to know what Newton’s method looks like, not only very near the root or very far away, but also in between.

Theorem 2.1: Let l be a line separating 0 from the roots, {r_{i}}, of f. Then T_{f}(0) lies on the side opposite from 0 of the line l′ = \frac{1}{d}l, i.e the line parallel to l and d times closer to 0.

Figure 2 For theorem 2.1

Proof: (See figure 2). We recall that the map f : C → C given by f(z) = \frac{1}{z} maps circles and lines to circles and lines (not respectively). If the roots, {r_{i}}, lie in the half-plane H, then \{\frac{1}{r_{i}} \}’s lie in a ball, B, through 0. Then, since B is convex, the sum of the \{\frac{1}{r_{i}} \}’s will lie in the ball dB; and its reciprocal hence lies in the half-place \frac{1}{d}H, whose boundary is \frac{1}{d}l.

We will give another instance where the geometry of Newton’s method makes things a bit simpler. Before we saw that for a root, r, of the polynomial f,

|T_{f}(r)| = r,  |T′_{f}(r)| < 1,  (2.7)

and concluded that near r, Newton’s method converges to r; i.e. B_{δ}(r) ⊂ {basin of r} for some δ > 0. We now want an estimate for δ.

Theorem 2.2: Let η = min_{r_{i}≠r} |r_{i} − r|, and δ = \frac{η}{2d}. Then B_{δ}(r) ⊂ \{basin of r\}. Furthermore, z ∈ B_{δ}(r) implies |T_{f}(z) − r| ≤ (1 − ϵ)|z − r| for some ϵ > 0 depending only on d.

Proof: An easy calculation— see appendix A.

By an invariant curve we mean a curve ϕ: R → C such that

T_{f}(ϕ(t)) = ϕ(t + 1)  (2.8)

for all t ∈ R. Note that if ϕ(t) lies in the basin of r, for some root r, for t ∈ [0, 1], then so would ϕ(t) for any t < 0 and any t > 0. We will prove that for each vertex, r, of ⟨r_{j}⟩, there will be an invariant curve from r to ∞ in the exterior wedge of r (and an open set about the curve) which lies in the basin of r (see figure 3).

Figure 3 Some parts of the basins

Lemma 2.3: If z lies on the bisector of the exterior angle at r, then T_{f}(z) lies in the exterior wedge at r.

Proof: In appendix A.

Let r be a vertex of ⟨r_{j}⟩, and let z be a point within B_{δ}(r), δ as in theorem 2.2, and lying on the bisector of the exterior angle at r. Then T_{f}(z) lies in B_{δ}(r) and in the exterior wedge at r. We construct an invariant curve ϕ: R → C by defining ϕ(0) = z, ϕ(1) = T_{f}(z), and

for 0 ≤ t ≤ 1  ϕ(t) ≡ (1 − t)z + (t)T_{f}(z).  (2.9)

Since B_{δ}(r) and the exterior wedge at r are convex, it follows that ϕ(t) ∈ B_{δ}(r) and lies in the exterior wedge for all t ∈ [0, 1].

(The reader may notice that the definition in equation (2.9) is rather arbitrary— all we need is that ϕ(t), for t ∈ [0, 1], lies in the exterior wedge and B_{δ}(r).)

One can use equation (2.8) to extend the curve ϕ to all of [0, ∞], but the important step is to extend ϕ backwards to −∞.

We can always extend the curve backwards for a short time (uniquely) as long as T_{f}^{−1} ≠ ∞ (or 0). By Lucas’ theorem we have f, f′, and f′′ have all their roots in ⟨r_{j}⟩. Since

T′_{f}(z) = \frac{f(z)f′′(z)}{(f′(z))^{2}},  (2.10)

it follows that we can extend ϕ backwards at least as long as ϕ remains outside ⟨r_{j}⟩.

But on the other hand, when we extend ϕ backwards, we will never leave the exterior wedge at r— if ϕ left the wedge it would do so at some initial time, T_{0}. But it is easy to see that any point on the boudary of the exterior wedge is mapped to a point outside the exterior wedge (assuming the wedge is non-degenerate; see figure 4).

Hence we can extend ϕ backwards to all of R.

Remark: In the degenerate case of all roots lying on one line segment, ϕ is just the continuation of the line segment.

Figure 4

We want to prove that as t → −∞, ϕ(t) → ∞. For this we need the following theorem—

Theorem 2.4: Let the angle at r be α. Then

\frac{|ϕ(t − n) − r|}{|ϕ(t) − r|} ≥ (\frac{d}{d − 1})^{n}\{ \begin{matrix}sin α, & if α > π/2 \\ 1, & if α ≤ π/2 \end{matrix} \}.

Figure 5

Proof: Let t be fixed and let z = ϕ(t − n). Let l and l′ be the lines depicted in figure 5, through z and parallel to the interior angle boundaries. By theorem (2.1), T_{f}(z) = ϕ(t − n + 1) and z must lie on opposite sides of both l_{r}(1 − \frac{1}{d}) and l′_{r}(1 − \frac{1}{d}). Applying T recursively it follows that ϕ(t) is contained in the diamond pictured above, bounded between (1 − \frac{1}{d})^{n} times l_{r} and l′_{r} and the exterior angle at r. It remains to prove the following—

Lemma 2.5: Let ABCD be a parallelogram. Let ^{}C̸ = α, and let E be any point in ABCD. Then

|AC| ≥ |EC| \{ \begin{matrix}1 & if α ≤ \frac{π}{2} \\ sin α & if α > \frac{π}{2} \end{matrix} \} .

Proof: See appendix A.

Corollary 2.6: ϕ(t) → ∞ as t → −∞.

At this point let us stop for a few remarks—

1. To estimate A_{d} we only need a sequence of points which are successive backward iterates of T_{f} and which are reasonably well-behaved. The invariant curves are a technical conveniece which gives us a lot of such sequences.

2. At this point we start to see some of the picture. We claim that the invariant curve is surrounded by an open region of points in the basin of r; more generally, Γ_{f} is an open set. The reason is that if z lies in the basin of r, then T_{f}^{n}(z) lies in the interior of B_{δ}(r) for some n. Then T_{f}^{−n} ≡ (T_{f}^{−1})^{n}, defined locally at z, gives us a neighborhood about z which lies in the basin of r.

3. Estimating the Area of the Basin Near the Invariant Curves

For each invariant curve constructed in §2, there is an open set containing it and lying in the basin of a root. We want to estimate the area of these open sets to get a lower bound on the density of Γ_{f}. To do this, we will fix a vertex, r, of ⟨r_{j}⟩ whoose interior angle is ≤ π(1 − \frac{2}{d}). Such an r always exists since the average angle of an m-gon is π(1 − \frac{2}{m}). Let ϕ be the invariant curve described in §2 determined by having ϕ(0) being the point on the bisector of the exterior angle satisfying |ϕ(0) − r| = δ/2. For a fixed r and ϕ we define for z ∈ Image ϕ,

ρ(z) ≡ sup{ρ : B_{ρ}(z) ⊂ ( basin r)}.

It is convenient to define

θ(z) ≡ \frac{ρ(z)}{|z − r|}.  (3.1)

In this section we will prove—

Theorem 3.1:

θ(z) > (\frac{1}{d})^{cd^{2} log d}.

Corollary 3.2:

A_{f} > π(\frac{1}{2}(\frac{1}{d})^{cd^{2} log d})^{2}/|B_{2}(0)| = (\frac{1}{d})^{c′d^{2} log d} .

First we will give some intuition for why theorem 3.1 should be true. Far away, when |z| ≫ |r|, T_{f}(z) = z(1 − \frac{1}{d}) + lower order terms. It follows that

\frac{|T_{f}(z) − r|}{|z − r|}, \frac{ρ(T_{f}(z))}{ρ(z)} are both 1 − \frac{1}{d} + O(\frac{1}{|z|}),

so that

\frac{θ(T_{f}(z))}{θ(z)} = 1 + O(\frac{1}{|z|}).

Hence

\frac{θ(ϕ(t − n))}{θ(ϕ(t))} = \frac{θ(ϕ(t − n))}{θ(ϕ(t − n + 1))} ⋯ \frac{θ(ϕ(t − 1))}{θ(ϕ(t))}

= 1 + O(\frac{1}{|ϕ(t)|} + \frac{1}{|ϕ(t − 1)|} + ⋯)

= 1 + O(\frac{1}{|ϕ(t)|}),

because the sequence |ϕ(t)|, |ϕ(t − 1)|,... behaves roughly like a geometric series, according to theorem 2.4.

So if z is far enough away from all the roots, there is little difference between θ(z) and θ(T_{f}^{−n}(z)) for any positive integer n. There may be other ranges of z for which θ does not change much. When we cannot prove that this is the case we will use

Lemma 3.3: There exist constants μ and c, independent of d, such that if s ≤ 0 and θ(ϕ(s)) < μ/d then

\frac{θ(ϕ(s))}{θ(ϕ(s + 1))} ≥ \frac{c}{d^{6}} .  (3.2)

Proof: See appendix A.

It is in this lemma that we get the main contribution for the lower bound. It turns out that we will apply the lemma 3.3 about d^{2} log d times to get a bound on θ, namely for t ∈ [0, 1] and integer n we have

\begin{aligned}θ(ϕ(t − n)) & = [\frac{θ(ϕ(t − n))}{θ(ϕ(t − n + 1))} ⋯]θ(ϕ(t)) \\ & ≥ (\frac{c}{d^{6}} )^{O(d^{2} log d)} \end{aligned}

The rest of the time θ will not change much.

Now we give more ranges of ϕ where the ratio of the θ’s doesn’t change much.

Lemma 3.4: There exist μ and c independent of d such that the following is true. Let m and M be positive integers with m < M. Assume that for each n ∈ [m, M], n integer, we have

\frac{|r_{i} − r|}{|ϕ(t − n) − r|} \{ \begin{matrix}< \frac{c}{d^{2}} for i = 1,…, k \\ > \frac{d^{2}}{c} for i = k + 1,…, d \end{matrix} \}

for some k ≥ 2. Then

\frac{|ϕ(t − n) − r|}{|ϕ(t − n + 1) − r|} ≤ 1 − \frac{1}{2d}

for n ∈ [m, M]. If, in addition, for m < n ≤ M we have

θ(ϕ(t − n)) < \frac{μ}{d},

then

θ(ϕ(t − M)) ≥ \frac{1}{2}θ(ϕ(t − m)).

Proof: See appendix A.

Lemma 3.5: For t ∈ [0, 1] we have

θ(ϕ(t)) ≥ 1.

Proof: Since ϕ(0) and ϕ(1) lie in B_{δ/2}(r), so does ϕ(t) for t ∈ [0, 1], and hence ρ(ϕ(t)) ≥ δ/2 so that θ(ϕ(t)) ≥ 1.

We are now ready for the lower bound

Theorem 3.6: For any s ≤ 1 we have θ(ϕ(s)) ≥ (1/d)^{cd^{2} log d}.

Proof: Let s ≤ 1. Let t ∈ [0, 1] and n be a positive integer such that s = t − n. By lemma 3.5 we have

θ(ϕ(t)) ≥ 1 ≥ \frac{μ}{d},  (3.3)

if μ is sufficiently small. Let n_{0} be the largest integer ≤ n such that θ(ϕ(t − n_{0})) ≥ μ/d, where μ is sufficiently small to make equation (3.3) and lemmas 3.3 and 3.4 hold. We write

\begin{matrix}θ(ϕ(t − n)) \\ = [\frac{θ(ϕ(t − n))}{θ(ϕ(t − n + 1))} ⋯ \frac{θ(ϕ(t − n_{0} + 1))}{θ(ϕ(t − n_{0}))}]θ(ϕ(t − n_{0})). \end{matrix}

Let I denote the subset of positive integers m such that

\frac{c}{d^{2}} ≤ \frac{|r_{i} − r|}{|ϕ(t − m) − r|} ≤ \frac{d^{2}}{c} , for some i,  (3.4)

with c as in lemma 3.4, and let J denote the set of positive integers not in I. By theorem 2.4 we see that the size of I is at most cd^{2} log(d)— for each of d − 1 possible r_{i}’s, each one can satisfy (3.4) for at most cd log d values of m. Hence, using (3.2),

∏_{m∈I,n_{0}≤m<n} \frac{θ(ϕ(t − m + 1))}{θ(ϕ(t − m))} ≥ (\frac{1}{d})^{cd^{2} log d}.

If m ≥ n_{0} and m ∈ J, then ϕ(t − m) must lie outside of B_{δ/2} (or else θ(ϕ(t − m)) ≥ 1), and thus there are at least two roots r_{i} with

\frac{|r_{i} − r|}{|ϕ(t − m) − r|} ≤ \frac{c}{d^{2}} .

It follows that J ∩ [n_{0}, n − 1] consists of a union of at most d − 1 sequences of consecutive integers, each satisfying the conditions for lemma 3.4. Applying lemma 3.4 we have

∏_{m∈J,n_{0}≤m<n} \frac{θ(ϕ(t − m + 1))}{θ(ϕ(t − m))} ≥ (\frac{1}{2})^{d−1}.

Hence

θ(ϕ(t − n)) =

[ ∏_{m∈I,n_{0}≤m<n} \frac{θ(ϕ(t − m + 1))}{θ(ϕ(t − m))}] [ ∏_{m∈J,n_{0}≤m<n} \frac{θ(ϕ(t − m + 1))}{θ(ϕ(t − m))}] θ(ϕ(t − n_{0}))

≥ (\frac{1}{d})^{cd^{2} log d}.

Appendix A. Some Calculations

Lemma 2.5: Let ABCD be a parallelogram. Let ^{}C̸ = α, and let E be any point in ABCD. Then

|AC| ≥ |EC| \{ \begin{matrix}1 & if α ≤ \frac{π}{2} \\ sin α & if α > \frac{π}{2} \end{matrix} \} .

Proof: Clearly we only need show the above for E = B or D, and by symmetry only for E = B. Consider triangle ABC. Then ^{}B̸ = π − α and ^{}A̸ = β, ^{}C̸ = γ with α = β + γ. Then, by law of sines,

\frac{|AC|}{|BC|} = \frac{sin α}{sin β}.

Since β satisfies 0 ≤ β ≤ α, we have

\frac{|AC|}{|BC|} ≥ min_{β∈[0,α]} \frac{sin α}{sin β} = \{ \begin{matrix}1 & if α ≤ \frac{π}{2} \\ sin α & if α > \frac{π}{2} \end{matrix} \}

Lemma A.1: Let r = r_{1} = ⋯ = r_{k}, k ≥ 1, and let η = min_{r_{i}≠r} |r_{i} − r|. Then |T_{f}(z) − r| ≤ (1 − ϵ)|z − r| if |z − r| ≤ \frac{η}{2d} for some ϵ depending only on d.

Proof: After a linear map (a translation, rotation, and dilation) we may assume z = 0 and r = −1/2. Assuming \frac{η}{2d} ≥ |z − r| = \frac{1}{2}, we have η > d. Thus the r_{i}’s not equal to r lie outside of B_{d− \frac{1}{2}} (0), and so

|∑_{r_{i}≠r} \frac{1}{r_{i}} | ≤ (d − 1)\frac{1}{d − \frac{1}{2}} = \frac{2d − 2}{2d − 1}.

Furthermore, since 1/r = −2 we have that

∑ \frac{1}{r_{i}} ∈ B_{\frac{2d−2}{2d−1}} (−2k)

which lies in the interior of

{y : ℜ(y) < −1},

since 1 ≤ k ≤ d and \frac{2d−2}{2d−1} < 1. Since the map y → 1/y maps \{y : ℜ(y) ≤ −1\} to B_{1/2}(−1/2), we have

\{y : \frac{1}{y} ∈ B_{\frac{2d−1}{2d−d}} (−2k) for some k = 1,…, d\} ⊂ B_{\frac{1−ϵ}{2}} (−1/2)

for some ϵ > 0. Reversing the linear map sending z, r to 0, −1/2 yields the lemma.

Theorem 2.2: Let η = min_{r_{i}≠r} |r_{i} − r|, and δ = \frac{η}{2d}. Then B_{δ}(r) ⊂ \{basin of r\}. Furthermore, z ∈ B_{δ}(r) implies |T_{f}(z) − r| ≤ (1 − ϵ)|z − r| for some ϵ > 0 depending only on d.

Proof: By lemma A.1, z ∈ B_{δ}(r) implies |T_{f}(z)−r| ≤ (1−ϵ)|z−r|, as well as |T_{f}^{n}(z)−r| ≤ (1 − ϵ)^{n}|z − r| and thus T_{f}^{n}(z) → r.

Lemma A.2: Let y_{1}, ..., y_{m} lie in the wedge W of angle α ≤ π with vertex 0. Then

\frac{|y_{1}^{2} + ⋯ y_{m}^{2}|}{|y_{1} + ⋯ + y_{m}|^{2}} ≤ cos^{2}(\frac{α}{2}).

Proof: By a rotation we may assume that W = {z : | arg(z)| ≤ α/2}. Then we have

\begin{aligned}|y_{1} + ⋯ + y_{m}|^{2} & ≥ |ℜ(y_{1} + ⋯ + y_{m})|^{2} \\ & ≥ (|y_{1}| + ⋯ + |y_{m}|)^{2} cos^{2}(\frac{α}{2}) \\ & ≥ (|y_{1}|^{2} + ⋯ + |y_{m}|^{2}) cos^{2}(\frac{α}{2}) \end{aligned} .

Lemma A.3: Let l be the line through r and perpendicular to the bisector of the interior angle at r with respect to the polygon ⟨r_{j}⟩. Let H_{r} be the set (half-plane) of points lying to side of l opposite from ⟨r_{j}⟩. Then if z ∈ H_{r} we have

|T′_{f}(z)| ≤ 1 + \frac{1}{cos^{2}(\frac{π+α}{4})}

where α = ^{}r̸.

Figure 6

Proof: (See figure 6) We have

T′(z) = 1 − \begin{matrix}∑ & ( & \frac{1}{z−r_{i}} & ) & 2 \\ [ & ∑ & ( & \frac{1}{z−r_{i}} & ) & ] & 2 \end{matrix} .  (A.1)

We can assume that l is parallel to the imaginary axis.

If z lies above the bisector of ^{}r̸, then the z − r_{i}’s lie in the wedge W = {y : −π/2 ≤ arg(y) ≤ α/2\}, a wedge of angle \frac{π}{2} + \frac{α}{2} (see figure 7). If z lies below the bisector of ^{}r̸, then similarly the z −r_{i}’s lie in a wedge of angle \frac{π}{2} + \frac{α}{2}. It then follows that the 1/(z −r_{i})’s

Figure 7

also lie in a wedge of angle \frac{π}{2} + \frac{α}{2}. Combining equation (A.1) with lemma A.3 yields the lemma.

Lemma A.4: Let W be a wedge of angle α < π and let w ∈ W. Then

|w + w′| ≥ |w| \{ \begin{matrix}sin α & if α ≥ π/2 \\ 1 & if α < π/2 \end{matrix} \}

for any w′ ∈ W.

Proof: We can assume w = 1. Let w′ ∈ W and let w′ make an angle of β with the x-axis. Then |β| ≤ α. If |β| ≤ π/2 then clearly |1 + w′| ≥ 1.

Figure 8

Otherwise, from figure 8 we can see that

|1 + w′| ≥ sin(π − β) = sin β ≥ sin α.

Lemma A.5: Let z lie in the exterior wedge at r, let α = ^{}r̸, and let r′ ≠ r be a root of f with

|\frac{r′ − r}{z − r} | ≤ ν.

Then

|\frac{T_{f}(z) − r}{z − r} | ≥ \frac{c}{ν + 1} \{ \begin{matrix}sin α & if α ≥ π/2 \\ 1 & if α < π/2 \end{matrix} \}

for some absolute constant c.

Proof: We can assume z = 0, r = 1. We have all the r_{i}’s lie in the wedge determined by the interior angle at r,

W = {w : θ_{1} ≤ arg(w − 1) ≤ θ_{2}},

with θ_{2} − θ_{1} = α. Since z is in the exterior wedge we have

W ⊂ W′ = {w : θ_{1} ≤ arg(w) ≤ θ_{2}}.

It follows that all the 1/r_{i}’s lie in

W′′ = {w : −θ_{2} ≤ arg(w) ≤ −θ_{1}}.

Hence

∑ \frac{1}{r_{i}} = \frac{1}{r} + \frac{1}{r′} + ⋯ = 1 + \frac{1}{r′} + w

where w ∈ W′′. Since |r′| ≤ ν + 1 we have by lemma A.4 that

|\frac{1}{r′} + w| ≥ \frac{1}{ν + 1} \{ \begin{matrix}sin α & if α ≥ π/2 \\ 1 & if α < π/2 \end{matrix} \} .  (A.2)

Since

T_{f}(z) = \frac{1}{∑ \frac{1}{r_{i}}} = \frac{1}{1 + (\frac{1}{r′} + w)}

and since the quantity on the right hand side of equation (A.2) is always ≤ 1, it follows that

|T_{f}(z) − 1| ≤ \frac{c}{ν + 1} \{ \begin{matrix}sin α & if α ≥ π/2 \\ 1 & if α < π/2 \end{matrix} \}

for some absolute constant c.

Corollary A.6: Let ϕ be the curve defined just before lemma 3.6. Then ϕ(t) ≥ cδ/d^{2} for t ≤ 1 for some absolute constant c.

Proof: Since |ϕ(0) − r| = δ/2 we can apply lemma A.5 with ν = 4d and α ≤ π(1 − \frac{2}{d}) to obtain |ϕ(1)−r| ≥ cδ/d^{2} for some absolute constant c. It then follows that |ϕ(t)−r| ≥ cδ/d^{2} for any t ∈ [0, 1], and therefore also for any t < 0 since |T_{f}(z) − r| ≤ |z − r| for z ∈ B_{δ}(r).

Lemma 3.3: There exist constants μ and c, independent of d, such that if s ≤ 0 and θ(ϕ(s)) < μ/d then

\frac{θ(ϕ(s))}{θ(ϕ(s + 1))} ≥ \frac{c}{d^{6}} .

Proof: Let z = ϕ(s). The mean-value theorem implies

ρ(T_{f}(z)) ≤ ρ(z) max_{ζ∈B_{ρ(z)}(z)} |T′_{f}(ζ)|.

For μ sufficiently small (independent of d) we have ζ ∈ B_{ρ(z)}(z), ρ(z) ≤ \frac{μ}{d}|z − r|, and the fact that z lies in the exterior wedge at r together imply ζ ∈ H_{r} and thus

max_{ζ∈Bρ̄(z)} |T′_{f}(ζ)| ≤ 1 + \frac{1}{cos^{2}(\frac{π+α}{4})} ≤ cd^{2}.

Since z = ϕ(s) with s ≤ 0 we have by lemma A.6 that |z − r| ≥ cδ/d^{2} and thus

|\frac{r′ − r}{z − r} | ≤ \frac{2dδ}{cδ/d^{2}} = c′d^{3}

for some root r′ ≠ r. Hence by lemma A.5

|\frac{T_{f}(z) − r}{z − r} | ≥ \frac{c}{d^{4}} .

Thus

\frac{θ(z)}{θ(T_{f}(z))} ≥ \frac{ρ(z)}{ρ(T_{f}(z))} \frac{|T_{f}(z) − r|}{|z − r|} ≥ \frac{c}{d^{6}} .

Lemma A.7: Let z lie on the bisector of the exterior angle. Then T_{f} lies in the exterior angle.

Proof: It suffices to prove it for z = 0, r = 1. The map y → 1/y maps the wedge W = {z : | arg(z − 1)| ≤ α/2} to the lune (intersection of two circles) L with vertices at 0 and 1 and of angle α (see figure 9).

It follows that

∑ \frac{1}{r_{i}}

Figure 9

lies in the wedge 1 + (d − 1)L, since one of the r_{i}’s is 1. Since 1 + (d − 1)L is a subset of W, its reciprocal, T_{f}(z), lies in L. Since L lies in the exterior wedge, we are done.

Lemma 3.4: There exist μ and c independent of d such that the following is true. Let m and M be positive integers with m < M. Assume that for each n ∈ [m, M], n integer, we have

\frac{|r_{i} − r|}{|ϕ(t − n) − r|} \{ \begin{matrix}< \frac{c}{d^{2}} for i = 1,…, k \\ > \frac{d^{2}}{c} for i = k + 1,…, d \end{matrix} \}

and

θ(ϕ(t − n)) < \frac{μ}{d}.

Then

θ(ϕ(t − M)) ≥ \frac{1}{2}θ(ϕ(t − m)).

Proof: Let z be such that \frac{|r−r_{i}|}{|z−r|} ≤ ϵ for i = 1,…, k and \frac{|r−r_{i}|}{|z−r|} ≥ B for i = k + 1,…, d. For i = 1,…, k we have

|\frac{1}{r_{i} − z} − \frac{1}{r − z} | = |\frac{r_{i} − r}{(r − z)(r_{i} − z)}| ≤ \frac{1}{|r − z|} \frac{ϵ}{1 − ϵ}

since

|r_{i} − z| ≥ |r − z| − |r − r_{i}| ≥ |r − z|(1 − ϵ).

For i = k + 1,…, d we have

|\frac{1}{r_{i} − z} | ≤ \frac{1}{|r − r_{i}| − |r − z|} ≤ \frac{1}{|r − z|} \frac{1}{B − 1}.

Thus

∑_{i=1}^{d} \frac{1}{r_{i} − z} = \frac{k}{r − z} + \frac{d}{|r − z|}O(\frac{1}{B} + ϵ) = \frac{k}{r − z} [1 + O(\frac{d}{B} + dϵ)]

and so

\frac{T_{f}(z) − r}{z − r} = \frac{z − \frac{r−z}{k} [1 + O(\frac{d}{B} + dϵ)] − r}{z − r} = 1 − \frac{1}{k} + O(\frac{d}{B} + dϵ).  (A.3)

For

y ∈ B_{|z−r|μ/d}(z)

we have

|z − r|(1 − \frac{μ}{d}) ≤ |y − r| ≤ |z − r|(1 + \frac{μ}{d}).

Assuming, say, μ/d ≤ 1/2, we get for i = 1,…, k

\frac{1}{r_{i} − y} = \frac{1}{r − y} (1 + O(ϵ)),

(\frac{1}{r_{i} − y} )^{2} = (\frac{1}{r − y} )^{2} (1 + O(ϵ)),

and for i = k + 1,…, d

\frac{1}{r_{i} − y} = \frac{1}{r − y} O(1/B),

(\frac{1}{r_{i} − y} )^{2} = (\frac{1}{r − y} )^{2} O(1/B^{2}).

Thus

\begin{aligned}T′(y) & = 1 − \begin{matrix}∑ & ( & \frac{1}{y−r_{i}} & ) & 2 \\ [ & ∑ & ( & \frac{1}{y−r_{i}} & ) & ] & 2 \end{matrix} \\ & = 1 − \frac{\frac{k}{(y−r)^{2}} (1 + O(\frac{d}{B^{2}} + dϵ))}{(\frac{k}{y−r})^{2}(1 + O(\frac{d}{B} + dϵ))^{2}} \\ & = 1 − \frac{1}{k} + O(\frac{d}{B} + dϵ) \end{aligned} .

Hence, assuming ρ(z) ≤ \frac{μ}{d}|z − r| we have

\frac{θ(z)}{θ(T_{f}(z))} = \frac{ρ(z)}{ρ(T_{f}(z))} \frac{|T_{f}(z) − r|}{|z − r|}

≥ \frac{1}{max_{y∈B_{ρ(z)}} |T′_{f}(y)|} \frac{|T_{f}(z) − r|}{|z − r|}

= 1 + O (\frac{d}{B} + dϵ) ,

where the constant in O() is absolute.

If d/B and dϵ are sufficiently small, say ≤ 1/2d, then from equation (A.3)

\frac{|T_{f}(z) − r|}{|z − r|} ≤ 1 − \frac{1}{k} + \frac{1}{2d} ≤ 1 − \frac{1}{2d}.

So given m < M and k integers with

\frac{|r_{i} − r|}{|ϕ(t − n) − r|} \{ \begin{matrix}< \frac{c}{d^{2}} for i = 1,…, k \\ > \frac{d^{2}}{c} for i = k + 1,…, d \end{matrix} \}

for all n ∈ [m, M] and for some c sufficiently small, we have |ϕ(t − M) − r| + |ϕ(t − M + 1) − r| + ⋯ + |ϕ(t − m) − r|

≤ |ϕ(t − M) − r|(1 + (1 − \frac{1}{2d}) + (1 − \frac{1}{2d})^{2} + ⋯)

≤ |ϕ(t − M) − r|2d

and

\frac{1}{|ϕ(t − m) − r|} + ⋯ + \frac{1}{|ϕ(t − M) − r|} ≤ \frac{1}{|ϕ(t − m) − r|}2d.

Letting s = max_{i≤k} |r_{i} − r| and S = min_{i>k} |r_{i} − r| we have, assuming θ(ϕ(t − n)) ≤ μ/d for n ∈ [n + 1, M],

\frac{θ(ϕ(t − M))}{θ(ϕ(t − m))} = \frac{θ(ϕ(t − M))}{θ(ϕ(t − M + 1))} ⋯ \frac{θ(ϕ(t − m − 1))}{θ(ϕ(t − m))}

≥ ∏_{i=m}^{M−1} 1 − O(\frac{|ϕ(t − i) − r|}{S}d + d\frac{s}{|ϕ(t − i) − r|})

≥ 1 − c_{1} ∑_{i=m}^{M−1} \frac{|ϕ(t − i) − r|}{S}d + d\frac{s}{|ϕ(t − i) − r|}

≥ 1 − c_{1}2d(\frac{|ϕ(t − M) − r|}{S}d + d\frac{s}{|ϕ(t − m) − r|})

≥ 1 − c_{1}(\frac{c}{d^{2}} 2d^{2} + \frac{c}{d^{2}} 2d^{2}) ≥ 1 − c_{1}(2c + 2c)

where c_{1} is an absolute constant. So for c sufficiently small and ≤ \frac{1}{8c_{1}} the lemma is proven.

Bibliography

[F] J. Friedman, On Newton’s Method for Polynomials, in 27th Annual Symposium on Foundations of Computer Science (1986), 153-161.

[M] A. Manning, How to be Sure of Solving a Complex Polynomial using Newton’s Method, University of Warwick, preprint.

[S] S. Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), 87–121.