# On the Distance to a Root of Polynomials

Authors: Somjate Chaiya
Journal: Abstract and Applied Analysis
 (2011)

---

## Abstract

In 2002, Dierk Schleicher gave an explicit estimate of an upper bound for the number of iterations of Newton's method it takes to find all roots of polynomials with prescribed precision. In this paper, we provide a method to improve the upper bound given by D. Schleicher. We give here an iterative method for finding an upper bound for the distance between a fixed pointz in an immediate basin of a root α to α, which leads to a better upper bound for the number of iterations of Newton's method.


---

## Body

## 1. Introduction

LetP be a polynomial of degree d, and let Np(z)=z-P(z)/P′(z) be the Newton map induced by P. Let ℕ be the set of positive integers. For each k∈ℕ, let Npk denote the k-iterate of Np, that is, Np1=Np,Np2=Np∘Np, and Npk=Npk-1∘Np. For a root α of P, we say that a set U is the immediate basin of α if U is the largest connected open set containing α and Npk(z)→α, as k→∞, for all z∈U. Every immediate basin U is forward invariant, that is, Np(U)=U, and is simply connected (see [1, 2]). In 2002, Schleicher [3] provided an upper bound for the number of iterations of Newton's method for complex polynomials of fixed degree with a prescribed precision. More precisely, Schleicher proved that if all roots of P are inside the unit disc and 0<ɛ<1, there is a constant n(d,ɛ) such that for every root α of P, there is a point z with |z|=2 such that |Npn(z)-α|<ɛ for all n≥n(d,ɛ). Schleicher also showed that n(d,ɛ) can be chosen so that(1.1)n(d,ɛ)≤9πd4fd2ɛ2log⁡2+|log⁡ɛ|+log⁡13log⁡2+1
with(1.2)fd:=d2(d-1)2(2d-1)(2dd).To obtain this estimate, Schleicher employed several rough estimates which cause the bound far from an efficient upper bound. The main point that causes the extremely inefficiency is the way Schleicher used to obtainfd which arose when he estimated an upper bound for the distance of a point z to a root α. Schleicher showed that if z is in the immediate basin of α and |Np(z)-z|=δ, then the distance between z and α is at most δfd.In this paper, we give an algorithm to improve the value offd. Even though, it is not an explicit formula, it can be easily computed. The following is our main result.Main Theorem 1.
LetP(z) be a polynomial of degree d≥3,and let y be a positive number larger than 4d-3. If z0 is in an immediate basin of a root α and |Np(z0)-z0|=ɛ, then |z0-α|≤ɛM(d,y), where M(d,y):=max{y,Ad+y(d-1)/(y-1)} and Ad can be derived from the following iterative algorithm.
Letb=y(y-d)/(y-1), and(1.3)A2=y(d-1)[2d(y-2d+3)-3y-1](y-1)(y-4d+3).
For k=2,…,d-1, set ak=1+∑j=2k-1(Ak/(Ak-Aj)).
If2Ak<b then let(1.4)Ak+1=Ak((ak+d-k)Ak+b(k+1-ak-d)Ak(ak+1)-bak).
Otherwise let
(1.5)Ak+1=Akak+d-kak.Note that the value ofM(d,y) in the main theorem depends only on the constant y and the degree d. Hence if we select y appropriately the value M(d,y) will be optimized under this method. However this estimate is still far away from the best possible one. We believe that this new upper bound M(d,y) is less than fd/2d/2 for all d≥10 when y=d1.52(4d/3)-2. We will discuss further about this matter in Section 4.


## 2. Preliminary Results

