Constructive Theory of Designing Optimal Eighth-Order Derivative-Free Methods for Solving Nonlinear Equations

DOI: 10.4236/ajcm.2020.101007   PDF   HTML   XML   141 Downloads   303 Views  

Abstract

This paper stresses the theoretical nature of constructing the optimal derivative-free iterations. We give necessary and sufficient conditions for derivative-free three-point iterations with the eighth-order of convergence. We also establish the connection of derivative-free and derivative presence three-point iterations. The use of the sufficient convergence conditions allows us to design wide class of optimal derivative-free iterations. The proposed family of iterations includes not only existing methods but also new methods with a higher order of convergence.

Share and Cite:

Zhanlav, T., Otgondorj, Kh. and Mijiddorj, R.-O. (2020) Constructive Theory of Designing Optimal Eighth-Order Derivative-Free Methods for Solving Nonlinear Equations. American Journal of Computational Mathematics, 10, 100-117. doi: 10.4236/ajcm.2020.101007.

1. Introduction

At present, there are a lot of iterative methods for solving nonlinear equations and systems of equations (see [1] [2] [3] and reference therein). In particular, the derivative-free methods are necessary when the derivative of the function f is unavailable or expensive to obtain. In the last decade, the derivative-free two and three-point methods with better convergence properties were developed (see [4] - [19] and references therein). It should be pointed out that most of these methods were proposed mainly for the concrete choice of parameters (see Table 1). Evidently, a systematic theory or an approach for constructing derivative-free methods is still needed. It is therefore of interest and necessity to develop a global theory. The aim of this paper is to fill up the above mentioned gap

Table 1. The derivative-free three-point iterative methods.

and to obtain the wide class of optimal derivative-free three-point methods. The paper is organized as follows. In Section 2, we give the necessary and sufficient conditions for derivative-free three-point iterations to be optimal order eight. We also establish the connection between derivative presence and derivative-free three-point methods. In Section 3, we apply the sufficient convergence conditions to obtain the optimal derivative-free methods which are dependent on parameters in the third-step of considered iterations. We obtain families of optimal derivative-free three-point methods. They include many existing methods as particular cases as well as new methods with the higher order of convergence. In last section, we present the results of numerical experiments that confirm the theoretical conclusion about the convergence order and make comparison with other known methods of the same order of convergence. Finally, numerical results show that new iterative methods can be significant by its high precision and practical use.

2. The Optimal Derivative-Free Three-Point Iterations

Typically, the optimal three-point iterative methods have a form [9]

y n = x n f ( x n ) f ( x n ) , z n = y n τ ¯ n f ( y n ) f ( x n ) , x n + 1 = z n α n f ( z n ) f ( x n ) , (1)

in which the parameters τ ¯ n and α n are given by

τ ¯ n = 1 + 2 θ n + β ˜ θ n 2 + γ ˜ θ n 3 + , (2)

and

α n = 1 + 2 θ n + ( β ˜ + 1 ) θ n 2 + ( 2 β ˜ + γ ˜ 4 ) θ n 3 + ( 1 + 4 θ n ) f ( z n ) f ( y n ) + O ( f ( x n ) 4 ) , (3)

where β ˜ , γ ˜ R , and θ n = f ( y n ) f ( x n ) . In [9] was proven the following theorem.

Theorem 1. Let the function f ( x ) be sufficiently smooth and have a simple root x * I . Furthermore, let the initial approximation x 0 be sufficiently close to x * . Then, the convergence order of the iterative method (1) is eight if and only if the parameters τ ¯ n and α n satisfy conditions (2) and (3), respectively.

Remark. The second sub-step in (1) can be rewritten as any two-point optimal fourth-order method

z n = ψ 4 ( x n , y n ) ,

where ψ 4 ( x n , y n ) is a real function using the evaluation of f ( x n ) , f ( x n ) and f ( y n ) . Each method in ψ 4 has a parameter τ ¯ n given by (2) with own β ˜ and γ ˜ .

Now we consider the derivative-free variant of (1)

y n = ψ 2 ( x n , y n ) = x n f ( x n ) ϕ n ,

z n = ψ 4 ( x n , y n ) = y n τ ˜ n f ( y n ) ϕ n , (4)

x n + 1 = z n α ˜ n f ( z n ) ϕ n ,

where

w n = x n + γ f ( x n ) ,

ϕ n = f ( w n ) f ( x n ) w n x n = 1 γ ( f ( w n ) f ( x n ) 1 ) f ( x n ) , γ R . (5)

Here ψ 2 ( x n , y n ) is any second-order method. Actually, in Formula (4), the fundamental quantities are

θ n = f ( y n ) f ( x n ) , σ n = f ( y n ) f ( w n ) , and υ n = f ( z n ) f ( y n ) .

Then θ n = O ( f ( x n ) ) , σ n = O ( f ( x n ) ) for x n x * , where x * is a simple root of f ( x ) . If ψ 4 ( x n , y n ) is any two-point optimal fourth-order method then f ( z n ) = O ( f ( x n ) 4 ) , therefore υ n = O ( f ( x ) 2 ) . The iteration (4) obtained from (1) replacing f ( x n ) by ϕ n . Due to change (5), the parameters in (4) does not remain as before and we denote them by τ ˜ n and α ˜ n . We call the iterations (1) and (4) the derivative presence (DP) and derivative-free (DF) variants respectively. If we use the notations

