1. Introduction

Multipoint iterative methods for solving nonlinear equations are of great practical importance since they overcome theoretical limits of one-point methods concerning the convergence order and computational efficiency. The new iterative methods are applied to find a simple root of the nonlinear equation

(1)

where is a scalar function on an open interval D and it is sufficiently smooth in a neighbourhood of α In this paper, a new family of four-point derivative-free methods of the optimal order eight are constructed by combining optimal two-step fourth-order methods and three-step eighth-order methods. In order to obtain these new sixteen order derivative-free methods, we replace derivatives with suitable approximations based on divided difference. In fact, it is well known that the various methods have been used in order to approximate the derivatives[1,2,12,16,17].

The prime motive of this study is to develop a class of very efficient four-step derivative-free methods for solving nonlinear equations. The sixteenth-order methods presented in this paper is derivative-free and only uses five evaluations of the function per iteration. In fact, we have obtained the optimal order of convergence which supports the Kung and Traub conjecture. Kung and Traub conjectured that the multipoint iteration methods, without memory based on n evaluations, could achieve optimal convergence order 2^n-1 Thus, we present new derivative-free methods which agree with the Kung and Traub conjecture for n=5 In addition, these new sixteenth-order derivative-free methods have an equivalent efficiency index to the recently established methods presented in[5,6]. Furthermore, the new sixteenth-order derivative-free methods have a better efficiency index than existing the two-step and three-step order derivative-free methods presented in[2,3,7,8,10-14,16,17,20] and, in view of this fact, the new methods are significantly better when compared with the established methods. Also, we have found that there is a typo error in[16], hence we shall show and use these eight order derivative-free methods to construct sixteen order methods. It should be noted that the eighth-order derivative-free methods presented in[16] are of optimal order and their order of convergence have been proved and shown in many examples. However, the typo errors actually occur in the weight functions of the eighth-order derivative-free methods in (2.27) and (2.32),[16]. Since these eighth-order derivative-free methods have been proved to converge of the order eight, we shall therefore use and simplify various expressions given in[16]. Consequently, we have found that the new sixteenth-order derivative-free methods are efficient and robust.

The paper is organized as follow. A new family of four-point derivative-free methods of optimal order sixteenth are constructed in the next section by combining two-point fourth-order methods and three-point eighth-order methods. The purpose of this paper is to obtain a suitable approximation of the derivatives of a function f in order to reduce the number of function evaluations. The total number of function evaluations of the proposed four-point derivative-free methods is five and according to the Kung-Traub conjecture is of the optimal order[9,18]. In section 3, we shall compare the effectiveness of the new methods with the recently introduced sixteenth-order methods[5,6]. Finally, in section 4, some computational aspects of the proposed four-point derivative-free methods and comparison with existing methods are also given.

2. Derivation of the Methods and Convergence Analysis

In this section we shall define new sixteenth-order derivative methods. In order to establish the order of convergence of these new derivative-free methods we state the three essential definitions.

Definition 1 Let be a real function with a simple root α and let be a sequence of real numbers that converge towards α The order of convergence m is given by

(2)

where ρ is the asymptotic error constant and

Definition 2 Let λ be the number of function evaluations of the new method. The efficiency of the new method is measured by the concept of efficiency index[4,18] and defined as

(3)

where µ is the order of the method.

Definition 3 Suppose that and are three successive iterations closer to the root α of (1). Then, the computational order of convergence[19], may be approximated by where

2.1. The four-point derivative-free methods

Consider the following iteration scheme

(5)

This scheme consists of four steps in which the Newton method is repeated. It is clear that the formula (5) requires eight evaluations per iteration and using (3) the efficiency index of (5) is which is same as the classical Newton method. In fact, scheme (5) does not increase the computational efficiency. The purpose of this paper is to establish new derivative-free methods with optimal order; hence we reduce the number of evaluations to five by using some suitable approximation of the derivatives. To derive a higher efficiency index, we consider approximating the derivatives by divided difference method. Therefore, the derivatives in (5) are replaced by

(6)

(7)

(8)

(9)

Substituting (6)-(9) into (5), we get

(10)

The first step of the formula (10) is the classical Steffensen second-order method[15] and the second step is the improvement of the first step. Furthermore, we have found that the second third and fourth step does not produce an optimal order four, eight and sixteenth, respectively. Therefore, we have introduced weight functions in the second, third and fourth step in order to achieve the desired optimal order of convergence. First we shall denote the following functions as,

