# The Convergence of a Class of Parallel Newton-Type Iterative Methods

Authors: Qinglong Huang
Journal: Advances in Numerical Analysis
 (2017)

---

## Abstract

A general iterative process is proposed, from which a class of parallel Newton-type iterative methods can be derived. A unified convergence theorem for the general iterative process is established. The convergence of these Newton-type iterative methods is obtained from the unified convergence theorem. The results of efficiency analyses and numerical example are satisfactory.


---

## Body

## 1. Introduction

Attempts to improve Newton method are the subject of many papers [1–10].Consider the following polynomial of degreen:(1)fx=∏i=1nx-ri,with simple zeros r1,r2,…,rn.In paper [1], a parallel iterative method for simultaneously finding all zeros of f(x) was suggested; that is, (2)xik+1=xik+αik1+αik∑j=1j≠in1/xik-xjk,(3)αik=-fxikf′xik,where i=1,2,…,n; k=0,1,2,….x
i
0  (i=1,2,…,n) are distinct initial approximations for zeros ri  (i=1,2,…,n) of polynomial f(x).For appropriate starting valuesxi(0), method (2) is of convergence order three.Suppose thatφ(x) is some iteration function and xjk+1=φ(xjk) converges to zeros rj  (j=1,2,…,n) of f(x) with convergence order m.From (2), we obtain the following parallel iterative process:(4)xik+1=xik+αik1+αik∑j=1j≠in1/xik-ujk,(5)ujk=φxjk,where i,j=1,2,…,n; k=0,1,2,….  αik is defined by (3). We call φ(x) correction iterative function.In particular, ifujk=φ(xjk)=xjk, then (4) is process (2) derived in paper [1]. If Newton iterative function is chosen as φ, that is, ujk=φ(xjk)=xjk+αj(k) and αjk are defined by (3), then (4) is the method discussed in paper [3]. Because (2) is a modification of Newton method and (4) is an improvement to (2), so we call (4) modified Newton-type iteration method.In this paper, a unified convergence theorem for the general modified process (4) is established in Section 2 (Theorem 2).Moreover, in Section3, three special iterative methods are derived from process (4) according to the choices of φ. These special methods are all modifications to process (2); their convergence and convergence order are obtained via the unified general convergence Theorem 2.All these special modified methods are convergent with higher order and are more efficient than both Newton method and process (2).In Section4, the method is extended to find the multiple zeros of polynomial.Finally, in Section5, we give several numerical examples and the computation results are satisfactory.


## 2. General Convergence Theorem