c ˜ n = 1 1 + γ ϕ n , d ˜ n = 1 + c ˜ n ,

then we have

σ n = c ˜ n θ n , θ n + σ n = d ˜ n θ n . (6)

DP can be derived from DF by substituting σ n = θ n . The following is the main result of our work [11].

Theorem 2. Let the assumptions of Theorem 1 be fulfilled. Then, the convergence order of the iteration (4) is eight if and only if the parameters τ ˜ n and α ˜ n in (4) are given by formulas

τ ˜ n = 1 + d ˜ n θ n + β ˜ θ n 2 + γ ˜ θ n 3 + , (7)

and

α ˜ n = 1 + d ˜ n θ n + ( β ˜ + c ˜ n ) θ n 2 + ( γ ˜ + d ˜ n ( β ˜ 1 c ˜ n 2 ) ) θ n 3 + ( 1 + 2 d ˜ n θ n ) υ n + O ( f ( x n ) 4 ) . (8)

The proposed method (4) with parameters given by (7) and (8) is three-point derivative free and optimal in the sense of Kung and Traub. Kung-Traub conjecture [20] states that the multi-point iterative methods, based on k evaluations, could achieve optimal convergence order 2 k 1 . Our proposed method is in concurrence with the conjecture as it needs only four function evaluation per iteration i.e., k = 4 . Moreover, using ideas in [3] [10] one can propose more general construction for τ ˜ n and α ˜ n as following:

Define τ ˜ n = h ( θ n , σ n ) , α ˜ n = g ( θ n , σ n , υ n ) as sufficiently smooth functions of θ n , σ n , υ n . It is easy to show that f ( z n ) = O ( f ( x n ) 4 ) if and only if h 00 = h 10 = h 01 = 1 , where h i j = h ( i , j ) ( 0,0 ) , ( i 0, j 0 ) . Hence, under the restriction h 11 = h 02 = h 21 = h 12 = h 03 = 1 , (4) is optimal if and only if

g 000 = 1 ,

g 100 = g 010 = g 001 = 1 ,

g 101 = g 011 = 2 ,

g 200 = h 20 , g 110 = 1 , g 020 = 0 ,

g 300 = h 20 + h 30 1 , g 210 = h 20 1 , g 120 = g 030 = 1.

Those can be easily checked with using (6). For the optimal formula, the remainder term is O ( f ( x n ) 4 ) in (8) because υ n = O ( f ( x ) 2 ) . In this sense, we can say that (4) is optimal if and only if τ ˜ n , α ˜ n can be written as (7) and (8).

When γ 0 the Formula (7) leads to (2) and the Formula (8) leads to (3). A query may arise that there exists an optimal (DF) variant (4) for each optimal (DP) variant (1) and vice versa. If yes, how to find its (DF) variant? To respond this we use the connection of formulas (3) and (8). Actually, from (3) and (8) we deduce that

α ˜ n = α n ( x n , y n , ϕ n ) + ( d ˜ n 2 ) ( 1 + θ n + ( d ˜ n + β ˜ ) θ n 2 + 2 υ n ) θ n , (9)

where α n ( x n , y n , ϕ n ) is obtained replacing f ( x n ) by ϕ n in α n ( x n , y n , f ( x n ) ) in (1). From (9) we find that

α n ( x n , y n , f ( x n ) ) = α ˜ n ( x n , y n , ϕ n ) | ϕ n = f ( x n ) = α ˜ n ( x n , y n , f ( x n ) ) . (10)

These relations (9) and (10) give the rule of mutual transition of (DP) and (DF) variants. There exists the one optimal (DP) variant (4) for each optimal (DF) variant (1). The converse does not true. Namely there are several (DF) variants of (DP).

3. Application of Sufficient Convergence Condition to Derive New DF Iterations

Now we give the application of Theorem 2 to construct new iterations. The sufficient convergence conditions (7) and (8) allow us to design new derivative-free optimal methods. Depending on the form of α ˜ n we can obtain different iterations. We consider some special cases.

1) Let α ˜ n in (4) be a form

α ˜ n = φ ( θ n ) + ψ ( υ n ) + μ ( f ( z n ) f ( x n ) ) , (11)

where φ , ψ , and μ are smooth enough functions. As regarding the iteration (4) with α ˜ n given by (11) we give the following result.

Theorem 3. The iteration (4) with τ ˜ n given by (7) and with α ˜ n given by (11) have the order of convergence eight, if the following conditions hold:

φ ( 0 ) = 1 , φ ( 0 ) = d ˜ n , φ ( 0 ) = 2 ( β ˜ + c ˜ n ) ,

φ ( 0 ) = 6 ( γ ˜ + d ˜ n ( β ˜ 1 c ˜ n 2 ) ) ,

ψ ( 0 ) = 0 , ψ ( 0 ) = 1 , (12)

μ ( 0 ) = 0 , μ ( 0 ) = 2 d ˜ n .

Proof. Using the Taylor expansion of smooth enough functions φ ( θ n ) , ψ ( υ n ) and μ ( θ n , υ n ) we obtain an expression for (11). The comparison of this expression with sufficient condition (8) gives conditions (12).