(11)

In order to achieve the fourth-order convergence in the second step we have found that there are three different forms of weight functions, which are expressed as

(12)

(13)

(14)

and to achieve the eighth-order convergence in the third step the weight functions are expressed as

(15)

Furthermore, to achieve the sixteenth-order of convergence in the fourth step, the weight function is expressed as

(16)

Then the iteration scheme (5) in its final form is given as

(17)

where are given by (14), (15), (16), respectively and provided that the denominators in (17) are not equal to zero. Thus the scheme (17) defines a new multipoint method with suitable weight functions. To obtain the solution of (1) by the new sixteenth order derivative-free methods, we must set a particular initial approximation , ideally close to the simple root. In numerical mathematics it is very useful and essential to know the behaviour of an approximate method. Therefore, we shall prove the order of convergence of the new sixteenth-order method. Theorem 1

Let be a simple root of a sufficiently differentiable function in an open interval D. If is sufficiently close to α then the order of convergence of the new derivative-free method defined by (17) is sixteen.Proof

Let α be a simple root of, i.e. and, and the error is expressed as

Using the Taylor expansion, we have

(19)

Taking and simplifying, expression (19) becomes

(20)

where and

(21)

Expanding the Taylor series of and substituting given by (20), we have

(22)

Substituting (20) and (22) in the first step of the expression (17), we obtain

(23)

The expansion of about α is given as

(24)

The expansion of the particular terms used in (17) are given as

(25)

(26)

(27)

(28)

Based on the particular weight function and substituting appropriate expressions in the second step of (17), we obtain

(29)

The Taylor series expansion of about is given as

(30)

In order to evaluate the essential terms of (17), we expand term by term

(31)

(32)

Collecting the above terms

(33)

(34)

(35)

Substituting appropriate expressions in (17), we obtain

(36)

Simplifying (36), we obtain the error equation of eighth- order convergence

(37)

The error equation (37) is a simplified version of the eighth-order derivative-free method established in[16].

The Taylor series expansion of about is given as

(38)

We progress to expand the terms used in the fourth-step of (17),

(39)

(40)

(41)

(42)

(43)

(44)

Collecting and Simplifying the appropriate terms used in (17), we obtain the error equation

(45)

The expression (45) establishes the asymptotic error constant for the sixteen order of convergence for the new derivative-free method defined by (17).

2.2 Method 2: (Liu1)

Recently we have introduced three-step eighth-order derivative-free methods[16], and one of them was constructed by using the two-step fourth-order method presented by Liu et al.[7] and the third-step was developed to achieve the eighth-order. It appears that the formula of the eighth-order derivative-free method based on Liu et al. method given by (2.27) in[16] has a typo error. This error actually occurs in the weight function of the third step of the eighth-order derivative-free method. We observe that the third step is corrected and simplified in the following sixteenth-order method given below

(46)

(47)

(48)

where

(49)

are given in (17), is given by (43), is the initial approximation and provided that the denominators of (46)-(49) are not equal to zero.Theorem 2

Let be a simple root of a sufficiently differentiable function in an open interval D. If is sufficiently close to α then the order of convergence of the new derivative-free method defined by (48) is sixteen.

Proof

Using appropriate expressions in the proof of the theorem 1 and substituting them into (48), we obtain the asymptotic error constant

(50)

The expression (50) establishes the asymptotic error constant for the sixteen order of convergence for the new derivative-free method defined by (48).

2.3. Method 3: (Liu2)

Another three-step eighth-order derivative-free method recently introduced in[16] , and one of them was constructed by using the two-step fourth-order method presented by Liu et al.[10] and the third-step was developed to achieve the eighth-order. It appears that the formula of the eighth-order derivative-free method based on Liu et al. method given by (2.32) in[16] has a typo error. Here also the error actually occurs in the weight function of the third step of the eighth-order derivative-free method. We observe that the third step given by (52) is corrected and simplified in the following sixteenth-order method given below

(51)

(52)

where

(54)

is given in (17), is given by (43), is the initial approximation and provided that the denominators of (51)-(54) are not equal to zero. It is well established that the eighth-order derivative-free method given by (52) converges to order eight, see[16]. However, we progress to establish the sixteenth-order method given by (53).Theorem 3

