American Journal of Computational Mathematics
Vol.10 No.01(2020), Article ID:98889,18 pages
10.4236/ajcm.2020.101007
Constructive Theory of Designing Optimal Eighth-Order Derivative-Free Methods for Solving Nonlinear Equations
Tugal Zhanlav1, Khuder Otgondorj2, Renchin-Ochir Mijiddorj1,3
1Institute of Mathematics and Digital Technology, Mongolian Academy of Sciences, Ulaanbaatar, Mongolia
2School of Applied Sciences, Mongolian University of Science and Technology, Ulaanbaatar, Mongolia
3Department of Informatics, Mongolian National University of Education, Ulaanbaatar, Mongolia
Copyright © 2020 by author(s) and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: February 17, 2020; Accepted: March 14, 2020; Published: March 17, 2020
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.
Keywords:
Multipoint Methods, Derivative-Free Methods, Order of Convergence
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.
Conflicts of Interest
The authors declare no conflicts of interest regarding the publication of this paper.
Cite this paper
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. https://doi.org/10.4236/ajcm.2020.101007
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