A Density Theorem for Purely Iterative Zero Finding Methods

Joel Friedman Princeton University

November 12, 1987 Revised January 6, 1989

1 Introduction

The goal of this paper is to prove a theorem about the density of points for which a purely iterative root finding method converges to a root.

For z ∈ C and f(z) = ∑_{i=0}^{d} a_{i}z^{i} consider a map

T_{f}(z) = \frac{P (z, f, f′,…, f^{(l)})}{Q(z, f, f′,…, f^{(l)})}

where P and Q are polynomials over C. For each f, T_{f} is a map from C∪{∞} to itself which we think of as an iteration in a root finding method. We require that

1.

T_{f}(z) = \frac{z^{s}P_{0}(f, zf′, z^{2}f′′,…)}{z^{s−1}Q_{0}(f, zf′, z^{2}f′′,…)}  (1.1)

where P_{0} and Q_{0} are homogeneous polynomials of the same degree.

2. T_{f}(z) depends only on z and the roots r_{1},…, r_{d} of f, and

A(T_{f}(z)) = T_{Af}(Az)

for any linear map A: z ↦ az + b, where

Af(z) = a_{d}(z − Ar_{1}) … (z − Ar_{d})

for

f(z) = a_{d}(z − r_{1}) … (z − r_{d}).

3. T_{f}(r) = r, |T′_{f}(r)| < 1 for any root r of f.

4. T_{f}(∞) = ∞, |T′_{f}(∞)| > 1 for any f of degree > 1.

To measure the density of convergent points for T_{f}, let P_{d} denote the polynomials of degree d with roots in the unit ball. For a polynomial f, let

Γ_{T,f} = {z : T_{f}^{n}(z) → a root of f as n → ∞}

where T_{f}^{n} is the n-th iterate of T_{f} (i.e. Γ_{T,f} is the set of points converging to a root of f under the iteration T_{f}). Let

A_{T,f} = |Γ_{T,f} ∩ B_{2}(0)| .

Then A_{T,f}/4π is the probability that a random point in B_{2}(0) converges to a root.

Theorem 1.1 Let T satisfy (1)-(4). Then for any d there is a c > 0 such that

A_{T,f} > c ∀f ∈ P_{d}.

Furthermore, we have

A_{T,f,r} > c  ∀f ∈ P_{d},  ∀r with f(r) = 0,

where A_{T,f,r} denotes the contribution to A_{T,f} from the root r of f.

More precisely,

A_{T,f,r} = |Γ_{T,f,r} ∩ B_{2}(0)|

where

Γ_{T,f,r} = {z : T_{f}^{n}(z) → r as n → ∞}

The above density theorem was conjectured to hold for Newton’s method by Smale in [Sma85]. This conjecture was proven in [Fri86]; the proof used some special properties of Newton’s method and explicit bounds on the constants as a function of d were given. The above theorem applies to a much larger class of root finding methods, though no explicit bounds on c are given.

Examples of T satisfying (1)-(4) are 1. Newton’s method, T_{f}(z) = z − \frac{f}{f′}.

2. Modified Newton’s method, T_{f}(z) = z − h\frac{f}{f′} with a constant h, 0 < h < 1.

3. Taylor’s method (see [Atk78])

T_{f}(z) = z + ∑_{i=1}^{k} \frac{d^{i}}{dt^{i}} (\frac{ϕ_{t}(z)}{i!})|_{t=0} h^{i}

where ϕ_{t}(z) solves

\frac{dϕ_{t}(z)}{dt} = −\frac{f(z)}{f′(z)}, ϕ_{0}(z) = z

with k a positive integer and h a positive number sufficiently small (depending on k).

4. Incremental Euler’s method (see [Atk78])

T_{f}(z) = z + ∑_{i=1}^{k} \frac{(−hf(z))^{k}}{k!} g^{(k)}(f(z))

with g = f^{−1}, k a positive integer, and h positive and sufficiently small.

5. Any iterate of a T satisfying (1)-(4). This shows that maps satisfying (1)-(4) may contain extraneous attractive fixed points. For example, Newton’s method, even applied to polynomials of degree as low as three, can contain attractive periodic points of period two. Therefore the second iterate of Newton’s method can have extraneous attractive fixed points.

