# Some Iterative Methods Free from Derivatives and Their Basins of Attraction for Nonlinear Equations

Authors: Farahnaz Soleimani; Fazlollah Soleymani; Stanford Shateyi
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

First, we make the Jain's derivative-free method optimal and subsequently increase its efficiency index from 1.442 to 1.587. Then, a novel three-step computational family of iterative schemes for solving single variable nonlinear equations is given. The schemes are free from derivative calculation per full iteration. The optimal family is constructed by applying the weight function approach alongside an approximation for the first derivative of the function in the last step in which the first two steps are the optimized derivative-free form of Jain's method. The convergence rate of the proposed optimal method and the optimal family is studied. The efficiency index for each method of the family is 1.682. The superiority of the proposed contributions is illustrated by solving numerical examples and comparing them with some of the existing methods in the literature. In the end, we provide the basins of attraction for some methods to observe the beauty of iterative nonlinear solvers in providing fractals and also choose the best method in case of larger attraction basins.


---

## Body

## 1. Introduction

In order to approximate the solution of nonlinear functions, it is suitable to use iteration methods which lead to monotone sequences. The construction of iterative methods for estimating the solution of nonlinear equations or systems is an interesting task in numerical analysis [1]. During the last years, a huge number of papers, devoted to the iterative methods, have appeared in many journals, see, for example, [2–5] and their bibliographies.The first famous iterative method was attributed by Newton asxn+1=xn-f(xn)/f′(xn). Steffensen approximated f′(xn), using forward finite difference of order one to obtain its derivative-free form as xn+1=xn-f(xn)2/(f(xn+f(xn))-f(xn)). Both methods reach the quadratically convergence consuming two evaluations per cycle [6].A very important aspect of an iterative process is the rate of convergence of the sequence{xn}n=0∞, which approximates a solution of f(x)=0. This concept, along with the cost associated to the technique, allows establishing the index of efficiency for an iterative process. In this way, the classical efficiency index of an iterative process [6] is defined by the value p1/n, where p is the convergence rate and n is the total number of evaluations per cycle. Consequently, Newton and Steffensen schemes both have the same efficiency index 1.414.In addition, Kung and Traub in [7] conjectured that a multipoint iteration without memory consuming n evaluation per full iteration can reach the maximum convergence rate 2n-1. Taking into account all these, many researchers in this topic have been trying to construct robust optimal methods; see, for example, [8, 9] and their bibliographies.The remained contents of this study are summarized in what follows. In Section2, we present an optimized form of the well-known cubically Jain’s method [10] with quartic convergence. Moreover, considering the Kung-Traub conjecture, we build a family of three-step without memory iterative methods of optimal convergence order 8. In order to give this, we use an approximation of the first derivative of the function in the last step of a three-step cycle alongside a well-written weight function. Analyses of convergence are given. A comparison with the existing, without memory methods of various orders, is provided in Section 3. We also investigate the basins of attraction for some of the derivative-free methods to provide the fractal behavior of such schemes in Section 4. Section 5 gives the concluding remarks of this research and presents the future works.


## 2. Main Results