When β ˜ = γ ˜ = 0 in (7) the Theorem 3 leads to a theorem in [5]. That is to say, the similar theorem was proved in [5] only for special case of τ ˜ n :

τ ˜ n = 1 + d ˜ n θ n . (13)

Therefore, Theorem 3 is more general, than that of [5]. Note that, in [5] are proposed four variants of α ˜ n that include redundant terms like υ n 2 and

( f ( z n ) f ( ω n ) ) 2 . By neglecting these terms, α ˜ n can be simplified essentially without loss of the order of convergence. When γ = 0 the condition (12) reduced to

φ ( 0 ) = 1 , φ ( 0 ) = 2 , φ ( 0 ) = 2 ( β ˜ + 1 ) , φ ( 0 ) = 6 ( γ ˜ + 2 β ˜ 4 ) ,

ψ ( 0 ) = 0 , ψ ( 0 ) = 1 , μ ( 0 ) = 0 , μ ( 0 ) = 4. (14)

It means that the derivative presence variant (1) with parameters given by (7) and (11) has a convergence order eight under conditions (14).

Thukral and Petković considered in [1] the particular case of (1) with α ˜ n given by (11) and with

τ ˜ n = 1 + b θ n 1 + ( b 2 ) θ n = 1 + 2 θ n + 2 ( 2 b ) θ n 2 + 2 ( 2 b ) 2 θ n 3 .

In this case β ˜ = 2 ( 2 b ) and γ ˜ = 2 ( 2 b ) 2 and the condition (14) coincides with that of [1]. They also considered another particular case of (1) with α ˜ n given by (11) and

τ ˜ n = θ n + 1 1 θ n = 1 + 2 θ n + θ n 2 + θ n 3 + .

In this case β ˜ = γ ˜ = 1 and the condition (14) leads to that of [1]. The function φ ( θ n ) in (11) can be written as

φ ( θ n ) = τ ˜ n + c ˜ n θ n 2 + d ˜ n ( β ˜ 1 c ˜ n 2 ) θ n 3 . (15)

Due to generating function method [10] instead of τ ˜ n we can take any function H

τ ˜ n = H ( θ n ) = c + ( H ( 0 ) c + d ) θ n + ω θ n 2 c + d θ n + b θ n 2 , b , c , d , ω R , (16)

satisfying conditions

H ( 0 ) = 1 , H ( 0 ) = d ˜ n , H ( 0 ) = 2 β ˜ , H ( 0 ) = 6 γ ˜ .

As a result, we have a family of optimal derivative-free three-point methods (4) with (11), (15), and (16). The constants β ˜ and γ ˜ can be expressed through b , c , d and ω as:

β ˜ = ω b d H ( 0 ) c , γ ˜ = d ( 2 b ω ) c 2 + ( H ( 0 ) c + d ) ( d 2 c 3 b c 2 ) d 3 c 3 .

That is we have the iterations (4) with τ ˜ n is given by (16) and α ˜ n is given by

α ˜ n = τ ˜ n + c ˜ n θ n 2 + d ˜ n ( β ˜ 1 c ˜ n 2 ) θ n 3 + ( 1 + 2 d ˜ n θ n ) υ n . (17)

Note that the choice of parameter τ ˜ n defined by (16) includes almost all the choices listed in Table 1 as particular cases. Thus the family of iterations (4) with (16) and (17) represents a wide class of optimal derivative-free three-point iterations.

2) Let α ˜ n in (4) be a form

α ˜ n = τ ˜ n + K ( θ n , υ n ) , (18)

where τ ˜ n is given by (7) and K ( θ n , υ n ) is sufficient smooth function of θ n and υ n .

Theorem 4. The iteration (4) with τ ˜ n given by (7) and α ˜ n given by (18) has the order of convergence eight, if the following conditions hold:

K ( 0 , 0 ) = K θ ( 0 , 0 ) = 0 , K υ ( 0 , 0 ) = 1 , K θ υ ( 0 , 0 ) = 2 d ˜ n ,

K θ θ ( 0 , 0 ) = 2 c ˜ n , K θ θ θ ( 0 , 0 ) = 6 d ˜ n ( β ˜ 1 c ˜ n 2 ) . (19)

Proof. From (7) and (8) it is clear that

K ( θ n , υ n ) = c ˜ n θ n 2 + d ˜ n ( β ˜ 1 c ˜ n 2 ) θ n 3 + ( 1 + 2 d ˜ n θ n ) υ n + O ( f ( x ) 4 ) (20)

which holds under conditions (19).

The (DP) variant of this iteration is obtained from (4), (7), and (18) when γ 0 . Note that the similar scheme was considered in [2].

In some cases, the form

α ˜ n = τ ˜ n ( 1 + K ( θ n , υ n ) τ ˜ n ) = τ ˜ n W ( θ n , υ n ) (21)

obtained from (18) is useful. Using (20) we obtain

W ( θ n , υ n ) = 1 + c ˜ n θ n 2 + ( c ˜ n d ˜ n + d ˜ n ( β ˜ 1 c ˜ n 2 ) ) θ n 3 + ( 1 + d ˜ n θ n ) υ n + O ( f ( x n ) 4 ) . (22)

For the iteration (4) with (7) and (21) we can formulate the following:

Theorem 5. The iteration (4) with (7) and (21) has the order of convergence eight, if the following conditions hold:

W ( 0 , 0 ) = 1 , W θ ( 0 , 0 ) = 0 , W θ θ ( 0 , 0 ) = 2 c ˜ n ,

W θ θ θ ( 0 , 0 ) = 6 ( c ˜ n d ˜ n + d ˜ n ( β ˜ 1 c ˜ n 2 ) ) , (23)

W υ ( 0 , 0 ) = 1 , W υ θ ( 0 , 0 ) = d ˜ n .

Proof. If we take (22) into account in the Taylor expansion of function W ( θ n , υ n ) we arrive at (23).

When γ = 0 the conditions (23) take a form

W ( 0 , 0 ) = 1 , W θ ( 0 , 0 ) = 0 , W θ θ ( 0 , 0 ) = 2 ,

W θ θ θ ( 0 , 0 ) = 12 ( β ˜ 3 ) , W υ ( 0 , 0 ) = 1 , W υ θ ( 0 , 0 ) = 2. (24)

Remark. Obviously, as for τ ˜ n one can take any function H given by (16) in the formulas (17) and (21).

Note that in [3] were obtained some conditions that guarantee order eight of the method (4) with (7) and (21) i.e.,

τ ˜ n = h ( θ n , s n ) = 1 + θ n + s n + a 2 θ n 2 + b θ n s n + c 2 s n 2 + ,

s n = c ˜ n f ( y n ) f ( x n ) ,

α ˜ n = h ( θ n , s n ) μ ( θ n , s n , υ n ) ,

μ ( θ n , s n , υ n ) = 1 + υ n + d 2 υ n 2 + θ n s n + θ n υ n + s n υ n + a 2 2 θ n 3 + c 2 2 s n 3 + m 6 υ n 3 + a + 2 b 4 2 θ n s n 2 + 2 b + c 4 2 θ n s n 2 = 1 + c ˜ n θ n 2 + ( 1 + d ˜ n θ n ) υ n + ( d ˜ n β ˜ ( 2 + c ˜ n 3 + 2 c ˜ n ) d ˜ n ) θ n 3 + O ( f ( x n ) 4 ) (25)

that does not coincide with (22). Moreover, the terms d 2 υ n 2 and m 6 υ n 3 seem to be redundant, because it suffices to determine α ˜ n with accuracy O ( f ( x n ) 4 ) .

Note that (DP) methods with (7) and (21) are often used. For example, Kung-Traub’s eighth-order method [21] has a form (1) with

τ ˜ n = 1 ( 1 θ n ) 2 , W ( θ n , υ n ) = f ( y n ) ( f 2 ( x n ) + f ( y n ) ( f ( y n ) f ( z n ) ) ) ( f ( x n ) f ( z n ) ) 2 ( f ( y n ) f ( z n ) ) = 1 + θ n ( θ n θ n υ n ) ( 1 θ n υ n ) 2 ( 1 υ n ) . (26)

The Bi-Wu-Ren’s optimal eighth-order method [22] has a form (1) with

τ ˜ n = h ( θ n ) , α n = f n ( x n ) ( f ( x n ) + β f ( z n ) ) f ( x n ) + ( β 2 ) f ( z n ) 1 f [ z n , y n ] + f [ z n , x n , x n ] ( z n y n ) , (27)

where

f [ z n , y n ] = f ( y n ) f ( z n ) y n z n , f [ z n , x n , x n ] = f ( x n f [ z n , x n ] ) x n z n .

But (27) is not the example for (21).

The Sharma and Arora’s optimal eighth-order method [21] has a form (1) with

τ ˜ n = 1 1 2 θ n , α ˜ n = τ ˜ n 4 θ n 2 ( 1 θ n ) 2 ( 1 υ n ) ( 1 + θ n υ n ) ( ( 1 2 θ n ) 2 + ( 3 4 θ n ) θ n υ n ) . (28)

Moreover, we suggest that more general theory for τ ˜ n as

τ ˜ n = 1 + θ n + σ n + h 20 θ n 2 + h 11 θ n σ n + h 02 σ n 2 + h 30 θ n 3 + h 21 θ n 2 σ n + h 12 θ n σ n 2 + h 03 σ n 3 + .

3) Let α ˜ n in (4) be a form

α ˜ n = ϕ n f [ z n , y n ] + ( z n y n ) f [ z n , y n , x n ] + ( z n y n ) ( z n x n ) f [ z n , y n , x n , ω n ] (29)

that often used in practice, see [4] [12] [14] [15] [16]. Of course, τ ˜ n and α ˜ n given by (7) and (29) satisfy the sufficient conditions (7) and (8). The (DP) variant of (4) with (7) and (29) has a form (1)

y n = x n f ( x n ) f ( x n ) ,

z n = ψ 4 ( x n , y n ) ,

x n + 1 = z n α n f ( z n ) f ( x n ) , (30)

where α n = f ( x n ) f [ z n , y n ] + ( z n y n ) f [ y n , x n , x n ] .

In [6] is proposed the eighth-order iteration (1) with (29) ( γ 0 ) and special τ ¯ n

τ ¯ n = 1 + 1 θ n + ( 1 + 1 1 + f ( x n ) f ( x n ) ) θ n . (31)

Our iteration (1) with (2) and (30) is more general than that of [6].

4) Let α ˜ n in (4) be a form