In this section, we discuss the convergence of the general modified process (4).Letk=0,1,2,…, be the indices of iterations and (6)d=min1≤i<j≤nri-rj,(7)hik=xik-ri,(8)hk=max1≤i≤nhik.By some simple calculation, process (4) can also be expressed as follows:(9)hik+1=Aik1+Aikhik,where hik are defined by (7) and(10)Aik=∑j=1j≠inxik-rirj-ujkxik-rjxik-ujk.Assume that the correction iteration function φ in (5) is locally convergent with convergence order m(m≥1) for each root rj of f(x); that is, xjk+1=φ(xjk) converges to root rj with convergence order m for sufficiently good starting values xj(0)  (j=1,2,…,n). Then we have the following Lemma 1.Lemma 1.
Letujk be defined by (5); then there exist constants c and δ (independent of j and k) such that(11)ujk-rj≤cxjk-rjmifxj0-rj≤δ,where j=1,2,…,n;  k=0,1,2,….In fact, becausexjk+1=φ(xjk) converges to root rj with convergence order m for sufficiently good starting values xj(0)  (j=1,2,…,n), for every j, there exist cj, δj, such that (12)ujk-rj≤cjxjk-rjmifxj0-rj≤δj.Let(13)δ=min⁡δ1,δ2,…,δn,c=max⁡c1,c2,…,cn,and then Lemma 1 holds.In the following Theorem2 and its proof, the constants c and δ are defined in Lemma 1 and n is the degree of f(x).Theorem 2.
Suppose that initial approximationsxj0  j=1,2,…,n satisfy |xj0-rj|<min⁡δ,c-1/(m-1),2d/(3+8n-7). Then the iterative process (4) converges to the zeros ri  i=1,2,…,n of f(x), and the convergence order is m+2.Proof.
Suppose thatxj0  j=1,2,…,n satisfy the condition in Theorem 2.
Then there exists a positive constants>max⁡{d/δ,c1/(m-1)d,(3+8n-7)/2} such that (14)xj0-rj≤dsj=1,2,…,n.Hence from Lemma 1 we know that, for k=0 and i≠j,(15)rj-uj0≤cxj0-rjm≤ds,xi0-rj≥ri-rj-xi0-ri≥s-1ds,uj0-xi0≥ri-rj-uj0-rj-xi0-ri≥s-2ds.By (10), it follows that (16)Ai0≤∑j=1j≠inchi0·hj0ms2s-1s-2d2≤n-1s-1s-2<12.Let(17)λ=n-1s-1s-2,μ=λ1-λ.It is evident that μ<1.
Thus, from (9), we obtain that, for all i, (18)hi1≤Ai01-Ai0hi0≤μhi0≤ds.Generally, if |xjk-rj|≤d/s  (j=1,2,…,n), then we can obtain analogously that(19)Aik=∑j=1j≠incs2hik·hjkms-1s-2d2≤λ<12,(20)hik+1≤μhik≤ds.By mathematical induction, we know that (19) and (20) are valid for i=1,2,…,n;  k=0,1,2,….
From (20), we have(21)hik≤μkhi0≤dsμk,fori=1,2,…,n;k=0,1,2,….It is evident that hik→0 (k→∞). That is, xik→ri  (k→∞) for i=1,2,…,n.
Making use of (8) and (19), we have(22)Aik≤cn-1s2s-1s-2d2hkm+1≤λcs2d2hkm+1.Further, by (9) and |Aik|<1/2, we have(23)hik+1≤2λcs2d2hkm+2.Hence, the convergence order of method (4) with (5) is m+2.


## 3. Some Special Modified Newton Methods Derived from Formula (4)

For the correction functionφ in (5), we will make several kinds of choice and derive some special modified Newton methods from (4). Furthermore, by the convergence Theorem 2, we give the convergence and efficiency of these special modified methods.Definition 3.
For an iteration method, we define the efficiency(24)e=log⁡kw,where k is the convergence order; w is the amount of computation required in every step of iteration.Sincef(x),f′(x),f′′(x) are all polynomials, computational efficiency requires that the evaluation of these functions be done by Horner’s method [8]. Then only n multiplications and n additions will be required to evaluate an arbitrary polynomial of degree n. Since f(x) defined by (1) is a polynomial of degree n, we take n multiplications or divisions as a unit of the amount of computation and take no count of additions in the following. As a consequence, the evaluation of f(xik),f′(xik),f′′(xi(k)) and ∑j=1j≠in1/xi(k)-xj(k) require approximately one unit, respectively. Now the convergence and efficiency analyses of these special modified methods can be given as follows.(i) Newton iterative function is chosen asφ; that is,(25)ujk=φxjk=xjk+αjk.We obtain the iterative method (4) with (25) which has been considered in [3].Because Newton iterative function is second-order convergent (m=2), the convergence and convergence order of method (4) with (25) can be concluded from Theorem 2 directly.Corollary 4.
Suppose that initial approximationsxj0  j=1,2,…,n satisfy |xj0-rj|<min⁡{δ,c-1,2d/(3+8n-7)}. Then the iterative process (4) with (25) converges to the zeros ri  (i=1,2,…,n) of f(x), and the convergence order is 4; the efficiency e1=log⁡4/3.(ii) Letφ be the Halley iterative function; that is,(26)ujk=φxjk=xjk+αjk1+1/2f′′xjk/f′xjkαjk.Halley iterative function is of convergence order 3; therefore we have the following conclusion from Theorem 2.Corollary 5.
Suppose that initial approximationsxj0  j=1,2,…,n satisfy |xj0-rj|<min⁡{δ,c-1/2,2d/(3+8n-7)}. Then the iterative process (4) with (26) converges to the zeros ri  (i=1,2,…,n) of f(x), and the convergence order is 5; the efficiency e2=log⁡5/4.(iii) Let(27)ujk=xjk+αjk1+αjk∑l=1l≠jn1/xjk-vlk,where vl(k)=xl(k)+αl(k).From Corollary4, we know (27) is 4th-order convergent, so we obtain the following conclusion from Theorem 2.Corollary 6.
Suppose that initial approximationsxj0  j=1,2,…,n satisfy |xj0-rj|<min⁡{δ,c-1/3,2d/(3+8n-7)}. Then the iterative process (4) with (27) converges to the zeros ri  (i=1,2,…,n) of f(x), and the convergence order is 6; the efficiency e3=log⁡6/4.In particular, if we letφ(xj(k))=xj(k), then (4) is the modified Newton method (2) (see [1]). The convergence of (2) was not proven in [1], but now its convergence follows directly from Theorem 2, and the convergence order is 3; therefore the efficiency e4=log⁡3/3.By the way, according to our definition, the computational efficiency of Newton iterative method islog⁡2/2.For simultaneously finding polynomial zeros, it is evident that these modified Newton-type methods discussed in Corollaries4–6 are convergent with higher order and are more efficient than both Newton method and process (2).