The main idea of this work is first to present a generalization of the well-known Jain’s method with optimal order four and the efficiency index 1.587 and then construct a three-step family of derivative-free eighth-order methods with optimal efficiency index 1.682.Let us take into consideration the Jain’s derivative-free method [10] as follows:
(1)yn=xn-f(xn)2f(xn+f(xn))-f(xn),x0given,xn+1=xn-f3(xn)[f(xn+f(xn))-f(xn)][f(xn)-f(yn)].Equation (1) is a cubical technique using three function evaluations per iteration with 31/3≈1.442 as its efficiency index. This index of efficiency is not optimal in the sense of Kung-Traub hypothesis. Therefore, in order to improve the index of efficiency and make (1) optimal, we consider the following iteration:(2)yn=xn-βf(xn)2f(wn)-f(xn),x0given,xn+1=xn-βf(xn)3[f(wn)-f(xn)][f(xn)-f(yn)-(f(yn)2)/f(wn)],whereinwn=xn+βf(xn) and β∈ℝ∖{0}. If we use divided differences and define f[xn,wn]=(f(wn)-f(xn))/βf(xn), then a novel modification of Jain’s method (1) in a more simpler format than (2) can be obtained as follows:
(3)yn=xn-f(xn)f[xn,wn],x0given,xn+1=xn-f(xn)2f[xn,wn][f(xn)-f(yn)-(f(yn)2)/f(wn)],
where its convergence order and efficiency index are optimal. Theorem 1 illustrates this fact.Theorem 1.
Letα∈I be a simple zero of a sufficiently differentiable function f:I⊆R→R in an open intervalI. If x0 is sufficiently close to α, then the method defined by (3) has the optimal convergence order four using only three function evaluations.Proof.
We expand any terms of (3) around the simple zero α in the nth iterate where cj=f(j)(α)/j!, j≥1, and en=xn-α. Therefore, we have f(xn)=c1en+c2en2+c3en3+c4en4+O(en5). Accordingly by Taylor’s series expanding for the first step of (3), we get that
(4)yn=α+(β+1c1)c2en2+(-(2+βc1(2+βc1))c22+c1(1+βc1)(2+βc1)c3)c12en3+O(en4).
Now, we ought to expandf(yn) around the simple root by using (4). We have
(5)f(yn)=(1+βc1)c2en2+O(en3).
Note that throughout this paper we omit writing many terms of the Taylor expansions of the error equations for the sake of simplicity. Additionally, by providing the Taylor’s series expansion, in the second step of (3), we have
(6)f(xn)2f[xn,wn][f(xn)-f(yn)-f(yn)2/f(wn)]=en1+(1+βc1)c2(-(2+βc1)c22+c1(1+βc1)c3)c13en4+O(en5).
Using (4), (6), and the second step of (3), we attain
(7)en+1=xn+1-α=(1+βc1)c2((2+βc1)c22-c1(1+βc1)c3)c13en4+O(en5).
This shows that (3) is an optimal fourth-order derivative-free method with three evaluations per cycle. Hence, the proof is complete.Remark 2.
It should be remarked that if one usesyn=xn-(βf(xn)2)/(f(xn)-f(xn-βf(xn))) in (3), that is, another variant of Steffensen’s method by backward finite difference of order one, then a similar optimal quartical convergence method will be attained. To illustrate more, using this variant will end in
(8)yn=xn-f(xn)f[xn,wn],x0given,xn+1=xn-f(xn)2f[xn,wn][f(xn)-f(yn)-(f(yn)2)/f(wn)],
whereinwn=xn-βf(xn) with β∈ℝ∖{0} and its error equation is as follows:
(9)en+1=xn+1-α=(-1+βc1)c2((-2+βc1)c22+c1(1-βc1)c3)c13en4+O(en5).Therefore, we have given a modification of the well-known cubical Jain’s method with fourth convergence order by using the same number of evaluations as the Jain’s scheme, while the orders are independent to the free nonzero parameterβ. The derivative-free iterations (3) and (8) satisfy the Kung-Traub conjecture for constructing optimal high-order multipoint iterations without memory. This was the first contribution of this research.Remark 3.
Although we provide the sketch for the proofs of the main Theorems inℝ, the proposed Steffensen-type methods of this paper could be applied for finding complex zeros as well. Toward such a goal, a complex initial approximation (seed) is needed.
Now in order to improve the convergence rate and the index of efficiency more, we compute a Newton’s step as follows in the third step of a three-step cycle in which the first two steps are (3) with wn=xn+βf(xn) and β∈ℝ∖{0}:
(10)yn=xn-f(xn)f[xn,wn],x0given,zn=xn-f(xn)2f[xn,wn][f(xn)-f(yn)-(f(yn)2)/f(wn)],xn+1=zn-f(zn)f′(zn).
Obviously, (10) is an eighth-order method with five evaluations (four function and one first derivative evaluations) per full iteration to reach the efficiency index 81/5≈1.515. This index of efficiency is lower than that of (3). For this reason, we should approximate f′(zn) by a combination of the already known data, that is, in a way that the order of (10) stay at eight but its number of evaluations lessen from five to four. First, we consider that the new-appeared first derivative of the function at this step can be approximated as follows:
(11)f′(zn)≈f(zn)-ρf(xn)zn-xn+f(zn)-f(yn)zn-yn.
In fact, (11) is a linear combination of two divided differences in which the best choice of ρ is zero, to attain a better order of convergence. However, (11) with ρ=0 does not preserve the convergence rate of (10). As a result, the new three-step method up to now (by only using (11)) will be of order six which is not optimal. In order to reach the optimality, we use a weight function at the third step as well. Thus, we consider the following three-step family without memory of derivative-free methods with the parameter γ∈ℝ. Theorem 4 illustrates that (12) reaches the eighth-order convergence using only four function evaluations per full iteration to proceed
(12)yn=xn-f(xn)f[xn,wn],x0given,zn=xn-f(xn)2f[xn,wn][f(xn)-f(yn)-(f(yn)2)/f(wn)],xn+1=zn-f(zn)f(zn)/(zn-xn)+f[yn,zn][H(xn,wn,yn,zn)],
where wn=xn+βf(xn) and
(13)H(xn,wn,yn,zn)=1+(11+βf[xn,wn])(f(yn)f(xn))2+(2βf[xn,wn]+(βf[xn,wn])2)(f(yn)f(wn))3+f(zn)f(wn)+γ(f(zn)f(yn))2.
By combining these two ideas, that is, an approximation of the new-appeared first derivative in the last step and a weight function, we have furnished a novel family of iterations.Theorem 4.
Letα∈I be a simple zero of a sufficiently differentiable function f:I⊆R→R in an open intervalI. If x0 is sufficiently close to α, then the method defined by (12) has the optimal local convergence order eight.Proof.
Using the same definitions and symbolic computations as done in the Proof of Theorem1, results in
(14)f(zn)=(1+βc1)c2((2+βc1)c22-c1(1+βc1)c3)c12en4+⋯+O(en9).
We also obtain by using (5) and (14) that(15)H(xn,wn,yn,zn)=1+(1+βc1)c22c12en2+(-(4+βc1(5+2βc1))c23+c1(1+βc1)(3+2βc1)c2c3)c13×en3+⋯+O(en9).
Note that the whole of such symbolic computations could be done using a simple Mathematica code as given in Algorithm1.
Additionally, applying (14) and (15) in the last step of (12) results in the following error equation:
(16)en+1=-1c17(1+βc1)c2(-(2+βc1)c22+c1(1+βc1)c3)×((3-4γ+βc1(4+βc1)(2-γ+βc1))c24+c1(1+βc1)(-3+4γ+β(-3+2γ)c1)c22c3-γc12(1+βc1)2c32+c12(1+βc1)2c2c4(3-4γ+βc1(4+βc1)(2-γ+βc1))c24)en8+O(en9).
This ends the proof and shows that (12) is an optimal eighth-order family using four function evaluations per iteration.Algorithm 1:The Mathematica code for finding the asymptotic error constant in Theorem 4.
C
lear[“Global’*”]
(
*
Assuming
e
=
x
-
α
and
c
j
=
(f
∧
(j)  (α))/j!,forj=1,2,…,8*)
f[e_]∶=c1*e  +  c2*e∧2  +  c3*e∧3  +  c4*e∧4  +  c5*e∧5  +  c6*e∧6  +  c7*e∧7  +  c8*e∧8;
(
*
Assuming  b=w  -  α*)
fe  =  f[e];  b  =  e+β  fe;  fw  =  f[b];  d  =  (fw-fe)/(β  fe);
(
*
Assuming  u = y - α*)
u = e-Series[fe/d,  {e,  0,  8}]//Simplify;
(*Assuming  v = z - α*)
f
u
=
f
[
u
];  v=e-((fe2)/(d*(fe-fu-(fu2)/fw)))//Simplify;
fv
=
f
[
v
];  fyz=(fu-fv)/(u-v);
(*Assuming  e1=  Subscript[x,  new]-α*)
e
1
=
v
-
(
fv
/
(
fv
/
(
v
-
e
)
+
fyz
)
)
*
(
1
+
(
1
/
(
1
+
β
d
)
)
(
fu
/
fe
)
∧2
+(2βd+(βd)∧2)(fu/fw)∧3+fv/fw+γ(fv/fu)∧2)//FullSimplifyRemark 5.
The index of efficiency for (3) and (8) is 41/3≈1.587 and for (12) is 81/4≈1.682, which are optimal according to the conjecture of Kung and Traub.A question might arise that how the weight functions in (12) were chosen to attain as high as possible convergence order with as small as possible number of functional evaluations. Although we have tried to suggest a simple family of iterations in (12), the weight function should be chosen generally in what follows:
(17)yn=xn-f(xn)f[xn,wn],x0given,zn=xn-f(xn)2f[xn,wn][f(xn)-f(yn)-(f(yn)2)/f(wn)],xn+1=zn-f(zn)f(zn)/(zn-xn)+f[yn,zn]×[G(f(yn)f(xn))+H(f(yn)f(wn))+L(f(zn)f(wn))],
where wn=xn+βf(xn) and G(f(yn)/f(xn)), H(f(yn)/f(wn)), L(f(zn)/f(wn)) are three weight functions that satisfy the following:
(18)G(0)=1-H(0)-L(0),(19)G′(0)=G′′(0)=G′′′(0)=0,|G(4)(0)|<∞,H′(0)=0,H′′(0)=2+2βf[xn,wn],H′′′(0)=6βf[xn,wn](2+βf[xn,wn]),|H(4)(0)|<∞,L′(0)=1,
to read the following error equation:
(20)en+1=124c17(1+βc1)c22(-(2+βc1)c22+c1(1+βc1)c3)×(+(1+βc1)4G(4)(0)+H(4)(0))72c1(1+βc1)2c2c3-24c12(1+βc1)2c4+c23(H(4)(0)-24(1+βc1)(3+βc1(5+βc1))+(1+βc1)4G(4)(0)+H(4)(0)))en8+O(en9).


