View of Accelerating the convergence of Newton-type iterations

J. Numer. Anal. Approx. Theory, vol. 46 (2017) no. 2, pp. 162–180 ictp.acad.ro/jnaat

ACCELERATING THE CONVERGENCE OF NEWTON-TYPE ITERATIONS^∗

T. ZHANLAV^§, O. CHULUUNBAATAR^§,†and V. ULZIIBAYAR^§,‡

Abstract. In this paper, we present a new accelerating procedure in order to speed up the convergence of Newton-type methods. In particular, we derive iterations with a high and optimal order of convergence. This technique can be applied to any iteration with a low order of convergence. As expected, the convergence of the proposed methods is remarkably fast. The effectiveness of this technique is illustrated by numerical experiments.

MSC 2010. 65H05.

Keywords. Newton-type iterations, accelerating procedure, convergence order, efficiency index.

1. INTRODUCTION

As it is known, the monotone approximations for the solutions of nonlinear equations inRis interesting not only from theoretical, but also from practical view points. In particular, two-sided approximations can be efficiently used as a posteriori estimations for the errors in approximating the desired solution. It means that one can control the error at each iteration step. In the last decade, many authors have developed new monotone iterative methods [9,18,19]. The main advantage of the monotone iterations is that it does not require good initial approximations contrary to what occurs in the other iteration methods, such as secant-like methods, Newton’s methods and others [4]. On the other hand, accelerating the convergence of iterative methods is also of interest both from theoretical and computational view points [1–3,5,10–14,16]. For example, in [4] was constructed a family of the predictor-corrector iterative method from the simplified secant method and a family of secant-like methods; the authors analyzed the initial conditions on the starting point in order to improve the semilocal convergence of the method. In general, it is desirable to choose the starting point from the convergence domain [15, 16, 19].

§Institute of Mathematics, National University of Mongolia, Mongolia, e-mail:

[email protected].

†Joint Institute for Nuclear Research, Dubna, 141980 Moscow region, Russia, e-mail:

[email protected].

‡School of Applied Sciences, Mongolian University of Science and Technology, Mongolia, e-mail: [email protected].

In recent years, many iterative methods for solving nonlinear equations have been developed [1–3, 5, 10–14, 16] to improve the local order of convergence of some methods such as Newton, Ostrowski, Potra-Ptak’s methods and so on.

The most efficient methods studied in the literature are the optimal eighth- order methods with four function evaluations per iteration, see [1–3,10,12] and references therein. The methods developed in [1, 7, 12] are based on optimal Ostrowski’s or King’s method and use arbitrary real parameters and weight functions. The methods proposed in [2, 3, 10] are obtained by composing an iterative method proposed by Chun and Potra-Ptak’s method with Newton’s method.

In this paper we propose a new accelerating procedure for Newton-type methods. By virtue of this procedure, we obtain a higher order, in particular optimal order methods. The usage of the optimal choice of parameter allows us to improve the convergence speed. This may be also helpful in order to extend the domain of convergence.

The paper is organized as follows. Section 2 describes monotone and two- sided approximations. In Section 3, we show the accelerating procedure and establish a convergence order of the new proposed methods. Section 4 is de- voted to finding an optimal parameter in the proposed iterations. Finally, Section 5 presents various numerical examples which confirm the theoretical results, and a numerical comparison with other existing optimal order meth- ods.

2. STATEMENT OF THE PROBLEMS

Let a, b ∈ R, a < b, f : [a, b] → R and consider the following nonlinear equation

f(x) = 0.

(2.1)

Assume that f(x) ∈ C⁴[a, b], f⁰(x) 6= 0, x∈(a, b) and Eq. (2.1) has a unique rootx^∗ ∈(a, b). In [18, 19] the following iterations were proposed:

x2n+1 =x2n−τnf(x2n) f⁰(x2n), (2.2)