α ˜ n = ϕ n ( 1 + A θ n + B θ n 2 + C θ n 3 + ( ω + Δ θ n ) υ n ) a f [ x n , z n ] + b f [ z n , y n ] + c f [ x n , y n ] , a + b + c = 1 , (32)

where a , b , c R .

We shall find the coefficients A , B , C and ω , Δ such that the iteration (4) with (7) and (32) has the order of convergence eight and state the following:

Theorem 6. The iteration (4) with (7) and (32) has the order of convergence eight, if the following conditions hold:

A = ( 1 b ) ( d ˜ n 1 ) , B = ( β ˜ d ˜ n ) ( 1 b ) + c ˜ n ( 1 a ) ,

C = a 1 + ( b a ) β + ( 1 b ) γ + ( a + β 2 ) c ˜ n + ( c 2 ) c ˜ n 2 c ˜ n 3 , (33)

ω = 1 b , Δ = a + b 1 + d ˜ n ( 2 b ) .

Proof. Using the following relations

f [ x n , y n ] = ϕ n ( 1 θ n ) , f [ z n , y n ] = ϕ n τ ˜ n ( 1 υ n ) ,

f [ x n , z n ] = ϕ n 1 + τ ˜ n θ n ( 1 θ n υ n ) ,

1 τ ˜ n = 1 d ˜ n θ n + ( d ˜ n 2 β ˜ n ) θ n 2 + ( 2 β ˜ n d ˜ n γ ˜ d ˜ n 3 ) θ n 3 + , (34)

1 1 + τ ˜ n θ n = 1 θ n + ( 1 d ˜ n ) θ n 2 + ( 2 d ˜ n β ˜ n 1 ) θ n 3 + ,

1 1 x = 1 + x + x 2 + x 3 + , | x | < 1 ,

we get

ϕ n a f [ x n , z n ] + b f [ z n , y n ] + c f [ x n , y n ] = 1 + ( a + c + b d ˜ n ) θ n + ( a ( d ˜ n 1 ) + b ( β ˜ d ˜ n 2 ) + ( a + c + b d ˜ n ) 2 ) θ 2 + ( a ( β ˜ + 1 2 d ˜ n ) + b ( γ ˜ + d ˜ n 3 2 β ˜ d ˜ n ) + 2 ( a + c + b d ˜ n ) ( a ( d ˜ n 1 ) + b ( β ˜ d ˜ n 2 ) ) + ( a + c + b d ˜ n ) 3 ) θ n 3 + ( b + ( a + 2 b ( a + c ) + ( 2 b 1 ) b d ˜ n ) θ n ) υ n + O ( f ( x n 4 ) ) . (35)

Substituting (35) into (32) and using the sufficient convergence condition (8) we arrive at (33).

Thus, we have a family of optimal three-point (DF) the iteration (4) with (7) and (32) that contains three parameters a, b and c. Now, we consider some particular cases of the iteration (4) with (7) and (32). Let a = b = 1 and c = 1 . Then from (33) we find that

A = B = 0 , C = ( 1 + γ ϕ n ) β ˜ d ˜ n 3 γ ϕ n ( 1 + γ ϕ n ) 2 , ω = 0 , Δ = c ˜ n .

Hence we obtain

α ˜ n = ( 1 + ( ( 1 + γ ϕ n ) β ˜ d ˜ n 3 γ ϕ n ) c ˜ n 2 θ n 3 + c ˜ n θ n υ n ) ϕ n f [ x n , z n ] + f [ z n , y n ] f [ x n , y n ] ( 1 + f ( z n ) f ( ω n ) ) ( 1 + ( ( 1 + γ ϕ n ) β ˜ d ˜ n 3 γ ϕ n ) f 3 ( y n ) f 2 ( ω n ) f ( x n ) ) ϕ n f [ x n , z n ] + f [ z n , y n ] f [ x n , y n ] , (36)

or

α ˜ n ϕ n ( 1 f ( z n ) f ( ω n ) ) ( 1 C ^ f 3 ( y n ) f 2 ( ω n ) f ( x n ) ) ( f [ x n , z n ] + f [ z n , y n ] f [ x n , y n ] ) , (37)

where C ^ = ( 1 + γ ϕ n ) β ˜ d ˜ n 3 γ ϕ n . The sign ≈ in (37) indicates that it holds with accuracy O ( f ( x n 4 ) ) . Now, we consider concrete choice of τ ˜ n :

τ ˜ n = 1 1 d ˜ n θ n + p c ˜ n θ n 2 , p N . (38)

For the choice (38) we have

β ˜ = d ˜ n 2 p c ˜ n

and

C ^ = ( p + 1 ) .

The iteration (4) with (38) and (36) (or (37)) is converted to one given by Soleymani in [23] for p = 0 and one given by Thukral in [7] for p = 1 . For the choice p = 1 the parameter α ˜ n is simplified as

α ˜ n = ( 1 + f ( z n ) f ( ω n ) ) ϕ n f [ x n , z n ] + f [ z n , y n ] f [ x n , y n ] , (39)

or using 1 + f ( z n ) f ( w n ) = 1 1 f ( z n ) f ( w n ) + O ( f ( x n ) 6 ) we have

α ˜ n = ϕ n ( 1 f ( z n ) f ( ω n ) ) ( f [ x n , z n ] + f [ z n , y n ] f [ x n , y n ] ) . (40)