To prove theorem 1.1, take any sequence f_{n} ∈ P_{d}; we will show that A_{T,f_{n}} can not approach 0 as n tends to infinity. By passing to a subsequence we can assume each of the f_{n}’s coefficients, or equivalently each of f_{n}’s roots, converge. If A_{T,f} were continous in f at the limit of the f_{n}’s then we would be done; the fact that A_{T,f} can be discontious at f’s having multiple roots makes the theorem more interesting. If the limit of f_{n} has at least one isolated root, one would get enough of a contribution to A_{T,f_{n}} from such an isolated root (for large n) to show that A_{T,f_{n}} is bounded away from zero. However, if all of f_{n}’s roots tend to cluster into several groups as n → ∞, we must look at the limiting geometry of each individual cluster to estimate A_{T,f_{n}}. So fix a cluster, and“blow-up” the picture of the roots at that cluster so that, while they remain in some bounded region, they separate into smaller subclusters. Again, if the blow-up of at least one cluster has as least one isolated root, we are done; the reason is that the isolated root’s contribution to Γ_{T,f_{n}} contains a sequence of balls which, from the point of view of the subcluster, tend to ∞ and whose radii get larger. These balls, from the point of view of the original scale of the problem, look like a sequence of balls whose radii get smaller and smaller and whose center converges to the cluster’s limit point. It is not hard to see that in the original scale of the problem, the largest ball is of appreciable size, thus bounding A_{T,f_{n}} from below.

If none of the clusters has an isolated root, we look at the geometry of each subcluster, blowing-up the picture at each subcluster. Since the blowing-up process separates a cluster of roots into at least two distinct subclusters, successive blowing-up eventually isolates the roots. One can then find balls in Γ_{T,f_{n}} for each root in the blow-up of the picture which isolates it, and back-up through the blow-ups until reaching the original scale of the problem, finding balls in each scale of blow-up which lie in Γ_{T,f_{n}}. The fact that this can be done for each root proves, in addition, the second part of the theorem.

The basic estimate for the existence of the aforementioned balls is lemma 2.2, proved in section 2. In section 3 we describe the blowing-up process more precisely, and show how lemma 2.2 can be applied backwards through the blowing-up process.

2 Some Preliminary Results

Let g: N → C∪{∞} be a complex analytic map, for an open N ⊂ C∪{∞}. Let z ∈ N be a repelling fixed point, i.e. g(z) = z and |g′(z)| > 1.

Lemma 2.1 For any open A ⊂ C we have that for n sufficiently large,

g^{n} {B_{ϵ}(z)} ∩ A ≠ ∅.

Proof Apply Cauchy’s formula for (fg^{n})′(z), where f is a Möbius function taking a point in A to ∞, and where the contour is a small circle around z.

For our maps T, we have that ∞ is a repelling fixed point so the lemma can be applied.

From condition (1)-(4) on T it is easy to see that

T′_{f}(∞) = q(d) = \frac{Q_{0}(1, d, d(d − 1),…)}{P_{0}(1, d, d(d − 1),…)}

is a rational funciton of d independent of f, and that if r is a k-tuple root, then

T′_{f}(r) = \frac{P_{0}(1, k, k(k − 1),…)}{Q_{0}(1, k, k(k − 1),…)} = \frac{1}{q(k)}.

For any f we have that for z in a neighborhood of ∞,

T_{f}(z) = \frac{z}{q(d)} + O(1)

and

T′_{f}(z) = \frac{1}{q(d)} + O (\frac{1}{|z|})  (2.1)

and T_{f}^{−1} is defined locally. We have

\frac{T_{f}(z)}{z} = \frac{1}{q(d)} + O (\frac{1}{|z|})

and so for |z| sufficiently large, we have z_{0} = z, z_{−1}, z_{−2},… given by T_{f}(z_{−i}) = z_{−i+1} has |z_{−n}| growing like (q(d) − ϵ)^{n} for any ϵ > 0 depending on how large |z| is, and thus

\frac{z_{−n}}{z} = ∏_{i=0}^{n−1} (1 − O (\frac{1}{|z_{−i}|})) q(d)
= q^{n}(d) (1 − O (\frac{1}{|z|})) .  (2.2)