## 3. Numerical Reports

The objective of this section is to provide a robust comparison between the presented schemes and some of the already known methods in the literature. For numerical reports here, we have used the second-order Newton’s method (NM), the quadratical scheme of Steffensen (SM), our proposed optimal fourth-order technique (3) with β=1 denoted by PM4, the optimal derivative-free eighth-order uni-parametric family of iterative methods given by Kung and Traub in [7] (KT1) with β=1, and our presented novel derivative-free eighth-order family (12) with γ=0 and β=1 denoted by PM8. Due to similarity of (3) and (8), we just give the numerical reports of (3). The considered nonlinear test functions, their zeros, and the initial guesses in the neighborhood of the simple zeros are furnished in Table 1.Table 1
The test functions considered in this study.
Test functions
Zeros
Initial guesses
f
1
(
x
)
=
3
x
+
sin
(
x
)
-
e
x
α
1
≈
0.360421702960324
x
0
=
0.5
f
2
(
x
)
=
sin
(
x
)
-
0.5
α
2
≈
0.523598775598299
x
0
=
0.3
f
3
(
x
)
=
x
e
-
x
-
0.1
α
3
≈
0.111832559158963
x
0
=
0.2
f
4
(
x
)
=
x
3
-
10
α
4
≈
2.15443490031884
x
0
=
1.7
f
5
(
x
)
=
10
x
e
-
x
2
-
1
α
5
≈
1.679630610428450
x
0
=
1.4
f
6
(
x
)
=
cos
(
x
)
-
x
α
6
≈
0.739085133215161
x
0
=
0.3The results are summarized in Table2 after three full iterations. As they show, novel schemes are comparable with all of the famous methods. All numerical instances were performed using 700 digits floating point arithmetic. We have computed the root of each test function for the initial guess x0. As can be seen, the obtained results in Table 2 are in harmony with the analytical procedure given in Section 2.Table 2
Results of comparisons for different methods after three iterations.
Absolute value off
NM
SM
PM4
KT1
PM8
|
f
1
(
x
3
)
|
0.6
e
-
9
0.1
e
-
4
0.1
e
-
43
0.4
e
-
325
0.4
e
-
328
|
f
2
(
x
3
)
|
0.1
e
-
9
0.5
e
-
8
0.7
e
-
59
0.9
e
-
462
0.4
e
-
478
|
f
3
(
x
3
)
|
0.6
e
-
8
0.3
e
-
6
0.1
e
-
51
0.7
e
-
391
0.1
e
-
391
|
f
4
(
x
3
)
|
0.3
e
-
3
0.4
0.2
e
-
170
0.1
e
-
167
0.6
e
-
186
|
f
5
(
x
3
)
|
0.7
e
-
5
0.1
e
-
1
0.1
e
-
38
0.1
e
-
75
0.3
e
-
216
|
f
6
(
x
3
)
|
0.3
e
-
6
0.1
e
-
8
0.6
e
-
98
0.1
e
-
476
0.2
e
-
623The proposed optimal fourth-order modification of Jain’s method performs well in contrast to the classical one-step method. We should remark that, in light of computational complexity, our constructed derivative-free family (12) is more economic, due to its optimal order with only four function evaluations per full cycle.In light of the classical efficiency index for the without memory methods which have compared in Table2, we have NM and SM that possess 1.414; (3) reaches 1.587, while (KT1) and (12) reach 1.682.An important aspect in the study of iterative processes is the choice of a good initial approximation. Moreover, it is known that the set of all starting points from which an iterative process converges to a solution of the equation can be shown by means of the attraction basins.Thus, we have considered the initial approximations close enough to the sought zeros in numerical examples to reach the convergence. A clear hybrid algorithm written in Mathematica [11] has recently been given in [12] to provide robust initial guesses for all the real zeros of nonlinear functions in an interval. Thus, the convergence of such iterative methods could be guaranteed by following such hybrid algorithms for providing robust initial approximations.In what follows, we give an application of the new scheme in Chemistry [13].Application. An exothermic first-order, irreversible reaction, A→B, is carried out in an adiabatic reactor. Upon combining the kinetic and energy-balance equations, the following equation is obtained for computing the final temperature T in K:
(21)f(T)=1T2e21000/T-1.11×1011=0,
where the temperature T is in K. The following logarithmic transformation improves the scaling of the problem, giving f(T)=2TlnT+25.432796T-21000=0. This nonlinear equation has only one real root. A starting point of zero for T is not feasible; instead, we arbitrarily select T0=400 K. The results are given in Table 3, when, for example, 7(0.1e-264) stands for 7 iterations while the absolute value of the function would be 0.1e-264. The true solution is 551.77382545730271467….Table 3
Results of comparisons for different methods in solvingf(T)=0.
Methods
NM
SM
PM4
KT1
PM8
|
f
|
7(0.1e-264)
8(0.7e-171)
4(0.2e-220)
3(0.1e-462)
3(0.5e-467)In the next section, we investigate the beauty of such zero-finder iterative methods in the complex plane alongside obtaining the fractal behavior of the schemes.


