# Two Bi-Accelerator Improved with Memory Schemes for Solving Nonlinear Equations

Authors: J. P. Jaiswal
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

The present paper is devoted to the improvement of theR-order convergence of with memory derivative free methods presented by Lotfi et al. (2014) without doing any new evaluation. To achieve this aim one more self-accelerating parameter is inserted, which is calculated with the help of Newton’s interpolatory polynomial. First theoretically it is proved that the R-order of convergence of the proposed schemes is increased from 6 to 7 and 12 to 14, respectively, without adding any extra evaluation. Smooth as well as nonsmooth examples are discussed to confirm theoretical result and superiority of the proposed schemes.


---

## Body

## 1. Introduction

Finding the root of a nonlinear equation frequently occurs in scientific computation. Newton’s method is the most well-known method for solving nonlinear equations and has quadratic convergence. However, the existence of the derivative in the neighborhood of the required root is compulsory for convergence of Newton’s method, which restricts its applications in practice. To overcome the this difficulty, Steffensen replaced the first derivative of the function in Newton’s iterate by forward finite difference approximation. This method also possesses the quadratical convergence and the same efficiency just like Newton’s method. Kung and Traub are pioneers in constructing optimal general multistep methods without memory. Moreover, they conjectured any multistep methods without memory usingn function evaluations that may reach the convergence order at most 2n-1 [1]. Thus both Newton’s and Steffenssen’s methods are optimal in the sense of Kung and Traub. But the superiority of Steffenssen’s method over Newton’s method is that it is derivative free. So it can be applied to nondifferentiable equations also. To compare iterative methods theoretically, Owtrowski [2] introduced the idea of efficiency index given by p1/n, where p is the order of convergence and n number of function evaluations per iteration. In other words we can say that an iterative method with higher efficiency index is more efficient. To improve convergence order as well as efficiency index without adding any new function evaluations, Traub in his book introduced the method with memory. In fact he changed Steffensen’s method slightly as follows (see [3, pp. 185–187]).x
0, γ0 are given suitably:
(1)γk=-xk-xk-1f(xk)-f(xk-1)fork≥1,xk+1=xk-γkfxk2f(xk+γkf(xk))-f(xk),(k=0,1,2,…).
The parameter γn is called self-accelerator and method (1) has R-order of convergence 2.414. The possibility to increase the convergence order cannot be denied by using more suitable parameters. Many researchers from the last few years, are trying to construct iterative methods without memory which support Kung and Traub conjecture such as [4–13] which are few of them. Although construction of optimal methods without memory is still an active field, from the last one year, many authors are shifting their attention for developing more efficient methods with memory.In the convergence analysis of the new method, we employ the notation used in Traub’s book [3]: if mk and nk are null sequences and mk/nk→C, where C is a nonzero constant, we will write mk=O(nk) or mk~Cnk. We also use the concept of R-order of convergence introduced by Ortega and Rheinboldt [14]. Let xk be a sequence of approximations generated by an iterative method (IM). If this sequence converges to a zero ξ of function f with the R-order OR((IM),ξ)≥α, we will write
(2)ek+1~Ak,αekα,
where Ak,α tends to the asymptotic error constant Aα of the iterative method (IM) when k→∞.The rest of the paper is organized as follows: in Section2 we describe the existing two- and three-point with memory derivative-free schemes and then their convergence orders are accelerated from six to seven and twelve to fourteen, respectively, without doing any extra evaluation. Proposed methods are obtained by imposing one more suitable iterative parameter. The parameter is calculated using Newton’s interpolatory polynomial.The numerical study is also presented in the next section to confirm the theoretical results. Finally, we give the concluding remarks.


## 2. Brief Literature Review and Improving with Memory Schemes