We will useB(a,r) for the open ball {z∈ℂ:|z-a|<r} and B¯(a,r) for the closed ball {z∈ℂ:|z-a|≤r}, where ℂ is the set of complex numbers. If S is a subset of ℂ, we denote the boundary of S by ∂S.Lemma 2.1.
LetP be a polynomial. Let β be a complex number and r>0. Suppose that Re{(z-β)P′(z)/P(z)}≥1/2 whenever |z-β|=r and P(z)≠0. Let U be an immediate basin of a root α of P. If U∩B¯(β,r)≠∅, then α is in B(β,r).Proof.
For|z-β|=r with P(z)≠0, we have
(2.1)Np(z)-β=(z-β)(1-1g(z)),
where g(z)=(z-β)P′(z)/P(z). Hence, |Np(z)-β|≤|z-β| if and only if |(g(z)-1)/g(z)|≤1 which holds if Re{g(z)}≥1/2. It means that if z is a point in ∂B(β,r) and Re{g(z)}≥1/2, then the distance of Np(z) to β is at most the distance of z to β. In other words, the image of z under the map Np also lies inside B¯(β,r).
Letα be a root of P and U be its immediate basin. Suppose that α∉B¯(β,r) and z∈U∩B¯(β,r). Since U is forward invariant under Np, Np(z) still stays in U. Since U is connected, there is a curve γ0 connecting z to Np(z) and lying entirely in U. Since Npk(γ0) converges uniformly to α as k→∞, the set ⋃k=1∞Npk(γ0)∪{α} forms a continuous curve γ joining z and α. Note that γ is contained in U because Npk(γ0) lies inside U for all k∈ℕ.
Letw be the last intersection point of γ with ∂B(β,r) (i.e., the part of the curve γ that connects w to α stays outside B¯(β,r) except at w). So Np must send w to a point outside B¯(β,r), otherwise β is a fixed point of Np, which is impossible because all fixed points of Np are only the roots of P, and here P(z)≠0 on |z-β|=r. From the first paragraph, however, we also have Np(w)∈B¯(β,r). Hence we get a contradiction. Therefore if U∩B¯(β,r) is not empty, then α is in B(β,r), as desired.Remark that, from the proof of Lemma2.1, if β is a root of P and Re{(z-β)P′(z)/P(z)}≥1/2 for all |z-β|≤r, then the closed ball B¯(β,r) is contained in the immediate basin of β.Lemma 2.2.
LetP be a polynomial of degree d≥3. Let α1 be a root of P and α2 the nearest root to α1. Let β=|α1-α2|, and let m be the multiplicity of α1. Suppose that there is a root α of P such that |α1-α|≥b for some positive number b≥β. Then the closed ball {z∈ℂ:|z-α1|≤δ} is contained entirely in the immediate basin of α1, where
(2.2)δ=12(2d-1)[(2m+1)β+(2d-3)b-[(2m+1)β+b(2d-3)]2-4(2d-1)(2m-1)bβ[(2m+1)β+b(2d-3)]2-4(2d-1)(2m-1)bβ].Proof.
Without loss of generality, we assume thatα1=0. From the previous remark, it suffices to show that Re{zP′(z)/P(z)}≥1/2 for all |z|≤δ. Let P(z)=zm∏k=2d-m(z-αk). We have
(2.3)zP′(z)P(z)=m+∑k=2d-mzz-αk.
Hence
(2.4)Re{zP′(z)P(z)}=m+∑k=2d-mRe{zz-αk}≥m+r(d-m-1)r-β+rr-b,
where r=|z|. Note that β≤b. For r<β, we have
(2.5)m+r(d-m-1)r-β+rr-b≥12,
if r≤δ. This shows that Re{zP′(z)/P(z)}≥1/2 for all |z|≤δ, as needed.Note that if we setb=β in Lemma 2.2, then the closed ball centered at α1 of radius β(2m-1)/(2d-1) is contained in the immediate basin of α1. Furthermore, if m=1, the radius of the ball is β/(2d-1). (Schleicher [3, Lemma 4, page 938] made a small mistake about the radius of the ball. Indeed, he should get β/(2d-1) instead of β/2(d-1)).Lemma 2.3.
LetP be a polynomial of degree d. For any complex number z and any positive number y>1, if |Np(z)-z|=ɛ and there is a root αd of P with |z-αd|≥yɛ, then there is a root α of P such that |z-α|≤y(d-1)ɛ/(y-1).Proof.
Letα1,α2,…,αd be all roots of P. Suppose that |z-αd|≥yɛ. If |z-αj|>y(d-1)ɛ/y-1 for 1≤j≤d-1, then
(2.6)|Np(z)-z|≥(∑j=1d1|z-αj|)-1>(y-1y(d-1)ɛ(d-1)+1yɛ)-1=ɛ,
a contradiction.We are now ready to prove our main theorem.