## 4. Finding the Basins

The basin of attraction for complex Newton’s method was first considered and attributed by Cayley [14]. The concept of this section is to use this graphical tool for showing the basins of different methods. In order to view the basins of attraction for complex functions, we make use of the efficient computer programming package Mathematica [15] using double precision arithmetic. We take a rectangle D=[-4,4]×[-4,4]∈ℂ and we assign the light to dark colors (based on the number of iterations) for z0∈D (for each seed) according to the simple zero at which the corresponding iterative method starting from z0 converges. See, for more details, [16, 17].The Julia set will be denoted by white-like colors. In this section, we consider the stopping criterion for convergence to be|f|<10-2 with a maximum of 30 iterations and with a grid 400 × 400 points. In fact, the colors we used are based on Figure 1.Figure 1
The distribution of colors.We compare the results of Steffensen’s method withβ=0.01, the third-order method of Jain, the quartical convergent method (3) for two values β=0.01 and β=0.0001 in Figures 2, 3, 4, 5, and 6 for the polynomials p1(z)=z2+1, p2(z)=z3+1, p3(z)=z4+1, p4(z)=z5+1, and p5(z)=z6+1 wherein their simple solutions are {0.-1.ⅈ,0.+1ⅈ}, {-1.,0.5-0.866025.ⅈ,0.5-0.866025.ⅈ}, {-0.707107-0.707107ⅈ,-0.707107+0.707107ⅈ,0.707107-0.707107ⅈ,0.707107+0.707107ⅈ}, {-1.,-0.309017-0.951057i,-0.309017+0.951057i,0.809017-0.587785i,0.809017+0.587785i}, and {-0.866025-0.5i,-0.866025+0.5i,0.-1.i,0.+1.i,0.866025-0.5i,0.866025+0.5i}, respectively. We do not invite optimal eighth order methods due to their large basins of attraction (their order is high).Fractal behavior for the rational function associated to the Steffensen’s method withβ=0.01 (a), Jain’s method (b), (3) with β=0.01 (c) and (3) with β=0.0001 (d) for f:z→z2+1. Shading according to the number of iterations.
(a)
(b)
(c)
(d)Fractal behavior for the rational function associated to the Steffensen’s method withβ=0.01 (a), Jain’s method (b), (3) with β=0.01 (c) and (3) with β=0.0001 (d) for f:z→z3+1. Shading according to the number of iterations.
(a)
(b)
(c)
(d)Fractal behavior for the rational function associated to the Steffensen’s method withβ=0.01 (a), Jain’s method (b), (3) with β=0.01 (c) and (3) with β=0.0001 (d) for f:z→z4+1. Shading according to the number of iterations.
(a)
(b)
(c)
(d)Fractal behavior for the rational function associated to the Steffensen’s method withβ=0.01 (a), Jain’s method (b), (3) with β=0.01 (c) and (3) with β=0.0001 (d) for f:z→z5+1. Shading according to the number of iterations.
(a)
(b)
(c)
(d)Fractal behavior for the rational function associated to the Steffensen’s method withβ=0.01 (a), Jain’s method (b), (3) with β=0.01 (c) and (3) with β=0.0001 (d) for f:z→z6+1. Shading according to the number of iterations.
(a)
(b)
(c)
(d)As was stated in [18–20], known derivative-free schemes do not verify a scaling theorem, so the dynamical conclusions on a set of polynomials cannot be extended to others of the same degree polynomials and they are only particular cases. Indeed, comparing the behavior of the methods analyzed in those papers with the dynamical planes obtained in this paper, it is clear that the introduction of the parameter β plays an important role in the analysis.Note that considering tighter conditions on our written codes may produce pictures with much more quality than these. In Figures2–6, darker blue areas stand for low number of iterations, darker blue needs more number of iterations to converge, and red areas mean no convergence or a huge number of iterations is needed.Based on Figures2–6, we can see that the method of (3) with β=0.0001 is the best method in terms of less chaotic behavior to obtain the solutions. It also has the largest basins for the solution and is faster than the other ones. This also clearly shows the significance of the free nonzero parameter β. In fact, whenever β is lower (is close to zero), the larger basin along with less chaotic behavior could be attained.In order to summarize these results, we have attached a weight to the quality of the fractals obtained by each method. The weight of 1 is for the smallest Julia set and a weight of 4 for scheme with chaotic behaviors. We then averaged those results to come up with the smallest value for the best method overall and the highest for the worst. These data are presented in Table4. The results show that (3) with β=0.0001 is the best one.Table 4
Results of chaotic comparisons for different derivative-free methods.
Method
p
1
(
x
)
p
2
(
x
)
p
3
(
x
)
p
4
(
x
)
p
5
(
x
)
Average
Steffensen's method withβ=0.01
1
1
3
4
4
13/4
Jain's method
3
2
4
4
4
17/4
(3) with β=0.01
2
2
3
4
4
15/4
(3) with β=0.0001
2
2
2
2
2
10/4


## 5. Concluding Remarks

Many problems in scientific topics can be formulated in terms of finding zeros of the nonlinear equations. This is the reason why solving nonlinear equations or systems are important. In this work, we have presented some novel schemes of fourth- and eighth-order convergence. The fourth-order derivative-free methods possess 1.587 as their efficiency index and the eighth-order derivative-free methods have 1.682 as their efficiency index. Per full cycle, the proposed techniques are free from derivative calculation. We have also given the fractal behavior of some of the derivative-free methods along some numerical tests to clearly show the acceptable behavior of the new scheme. We have concluded thatβ has a very important effect on the convergence radius and the speed of convergence for Steffensen-type methods. With memorization of the obtained fourth- and eighth orders families could be considered for future studies.



---

*Source: 301718-2013-04-21.xml*