## 4. Extending the Iterative Method (4) to Find Multiple Zeros

In complex number field polynomialfx of degree n can be factored as(28)fx=x-r1μ1x-r2μ2⋯x-rmμm;r1,r2,…,rm are multiple zeros of polynomial fx.Hereri≠rj  (i≠j) and ∑i=1mμi=n.By logarithmic derivation, we know that(29)f′xfx=∑j=1mμjx-rj,ri=x-μifx/f′x1-fx/f′x∑j=1j≠imμj/x-rj,i=1,2,…,m.So we get the iterative method for simultaneously finding all zeros of f(x).(30)xik+1=xik-μifxik/f′xik1-fxik/f′xik∑j=1j≠imμj/xik-xjk,where i=1,2,…,m;  k=0,1,2,….  xi0  (i=1,2,…,m) were distinct initial approximations for zeros ri  (i=1,2,…,m) of f(x).Whenμi=1 for all i=1,2,…,m, the iterative method (30) shall be the iterative method (2) in Section 1.Using the same technique as in formula (4), we obtain(31)xik+1=xik-μifxik/f′xik1-fxik/f′xik∑j=1j≠imμj/xik-ujk.Here,(32)ujk=φjx1k,x2k,…,xmk.For appropriate starting values xi(0), we suppose that xjk+1=φj(x1(k),x2(k),…,xmk) converges to zeros rj  (j=1,2,…,m) of f(x) with convergence order p.By some simple calculation, formula (31) can be expressed as follows:(33)hik+1=Bik1+Bikhik,where(34)hik=xik-ri,i=1,2,…,m,k=0,1,2,…,Bik=1μi∑j=1j≠imμjxik-rirj-ujkxik-rjxik-ujk,d=min1≤i<j≤mri-rj,μ=min1≤i≤mμi.Lemma 7.
Letujk be defined by (32); then there exist constants c and δ (independent of j and k), such that (35)ujk-rj≤cxjk-rjpifxj0-rj≤δ.The proof is similar to Lemma1.In the following Theorem8 and its proof, the constants c and δ are defined in Lemma 7 and n is the degree of f(x).Take the constantθ>max⁡4,n/μ,d/δ and θp-1≥cdp-1; we have the following Theorem 8.Theorem 8.
Suppose that initial approximationsxj0j=1,2,…,m satisfy xj0-rj≤d/θ(j=1,2,…,m), and xjk+1=φj(x1(k),x2(k),…,xmk) converges to zeros rj with convergence order p. Then the iterative process (31) with (32) converges to zeros ri  i=1,2,…,m with convergence order p+2.Proof.
Suppose thatxj0  j=1,2,…,m satisfy the condition in Theorem 8. Then (36)xi0-rj≥θ-1θd,uj0-rj≤cxj0-rjp≤cdθp≤dθ.Therefore(37)xi0-uj0≥ri-rj-uj0-rj-xi0-ri≥θ-2θd.Further,(38)Bi0≤1μi∑j=1j≠imcμjθ2hi0·hj0pθ-1θ-2d2.Note that θ>max⁡4,n/μ,d/δ and θp-1≥cdp-1; we have(39)Bi0≤1θ-2<12.Let(40)q=1θ-3<1.Then(41)hi1≤Bi0hi01-Bi0≤qhi0≤dθi=1,2,…,m.Generally, we can obtain analogously that(42)Bik≤1μi∑j=1j≠imcθ2μjhik·hjkpθ-1θ-2d2≤1θ-2<12,(43)hik+1≤qhik≤dθ.By mathematical induction, we know that (43) is valid for i=1,2,…,m;  k=0,1,2,….
From (43), we get |hik|≤qk(d/θ)→0 (when k→∞).
Leth(k)=max1≤j≤m⁡{|hj(k)|}, and from (42) it is inferred that(44)Bik≤cθ2μiθ-1θ-2d2∑j=1j≠imμj·hkp+1≤cθ22d2hkp+1.Because Bi(k)<1/2, hi(k+1)≤2Bi(k)·hi(k)≤cθ2/d2·h(k)p+2.
Hence, the convergence order of method (31) is p+2. The proof is completed.Let(45)ujk=xjk-μjfxjkf′xjk.Combine (31) and (45); we have the following Corollary 9.Corollary 9.
Suppose that initial approximationsxj0  j=1,2,…,m satisfy |xj0-rj|<min⁡{1/4,μ/n}d  (j=1,2,…,m). Then the iterative process (31) with (45) converges to the zeros ri  (i=1,2,…,m)of f(x), and the convergence order is 4.