Two-step (double) and three-step (triple) Newton’s methods can be, respectively, written as(3)yk=xk-fxkf′xk,k=0,1,2,…,xk+1=yk-fykf′yk,(4)yk=xk-fxkf′xk,k=0,1,2,…,zk=yk-f(yk)f′(yk),xk+1=zk-f(zk)f′(zk).
The orders of convergence of the schemes (3) and (4) have been increased to four and eight, respectively, but both of them have no improvement in efficiency as compared to the original Newton’s method. One major draw back of the same schemes is that they also involved derivatives. For the purpose of obtaining efficient as well as free from derivatives schemes, Lotfi et al. [15] approximated the derivatives f′(xk), f′(yk), and f′(zk) by Lagrange’s interpolatory polynomials of degrees one, two, and three, respectively, which are given by
(5)f′(xk)≈P1′(xk)=f(xk)xk-wk+f(wk)wk-xk=f[xk,wk],
where wk=xk+γf(xk) and γ∈R-{0},
(6)f′yk≈P2′yk=2yk-wk-ykxk-wkxk-ykfxk+2yk-xk-ykwk-xkwk-ykfwk+2yk-wk-xkyk-wkyk-xkfyk,f′zk≈P3′zk=wkyk+wkzk+ykzk-2wk+yk+zkzk+3zk2xk-wkxk-ykxk-zk·fxk+xkyk+xkzk+ykzk-2xk+yk+zkzk+3zk2wk-xkwk-ykwk-zk·f(wk)+xkwk+xkzk+wkzk-2xk+wk+zkzk+3zk2yk-wkyk-xkyk-zk·f(yk)+xkwk+xkyk+wkyk-2xk+wk+ykzk+3zk2zk-wkzk-xkzk-yk·f(zk).
Thus modified versions of schemes (3) and (4), respectively, become
(7)yk=xk-fxkP1′xk,k=0,1,2,…,xk+1=yk-fykP2′yk,(8)yk=xk-fxkP1′xk,k=0,1,2,…,zk=yk-f(yk)P2′(yk),xk+1=zk-f(zk)P3′(zk).
The authors have shown that without memory methods (7) and (8) preserve the convergence order with reduced number of function evaluation. Their corresponding error expressions are given by
(9)ek+1=1c131+γc12c2c22-c1c3ek4+Oek5,(10)ek+1=1c171+γc14c22c22-c1c3·c23-c1c2c3+c12c4ek8+O(ek9),
respectively, where ci=f(i)(ξ)/i!. The above two without memory schemes are optimal in the sense of Kung and Traub. Initially, Traub showed that the convergence of the without memory methods can be increased by use of information from current and previous iterations without adding any evaluation, which are known as with memory methods. To get increased order of convergence the authors in the same paper [15] first replaced γ by γk and then γk=-1/f¯′(ξ) for k=1,2,…, where ξ is the exact root and f¯′(ξ) is the approximation of f′(ξ). In addition, they used the approximation
(11)γk=-1f¯′(ξ)=-1N3′(xk),
for method (7) and
(12)γk=-1f¯′(ξ)=-1N4′(xk)
for method (8), where
(13)N3t=fxk+fxk,xk-1t-xk+f[xk,xk-1,yk-1](t-xk)(t-xk-1)+f[xk,xk-1,yk-1,wk-1]·(t-xk)(t-xk-1)(t-yk-1),N4t=fxk+fxk,zk-1t-xk+f[xk,zk-1,yk-1](t-xk)(t-zk-1)+f[xk,zk-1,yk-1,xk-1]·(t-xk)(t-zk-1)(t-yk-1)+f[xk,zk-1,yk-1,xk-1,wk-1]·(t-xk)(t-zk-1)(t-yk-1)(t-xk-1),
are Newton’s interpolatory polynomial of degrees three and four, respectively. Here the single prime (′) denotes the first derivative and double prime (′′) will later denote the second derivative. So that the one-parametric version of the methods (7) and (8) can be written as(14)wk=xk+γkfxk,γk+1=-1N3′xk,k=0,1,2,…,yk=xk-f(xk)P1′(xk),xk+1=yk-fykP2′yk,(15)wk=xk+γkfxk,γk+1=-1N4′xk,k=0,1,2,…,yk=xk-f(xk)P1′(xk),zk=yk-f(yk)P2′(yk),xk+1=zk-f(zk)P3′(zk).
The authors showed that the convergence order of methods (14) and (15) is increased from 4 to 6 and from 8 to 12, respectively. The aim of this paper is to find more efficient methods using the same number of evaluations. For this purpose we introduce one more iterative parameter in the above methods; then the modified with memory methods are given by
(16)wk=xk+γkfxk,γk+1=-1N3′xk,k=0,1,2,…,yk=xk-f(xk)P1′(xk)+αkf(wk),xk+1=yk-f(yk)P2′(yk)+αkf(yk)
with their error expression
(17)ek+1=1c131+γkc12(αkc1+c2)·αk2c1+c22+c12αkc2-c3ek4+Oek5,(18)wk=xk+γkfxk,γk+1=-1N4′xk,k=0,1,2,…,yk=xk-f(xk)P1′(xk)+αkf(wk),zk=yk-f(yk)P2′(yk)+αkf(yk),xk+1=zk-fzkP3′zk+αkfzk.
With its error expression,
(19)ek+1=1c171+γkc14αkc1+c22·(αk2c1+c22+c1(2αkc2-c3))·+c13(3αk2c2-αkc3+c4)αkc13+c23+c1c2(3αkc2-c3)+c13(3αk2c2-αkc3+c4)ek8+O(ek9).
Since the above error equations contain the iterative parameters both γk and αk, we should approximate these parameters in such a way that they will increase the convergence order. To this end, we approximate γk and αk as follows.For method (16)(20)γk=-1c1≈-1c1~=-1N3′(xk),αk=-c2c1≈-c2¯c1¯=-N4′′wk2N4′wk,
and for method (18)(21)γk=-1c1≈-1c1~=-1N~4′(xk),αk=-c2c1≈-c2︷c1︷=-N~5′′(wk)2N~5′(wk),
where
(22)N3t=N3t;xk,yk-1,xk-1,wk-1=fxk+fxk,yk-1t-xk+f[xk,yk-1,xk-1](t-xk)(t-yk-1)+f[xk,yk-1,xk-1,wk-1]·(t-xk)(t-yk-1)(t-xk-1),N4t=N4t;xk,wk,yk-1,xk-1,wk-1=f(xk)+f[xk,wk](t-xk)+f[xk,wk,yk-1](t-xk)(t-wk)+f[xk,wk,yk-1,xk-1]·t-xkt-wkt-yk-1+fxk,wk,yk-1,xk-1,wk-1·t-xkt-wkt-yk-1t-xk-1,N~4t=N~4t;xk,zk-1,yk-1,xk-1,wk-1=f(xk)+f[xk,zk-1](t-xk)+f[xk,zk-1,yk-1](t-xk)(t-zk-1)+f[xk,zk-1,yk-1,xk-1]·(t-xk)(t-zk-1)(t-yk-1),+f[xk,zk-1,yk-1,xk-1,wk-1]·(t-xk)(t-zk-1)(t-yk-1)(t-xk-1),N~5t=N~5t;xk,wk,zk-1,yk-1,xk-1,wk-1=f(xk)+f[xk,wk](t-xk)+f[xk,wk,zk-1](t-xk)(t-wk)+f[xk,wk,zk-1,yk-1]·(t-xk)(t-wk)(t-zk-1)+f[xk,wk,zk-1,yk-1,xk-1]·(t-xk)(t-wk)(t-zk-1)(t-yk-1),+fxk,wk,zk-1,yk-1,xk-1,wk-1·t-xkt-wkt-zk-1·(t-yk-1)(t-xk-1)
are Newton’s interpolatory polynomial of degrees three, four, four and five, respectively. Now we denote
(23)ek=xk-ξ,ek,z=zk-ξ,ek,y=yk-ξ,ek,w=wk-ξ,
where ξ is the exact root. Before going to prove the main result, we state the following two lemmas which can be obtained by using the error expression of Newton’s interpolation, in the same manner as in [16].Lemma 1.
Ifγk=-1/N3′(xk) and αk=-N4′′(wk)/2N4′(wk), then the estimates(i)
1+γkc1~(c4/c1)ek-1,yek-1,wek-1,(ii)
αkc1+c2~-c5ek-1,yek-1,wek-1.Lemma 2.
Ifγk=-1/N~4′(xk) and αk=-N~5′′(wk)/2N~5′(wk), then the estimates(i)
1+αkc1~-c5/c1ek-1,zek-1,yek-1,wek-1,(ii)
βkc1+c2~c6ek-1,zek-1,yek-1,wek-1.The theoretical proof of the order of convergence of the proposed methods is given by the following theorem.Theorem 3.
If an initial approximationx0 is sufficiently close to a simple zero ξ of f(x) and the parameters γk and αk in the iterative scheme (16) and (18) are recursively calculated by the forms given in (20) and (21), respectively, then the R-orders of convergence of with memory schemes (16) and (18) are at least seven and fourteen, respectively.Proof.
First, we assume that theR-orders of convergence of the sequences xk, wk, yk, and zk are at least m, m1, m2, and m3, respectively. Hence
(24)ek+1~Ak,mekm~Ak,mAk-1,mek-1mm~Ak,mAk-1,mmek-1m2,(25)ek,w~Ak,m1ekm1~Ak,m1Ak-1,mek-1mm1~Ak,m1Ak-1,mm1ek-1mm1.
Similarly(26)ek,y~Ak,m2Ak-1,mm2ek-1mm2,(27)ek,z~Ak,m3Ak-1,mm3ek-1mm3.
Now we will prove the results in two parts. First for method (16) and then for (18).
Modified Method I. For method (16), it can be derived that
(28)ek,w~(1+γkc1)ek,ek,y~L1(1+γkc1)(αkc1+c2)ek2whereL1=1c1,ek+1~L21+γkc12αkc1+c2ek4,whereL2=1c13αk2c1+c22+c12αkc2-c3.
Using the results of Lemma1 in (28), we have
(29)ek,w~c4c1Ak-1,m2Ak-1,m1·Ak-1,mek-1m2+m1+m+1,(30)ek,y~-c4c5c1L1Ak-1,m22Ak-1,m12·Ak-1m2ek-12m2+2m1+2m+2,(31)ek+1~-c42c5c12L2Ak-1,m23Ak-1,m13·(Ak-1,m4)ek-13m2+3m1+4m+3.
Now comparing the equal powers of ek-1 in three pairs of (29)-(25), (30)-(26), and (31)-(24), we get the following nonlinear system:
(32)mm1-m2-m1-m-1=0,mm2-2m2-2m1-2m-2=0,m2-3m2-3m1-4m-3=0.
After solving these equations, we get m=7, m2=3, and m1=2. It confirms the convergence of method (16). This shows the first part.
Modified Method II. For method (18), it can be derived that
(33)ek,w~(1+αkc1)ek,ek,y~L11+γkc1αkc1+c2ek2whereL1=1c1,ek,z~L21+γkc12(αkc1+c2)ek4,whereL2=1c13αk2c1+c22+c12αkc2-c3.ek+1~O31+γkc14αkc1+c22ek8,whereO3=αk2c1+c22+c12αkc2-c3×+c13(3αk2c2-αkc3+c4)αkc13+c23+c1c2(3αkc2-c3)20+c13(3αk2c2-αkc3+c4).
Now using the results of Lemma 2 in (33), we have
(34)ek,w~-c5c1Ak-1,m3Ak-1,m2Ak-1,m1·(Ak-1,m)ek-1m3+m2+m1+m+1,(35)ek,y~-c5c6c1L1Ak-1,m32Ak-1,m22Ak-1,m12·(Ak-1m2)ek-12m3+2m2+2m1+2m+2,(36)ek,z~c52c6c12L2Ak-1,m33Ak-1,m23Ak-1,m13·Ak-1,m4ek-13m3+3m2+3m1+4m+3,(37)ek+1~c54c62c14O3Ak-1,m36Ak-1,m26Ak-1,m16·(Ak-1,m8)ek-16m3+6m2+6m1+8m+6.
Comparing the equal powers ofek-1 in four pairs of (34)-(25), (35)-(26), (36)-(27), and (37)-(24), we get the following nonlinear system:
(38)mm1-m3-m2-m1-m-1=0,mm2-2m3-2m2-2m1-2m-2=0,mm3-3m3-3m2-3m1-4m-3=0,m2-6m3-6m2-6m1-8m-6=0.
After solving these equations we get m=14, m3=7, m2=3, and m1=2. And thus the proof is completed.Note 1.
The efficiency index of the proposed method (16) along with (20) is 71/3=1.9129 which is more than 61/3=1.8171 of method (14).Note 2.
The efficiency index of the proposed method (18) along with (21) is 141/4=1.9343 which is more than 81/4=1.8612 of method (15).


