\(^\ast \)Naval Postgraduate School, Department of Applied Mathematics, Monterey, CA 93943; e-mail: bneta@nps.edu, Tel.: 1 (831) 656-2235, Fax: 1 (831) 656-2355.

1 Introduction

In engineering and applied science we encounter the problem of solving a nonlinear equation \(f(x)=0.\) Most numerical solution techniques are based on Newton’s method, i.e., starting with an initial guess \(x_0\) for the root \(\xi \), we create a sequence \(\{ x_n\} \)

The convergence is quadratic, that is

and 2 is the largest with such property. In general, we say that a method is of order \(p\) if

and \(p\) is the largest with such property.

The vast literature (see Traub [ 20 ] and the more recent book by Petković et al. [ 12 ] ) for the numerical solution of a single nonlinear equation include relatively few derivative-free methods. The methods are multistep with Steffensen’s method [ 17 ] as first step. See, Khattri and Steihaug [ 7 ] , Soleymani and Shateyi [ 15 ] , Soleymani and Vanani [ 16 ] , Thukral [ 19 ] , Zheng et al. [ 23 ] , Veiseh et al. [ 21 ] , Sharma and Goyal [ 14 ] , Chicharro et al. [ 1 ] , Cordero and Torregrosa [ 5 ] , Petković et al. [ 11 ] , Peng et al. [ 9 ] and Zhanlav and Otgondorj [ 22 ] . Such methods are especially useful when the derivative is very expensive and, of course, when the function is non-differentiable.

The methods are of order \(p\) using \(d\) function evaluations per step. Kung and Traub [ 8 ] conjectured that multipoint methods without memory using \(d\) evaluations could have order no larger than \(2^{d-1}\). The efficiency index \(I\) defined as \(p^{1/d}\). Thus an optimal method of order 8 has an efficiency index of \(I=8^{1/4}=1.6817\) and an optimal method of order 4 has an efficiency index \(I=4^{1/3}=1.5874\) which is better than Newton’s method for which \(I=\sqrt{2}=1.4142\). The efficiency index of optimal method cannot reach a value of 2. In fact realistically one uses methods of order at most 8. There are one step methods that converge super-linearly with \(p=1.618\) such as the secant method and \(p=1.839\). These one step methods require one function evaluation per step (except that they require additional starting value(s)). Therefore the efficiency index is 1.618 (secant) and 1.839. Here we will list the one-step methods along with their order of convergence. We will compare the basin of attraction of the methods and suggest a multistep method that is almost optimal but having higher efficiency index (because it uses one less function evaluation). We measure the behavior on 5 functions, 4 of which are polynomials. It was demonstrated by Petković and Herceg [ 10 ] that the conclusions are the same even if we take more examples.

The basin of attraction method was initially discussed by Stewart [ 18 ] . This is better than comparing methods on the basis of running several nonlinear functions using a certain initial value. In the last decade many papers appeared using the idea of basin of attraction to compare the efficiency of many methods. See, for example, Chun and Neta [ 2 ] , [ 3 ] and references there.

The paper is organized in the following way: In the next section, we will describe several super linear and one quadratic derivative-free methods. In section 3, we compare the methods using the idea of basins of attraction. Section 4 details our new derivative-free method of order 6.219 and in section 5 we study its dynamics and compare it to a certain eighth-order derivative-free method. We close with conclusions.

2 Super-linear derivative-free schemes

In this section, we describe the following derivative-free methods in the literature:

1. Secant Method (\(p=1.618\))

2. Three Traub’s Methods (\(p=1.839\))

3. Jarratt and Nudds’ method (\(p=1.839\))

4. Popovski’s method (\(p=1.839\))

5. Steffensen’s method (\(p=2\))

Secant Method Given \(f(x)\) and \( x_0, x_1\) be 2 initial guesses for the root \(\xi \), then

where \(f_k=f(x_k).\)