## 5. Numerical Example

In this section, we will report on three numerical examples. The computations were performed on Lenovo computer using MATLAB.Example 1.
As in [5], we consider complex polynomial of degree 10 (i=-1):(46)fx=x10-201+ix9+400ix8+3×104x6-6×1051+ix5+12×106ix4-4×108x2+8×1091+ix-16×1010i.We want to find the zeros of f(x) by method (4) with (25).
The zeros off(x) are r1,2=±10,r3,4=±10i,r5,6=10±10i,r7,8=-10∓10i,r9=20,r10=20i.
In our computation, we take errorε=10-12 (in paper [5], error ε=10-6) and choose the starting values just as paper [5]; that is,(47)x1,20=±10.1+0.1i,x3,40=±0.1+10.1i,x5,60=10.11±i,x7,80=-10.11±i,x90=19.9+0.1i,x100=0.1+19.9i.The numerical results of method (4) with (25) are listed as follows.
Numerical Results of Example1
(48)
x
1
1
=
9.999998471976
+
0.000002471890
i
,
x
2
1
=
-
10.000000671094
-
0.000002530585
i
,
x
3
1
=
0.000002471890
+
9.999998471976
i
,
x
4
1
=
-
0.000002530585
-
10.000000671094
i
,
x
5
1
=
9.999999158562
+
9.999999158562
i
,
x
6
1
=
10.000001503999
-
10.000002165629
i
,
x
7
1
=
-
9.999999683089
-
9.999999683089
i
,
x
8
1
=
-
10.000002165629
+
10.000001503999
i
,
x
9
1
=
19.999999580699
-
0.000001353811
i
,
x
10
1
=
-
0.000001353811
+
19.999999580699
i
,
x
1
2
=
10.000000000000
-
0.000000000000
i
,
x
2
2
=
-
10.000000000000
-
0.000000000000
i
,
x
3
2
=
-
0.000000000000
+
10.000000000000
i
,
x
4
2
=
-
0.000000000000
-
10.000000000000
i
,
x
5
2
=
10.000000000000
+
10.000000000000
i
,
x
6
2
=
10.000000000000
-
10.000000000000
i
,
x
7
2
=
-
10.000000000000
-
10.000000000000
i
,
x
8
2
=
-
10.000000000000
+
10.000000000000
i
,
x
9
2
=
20.000000000000
-
0.000000000000
i
,
x
10
2
=
-
0.000000000000
+
20.000000000000
i
.We see from (48) that, for method (4) with (25), after two iterations the numerical results attain the precision.Example 2.
Given a polynomial(49)fx=32x3-56x2+24x-3,f(x)=0 is the so-called Rayleighequation in theory of earthquake.
The exact roots of the equation or the zeros off(x) are x1=1/4,x2=(3-3)/4,x3=(3+3)/4.
We want to find the zeros off(x) by Newton method, process (2), and the three modified methods discussed in Corollaries 4–6. We choose starting values x1(0)=0,x2(0)=0.5,x3(0)=1, and we take error ε=10-12.
The numerical results of process (2), method (4) with (25), method (4) with (26), and method (4) with (27) are listed in Table 1, but for Newton method we only give the final numerical results.
From Table1, we see that, for Newton method, after eight iterations, the iteration approximations attain the precision; for method (2) with (3), after five iterations, the iteration approximations attain the precision; for method in Corollary 4, after four step iterations, the iteration approximations attain the precision; for methods in Corollary 5 and in Corollary 6, after three iterations, all the iteration approximations attain the precision. Hence, these modified Newton-type methods converge faster than both Newton method and iterative method (2).Table 1
Numerical results of Example2.
Iterative method
Number of iterations
Results
x
1
k
x
2
k
x
3
k
Method (2)
1
0.200000000000
0.375000000000
1.176470588235
2
0.243808087597
0.323805689748
1.183011463275
3
0.249955665119
0.317035707337
1.183012701892
4
0.249999999979
0.316987298131
1.183012701892
5
0.250000000000
0.316987298108
1.183012701892
Method (4) with (25)
1
0.217105263158
0.345588235294
1.184859154930
2
0.249398039932
0.317688644132
1.183012708464
3
0.249999999474
0.316987298719
1.183012701892
4
0.250000000000
0.316987298108
1.183012701892
Method (4) with (26)
1
0.231729055258
0.346042471043
1.183941605839
2
0.249920728625
0.317052319337
1.183012700566
3
0.250000000000
0.316987298108
1.183012701892
Method (4) with (27)
1
0.234609565063
0.331231334248
1.182746284452
2
0.249997316046
0.316989331975
1.183012701890
3
0.250000000000
0.316987298108
1.183012701892
Newton method
8
0.250000000000
0.316987298108
1.183012701892Example 3.
We consider polynomialf(x)=x7+x6+x5+17x4-x3+31x2-x+15. We want to find the zeros of f(x) by iterative process (31) with (45). The exact zeros of f(x) are r1=-3,r2,3=±i,r4,5=1±2i; the corresponding multiplicities are μ1=1,μ2=2,μ3=2,μ4=1,μ5=1. We choose starting values x1(0)=-2.5+0.5i,x2(0)=0.5+1.5i,x3(0)=0.5-1.5i,x4(0)=1.5+2.5i, and x5(0)=1.5-2.5i, and we take error ε=10-14. The numerical results of the first three iterations by iterative process (31) with (45) are listed as follows.
Numerical Results of Example3
(50)
x
1
1
=
-
3.00565194346854
-
0.01318777497764
i
,
x
2
1
=
-
0.15410479694978
+
0.89034788387744
i
,
x
3
1
=
-
0.15107817440832
-
0.88441680259590
i
,
x
4
1
=
0.96243366036343
+
2.03642298912267
i
,
x
5
1
=
0.96330847662789
-
2.03255647412651
i
,
x
1
2
=
-
2.99999982955636
-
0.00000016455696
i
,
x
2
2
=
-
0.00000190344179
+
1.00020769732097
i
,
x
3
2
=
-
0.00003765337762
-
1.00020338825104
i
,
x
4
2
=
1.00004824175549
+
1.99995917074785
i
,
x
5
2
=
1.00004838408085
-
1.99997115571258
i
,
x
1
3
=
-
3.00000000000000
+
0.00000000000000
i
,
x
2
3
=
-
0.00000000000002
+
1.00000000000016
i
,
x
3
3
=
0.00000000000002
-
1.00000000000004
i
,
x
4
3
=
1.00000000000000
+
2.00000000000000
i
,
x
5
3
=
1.00000000000000
-
2.00000000000000
i
.From (50) we see that, for iterative method (31) with (45), after three iterations, all the iteration approximations attain the precision 10-12.The numerical results computed by these new parallel Newton-type iterative methods are satisfactory.



---

*Source: 4281684-2017-03-05.xml*