Let be a simple root of a sufficiently differentiable function in an open interval D. If x₀ is sufficiently close to α then the order of convergence of the new derivative-free method defined by (53) is sixteen.Proof

Using appropriate expressions in the proof of the theorem 1 and substituting them into (53), we obtain the asymptotic error constant

(55)

The expression (55) establishes the asymptotic error constant for the sixteenth-order of convergence for the new derivative-free method defined by (53).

3. Kim and Guem Sixteenth Order Methods

For the purpose of comparison, we consider two sixteenth-order methods presented recently in[5,6]. Since these methods are well established, we shall state the essential expressions used in order to calculate the approximate solution of the given nonlinear equations and thus compare the effectiveness of the new sixteen order derivative-free methods.

The first of the Kim et al. method[6] is given as

(56)

where

(57)

(58)

(59)

(60)

There are many versions of see[6], for the purpose of this paper we shall consider the following

(61)

(62)

(63)

(64)

Another sixteenth-order methods introduced by Kim et al. is given in[5] and is expressed as

(65)

where

(66)

(67)

(68)

(69)

As before we shall consider the particular weight function used in (68), which is given as

(70)

(71)

where x₀ is the initial approximation and provided that the denominators of (65) are not equal to zero. In addition, further details and expressions of the recently introduced sixteenth-order method are given[5].

4. Application of the New Sixteenth- Order Derivative-Free Iterative Methods

The present sixteenth-order methods given by (17), (48), (53), are employed to solve nonlinear equations and compare with the Kim et al type 1 and type 2 methods (56) and (65). To demonstrate the performance of the new sixteenth-order methods, we use ten particular nonlinear equations. We shall determine the consistency and stability of results by examining the convergence of the new derivative-free iterative methods. The findings are generalised by illustrating the effectiveness of the sixteenth-order methods for determining the simple root of a nonlinear equation. Consequently, we shall give estimates of the approximate solution produced by the sixteenth-order methods and list the errors obtained by each of the methods. The numerical computations listed in the tables were performed on an algebraic system called Maple. In fact, the errors displayed are of absolute value and insignificant approximations by the various methods have been omitted in the following tables.

Remark 1

The new four-step derivative-free methods require five function evaluations and have the order of convergence sixteen. Therefore, these new methods are of optimal order and support the Kung-Traub conjecture[9]. To determine the efficiency index of these new derivative-free methods, we shall use the definition 2. Hence, the efficiency index of the sixteenth-order derivative-free methods given is which are better than the other two and three point derivative-free methods given in[2,3,7,8,10-14,16, 17,20].

Remark 2

The test functions and their exact root α are displayed in table 1. The difference between the root α and the approximation for test functions with initial approximation are displayed in Table 2. In fact, is calculated by using the same total number of function evaluations (TNFE) for all methods. In the calculations, 15 TNFE are used by each method. Furthermore, the computational order of convergence (COC) is displayed in Table 3.

Table 1. Test functions and their roots

Table 2. Comparison of various four-point iterative methods

Table 3. COC of various iterative methods

5. Conclusions

In this study, we have constructed new sixteenth-order derivative-free methods for solving nonlinear equations. Convergence analysis proves that these new derivative-free methods preserve their order of convergence. From the results in the tables, based on a number of numerical experiments, it can be concluded that the convergence of the new multipoint method of the sixteenth-order is remarkably fast. Furthermore, we have found that the new four-point methods (17) produced identical results with all three types of weight function, given by (12)-(14), used in the second step of (17). After an extensive experimentation we were not able to designate a specific iterative method which always produces the best results for all tested nonlinear equations.

There are two major advantages of the higher order derivative-free methods. Firstly, we do not have to evaluate the derivative of the functions; therefore they are especially efficient where the computational cost of the derivative is expensive, and secondly we have established a higher order of convergence method than the existing derivative-free methods[2,3,7,8,10-14,16,17,20]. We have examined the effectiveness of the new derivative-free methods by showing the accuracy of the simple root of a nonlinear equation. The main purpose of demonstrating the new sixteenth-order derivative-free methods for many different types of nonlinear equations was purely to illustrate the accuracy of the approximate solution, the stability of the convergence, the consistency of the results and to determine the efficiency of the new iterative methods. Finally, we conclude that the new four-point methods may be considered a very good alternative to the classical methods.