\(^\bullet \)Institute of Mathematics and Digital Technology, Mongolian Academy of Sciences, Mongolia e-mail: tzhanlav@yahoo.com.

\(^\ast \)School of Applied Sciences, Mongolian University of Science and Technology, Mongolia e-mail: otgondorj@gmail.com.

1 Introduction

At present there exist many optimal derivative-free three-point iterations see, for example, [ 1 - 3 , 5 - 9 - and references therein. They mainly distinguished among themselves by approximations of \(f'(z_n)\) at the last step. Let the values of \(f(x)\) be known at points \(x_n\), \(w_n\), \(y_n\) and \(z_n\). Often the following three approaches are used for approximation \(f'(z_n)\). The most preferred approximation (see [ 1 ] , [ 6 , 7 , 9 ] , [ 14 ] ) is

where \(N_3(z)\) is Newton’s interpolation polynomial of degree three at the point \(x_n,\) \(w_n,\) \(y_n\) and \(z_n\). The second approach is [ 5 ]

The real constants \(\nu _1,\) \(\nu _2,\) \(\nu _3\) and \(\nu _4\) are determined such that the relation (2) holds with equality for the four functions \(f(x)=1\), \(x\), \(x^2\), \(x^3.\) While in [ 13 ] was used the approximation

The real constants \(a, b, c\) and \(d\) in (3) are determined such that the equality (3) holds with accuracy \(\mathcal{O}(f(x_n)^4).\) Note that in last years have been appeared papers, in which were used another approximations such as Pade approximant [ 3 ] and rational approximations [ 2 ] and so on. As we seen from (1), (2) and (3) more suitable and guaranteed approximation is (3). In general, all these three approaches turn out to be identical. This is well-known long ago fact [ 16 ] . This idea motivated us to make detail comparison of methods based on (1), (2) and (3). Note that the detail comparison of optimal three-point methods was made in [ 4 ] and such comparison for optimal derivative-free methods is still needed. The paper organized as follows. In section 2 we consider some methods based on the approximations (1), (2), (3) and made comparison of them. We obtain the sufficient convergence condition for these families in section 3. Numerical and visual comparison some optimal derivative-free methods are made in section 4.

2 Some methods based on the approximation (1), (2) and (3)

The well-known Zheng et al. [ 14 ] methods (Z8) based on (1) and has a form

where \(F=(z_n-x_n)f[z_n,y_n,x_n,w_n]\). Based on (2) the well-known Khattri et al. [ 5 ] methods (KS8) has the following form:

Here

In [ 5 ] , the authors pointed out that these methods given by (5), (6) is similar to the already known methods proposed in [ 1 , 6 , 7 , 9 ] , in particular to method in [ 14 ] , however, they are not the same methods. From (4) and (5) we see that the second and third substeps in (5) are much complicated as compared with (4). The formula, requiring many mathematical operations absolutely unfitted for numerical and stability points of view. Hence, the formula (5) needed further simplifications. The families of derivative-free optimal methods proposed in [ 13 ] are based on (3) and have a form

where

and

with

We call the representation (7) of three-point methods as canonical form. Each derivative-free three-point methods, in particular the methods (4) and (5) can be written in canonical form uniquely. Note that all the considered methods (4), (5) and (7) are optimal in the sense of Kung and Traub [ 17 ] . So they has an efficiency index \(8^{1/4}\approx 1.68179 \). The methods (4) and (5) contain one free parameter \(\gamma \), whereas the methods (7) contain, in addition \(\gamma \), yet four parameter \(c\), \(d\), \(b\) and \(w\). Hence, in our opinion, the families (7) represent a wide class of optimal three-point methods. Our aim is to compare the above mentioned methods in detail. First, we will show that the optimal derivative-free methods (4) and (5) are identical. Namely, we obtain

the second-step in (4) and (5) can be easily rewritten as

where

Thus, the first two sub-steps of (4) and (5) are the same. In passing, we obtain very simple calculation formula (12) for iteration method (5). It remains to compare the third sub-steps in (4) and (5). The third sub-steps in (4) and (5) can be rewritten as

where

for iteration (4) and

for iteration (5). Using the following relations

one can write (14) as:

where \(Q=\frac{\tau _n(3\tau _n-2)+\gamma \phi _n(2\tau _n-1)}{\tau _n(\tau _n-1)(\tau _n+\gamma \phi _n)}.\) In a similar way, using (16), the expression (15) can be easily rewritten as (17). Thus, the third-step of (4) and (5) also coincide with each other.

Therefore, the iterations (4) and (5) are identical.

Therefore, the iterations (4), (5) and (7) can be written in more convenient and unified form as:

where \(\bar{\tau }_n\) is given by (8) for (7) and is given by (13) for (4) and (5). When \(c=1\), \(d=-\hat{d}_n\) and \(\omega =b=0\) in (8), \(\bar{\tau }_n\) coincides with (12). In this case the iterations (4) and (5) and (18) are identical. So our iterations (7) contain the methods (4) and (5) as particular cases. In addition, the iterations (18) contain some well-known iterations as particular cases (see Table 1).

Later on, we denote the method (18) with \(c=1\), \(d=-\hat{d}_n\), \(b=-\frac{1}{1+\gamma \phi _n}\) and \(\omega =0\) by M1. These parameters are chosen to have a large region of convergence and a big basin of attraction for family 18.

Moreover, the iteration (18) can be rewritten as

where \(\psi _4\) is any optimal fourth order derivative-free method. From (19) we see that the each iteration of the family of derivative-free optimal three-point iterations (19) essentially depends on the choice \(\psi _4\) or the choice of iteration parameter \(\bar{\tau }_n\) in (18).

3 Convergence analysis

Generally, the convergence properties of family of iterations (18) essentially depend on the convergence of iterations consisting of the first two sub-steps in (18) i.e.,

where \(\bar{\tau }_n\) is given by (8). It is easy to show that if the iterations (20) converge then its convergence order is four. Moreover, if the iterations (20) converge, so does (18) with convergence order eight. From this clear that in order to establish the convergence of (18) it suffice to establish the convergence of iterations (20). To this end we use Taylor expansion of function \(f\in C^2(I)\) and another form of second-step in (20) as

As a result, we have

where

From (22) it follows

where

From (24) we see that the convergence of iterations (20) is expected only when

Thus, it suffice to find conditions for which (26) holds true. It is easy to prove that

and

in (25) we obtain

If we use (31) then the condition (27) can be written in term of \(\theta _n\) as (30) within the accuracy \(\mathcal{O}(f^2(x_n))\). In other words, (26) holds true under condition (30).

where

Let \(|\omega -b|{\lt}\hat{d}_n c\). Then \(\varphi (\theta _n){\gt}0\) on \(\theta _n\in [-1,1]\). Then from (32) we deduce that the following relations

are equivalent and the convergence of sequences \(f(z_n)\) and \(\theta _n\) to zero as \(n\rightarrow \infty \) expected simultaneously with equal order four. On the other hand, the iteration (20) can be considered as damped Newton’s method

with damping parameter \(\eta _n \) given by (30). As is known that, the damped Newton’s method converges [ 15 ] if

In term of \(\theta _n\) the condition (33) gives the same result (31).

4 Numerical experiments and dynamical behavior

In this section, we will give a numerical comparison of our method M1 with other well known optimal eighth order methods listed in table 1. For this purpose, we consider several test functions given in table 2. In particular, \(f_2=0\) is Kepler’s equation which relates the eccentric anomaly \(E\), the mean anomaly \(M\) and the eccentricity \(\epsilon \) in an elliptic orbit.

Additionally, we will make comparison of method M1 and other methods based on the dynamical behaviour.

Further, we will use the abbreviated names for methods (see last column of table 1). In ??, we consider method (CH8) using the weight function \(H(\theta _n)=1+(1-2\alpha )\theta _n\) with values of the parameter \(\alpha =0,\pm 1\) (see [ 1 ] ), method (L8) for \((a=0,\pm 1)\) and method (K8) for \((\beta =0,\pm 1)\). In addition to compare family (18) with other methods we also consider some optimal methods, which third substeps are different from method (18). Namely, we used the following substeps:

Derivative-free Soleymani et al. [ 11 ] three-step method (SV8) has the following substep:

Derivative-free Kung-Traub’s [ 17 ] three-step method (KT8) has the following substep:

Derivative-free Thukral’s [ 12 ] three-step method (T8) has the following sub-step:

Derivative-free Soleymani et al. [ 10 ] three-step method (SS8) has the following substep:

All computations are carried out using Maple18 computer algebra system with 1000 digits. We use the following stopping criterion for the methods:
\(|x_n-x^*|\leq \varepsilon \) where \(\varepsilon =10^{-50}\) and \(x^*\) is the exact solution of the considered equation. In all examples, we consider that the parameter \(\gamma =-0.01\).

To check the theoretical order of convergence of methods, we calculated the computational order of convergence \(\rho \) (see [ - ) using formula

where \(x_{n} , x_{n-1} , x_{n-2}\) are last three consecutive approximations in the iteration process. In ??, we use test functions \(f_1\), \(f_2\), \(f_3\) and exhibit the iteration numbers \(n\), the absolute value \(|x_{n}-x^*|\) and the computational order of convergence \(\rho \). When the iteration diverges for the considered initial guess \(x_0\), we denote it by \('-'\). From ?? we see that the convergence order of all the methods in table 1 confirmed by numerical experiments. From the result of ??, we can observe that the region of convergence of methods M1 and Z8 are wider than that of other considered methods.

Generally, higher order convergence methods consist of multi-steps which may use more evaluations of functions than the original one. In this case, multi-point methods may have the extraneous fixed points (black points). In order to find the extraneous fixed points, we rewrite any three–point method as [ 4 ] :

where \(H_f=1+\theta _n(\bar{\tau }_n+\alpha _n\upsilon _n)\). Clearly, the root \(x^*\) of \(f(x)\) is a fixed point of the method. The points \(\xi \neq x^*\) for which \(H_f(\xi )=0\) are also fixed points of the method. These fixed points are called extraneous fixed points. As we all know, a fixed point \(\xi \) is called:

• attractive if \(|R'(\xi )|{\lt}1,\)

• repulsive if \(|R'(\xi )|{\gt}1,\)

• parabolic if \(|R'(\xi )|=1,\)

where \(R(z)=z-\frac{f(z)}{f[z,w]}H_f(z)\) is the iteration function.

In addition, if \(|R'(\xi )|=0\), the fixed point is superattracting. Now, we will discuss the extraneous fixed points of each method for comparison. To make it easier , we have taken the simple quadratic polynomial \(p(z)=z^2-1\), whose roots are \(z=\pm 1\).

In table 5, we have collected the extraneous fixed points of the methods Z8, KS8, M1.Next nine methods are analyzed and found that they are unable to compare with other methods. These methods have more than \(20\) extraneous fixed points. Therefore, we have not include those results in table 5. For methods Z8 and KS8, we found that the methods have same ten extraneous fixed points. All fixed points are repulsive.

The basin of attraction of iterative methods is another tool for comparing them. Thus, we compare our methods 18 with other methods by using the basins of attraction for polynomials \(p(z)=z^3-1\).

To illustrate the behavior of the iterative methods, We take \(600 \times 600\) equally spaced points in the square \([-3, 3]\times [-3, 3]\subset C\). In figure 1, the basin of attraction for \(12\) methods are displayed. The red, green and blue colors are assigned for the attraction basin of the three zeros and the roots of function are marked with white points. Black color is shown lack of convergence to any of the roots. In this cases, the stopping criterion \(\varepsilon =10^{-4}\) and maximum of 25 iterations are used. These dynamical planes have been generated by using the Mathematica 11. From figure 1 and table 5, we can also see that methods M1 and Z8 is much more stable than the others. It can be observed from the figures that the methods M1 along with the existing methods Z8 have wide attraction basins to corresponding zeros than other methods. Z8 also has the least number of black points.

5 Conclusion

We have shown that the well-known Khattri et al. [ 5 ] methods and Zheng et al. [ 14 ] methods are identical. For the Khattri methods, we propose a suitable calculation formula (18) instead of (5). Our proposed method (18) represents wide class of optimal derivative-free iterations. The method (18) contain some well known iterations as particular cases (see table 1). The comparison of some eighth-order methods was made from the dynamic behavior of view. We observe that the methods M1 and Z8 are much more stable than the others. Note that the family of derivative-free methods (18) can be extended to the systems of nonlinear equations and this study is currently ongoing.

figuresection