Let

τ ˜ n = 1 1 d ˜ n θ n = 1 + d ˜ n θ n + β ˜ θ n 2 + γ ˜ θ n 3 + , (41)

with

β ˜ = d ˜ n 2 , γ ˜ = d ˜ n 3 .

Then C = c ˜ n 2 and we have

α ˜ n = ( 1 c ˜ n 2 θ n 3 + c ˜ n θ n υ n ) ϕ n f [ x n , z n ] + f [ z n , y n ] f [ x n , y n ] . (42)

The iteration (4) with (41) and (42) coincides with one given by Soleymani in [23] with

α ˜ n = ( 1 + θ n 4 ( 1 + γ ϕ n ) f 3 ( y n ) ( 1 + γ ϕ n ) 3 f 3 ( x n ) υ n 2 + c ˜ n σ n υ n + ( θ n υ n ) 2 ) ϕ n f [ x n , z n ] + f [ z n , y n ] f [ x n , y n ] ,

here we can neglect the redundant terms θ n 4 υ n 2 + θ n 2 υ n 2 . Let a = 1 , and b = c = 0 . Then from (33) we find that

A = d ˜ n 1 , B = β ˜ d ˜ n , C = β ˜ ( d ˜ n 2 ) + γ ˜ c ˜ n d ˜ n 2 ,

ω = 1 , Δ = 2 ( d ˜ n 1 ) .

The Formula (32) is converted to

α ˜ n = ( 1 + ( d ˜ n 1 ) θ n + ( β ˜ d ˜ n ) θ n 2 + ( β ˜ ( d ˜ n 2 ) + γ ˜ c ˜ n d ˜ n 2 ) θ n 3 + ( 1 + 2 ( d ˜ n 1 ) θ n ) υ n ) ϕ n f [ x n , z n ] . (43)

On the other hand, the direct calculation using relations (34) gives

( 1 f ( z n ) f ( ω n ) ) 1 ( 1 η f 3 ( y n ) f ( ω n ) f 2 ( x n ) ) × f [ x n , y n ] f [ z n , y n ] = 1 + ( d ˜ n 1 ) θ n + ( β ˜ d ˜ n ) θ n 2 + ( γ ˜ β ˜ η c ˜ n ) θ n 3 + ( 1 + 2 c ˜ n θ n ) υ n + O ( f ( x n ) 4 ) , η R . (44)

We choose parameter η in (44) such that the expression (44) coincides with the numerator of (43) within accuracy O ( f ( x n ) 4 ) . That is to say, that

η = β ˜ + d ˜ n 2 .

As a result, (43) can be rewritten as

α ˜ n = ( 1 f ( z n ) f ( ω n ) ) 1 ( 1 ( d ˜ n 2 β ˜ ) f 3 ( y n ) f ( ω n ) f 2 ( x n ) ) f [ x n , y n ] ϕ n f [ x n , z n ] f [ z n , y n ] . (45)

Thus, we find a family of optimal (DF) iteration (4) with (7) and (45), that contains some existing iterations as particular cases. Thukral in [24] proposed eighth-order derivative-free iterations (called M 1 , M 2 , M 3 ) for some special τ ˜ n :

τ ˜ n = 1 1 d ˜ n θ n + c ˜ n θ n 2 = 1 + d ˜ n θ n + ( d ˜ n 2 c ˜ n ) θ n 2 + .

In this case β ˜ = d ˜ n 2 c ˜ n and hence η = c ˜ n , the α ˜ n given by (45) leads to that of M 1 and M 3 in [24]. So, the Thukral’s method ( M 1 , M 2 , M 3 ) are included in our family of (4) with (7) and (45). Thukral in [24] proposed also Petković type methods ( P 1, P 2 ). For P 1 we get τ ˜ n = 1 + d ˜ n θ n , i.e. β ˜ = 0 . In this case η = d ˜ n 2 in (45) and our family of method (4) with (45) converted to P 1 . For P 2 we get

τ ˜ n = 1 + θ n 1 c ˜ n θ n . (46)

In this case β ˜ = c ˜ n d ˜ n and η = d ˜ n . Thus, our family of method (4) with (45) converted to P 2 . It means that the ( P 1, P 2 ) methods are also included in our family of (4) with (7) and (45). As stated above for the choice of (41) we have β ˜ = d ˜ n 2 , so (45) is simplified as

α ˜ n = ( 1 f ( z n ) f ( ω n ) ) 1 f [ x n , y n ] ϕ n f [ x n , z n ] f [ z n , y n ] . (47)

Thus, we have optimal (DF) methods

y n = x n f ( x n ) ϕ n ,

z n = y n τ ˜ n f ( y n ) ϕ n , τ ˜ n = 1 1 d ˜ n θ n , (48)

x n + 1 = z n α ˜ n f ( z n ) ϕ n ,

where α ˜ n is defined by (47). This is (DF) variant of Sharma and Sharma’s optimal methods given in [19] [21] within accuracy O ( f ( x n ) 4 ) . It means that we develop (DF) variant of Sharma and Sharma’s method.

4. Numerical Experiments

In this section, we make some numerical experiments to show the convergence behavior of the presented derivative-free method (4) with parameters τ ˜ n and α ˜ n . We also compare them with the ones developed by Soleymani [23], Thukral [7] [24] and Sharma et al. [19]. For this purpose, we consider smooth and non-smooth nonlinear functions, which are given as follows:

f 1 ( x ) = e x + x 5 1 , x * = 4.9651142

f 2 ( x ) = e x 3 x cos ( x 2 1 ) + x 3 + 1 , x * = 1

f 3 ( x ) = sin x + e x 2 1 , x * = 0

f 4 ( x ) = 1 x | x | , x * = 1.

All computations are performed using the programming package Maple18 with multiple-precision arithmetic and 2500 significant digits. The test functions have been used with stopping criterion | x n x * | < 10 250 , where x * is a root of f ( x ) and the approximation x n to x * . In all examples, we consider that the parameter γ = 0.01 and that α = 2 in Chebyshew-Halley’s method.

Nowadays, high order methods are important due to scientific computations in many areas of science and engineering use. For instance, planetary orbit calculation, radiation calculations and many real life problems demand higher precision for desired results [4] [13]. The first example addresses this situation and we apply the presented methods to solve one such physical problem. In [4] have considered one of the famous classical physics problem which is known as Planck’s radiation law problem. First nonlinear function f 1 arises from this problem.

f 1 ( x ) = 0 has two zeros. Obviously, one of the roots x = 0 is not taken for discussion. Another root is x * 4.965114231744276303699 . Now, we give some numerical experiments and compare new methods with some well-known methods for the smooth function f 1 using the initial guess x 0 = 6 . In Table 2 and Table 3, we exhibit computational order of convergence (COC) and absolute error | x n x * | as well as iteration numbers n are displayed. For presented methods and test functions, by using (see, e.g., [4] [11] [16])

COC l n ( | x n x * | / | x n 1 x * | ) l n ( | x n 1 x * | / | x n 2 x * | ) ,

we have computed the order of convergence.

From Table 2, we can observe that computed results completely support the

Table 2. Convergence behavior of scheme (4) for f 1 ( x ) , x 0 = 6 .

Table 3. Some particular cases of (4) with τ ˜ n (16) and α ˜ n (29).

theory of convergence discussed in previous section. In addition to the comparison of new methods with other methods we include some special cases of proposed family (4) in Table 3.

Table 4 illustrates the number of iterations needed to achieve approximate solution and absolute residual error of the corresponding function | f ( x n ) | using the stopping criterion | x n x * | < 10 250 .

As τ ˜ n in Table 2 is used same in each method, it is shown in Table 4.

Table 4. Comparisons between different methods.

Furthermore, when the iteration diverges for the considered initial guess x 0 , we denote it by “−”.

From Table 4, we see that the convergence behavior of the presented families with different parameters and the iteration number n are the same as for all considered methods.

The result of Table 5 demonstrates that new methods iteration numbers are

Table 5. Comparison of various iterative methods for f 4 ( x ) , x 0 = 2 .

used lesser than other existing methods under condition | x n x * | < 10 250 . However, the dynamic behavior of iterations may depend on the choices of parameters and problems under consideration. In sum, numerical results show that new iterative methods can be significant by its high precision and practical use.

5. Conclusion

We derive the necessary and sufficient conditions for derivative-free three-point iterations with the optimal order. The use of these conditions allows us to derive the families of optimal derivative-free iterations. We propose the families of optimal derivative-free iterations (4) with τ ˜ n given by (16) and α ˜ n given by (17), (29), (32), and (45). Our families include many existing iterations as particular cases, as well as new effective iterations. We reveal redundant terms in well-known methods given in [3] [5] [23]. Dropping these terms allows us to simplify their algorithms and save computation time.

Acknowledgements