This algorithm is similar to Regula Falsi. The order of convergence is 1.618 and the method requires one function evaluation per iteration. thus the efficiency index \(I = 1.618\). Geometrically, the method approximates the slope of \( f(x_n)\) by using the secant line via the points \( (x_n,f_n)\) and \( (x_{n-1},f_{n-1})\).

Traub methods ( [ 20 ] )

1. The first method denoted Traub1 (Method 7a on page 234) is:

   \begin{equation} x_{n+1} = x_n -\frac{f_n}{ \frac{(f_{n-2}-f_{n-1})+(f_{n-1}-f_n)}{(x_{n-2}-x_{n-1})+(x_{n-1}-x_n)} - \frac{f_{n-2}-f_{n-1}}{x_{n-2}-x_{n-1}} + \frac{f_{n-1}-f_n}{x_{n-1}-x_n}} \label{Traub1} \end{equation}

   2

2. The second method denoted Traub2 (Method 5a on page 233) is:

   \begin{equation} x_{n+1} = x_n - \left[ \tfrac {(x_{n-2}-x_{n-1})+(x_{n-1}-x_n)} {(f_{n-2}-f_{n-1})+(f_{n-1}-f_n)} - \tfrac {x_{n-2}-x_{n-1}} {f_{n-2}-f_{n-1}} + \tfrac {x_{n-1}-x_n}{f_{n-1}-f_n} \right] f_n \label{Traub2} \end{equation}

   3

3. The third method denoted Traub3 (Method 2a on page 233) is given by:

   \begin{equation} x_{n+1} = x_n + \Big\{ \left[ \tfrac {x_n - x_{n-1}}{f_n - f_{n-1}} - \tfrac {x_{n-1} - x_{n-2}}{f_{n-1} - f_{n-2}} \right] \tfrac {f_{n-1}} {f_n - f_{n-2}} - \tfrac {x_n - x_{n-1}}{f_n - f_{n-1}} \Big\} f_n. \label{Traub3} \end{equation}

   4

   All three Traub’s methods have order and efficiency index of 1.839 (see [ 20 , p. 233 ] ).

Jarratt and Nudds

Jarratt and Nudds [ 6 ] developed a method based on the rational interpolating function

using the last three points \( (x_i,f_i), \quad i = n-2,n-1,n\) as data. Thus the method

The rate of convergence of the method and the efficiency are 1.839.

Popovski’s method

Popovski [ 13 ] used the same interpolating function as Jarratt and Nudds [ 6 ] to derive the following method of order 1.839. The method is referred to as the method of tangential hyperbolic approximation.

The efficiency index of the method is \(I = 1.839\).

Steffensen’s family of methods

Steffensen’s method [ 17 ]

The method converges quadratically and uses two function-evaluation. Therefore its efficiency index is 1.4142 as Newton’s method. This is the reason that higher order derivative-free methods use the method as a first step.

3 Dynamics study of the methods

In this section, we describe the experiments with each of the 7 methods detailed above. We chose 4 polynomials and one non-polynomial function all having roots within a 6 by 6 square centered at the origin. The square is divided horizontally and vertically by equally spaced lines. We took the intersection of all these lines as initial points in the complex plane for the iterative schemes. The code collected the number of iteration or function evaluation to converge within a tolerance of \(10^{-7}\) and the root to which the sequence converged. If the sequence did not converge within 40 iteration, we denote it as a divergent point. Each point is colored by the color corresponding to the root. A divergent point is colored black. We also collected the CPU run time to execute the code on all initial points using Dell Optiplex 990 desktop computer.

We ran all methods on the following 5 examples, 4 of which are polynomials:

1. \(z^2-1\)

2. \(z^3-1\)

3. \(z^4-1\)

4. \(z^5-1\)

5. \(\left(e^{z+1}-1\right)(z-1)\)

Example 2

The first example is

\begin{equation} p_1(z)=z^2-1, \label{example1} \end{equation}

8

vanishing at \(z=\pm 1\). The basins for all methods are given in figure 1. Clearly from the figure one can see that the best schemes are secant, Traub1 and Jarratt-Nudds methods.