## 3. Proof of Main Theorem

Letα1,α2,…,αd be all roots of P such that α1 is the nearest root to z0 and |α1-αk|≤|α1-αk+1| for k=2,…,d-1. Suppose that |z0-αd|≥yɛ. By Lemma 2.3, we have |z0-α1|≤y(d-1)ɛ/(y-1). Note that |α1-αd|≥bɛ. If α=α1, we are done. Otherwise, z is not in the immediate basin of α1; thus by Lemma 2.2 with m=1, we get that |z0-α1|>δ, where δ is defined in Lemma 2.2, that is,(3.1)δ=3r2+bɛ(2d-3)-[3r2+bɛ(2d-3)]2-4(2d-1)bɛr22(2d-1),
where r2=|α1-α2|. Thus z0 satisfies the inequalities(3.2)δ<|z0-α1|≤y(d-1)ɛy-1,
which holds if |α1-α2|<A2ɛ. If α=α2, we are done. Suppose next that α≠α2.Now let|α1-αk|=ɛrk. If |z-α1|=A2ɛ and r3>A3, then (3.3)Re{(z-α1)P′(z)P(z)}≥1+A2A2+r2+A2(d-3)A2-r3+A2A2-rd>1+12+A2(d-3)A2-r3+A2A2-b>12.
hence by Lemma 2.1 α must be either α1 or α2 which is not the case. Therefore r3≤A3, and if α is α3 we are done. Otherwise, let |z-α1|=A3ɛ and suppose r4>A4; then Re{(z-α1)P′(z)/P(z)}>1/2, and by Lemma 2.1 we get a contradiction. Thus we obtain r4≤A4, and if α is α4 we are done. Continuing this process, finally we get rd≤Ad which gives |z0-αd|≤ɛ(Ad+y(d-1)/(y-1)).Note that ifAd<b, it is a contradiction to the fact that ɛrd=|α1-αd|≥bɛ, which implies that assumption |z0-αd|≥yɛ is false. Hence in this case we have |z0-αd|<yɛ. The proof is now complete.


## 4. Discussion

For a fixedd, M(d,y) depends on only y. If we choose y too large (for instance, y≥fd), the value of M(d,y) is useless when it is compared to fd. So we have to choose y carefully so that M(d,y) is minimal as possible. We do not know yet whether there is an explicit formula for the value y that minimizes M(d,y). Table 1 below shows the values of M(d,y) where we set y=d1.524d/3-2. It seems that this method can reduce upper bounds for the distance of z0 to the root it converges to at least 2d/2 times compared to fd. If we replace fd in (1.1) by M(d,y), we derive a new upper bound for the number of iterations.Table 1
Examples of values ofM(d,y) compared to fd when y=d1.524d/3-2.
d=M(d,y) is less thanfd is greater thanfd/2d/2M(d,y) is greater than101.3385×1054.3758×1061.0216201.0131×10101.343×10131.2946304.4559×10142.6158×10191.7915401.5878×10194.2458×10252.5502505.0059×10236.2420×10313.7162601.1486×10288.6222×10375.4054704.2054×10321.1410×10447.8967801.1429×10371.4634×105011.6467903.0424×10411.8327×105617.12121007.9376×10452.2523×106225.20271102.0274×10502.7262×106837.32441205.1302×10543.2588×107455.09781301.2839×10593.8546×108081.37921403.1697×10634.5186×1086120.75111507.7889×10675.2563×1092178.63151601.8954×10726.0735×1098265.06351704.5932×10766.9764×10104392.61751801.1074×10817.9718×10110581.54691902.6450×10859.0669×10116863.72822006.3268×10891.0269×101231280.4536



---

*Source: 495312-2011-10-27.xml*