## 3. Numerical Examples and Conclusion

In this section the proposed derivative free methods are applied to solve smooth as well as nonsmooth nonlinear equations and compared with the existing with memory methods. Nowadays, high-order methods are important because numerical applications use high precision in their computations; for this reason numerical tests have been carried out using variable precision arithmetic inMATHEMATICA 8 with 700 significant digits. The computational order of convergence (COC) is defined by [17, 18]
(39)COC=ln⁡⁡f(xk)/f(xk-1)ln⁡⁡f(xk-1)/f(xk-2).
To test the performance of new method consider the following three nonlinear functions (which are taken from [5, 15]): (1)
f1(x)=sin(πx)ex2+xcos⁡(x)-1+xlog⁡(xsin(x)+1),(2)
f2(x)=ex3-x-cos⁡(x2-1)+x3+1,(3)
f3(x)=10(x4+x),x<0-10(x3+x),x≥0.The absolute errors for the first three iterations are given in Table 1. In the table ae±b stands for a×10±b. Note that a large number of three-step derivative-free (with and without memory) methods are available in the literature. But the methods which have been tested for nonsmooth functions are rare and this clearly proves the significance of this paper.Table 1
Comparison of the absolute error in first, second, and third iteration.
Function
Method
x
1
-
ξ
x
2
-
ξ
x
3
-
ξ
COC
f
1 ξ=0  x0=0.6
(14)  with  γ0=-1
0.67423e − 2
0.72063e − 12
0.23027e − 72
6.0653
(15)  with  γ0=-1
0.23448e − 3
0.56614e − 45
0.86233e − 543
11.962
(16)  with  γ0=-1  and α0=-0.1
0.29657e − 2
0.28414e − 14
0.99885e − 101
7.1926
(18)  with  γ0=-1  and α0=-0.1
0.98901e − 4
0.14013e − 44
0.41159e − 628
14.285
f
2 ξ=-1  x0=-1.65
(14)  with  γ0=1
0.10743e − 0
0.40447e − 5
0.24898e − 34
6.6381
(15)  with  γ0=1
0.23223e − 1
0.62952e − 20
0.77469e − 241
11.901
(16)  with  γ0=1  and  α0=0.65
0.21296e − 0
0.50014e − 4
0.73645e − 32
7.7919
(18)  with  γ0=1  and α0=0.65
0.67736e − 1
0.22204e − 15
0.55387e − 214
13.725
f
3 ξ=-1  x0=-0.8
(14)  with  γ0=1
0.13702e − 0
0.85922e − 4
0.99097e − 23
5.7102
(15)  with  γ0=1
0.35840e − 1
0.25132e − 14
0.61401e − 172
11.954
(16)  with  γ0=1  and  α0=-0.3
0.19721e − 0
0.19721e − 4
0.33883e − 29
6.6720
(18)  with   γ0=1  and α0=-0.3
0.68741e − 1
0.33307e − 15
0.26137e − 215
13.922The effectiveness of the new proposed derivative free with memory methods is confirmed by comparing this with the existing memory family. The numerical results shown in Table1 are in concordance with the theory developed here. From the theoretical result, we can conclude that the order of convergence of the without memory family can be made more higher than the existing with memory family by imposing more self-accelerating parameter without any additional calculations and the computational efficiency of the presented with memory method is high. The R-orders of convergence are increased from 6 to 7 and 12 to 14 in accordance with the quality of the applied accelerating method proposed in this paper. We can see that the self-accelerating parameters play a key role in increasing the order of convergence of the iterative method.



---

*Source: 938606-2015-02-23.xml*