From table 1, the average number of function-evaluations per point is minimum (5.82) for Traub1 followed by Jarratt-Nudds (5.86). The highest number (11.75) was used by Traub2.

The CPU runtime in seconds, see table 2, is the lowest for secant method (115.423) followed by Traub1 (122.283). The slowest is Traub2 with 227.337 seconds.

The secant method has no divergent point (see table 3) and Popovski has only 1 point. Traub2 has the highest number of divergent points (52648), which is unacceptable. â–¡

Method	Ex1	Ex2	Ex3	Ex4	Ex5	average
Secant	7.78	11.5	16.65	17.35	6.85	12.02
Traub1	5.82	6.97	8.88	9.62	6.52	7.56
Traub2	11.75	17.70	22.34	21.15	9.26	16.44
Traub3	7.10	10.32	15.64	16.35	6.64	11.21
Steffensen	5.78	7.93	10.84	17.47	5.28	9.46
Popovski	5.87	7.13	8.84	9.23	5.86	7.39
JN	7.32	9.79	13.24	13.98	7.28	10.32
TZKO	11.85	19.52	25.60	29.26	12.25	19.70
Neta	10.54	10.91	13.13	13.79	9.10	11.49

Method	Ex1	Ex2	Ex3	Ex4	Ex5	average
Secant	115.423	215.15	373.899	418.568	154.492	255.506
Traub1	122.283	183.568	252.397	328.295	195.38	216.385
Traub2	227.337	394.5	590.03	584.702	217.026	402.719
Traub3	170.923	287.784	508.552	557.584	245.495	354.068
Steffensen	111.546	224.375	306.197	545.721	174.007	272.370
Popovski	154.366	272.019	392.188	482.016	212.037	302.525
JN	156.286	221.251	304.169	425.87	196.356	260.786
TZKO	290.886	545.869	621.265	745.541	334.541	507.620
Neta	231.431	311.934	368.234	452.034	282.761	329.279

Method	Ex1	Ex2	Ex3	Ex4	Ex5	average
Secant	0	14605	62225	64895	139	28375
Traub1	601	2	203	1054	809	534
Traub2	52648	110398	156658	133868	27955	96305
Traub3	61	11034	58766	68535	34	27686
Steffensen	2	6188	27514	95107	997	25962
Popovski	197	25	1771	3464	8	1093
JN	1	645	6305	11911	5180	4808
TZKO	2364	16674	27745	33419	2640	16568
Neta	2930	0	0	1	901	766

Example 3

The cubic polynomial

\begin{equation} p_2(z)=z^3-1, \label{example2} \end{equation}

9

having the 3 roots of unity. Figure 2 shows that the best schemes are again Traub1 and Jarratt-Nudds methods.

The average number of function-evaluations per point (table 1) is minimum (6.97) for Traub1 followed by Popovski (7.13). The highest number (17.70) was used by Traub2.

Based on the CPU time in seconds, we find that the fastest method is Traub1 (183.568 seconds) followed by secant method (215.15 seconds). The slowest is Traub2 with 394.5 seconds.

Traub1 (see table 3) has the lowest number (2 divergent points), followed by Popovski (25 points). â–¡

Example 4

The third example is a quartic polynomial

\begin{equation} p_3(z)=z^4-1 \label{example3} \end{equation}

10

and the roots are just the four roots of unity. Figure 3 shows that the best schemes are again Jarratt-Nudds and Traub1 methods.

The minimum average number of function-evaluations per point (table 1) is 8.84 for Popovski followed closely by Traub1 (8.88). The highest number (22.34) was for Traub2.

Based on the CPU execution time in seconds, we find again that the fastest method is Traub1 (252.397 seconds) and the slowest is again Traub2 with 590.03 seconds.

Traub1 has the lowest number of black points (see Table 3). Again Traub2 has the highest number of divergent points (156658). â–¡

Example 5

The fourth example is a fifth degree polynomial