The mean value theorem and equation 2.1 yield for, say, r < |z|/2,

T_{f}^{n} {B_{r′}(z_{−n})} ⊂ B_{r}(z)  (2.3)

with

r′ = r q^{n}(d) (1 − O (\frac{1}{|z_{−n+1}|} + ⋯ + \frac{1}{|z|}))
= r q^{n}(d) (1 − O (\frac{1}{|z|})) .  (2.4)

Let

z̃ = lim_{n→∞} \frac{z_{−n}}{q^{n}(d)},

the limit existing by virtue of equation 2.2. For any r < |z|/2, using equations 2.3 and 2.4, we have

T_{f}^{n} {B_{rq^{n}(d)/2} (z̃q^{n}(d))} ⊂ B_{r}(z)  (2.5)

for n sufficiently large (depending on r).

Next we would like to obtain a version of equation 2.5 for polynomials close to f in a certain sense. Fix d, D, and f, and consider the set F_{f,δ,D} of polynomials

g(z) = (z − s_{1}) … (z − s_{d+D})

with s_{i} ∈ B_{δ}(r_{i}) for 1 ≤ i ≤ d and |s_{i}| > 1/δ for i > d.

Lemma 2.2 For any sufficiently large z and r < |z|/2 there is a c, δ_{0} and n_{0} such that if δ < δ_{0} and n > n_{0} we have

T_{g}^{n} {B_{rq^{n}(d)/2}(z̃q^{n}(d))} ⊂ B_{r}(z)

if

|z̃|q^{n}(d) < \frac{c}{δ}

for all g ∈ F_{f,δ,D}.

Proof Dividing both numerator and denominator by z^{s−1}g^{deg(P_{0})} in condition (1) on T yields

T_{g}(z) = \frac{zP_{0}(1, z \frac{g′}{g} , z^{2} \frac{g′′}{g} ,…)}{Q_{0}(1, z \frac{g′}{g} , z^{2} \frac{g′′}{g} ,…)}.

For |z| sufficiently large and, say, ≤ \frac{1}{2δ} we have

|\frac{f′}{f} − \frac{g′}{g} | ≤ ∑_{i=1}^{d} |\frac{1}{z − r_{i}} − \frac{1}{z − s_{i}} | + ∑_{j=d+1}^{d+D} |\frac{1}{z − s_{j}} |

= ∑ |\frac{s_{i} − r_{i}}{(z − r_{i})(z − s_{i})}| + ∑ \frac{1}{|z − s_{i}|}
= O (\frac{δ}{|z|^{2}} + δ) .

Similarly we have

|\frac{f^{(k)}}{f} − \frac{g^{(k)}}{g} | ≤ ∑_{1≤i_{1}<...<i_{k}≤d} k! |\frac{1}{(z − r_{i_{1}}) … (z − r_{i_{k}})} − \frac{1}{(z − s_{i_{1}}) … (z − s_{i_{k}})}| +

∑_{1≤i_{1}<...<i_{k}≤d+D, i_{k}>d} k! |\frac{1}{(z − s_{i_{1}}) … (z − s_{i_{k}})}|

= O (\frac{δ}{|z|^{k+1}} + \frac{δ}{|z|^{k−1}} + \frac{δ^{2}}{|z|^{k−2}} + ⋯ + δ^{k})
= O (\frac{δ}{|z|^{k+1}} + \frac{δ}{|z|^{k−1}} );

in the last line we have used the fact that for sufficiently large z and n we have |z|δ < 1 (which follows from the second equation in the statement of the lemma). Thus

|z^{k} \frac{f^{(k)}}{f} − z^{k} \frac{g^{(k)}}{g} | = O (\frac{δ}{|z|} + δ|z|)

and so

T_{g}(z) = T_{f}(z) (1 + O (\frac{δ}{|z|} + δ|z|)) ,  (2.6)
T′_{g}(z) = T′_{f}(z) (1 + O (\frac{δ}{|z|} + δ|z|)) .