The authors wish to thank the editor and anonymous referees for their valuable suggestions on the first version of this paper. This work was supported by the Foundation of Science and Technology of Mongolian under grant SST_18/2018.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1] Thukral, R. and Petković, M.S. (2010) A Family of Three-Point Methods of Optimal Order for Solving Nonlinear Equations. The Journal of Computational and Applied Mathematics, 233, 2278-2284.
https://doi.org/10.1016/j.cam.2009.10.012
[2] Rhee, M.S., Kim, Y.I. and Neta, B. (2018) An Optimal Eighth-Order Class of Three-Step Weighted Newton’s Methods and Their Dynamics behind the Purely Imaginary Extraneous Fixed Points. International Journal of Computer Mathematics, 95, 2174-2211.
https://doi.org/10.1080/00207160.2017.1367387
[3] Petković, M.S., Neta, B., Petković, L.D. and Dzunic, J. (2014) Multipoint Methods for Solving Nonlinear Equations. Applied Mathematics and Computation, 226, 635-660.
https://doi.org/10.1016/j.amc.2013.10.072
[4] Argyros, I.K., Kansal, M., Kanwar, V. and Bajaj, S. (2017) Higher-Order Derivative-Free Families of Chebyshev-Halley Type Methods with or without Memory for Solving Nonlinear Equations. Applied Mathematics and Computation, 315, 224-245.
https://doi.org/10.1016/j.amc.2017.07.051
[5] Soleymani, F. and Khattri, S.K. (2012) Finding Simple Roots by Seventh- and Eighth-Order Derivative-Free Methods. International Journal of Mathematical Models and Methods in Applied Sciences, 6, 45-52.
https://doi.org/10.1155/2012/932420
[6] Matthies, G., Salimi, M., Sharifi, S. and Varona, J.L. (2016) An Optimal Three-Point Eighth-Order Iterative Method without Memory for Solving Nonlinear Equations with Its Dynamics. Japan Journal of Industrial and Applied Mathematics, 33, 751-766.
https://doi.org/10.1007/s13160-016-0229-5
[7] Thukral, R. (2011) Eighth-Order Iterative Methods without Derivatives for Solving Nonlinear Equations. International Scholarly Research Network ISRN Applied Mathematics, 2011, Article ID: 693787.
https://doi.org/10.5402/2011/693787
https://www.hindawi.com/journals/isrn/2011/693787
[8] Soleymani, F. and Vanani, S.K. (2011) Optimal Steffensen-Type Methods with Eighth Order of Convergence. Computers & Mathematics with Applications, 62, 4619-4626.
https://doi.org/10.1016/j.camwa.2011.10.047
[9] Zhanlav, T., Ulziibayar, V. and Chuluunbaatar, O. (2017) Necessary and Sufficient Conditions for the Convergence of Two and Three-Point Newton-Type Iterations. Computational Mathematics and Mathematical Physics, 57, 1090-1100.
https://doi.org/10.1134/S0965542517070120
[10] Zhanlav, T., Chuluunbaatar, O. and Ulziibayar, V. (2017) Generating Function Method for Constructing New Iterations. Applied Mathematics and Computation, 315, 414-423.
https://doi.org/10.1016/j.amc.2017.07.078
[11] Zhanlav, T., Chuluunbaatar, O. and Otgondorj, Kh. (2019) A Derivative-Free Families of Optimal Two- and Three-Point Iterative Methods for Solving Nonlinear Equations. Computational Mathematics and Mathematical Physics, 59, 920-936.
https://doi.org/10.1134/S0965542519060149
[12] Zheng, Q., Li, J. and Huang, F. (2011) An Optimal Steffensen-Type Family for Solving Nonlinear Equations. Applied Mathematics and Computation, 217, 9592-9597.
https://doi.org/10.1016/j.amc.2011.04.035
[13] Khattri, S.K. and Steihaug, T. (2014) Algorithm for Forming Derivative-Free Optimal Methods. Numerical Algorithms, 65, 809-842.
https://doi.org/10.1007/s11075-013-9715-x
[14] Sharma, J.R., Guha, R.K. and Gupta, P. (2012) Some Efficient Derivative Free Methods with Memory for Solving Nonlinear Equations. Applied Mathematics and Computation, 219, 699-707.
https://doi.org/10.1016/j.amc.2012.06.062
[15] Lotfi, T., Soleymani, F., Ghorbanzadeh, M. and Assari, P. (2015) On the Construction of Some Tri-Parametric Iterative Methods with Memory. Numerical Algorithms, 70, 835-845.
https://doi.org/10.1007/s11075-015-9976-7
[16] Sharifi, S., Siegmund, S. and Salimi, M. (2016) Solving Nonlinear Equations by a Derivative-Free Form of the King’s Family with Memory. Calcolo, 53, 201-215.
https://doi.org/10.1007/s10092-015-0144-1
[17] Cordero, A., Hueso, J.L., Martinez, E. and Torregrosa, J.R. (2013) A New Technique to Obtain Derivative-Free Optimal Iterative Methods for Solving Nonlinear Equations. The Journal of Computational and Applied Mathematics, 252, 95-102.
https://doi.org/10.1016/j.cam.2012.03.030
[18] Behl, R., Gonzalez, D., Maroju, P. and Motsa, S.S. (2018) An Optimal and Efficient General Eighth-Order Derivative-Free Scheme for Simple Roots. The Journal of Computational and Applied Mathematics, 330, 666-675.
https://doi.org/10.1016/j.cam.2017.07.036
[19] Sharma, J.R. and Sharma, R. (2010) A New Family of Modified Ostrowskis Method with Accelerated Eighth-Order Convergence. Numerical Algorithms, 54, 445-458.
https://doi.org/10.1007/s11075-009-9345-5
[20] Kung, H.T. and Traub, J.F. (1974) Optimal Order of One-Point and Multi-Point Iteration. Journal of Applied and Computational Mathematics, 21, 643-651.
https://doi.org/10.1145/321850.321860
[21] Chun, C. and Neta, B. (2017) Comparative Study of Eighth-Order Methods for Finding Simple Roots of Nonlinear Equations. Numerical Algorithms, 74, 1169-1201.
https://doi.org/10.1007/s11075-016-0191-y
[22] Bi, W., Wu, Q. and Ren, H. (2009) A New Family of Eighth-Order Iterative Methods for Solving Nonlinear Equations. Applied Mathematics and Computation, 214, 236-245.
https://doi.org/10.1016/j.amc.2009.03.077
[23] Soleymani, F. (2011) On a Bi-Parametric Class of Optimal Eighth-Order Derivative-Free Methods. International Journal of Pure and Applied Mathematics, 72, 27-37.
[24] Thukral, R. (2012) A Family of Three-Point Derivative-Free Methods of Eighth-Order for Solving Nonlinear Equations. Journal of Modern Methods in Numerical Mathematics, 3, 11-21.
https://doi.org/10.20454/jmmnm.2012.281

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.