Constructive Theory of Designing Optimal Eighth-Order Derivative-Free Methods for Solving Nonlinear Equations ()
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]
(1)
in which the parameters
and
are given by
(2)
and
(3)
where
, and
. In [9] was proven the following theorem.
Theorem 1. Let the function
be sufficiently smooth and have a simple root
. Furthermore, let the initial approximation
be sufficiently close to
. Then, the convergence order of the iterative method (1) is eight if and only if the parameters
and
satisfy conditions (2) and (3), respectively.
Remark. The second sub-step in (1) can be rewritten as any two-point optimal fourth-order method
where
is a real function using the evaluation of
and
. Each method in
has a parameter
given by (2) with own
and
.
Now we consider the derivative-free variant of (1)
(4)
where
(5)
Here
is any second-order method. Actually, in Formula (4), the fundamental quantities are
Then
,
for
, where
is a simple root of
. If
is any two-point optimal fourth-order method then
, therefore
. The iteration (4) obtained from (1) replacing
by
. Due to change (5), the parameters in (4) does not remain as before and we denote them by
and
. We call the iterations (1) and (4) the derivative presence (DP) and derivative-free (DF) variants respectively. If we use the notations
then we have
(6)
DP can be derived from DF by substituting
. 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
and
in (4) are given by formulas
(7)
and
(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
. Our proposed method is in concurrence with the conjecture as it needs only four function evaluation per iteration i.e.,
. Moreover, using ideas in [3] [10] one can propose more general construction for
and
as following:
Define
as sufficiently smooth functions of
. It is easy to show that
if and only if
, where
,
. Hence, under the restriction
, (4) is optimal if and only if
Those can be easily checked with using (6). For the optimal formula, the remainder term is
in (8) because
. In this sense, we can say that (4) is optimal if and only if
can be written as (7) and (8).
When
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
(9)
where
is obtained replacing
by
in
in (1). From (9) we find that
(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
we can obtain different iterations. We consider some special cases.
1) Let
in (4) be a form
(11)
where
, and
are smooth enough functions. As regarding the iteration (4) with
given by (11) we give the following result.
Theorem 3. The iteration (4) with
given by (7) and with
given by (11) have the order of convergence eight, if the following conditions hold:
(12)
Proof. Using the Taylor expansion of smooth enough functions
and
we obtain an expression for (11). The comparison of this expression with sufficient condition (8) gives conditions (12).
When
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
:
(13)
Therefore, Theorem 3 is more general, than that of [5]. Note that, in [5] are proposed four variants of
that include redundant terms like
and
. By neglecting these terms,
can be simplified essentially without loss of the order of convergence. When
the condition (12) reduced to
(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
given by (11) and with
In this case
and
and the condition (14) coincides with that of [1]. They also considered another particular case of (1) with
given by (11) and
In this case
and the condition (14) leads to that of [1]. The function
in (11) can be written as
(15)
Due to generating function method [10] instead of
we can take any function H
(16)
satisfying conditions
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
and
as:
That is we have the iterations (4) with
is given by (16) and
is given by
(17)
Note that the choice of parameter
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
in (4) be a form
(18)
where
is given by (7) and
is sufficient smooth function of
and
.
Theorem 4. The iteration (4) with
given by (7) and
given by (18) has the order of convergence eight, if the following conditions hold:
(19)
Proof. From (7) and (8) it is clear that
(20)
which holds under conditions (19).
The (DP) variant of this iteration is obtained from (4), (7), and (18) when
. Note that the similar scheme was considered in [2].
In some cases, the form
(21)
obtained from (18) is useful. Using (20) we obtain
(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:
(23)
Proof. If we take (22) into account in the Taylor expansion of function
we arrive at (23).
When
the conditions (23) take a form
(24)
Remark. Obviously, as for
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.,
(25)
that does not coincide with (22). Moreover, the terms
and
seem to be redundant, because it suffices to determine
with accuracy
.
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
(26)
The Bi-Wu-Ren’s optimal eighth-order method [22] has a form (1) with
(27)
where
But (27) is not the example for (21).
The Sharma and Arora’s optimal eighth-order method [21] has a form (1) with
(28)
Moreover, we suggest that more general theory for
as
3) Let
in (4) be a form
(29)
that often used in practice, see [4] [12] [14] [15] [16]. Of course,
and
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)
(30)
where
.
In [6] is proposed the eighth-order iteration (1) with (29) (
) and special
(31)
Our iteration (1) with (2) and (30) is more general than that of [6].
4) Let
in (4) be a form
(32)
where
.
We shall find the coefficients
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:
(33)
Proof. Using the following relations
(34)
we get
(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
and
. Then from (33) we find that
Hence we obtain
(36)
or
(37)
where
. The sign ≈ in (37) indicates that it holds with accuracy
. Now, we consider concrete choice of
:
(38)
For the choice (38) we have
and
The iteration (4) with (38) and (36) (or (37)) is converted to one given by Soleymani in [23] for
and one given by Thukral in [7] for
. For the choice
the parameter
is simplified as
(39)
or using
we have
(40)
Let
(41)
with
Then
and we have
(42)
The iteration (4) with (41) and (42) coincides with one given by Soleymani in [23] with
here we can neglect the redundant terms
. Let
, and
. Then from (33) we find that
The Formula (32) is converted to
(43)
On the other hand, the direct calculation using relations (34) gives
(44)
We choose parameter
in (44) such that the expression (44) coincides with the numerator of (43) within accuracy
. That is to say, that
As a result, (43) can be rewritten as
(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
) for some special
:
In this case
and hence
, the
given by (45) leads to that of
and
in [24]. So, the Thukral’s method (
) are included in our family of (4) with (7) and (45). Thukral in [24] proposed also Petković type methods (
). For
we get
, i.e.
. In this case
in (45) and our family of method (4) with (45) converted to
. For
we get
(46)
In this case
and
. Thus, our family of method (4) with (45) converted to
. It means that the (
) methods are also included in our family of (4) with (7) and (45). As stated above for the choice of (41) we have
, so (45) is simplified as
(47)
Thus, we have optimal (DF) methods
(48)
where
is defined by (47). This is (DF) variant of Sharma and Sharma’s optimal methods given in [19] [21] within accuracy
. 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
and
. 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:
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
, where
is a root of
and the approximation
to
. In all examples, we consider that the parameter
and that
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
arises from this problem.
has two zeros. Obviously, one of the roots
is not taken for discussion. Another root is
. Now, we give some numerical experiments and compare new methods with some well-known methods for the smooth function
using the initial guess
. In Table 2 and Table 3, we exhibit computational order of convergence (COC) and absolute error
as well as iteration numbers n are displayed. For presented methods and test functions, by using (see, e.g., [4] [11] [16])
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
.
Table 3. Some particular cases of (4) with
(16) and
(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
using the stopping criterion
.
As
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
, 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
.
used lesser than other existing methods under condition
. 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
given by (16) and
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.