We caution the reader that the big-O notation above is as the quantity in parenthesis tends to zero, and that the constants in the big-O notation depend on d and D. Now fix a z sufficiently large and a small ϵ so that z_{0} = z, z_{−1}, z_{−2},… defined as before grow like a geometric series. Then, using equation 2.6, we see that for δ sufficiently small we have that y_{0} = z, y_{−1}, y_{−2},…, y_{−n} given by T_{g}(y_{−i}) = y_{−i+1} grows like a geometric series, as long as |y^{−n}| < c/δ for c sufficiently small. Then we get

y_{−n} = z_{−n} ∏_{i=0}^{n−1} (1 + O (\frac{δ}{|y_{−i}|} + δ|y_{−i}|))
= z_{−n} (1 + O (\frac{δ}{|z|} + δ|y_{−n}|)) .

Using the chain rule we have

(T_{g}^{n})′(w) = ∏_{i=0}^{n−1} T′_{g}(T_{g}^{i}(w))
= (\frac{1}{q(d)})^{n} (1 + O (\frac{δ}{|T_{g}^{n}(w)|} + δ|w|))

assuming |T_{g}^{n}(w)| is sufficiently large and |w| ≤ c/δ. The mean value theorem then implies

T_{g}^{n} {B_{r′}(z_{−n})} ⊂ B_{r}(z)

where

r′ = rq^{n}(d) (1 + O (\frac{δ}{|z|} + δ|z_{−n}|)) .

Hence, as before, we get that for sufficiently large n,

T_{g}^{n} {B_{rq^{n}(d)/2}(z̃q^{n}(d))} ⊂ B_{r}(z)

as long as |z̃|q^{n}(d) < \frac{c}{δ} for c sufficiently small.

3 Successive Normalizations

The difficulty in proving theorem 1.1 is that A_{T,f} is not necessarily continuous when f has multiple roots. Let f_{1}, f_{2},… be a sequence in P_{d}, and r_{1}^{1}, r_{1}^{2},… a sequence of respective roots for which

lim_{n→∞} A_{T,f_{n},r_{1}^{n}} = inf_{f∈P_{d}, f(r)=0} A_{T,f,r}.

By passing to a subsequence we may assume that

f_{n}(z) = (z − r_{1}^{n})^{e_{1}} … (z − r_{k_{0}}^{n})^{e_{k_{0}}}

with

e_{1} + ⋯ + e_{k_{0}} = d

and

r_{i}^{n} ≠ r_{j}^{n} ∀n, i < j ≤ k_{0}.

By passing to a subsequence we can assume

r_{i}^{n} → r_{i} as n → ∞.

If r_{1} is isolated, i.e. e_{1} = 1, then it would be easy to show that for some δ > 0 we have

B_{δ}(r_{i}^{n}) ⊂ Γ_{T,f_{n}}

for all n sufficiently large, and thus

inf_{f∈P_{d}, f(r)=0} A_{T,f,r} > 0

(the details of the argument appear as part of the proof later in this section). If not, we can assume

r_{1} = r_{2} = … = r_{k_{1}}

and r_{j} ≠ r_{1} for j > k_{1}. We will now analyze more carefully the way in which r_{1}^{n},…, r_{k_{1}}^{n} converge to r_{1}.

For z_{1},…, z_{m} ∈ C not all the same, we define the normalization of z_{1},…, z_{m} centered at z_{1} to be the unique linear map

g(z) = az + b, a ∈ R, a > 0, b ∈ C

such that

∑_{i<j} |g(z_{i}) − g(z_{j})| = 1,

and g(z_{1}) = 0.

By passing to a subsequence we can assume that 1. the normalizations of r_{1}^{n},… r_{k_{0}}^{n}, g_{n}(z) = a_{n}z + b_{n}, centered at r_{1}^{n} have

g_{n}(r_{i}^{n}) → s_{i} as n → ∞, and

2.

q_{1}^{⌊− log_{q_{1}} a_{n}⌋}a_{n} → a  (3.1)

as n → ∞ for some a ∈ [1/q_{1}, 1] where

q_{1} = q (∑_{i=1}^{k_{1}} e_{i})

and where ⌊β⌋ denotes the largest integer ≤ β.

Clearly

∑_{i<j} |s_{i} − s_{j}| = 1,

and so we have

s_{1} = ⋯ = s_{k_{2}}