x2n+2 =x2n+1−_f^f0^(x(x²ⁿ⁺¹2n+1⁾), n= 0,1, . . . (2.3)

In [19] it is shown that the iterations (2.2) and (2.3) monotone convergent under conditions

0< τn≤1, an= ^M_(f²0^|f(x(xn))^n2)| < ¹₂, M2 = sup

x∈Ur(x^∗)

|f⁰⁰(x)|, (2.4)

and under the assumption H :f⁰(x)6= 0, f⁰⁰(x) preserve sign in the small neighborhood Ur(x^∗) ={x:|f(x)|< r}.However the iterations (2.2) and (2.3) are not equipped with a suitable choice of parameter τn. In [18] it was shown that the iterations (2.2) and (2.3) have a two-sided approximation behavior

under conditions

τn∈I2n=^ht¹⁻

√1−2a2n

a2n ,⁻¹⁺

√1+4a2n

a2n

⊆(1,2), a2n< ⁴₉. (2.5)

It is also proved that the convergence rate of these iterations is at least 2, and the order of convergence is increased up to 4, when τn → 1. From this it is clear that the accelerating of the convergence of iterations (2.2) and (2.3) is important, especially at the early stage of iterations.

3. MONOTONE AND TWO-SIDED CONVERGENCE OF ITERATIONS AND THEIR ACCELERATION

Ifτ_n≡1, then the iterations (2.2) and (2.3) become as Newton’s one xn+1=xn−_f^f(x0(xⁿn⁾), n= 0,1. . .

(3.1)

According to [19] the iteration (3.1) is a monotone convergent under condition (2.4) and assumption H.

Letθn= ^f(x_f(xⁿ⁺¹⁾

n) . Then the Taylor expansion of f(xn+1) gives 0< θ_n≤ ^a₂ⁿ < ¹₄.

(3.2)

Now we proceed to accelerate the convergence of monotone iteration (3.1).

To this end, we use two known approximations xn, xn+m satisfying either x_n< x_n+m< x^∗ orx^∗< x_n+m< x_n and consider

yn=xn+t(xn+m−xn), t >1.

(3.3)

From (3.3) it is clear that y_n belongs to interval connecting x_n and x_n+m under condition 0≤t≤1. Hence, the extrapolating approach corresponds to the case t >1. Our aim is to find the optimal value of t=t_opt in (3.3) such that the new approximation yn given by (3.3) will be situated more close to x^∗ as compared with x_n and x_n+m. We use Taylor expansion of the smooth functionf(x)∈ C^k+1[a, b]:

f(y_n) =f(x_n) +f⁰(x_n)t(x_n+m−x_n) +. . .

+^f(k)_k!^(xn)t^k(xn+m−xn)^k+O (xn+m−xn)^k+1. (3.4)

Neglecting small termO (x_n+m−x_n)^k+1in (3.4), we have (3.5)

f(y_n)≈f(x_n) +f⁰(x_n)t(x_n+m−x_n) +. . .+^f(k)_k!^(xn)t^k(x_n+m−x_n)^k≡P_k(t).

From (3.5) it is clear that

f(xn) =P_k(0).

(3.6)

We also require that

f(x_n+m) =P_k(1).

(3.7)

From (3.7) we find ^f(k)_k!^(xn)(xn+m−xn)^k and substituting it into (3.5), we get P_k(t). From this we findt >1 such that

f(yn)≈Pk(t) = 0.

(3.8)

Geometrically, (3.5) means that the graph (plot) off(x) in the vicinity of root x^∗ is replaced by curveP_k(t) passing through the given points (x_n, f(x_n)) and (xn+m, f(xn+m)). Thus, Eq. (3.5) fork= 1,2 and k= 3 gives us

P₀(t) = f(x_n)≈f(y_n), y_n=x_n, (3.9)

P₁(t) = f(x_n) + (f(x_n+m)−f(x_n))t, (3.10)

P2(t) = f(xn) +f⁰(xn) (xn+m−xn)t

+ f(xn+m)−f(xn)−f⁰(xn)(xn+m−xn)t², (3.11)

P₃(t) = f(x_n) +f⁰(x_n) (x_n+m−x_n)t+^f00(x₂ⁿ⁾(x_n+m−x_n)²t² +f(xn+m)−f(xn)−f⁰(xn)(xn+m−xn)

(3.12)

−^f00(x₂ⁿ⁾(xn+m−xn)²t³,

respectively. Thus, the parameter t in (3.3) is calculated as a root greater than 1 of Eq. (3.8). In particular, fork= 1, we have

topt= _f(x ^f(xn)

n)−f(xn+m) >1.

(3.13)

Since P_k(0)P_k(1) =f(x_n)f(x_n+m)>0 for k≥1, Eq. (3.8) may have at least one root satisfying the condition t^∗ >1. From (3.2) it follows that

|f(x_n+1)|< ¹₄|f(x_n)|.

(3.14)

Therefore, it is desirable to choose nand m such that

|f(x_n+m)|< ¹₄^m|f(x_n)| 0.1.

(3.15)

This inequality is written in term of P_k(t) as

|P_k(1)| ≤ ¹₄^m|P_k(0)|<0.1.

(3.16)

On the other hand, from (3.5) we see that P_k⁰(1) is not equal to 0 underthe assumption H, i.e. t= 1 is not a critical point of P_k(t). Thus,P_k(t) is de- creasing aroundt= 1. Therefore, there existstopt >1 such thatP_k(topt) = 0.

Lemma 3.1. Assume that f ∈ C⁴[a, b], the assumption H is satisfied and

|x^∗−x_n|=ε_n<1.

(3.17)

Then the following holds

topt−1 =O(ε_n).

(3.18)

Proof. First of all, let us note that the inequality (3.17) is equivalent to

|f(x_n)|=O(ε_n), (3.19)

which follows from the expansion

0 =f(x^∗) =f(xn) +f⁰(ξ)(x^∗−xn).

Of course, |x^∗−xn+m|< εn and |x_n+m−xn|< εn under (3.17).

We also use an analogous expansion for P_k(t)

0 =P_k(t_opt) =P_k(1) +P_k⁰(η)(t_opt−1), η ∈(1, t_opt).

(3.20)

Since P_k(t) is decreasing aroundt= 1, thenP_k⁰(η)6= 0.

Hence, from (3.19), (3.20) and (3.15) we conclude that topt−1 =−^f(x_P^n+m0 ⁾

k(η) ≈ O(ε_n).

(3.21)

The Lemma is proved.

Note that in [16] the iterations was proposed:

x_2n+1=x_2n−τ_nf^f(x0(x²ⁿ2n⁾), (3.22)

x_2n+2=x_2n+1− _f(x^x2n+1−x2n

2n+1)−f(x_2n)f(x_2n+1), n= 0,1, . . . , (3.23)

which has a third order of convergence when τ_n = 1 or τ_n tends to 1. It is easy to show that the iteration (3.23) coincides fully with our acceleration procedure (3.3) and (3.13) withm = 1 andk= 1. Therefore, one can expect a high acceleration when k= 2,3 for Newton’s method.

How to accelerate the convergence rate of iteration (3.1)? The answer of this question gives the following theorem.

Theorem 3.2. Assume f(x) ∈ C^k+2 and the condition (3.17) is satisfied.

Then for y_n with t_opt we have

|x^∗−yn|

|x^∗−xn|^k+2 ≈ O(1), (3.24)

where O is the Landau symbol.

Proof. Let

x^∗=xn+t^∗(xn+m−xn), t^∗ ≥1, yn=xn+topt(xn+m−xn).

(3.25)

We use Taylor expansions of f(x)∈ C^k+2 0 =f(x^∗) =

(3.26)

=

k

X

p=0

f^(p)(xn)

p! (t^∗)^p(xn+m−xn)^p+^f(k+1)_(k+1)!^(ηn)(t^∗)^(k+1)(xn+m−x_n)^(k+1),

f(x_n+m)−

k−1

X

p=0

f^(p)(xn)

p! (x_n+m−x_n)^p = (3.27)

= ^f(k)_k!^(xn)(xn+m−xn)^k+ ^f(k+1)_(k+1)!^(ξn)(xn+m−xn)^k+1,

and

0 =P_k(t_opt) =

k−1

X

p=0

f^(p)(xn)

p! (t_opt)^p(x_n+m−x_n)^p (3.28)

+f(x_n+m)−

k−1

X

p=0

f^(p)(xn)

p! (x_n+m−x_n)^p(t_opt)^k, whereη_n∈(x_n, x^∗) andξ_n∈(x_n, x_n+m). Using (3.27) in (3.28) and subtract- ing (3.28) from (3.26) we get

hf⁰(xn) + ^f00(x₂ⁿ⁾(xn+m−xn)(t^∗+topt) +^f000(x₆ ⁿ⁾(xn+m−xn)² (t^∗2+t^∗topt+t²_opt) +· · ·+^f(k)_k!^(xn)t^∗k−1 +t^∗k−2topt+· · ·+t^k−1_opt

(xn+m−xn)^k−1i(t^∗−topt) =

=−^(xn+m_(k+1)!^−xn)kf^(k+1)(ηn)t^∗k+1−f^(k+1)(ξn)t^k_opt. (3.29)

Since f⁰(x_n)6= 0, then from last expression we deduce that t^∗−t_opt =O(ε^k_n).

(3.30)

It is possible to derive a more precise estimation than (3.30). Indeed, using (3.30) andf ∈ C^k+2 we evaluate

An=f^(k+1)(ηn)t^∗k+1−f^(k+1)(ξn)t^k_opt

=f^(k+1)(ξn)(t^∗k+1−t^k_opt) +f^(k+2)(ωn)(ηn−ξn).

(3.31)

By definition we have

|η_n−ξn| ≤ |x^∗−xn|=εn. (3.32)

Using (3.18) and (3.30) we have

t^∗k+1−t^k_opt = t_opt+O(ε^k_n)^k+1−t^k_opt

=t^k_optt_opt(1 +O(ε^k_n))^k+1−1=t^k_opt t_opt+O(ε^k_n)−1=O(ε_n).

(3.33)

Then An=O(ε_n) and thereby from (3.29) we get t^∗−t_opt =O(ε^k+1_n ).

(3.34)

Hence, from (3.25) and (3.26) we find that x^∗−yn=O(ε^k+2_n ).

which proves (3.24).

The sequence {y_n} given by formula (3.3) can be considered as a new a iteration. For it we have the followlng:

Theorem3.3. Assumef(x)∈ C^k+1 and the convergence order of iterations (3.1) equal to 2 i.e., the following holds

|x^∗−x_n| ≤M q²ⁿ|x^∗−x₀|, 0< q <1, M = const.

(3.35)

If the equation (3.8) has at least one root t_opt, greater than 1, then the con- vergence order of new iteration (3.3)is the same as (3.1)and we have

(3.36) |x^∗−yn| ≤M1q²₁ⁿ|x^∗−y0|, 0< q1=q^k+1<1, M1 =const.

Proof. By virtue of (3.35) the condition (3.17) is satisfied for largen. Then by Theorem 3.2, the relation (3.24) holds. Using (3.35) in (3.24), we get

|x^∗−y_n| ≤C q^dnk+2|x^∗−x₀|^k+2=C q^k+2dn|x^∗−x₀|^k+2

=Cq^d₁ⁿ|x^∗−x₀|^k+2 ≤M₁q₁^dn|x^∗−y₀|, q₁ =q^k+2 < q <1.

(3.37)

The proof is completed.

Theorem 3.3 shows that the convergence order of iteration (3.3) is the same as iteration (3.1).

However, the speed of convergence of these iterations depends on the factor q1 andq in (3.35) and (3.36), respectively. Sinceq1=q^k+2< qfork= 1,2,3, one can expect a more rapid convergence of iteration (3.3). Of course, the higher is acceleration of iteration attained atk= 3.

From (3.35) and (3.36) it is clear that the iteration (3.3) converges to x^∗ more rapidly than iteration (3.1) by virtue ofq1=q^k+1< q. This accelerating procedure is useful, especially at the beginning of iterations, but under condi- tion (3.17). From Theorem 3.3, it is clear that the sequence{y_n}given by (3.3) together with (3.1) can be considered as a new iteration process with a small factor compared to (3.1). The acceleration procedure is achieved without ad- ditional calculations, so that the iteration (3.3) possesses a high computational efficiency. However, despite the sequence x_n is monotone, the new iteration (3.3) may not be monotone. For instance, whenk= 1 it is easy to show that

f(yn) = ^f00(ξ₂ⁿ⁾(xn+m−xn)². (3.38)

From this it is clear that

f(yn)>0 if f⁰⁰(x)>0, (3.39)

and

f(yn)<0 if f⁰⁰(x)<0.

(3.40)

Let us know two successive approximationsxn andxn+1, for which f(xn)f(xn+1)<0

(3.41)

holds. We consider

y_n=x_n+t(x_n+1−x_n), 0≤t≤1.

(3.42)

The acceleration technique will be the same as a previous case with m = 1.

In this case, according to (3.41) we have P_k(0)P_k(1) =f(x_n)f(x_n+1)<0 for k = 1,2,3. Hence, Eq. (3.8) has a root topt ∈ (0,1). Obviously, the new approximation

yn=xn+topt(xn+1−xn), 0≤t≤1, (3.43)

will be situated more close to x^∗ as compared to x_n, x_n+1 and Theorem 3.2 holds true for this case, too. It indicates that the two-sided approximations are useful not only for estimations of roots, but also for finding it approximately with a higher accuracy. Of course, the acceleration procedure (3.3) can be continued further with xn+m := yn, xn := xn+m and with t > 1 if yn and x_n+m are located on side of x^∗ and witht∈(0,1) ify_n and x_n+m are located on two-sides of root. Note that the accelerating procedure (3.3) is applicable not only for iterations (3.1), but also for any iteration, in particular, for the following iterations (A), (B), (C) and (D).

Now we consider the accelerated iteration

(A) y_n=x_n−_f^f0^(x(xⁿn⁾), x_n+1=x_n+t_opt(y_n−x_n), n= 0,1, . . .

The iteration (A) is a damped Newton’s method [17, 20] with optimal param- eter τ_n=t_opt. The first step y_n is used for finding the optimal parameter.

Theorem 3.4. Assume that the assumptions of Theorem 3.2 are fulfilled.

Then the convergence order of iteration(A)with optimaltopt isd=k+ 2, k= 1,2,3, depending on the smoothness of f.

Proof. If we compare (A) with (3.1) and (3.3), thenx_n+m :=y_n and y_n :=

xn+1. Therefore, the expression (3.24) in the Theorem 3.2 has a form

|x^∗−xn+1|

|x^∗−xn|^k+2 =O(1)⇐⇒ |x^∗−x_n+1| ≤M|x^∗−x_n|^k+2, (3.44)

which completes the proof of the Theorem 3.4.

Now let us consider another three-step iteration

yn=xn−_f^f(x0(xⁿn⁾), zn=yn− _f^f(y0(xⁿn⁾), x_n+1=y_n+t(z_n−y_n), n= 0,1, . . . (B)

Note that ift≡1 in (B), then it leads to

(B⁰) y_n=x_n−_f^f(x0(xⁿn⁾), x_n+1=y_n− _f^f0^(y(xⁿn⁾), n= 0,1, . . .

The iteration (B⁰) is a particular case of scheme (40) given in [16] withσ= 0 end τ = 1 and has a third order of convergence. Therefore, the iteration (B) can be considered as improvement of iteration (B⁰).

Theorem 3.5. The assumptions of the Theorem 3.2are fulfilled. Then the convergence order of iteration (B) with optimalt_opt equal to d= 2k+ 3.

Proof. If we compare (B) with (3.3), thenxn:=yn,xn+m :=zn,yn:=xn+1. Then form (3.29) and (3.19) we get

t^∗−t_opt=M A_n(z_n−y_n)^k≈ O(ε^2k+1_n ), (3.45)

where

x^∗=yn+t^∗(zn−yn), xn+1 =yn+topt(zn−yn).

(3.46)

From this and from (3.45) we obtained

(3.47) x^∗−xn+1 = (t^∗−topt)(zn−yn)≈ O(ε^2k+1_n )O(ε²_n) =O(ε^2k+3_n ), i.e., we have

|x^∗−x_n+1| ≤M₁|x^∗−x_n|^2k+3,

which means that the convergence order of iteration (B) is equal tod= 2k+ 3,

k= 1,2,3.

From the Theorem 3.5, we see that the convergence order of iteration (B⁰) can be increased two or four units at the expense of only two additional eval- uations of the function. So the order of convergence and the computational efficiency of the method are greatly improved.

In [5] Algorithm 2 was constructed:

z_n=x_n−_f^(x0(xⁿn⁾), x_n+1 =z_n−H(x_n, y_n)_f^f(z0(xⁿn⁾),

and it is proved that the order of convergence equals 5, 6, 7 depending on a suitable choice of two-variable function H(xn, yn). For comparison purpose we can rewrite iteration (B) as

yn=xn−_f^f(x0(xⁿn⁾), xn+1 =yn−t_f^f0^(y(yⁿn⁾).

We see that these two methods are different from one another only by chosen factorst and H(x_n, y_n).

Now we consider the following iteration:

(C) yn=xn−_f^f0^(x(xⁿn⁾), zn=yn−_f^f0^(y(yⁿn⁾), xn+1 =yn+t(zn−yn), n= 0,1, . . . The iteration (C) can be considered as improvement of iteration

(C⁰) y_n=x_n−_f^f(x0(xⁿn⁾), x_n+1 =y_n−_f^f0^(y(yⁿn⁾), n= 0,1, . . . , since ift≡1 in (C), then it leads to (C⁰).

In [16], it was proven that the convergence order of (C⁰) is four.

Theorem 3.6. The assumptions of Theorem 3.2 are fulfilled. Then the convergence order of iteration (C) with optimal t_opt equal to d = 2(k+ 2), k= 1,2,3.

Proof. If we compare (C) with (3.3), thenxn:=yn,xn+m :=zn,yn:=xn+1. Therefore, the expression (3.24) reads as

|x^∗−xn+1|

|x^∗−yn|^k+2 =O(1)⇐⇒ |x^∗−x_n+1| ≤M|x^∗−y_n|^k+2. (3.48)

From (C), we find that

x^∗−yn=x^∗−xn+^f(x_fⁿ0^)−f(xn^(x) ^∗). (3.49)

Substituting here the expansion off(x^∗)

f(x^∗) =f(x_n) +f⁰(x_n)(x^∗−x_n) + ^f00(ξ₂ⁿ⁾(x^∗−x_n)², (3.50)

we have

|x^∗−yn| ≤ ^|f_|f⁰⁰0(x^(ξnⁿ)|^)||x^∗−xn|². (3.51)

Using the last estimate in (3.45), we obtain

|x^∗−x_n+1| ≤M₁|x^∗−x_n|^2(k+2),

which means that the convergence order of iteration (C) equalsd= 2(k+ 2),

k= 1,2,3.

Note that the iterations (A), (B) and (C) can be rewritten as a damped Newton’s method [20]

x_n+1 =x_n−τ_nf^f(x0(xⁿn⁾), (3.52)

τn=topt, (3.53)

τn=1 +toptf(yn) f(xn), (3.54)

τn=1 +toptf(yn) f(xn)

f⁰(xn) f⁰(yn), (3.55)

respectively. The unified representation (3.52) of different iterations shows that the choice of the damped parameter τ_n in (3.52) is essentially affected for the convergence order. Of course, the parameterτn in (3.52) is defined by different ways, but in all cases τ_n→1 as n→ ∞.

The speed of convergence of sequence {τ_n} to unit is different for each iteration methods. In [17] the conjecture was proposed:

|1−τn| ≤M q^ρn, 0< q <1.

(3.56)

Now we consider the following three-point iterative method:

yn=xn− _f^f(x0(xⁿn⁾), zn=xn+ ¯t(yn−xn), x_n+1=y_n+t(z_n−y_n), n= 0,1, . . . , (D)

where ¯tandtin (D) are some parameters to be determined. We can formulate the following theorem.

Theorem 3.7. Assume that f(x) ∈ C⁴(a, b) and an initial approximation x₀ is sufficiently close to the zerox^∗∈(a, b) and the parameter¯t is chosen by as a root of equation

θ_n¯t²−¯t+ 1 = 0, θ_n= ^f_f(x^(yn)

n), (3.57)

and t is a root of equation

Ψ(t, α) =αΨ₁(t) + (1−α)Ψ₂(t) = 0, (3.58)

where

Ψ₁(t) =at²− a+^f(x_f(yⁿ⁾

n) f(zn)−f(yn)t−f(xn), (3.59)

a=−2f(z_n)−f(xn)(1−¯t)², and

Ψ₂(t) = (1−t)(2¯ −¯t)f(x_n)−(2−3¯t)f(z_n)t + (1−t) 2f¯ (z_n)−(2−¯t)f(x_n). (3.60)

Then the three-point methods (D) is of eight order of convergence.

Proof. Usingzn−yn= (1−t)¯ _f^f(x0(xⁿn⁾) in Taylor expansion

f(x_n+1) =f(y_n) +f⁰(y_n)t(z_n−y_n) + ^f00(y₂ⁿ⁾t²(z_n−y_n)²+O (z_n−y_n)³, we get

f(x_n+1) =f(y_n) +t(1−¯t)^f_f0⁰(x^(ynn⁾)f(x_n) +^f00(y₂ⁿ⁾t²(1−¯t)^{2 f2(xn)}

f⁰(xn)² +O f⁶(x_n). (3.61)

Analogously, the Taylor expansion off(xn+1) at point x=zn gives f(x_n+1) =f(z_n)−(1−t)(1−¯t)_f^f0⁰(x^(znn⁾)f(x_n)

+^f00(z₂ⁿ⁾(1−t)²(1−¯t)^{2 f2(xn)}

f⁰(xn)² +O (1−t)³f⁶(x_n). (3.62)

Usingf⁰(z_n) =f⁰(y_n) +f⁰⁰(y_n)(z_n−y_n) +O (z_n−y_n)²in the last expansion, we have

f(x_n+1) =f(z_n)−(1−t)(1−¯t)_f^f00^(z(xⁿn⁾)f(x_n) + ^f00(z₂ⁿ⁾(1−t)²(1−¯t)^{2 f2(xn)}

f⁰(xn)² +O (1−t)³f⁶(x_n). (3.63)

Usingf⁰(zn) =f⁰(yn) +f⁰⁰(yn)(zn−yn) +O(zn−yn)²in the last expansion, we have

f(xn+1) =f(zn)−(1−t)(1−¯t)^f_f0⁰(x^(ynn⁾)f(xn)

−^{f00(yn)f2(xn)}

2 f⁰(xn)² (1−t²)(1−¯t)²+O f⁸(xn). (3.64)

From (3.61) and (3.64) one can eliminate term with ^f_f0⁰(x^(ynn⁾)f(x_n). As a result, we have

f(x_n+1) =tf(z_n)+(1−t)f(y_n)−^{f00(yn)f2(xn)}

2 f⁰(xn)² (1−¯t)²t(1−t)+O f⁸(x_n). (3.65)

Note that in driving (3.65), we keep in mind that 1−t=O f²(xn). (3.66)

Further, using Taylor expansion of f(x)∈ C⁴(D) at pointsy_n we obtain f⁰⁰(yn) = ^{2 f}

0(xn)²

f²(xn)¯t(1−¯t)

(1−¯t)f(xn) + ¯tf(yn)−f(zn)

−^f000(y₃ⁿ⁾f(xn)

f⁰(x_n)(2−¯t) +O f²(xn). (3.67)

The same technique gives us f⁰⁰(y_n) =^{2 f(zn)−(1−¯t)f(xn)}

¯t²f²(xn) f⁰(x_n)²−^f000₃^(yn)_f^f(x0(xⁿn⁾)(3−¯t)+O f²(x_n). (3.68)

For (3.67) and (3.68) one can eliminate the term withf⁰⁰⁰(y_n). As a result, we obtain

f⁰⁰(yn)f²(xn)

2 f⁰(xn)² =_¯t2(1−¹ _¯t) (3−¯t)¯t −f(zn) + ¯tf(yn) + (1−¯t)f(xn)

−(2−¯t)(1−t)¯f(z_n)−(1−¯t)f(x_n)+Of⁴(x_n). (3.69)

Substituting (3.69) into (3.64), we obtain

f(xn+1) = Ψ₁(t) +O f⁸(xn), (3.70)

where

Ψ₁(t) =at²− a+^f(x_f(yⁿ⁾

n) f(zn)−f(yn)t−f(xn), (3.71)

a=−2f(z_n)−f(x_n)(1−¯t)². On the other hand, by virtue of (D) we have

x_n+1−z_n=−(1−t)(1¯ −t)_f^f0^(x(xⁿn⁾). (3.72)

If we take (3.57) and (3.66) into account in (3.72), from it we deduce x_n+1−z_n=O f⁴(x_n).

Then, from (3.62) we get

f(xn+1) =f(zn) + (1−¯t)(1−t)_f^f0⁰(x^(znn⁾)f(xn) +O f⁸(xn). (3.73)

Now we approximate f⁰(zn) by the method of undetermined coefficient such that

(3.74) f⁰(zn)≈anf(xn) +bnf(yn) +cnf(zn) +dnf⁰(xn) +O f⁴(xn), This can be done by means of Taylor expansion of f(x)∈ C⁴(a, b) at pointzn

and we obtain the following linear system of equations















an+bn+cn= 0,

a_n(x_n−z_n) +b_n(y_n−z_n) +d_n= 1,

a_n(x_n−z_n)²+b_n(y_n−z_n)²+ 2d_n(x_n−z_n) = 0, an(xn−zn)³+bn(yn−zn)³+ 2dn(xn−zn)²= 0, which has a unique solution

a_n= ^β_ω^{n(2βn−3ωn)}

n(βn−ωn)² , b_n= _β ^ωn2

n(βn−ωn)², (3.75)

c_n=−^2β_β^n+ωn

nωn , d_n=−_β ^βn

n−ω_n, where

ωn=xn−zn= ¯t_f^f0^(x(xⁿn⁾), βn=yn−zn= (1−¯t)_f^f0^(x(xⁿn⁾).

Substituting (3.74) with coefficients defined by (3.76) into (3.73), we get f(x_n+1) = Ψ₂(t) +O f⁸(x_n),

(3.76) where

Ψ₂(t) = (1−t)(2¯ −¯t)f(xn)−(2−3¯t)f(zn)t (3.77)

+ (1−¯t) 2f(z_n)−(2−¯t)f(x_n). The linear combination of (3.70) and (3.76) gives

f(x_n+1) =αΨ₁(t) + (1−α)Ψ₂(t) +O f⁸(x_n). Clearly, if we choosetas a root of quadratic equations

Ψ(t, α) =αΨ₁(t) + (1−α)Ψ₂(t) = 0, (3.78)

then we have

f(x_n+1) =O f⁸(x_n)

which completes the proof.

Remark 3.8. Since t is a root of Eq. (3.78), it depends on the parameter α, i.e. t=t(α). Therefore, (D) are one parameter family of iterations.

It is easy to show that

Ψ₂(ˆt) = 0, ˆt→1, Ψ₁(˘t) = 0, ˘t→1.

Then taking this into account and passing to the limit t → 1 in Eq. (3.78), we get

Ψ(t, α)−−→^t→1 αΨ₁(1) + (1−α)Ψ₂(1)≈0.