\begin{equation} p_4(z)=z^5-1. \label{example4} \end{equation}

11

Figure 4 indicates that the best scheme is Jarratt-Nudds method.

Based on table 1 the minimum average number of function-evaluations per point is 9.23 for Popovski followed by Traub1 with 9.62.

Based on the CPU time in seconds, we find again that the fastest method is Traub1 (328.295 seconds). The slowest is again Traub2.

In terms of the number of black points (see table 3) we find again that Traub1 has the lowest number (1054 points) and the highest is Traub2 (133868 points). â–¡

Example 6

The last example is a non-polynomial example.

\begin{equation} F_1(z)=(e^{z+1}-1)(z-1). \label{example5} \end{equation}

12

Figure 5 indicates an interesting phenomenon. The basin for \(z=-1\) is much larger than the other. It seems that the best scheme is Jarratt-Nudds method, even though Traub1 give slightly more equitable division of the basins.

The minimum average number of function-evaluations per point (see table 1) is 5.28 for Steffensen’s method followed closely by Popovski with 5.86. This is the first time that Steffensen’s method came at the top. The highest number (9.26) for Traub2.

The CPU runtime in seconds (table 2) is the lowest for secant (154.492 seconds), followed by Steffensen’s method with 174.007 seconds. The slowest is now Traub3.

Popovski’s method has the lowest number (8) of divergent points, followed by Traub3 (34). The highest is Traub2 (27955 points). â–¡

We now averaged the results across the five examples and find the top three methods in each category. Based on table 1 the order is Popovski, Traub1 and Steffensen. In terms of CPU time: Traub1, Secant, Jarratt-Nudds method. The lowest number of divergent points is for Traub1 followed by Popovski and Jarratt-Nudds. Therefore we find the Traub1 is the only method in the top three in all three categories. As a results, we have decided to try and develop a method (of order 6.219) based on Traub1 as first step instead of Steffensen’s method. The new method is of order \(p=1.839^3=6.219\) and uses only 3 function evaluations per cycle. Therefore the efficiency index is \(I=6.219^{1/3}=1.839\) which is higher than the optimal eighth order method. This is possible for methods with memory.

In the next section, we will develop the new scheme and discuss the order and efficiency index. The section after that will compare the basins for our new method to an optimal eighth order method due to Zhanlav and Otgondorj.

4 New method

We now develop a 3-step method having Traub1 method as first step instead of Steffensen. The method is

As usual, we approximate the derivatives in the last two steps by an interpolating polynomial, in this case, using the last 3 function values,

where

and

where

This method uses memory, the point \(x_{n-1}\) in the second step. The order of the method is the product of the orders \(p=1.839^3=6.219\), see [ 20 ] Theorem 2.4. We arrived at this by using the fact that each step uses the values of \(f\) at the current and two previously computed values, and it is known that in that case the order is 1.839. Clearly this is not optimal. The efficiency index is \(I=6.219^{1/3}=1.839\). This is better than the optimal eighth-order method (denoted TZKO) without memory of [ 22 ] .

We now refer to Table 4 showing the computational order of convergence as defined by

where \(nexx\) is the final approximation for the zero.

5 Dynamics of our new method

We ran the same five examples from the numerical experiments section above on our new method (Neta) and compared it to TZKO [ 22 ] . The results are given in the previous figures as the last two sub figures and in tabl1tabl3. The average over all 5 examples of the average number of function evaluation is 12.132 versus 18.382 for TZKO. Our new method is much faster 329.279 seconds versus 507.620 second for TZKO. The number of divergent point on average over all examples is 766.4 for our method versus 16568.4 for TZKO. We can conclude that our method is better than the optimal method of Zhanlav and Otgondorj.

Conclusions

We have considered several derivative free super linear methods and compared them to the quadratic method due to Steffensen. We found that one of Traub’s method, namely Traub1, performed best on the five examples. We then developed a new method with memory based on Traub1 method as first step and we showed that our method is faster, have much less divergent points and require less iteration per initial point.