and s_{j} ≠ s_{1} for j > k_{2} where k_{2} < k_{1}. In other words, by normalizing we separate the first k_{1} roots into smaller groups. By repeated normalization we will finally separate r_{1}^{n} from all other r_{i}^{n}’s. Now we start with the deepest level of normalization and work up, proving a density lower bound for each level.

Let the deepest level be ℓ, and let

h_{n}(r_{i}^{n}) → t_{i} for 1 ≤ i ≤ k_{ℓ}

where h_{n} is the normalization of r_{1}^{n},…, r_{k_{ℓ}}^{n} centered at r_{1}^{n}. We have

∑_{i<j} |t_{i} − t_{j}| = 1,

t_{1} = 0, and t_{i} ≠ t_{1} if i > 1. Consider

f̃(z) = (z − t_{1})^{e_{1}} … (z − t_{k_{ℓ}})^{e_{k_{ℓ}}}.

Since Tf̃(t_{1}) = t_{1}, |T ′ ; f̃(t_{1})| < 1, and ∞ is a repelling fixed point for Tf̃ we have open sets E, arbitrarily near ∞, such that T n ; f̃{E} → t_{1} as n → ∞. Take a point z large enough so that lemma 2.2 holds, with B_{ϵ}(z) converging to t_{1} uniformly under Tf̃ for some ϵ > 0 (we can assure uniform convergence by assumption (3) of section 1). We have

B_{ϵq_{ℓ}^{m}/2}(z̃q_{ℓ}^{m}) ⊂ Γ_{T,f̃}

for m sufficiently large where z̃ is as in lemma 2.2 and

q_{ℓ} = q (∑_{i=1}^{k_{ℓ}} e_{i}) .

Let h′_{n} be the normalization of the ℓ−1-th level, i.e. of r_{1}^{n},…, r_{k_{ℓ−1}}^{n} centered at r_{1}^{n},

h′_{n}(z) = a′_{n}z + b′_{n}

and let

h_{n}(z) = a_{n}z + b_{n}.

We have that

\frac{a_{n}}{a′_{n}} q_{ℓ}^{⌊− log_{q_{ℓ}}(a_{n}/a′_{n})⌋} → a

as n → ∞ for some a ∈ [\frac{1}{q_{ℓ}} , 1] (at each level we normalize and pass to a subsequence satisfying a condition analogous to that of equation 3.1 as well as the preceeding condition). We want to prove that

B_{ϵ_{0}}(z_{0}) ⊂ Γ_{T,h′_{n}f_{n}}  (3.2)

for all sufficiently large n, where

z_{0} = z̃aq_{ℓ}^{−M}
ϵ_{0} = ϵaq_{ℓ}^{−M}/4

for some positive integer M; this will complete the first stage moving backwards through the normalizations, each time finding a ball of fixed size with respect to the current normalization in Γ_{T,f_{n}} for sufficiently large n. To prove equation 3.2, consider first

h_{n}f_{n}(z) = (z − h_{n}(r_{1}^{n}))^{e_{1}} … (z − h_{n}(r_{k_{ℓ}}^{n}))^{e_{k_{ℓ}}}.

We claim that for n sufficiently large we have

B_{ϵ}(z) ⊂ Γ_{T,h_{n}f_{n}}.

To see this, we note that for some small η > 0 we have

|z − t_{1}| ≤ η ⟹ |Tf̃(z) − t_{1}| ≤ (1 − μ)|z − t_{1}|,

by assumption (3) of section 1, for some μ > 0, and that for some large N,

T N ; f̃ {B_{ϵ}(z)} ⊂ B_{η/2}(t_{1})

by the uniform covnergence. Estimating as in lemma 2.2 (note that for any δ we have h_{n}f_{n} ∈ F_{f̃,δ,D} for n sufficiently large and D = d − q_{ℓ}) we get that for n sufficiently large

|z − t_{1}| ≤ η ⟹ |T_{h_{n}f_{n}}(z) − t_{1}| ≤ (1 − μ/2)|z − t_{1}|
⟹ z ∈ Γ_{T,h_{n}f_{n}}

and that

T_{h_{n}f_{n}}^{N} {B_{ϵ}(z)} ⊂ B_{η}(t_{1}) ⊂ Γ_{T,h_{n}f_{n}}

using h_{n}(r_{1}^{n}) = t_{1} and that for any y ∈ B_{ϵ}(z) we have y, Tf̃(y), T 2 ; f̃(y),… stays away from the r_{i}^{n}’s with i > 1. Now we apply lemma 2.2 to conclude that for m sufficiently large we have

T_{h_{n}f_{n}}^{m} {B_{ϵq_{ℓ}^{m}/2}(z̃q_{ℓ}^{m})} ⊂ B_{ϵ}(z) ⊂ Γ_{T,h_{n}f_{n}}

so that

B_{ϵq_{ℓ}^{m}/2}(z̃q_{ℓ}^{m}) ⊂ Γ_{T,h_{n}f_{n}}

as long as |z̃|q_{ℓ}^{m} < c/δ for some c sufficiently small, where 1/δ is a lower bound on h_{n}(r_{i}^{n}) for i > k_{ℓ}. Rescaling by a factor of a_{n}/a′_{n} and translating appropriately we get

B_{ϵq_{ℓ}^{m}a_{n}/(2a′_{n})}(z̃q_{ℓ}^{m}a_{n}/a′_{n}) ⊂ Γ_{T,h′_{n}f_{n}}

if

|z̃|q_{ℓ}^{m}a_{n}/a′_{n} < c min_{i>k_{ℓ}} h′_{n}(r_{i}^{n}) < c′.  (3.3)

Taking

m(n) = ⌊log_{q_{ℓ}} \frac{a′_{n}}{a_{n}} ⌋ − M

where M is sufficiently large to ensure equation 3.3 holds, we get that for sufficiently large n,

B_{ϵaq_{ℓ}^{−M} /4}(z̃aq_{ℓ}^{−M}) ⊂ Γ_{T,h′_{n}f},

the 4 in ϵaq_{ℓ}^{−M}/4 appearing to account for the fact that

\frac{a_{n}}{a′_{n}} q_{ℓ}^{m(n)}

approaches, rather that equals, aq_{ℓ}^{−M} as n → ∞. Thus equation 3.2 is established.

Now that we have a statement of the form

B_{ϵ_{0}}(z_{0}) ⊂ Γ_{T,h′_{n}f_{n}},

we proceed to get a statement of the form

B_{ϵ_{1}}(z_{1}) ⊂ Γ_{T,h′′_{n}f_{n}},

where h′′_{n} is the normalization at the ℓ − 2-th level, i.e. the normalization of r_{1}^{n},…, r_{k_{ℓ−2}}^{n} centered at z_{1}^{n}. To do this we consider

f̂(z) = (z − t_{1})^{e_{1}} … (z − t_{k_{ℓ−1}})^{e_{k_{ℓ−1}}}.

Using lemma 2.1 we can find an arbitrarily large z with an ϵ so that for some N

T N ; f̂ {B_{ϵ/2}(z)} ⊂ B_{ϵ_{0}}(z_{0}).

Now we repeat the argument of before to conclude

T_{h′_{n}f_{n}}^{N} {B_{ϵ}(z)} ⊂ B_{ϵ_{0}}(z_{0})

i.e.

B_{ϵ}(z) ⊂ Γ_{T,h′_{n}f_{n}}

(with uniform convergence) for n sufficiently large, and that

T_{h′′_{n}f_{n}}^{m′(n)} {B_{ϵ_{1}}(z_{1})} ⊂ Γ_{T,h′′_{n}f_{n}}

(again with uniform convergence) for some m′(n) and fixed ϵ_{1}, z_{1}.

Repeating the above argument ℓ − 2 more times yields that for all n sufficiently large we have

B_{ϵ}(z) ⊂ Γ_{T,f_{n}}

for some fixed ϵ and z with z very near r_{1}^{n}. Hence

lim_{n→∞} A_{T,f_{n},r_{1}^{n}} > πϵ^{2} > 0

and theorem 1.1 is proven.

References

[Atk78] K. Atkinson. An Introduction to Numerical Analysis. Wiley, New York, 1978.

[Fri86] Joel Friedman. On the convergence of newton’s method. In 27th Annual Symposium on Foundations of Computer Science, pages 153–161, 1986.

[Sma85] Steve Smale. On the efficiency of algorithms of analysis. Bull. of the AMS, 13(2):87–121, Oct. 1985.