On comparisons of Chebyshev-Halley iteration functions based on their asymptotic constants

François Dubeau

Département de mathématiques Faculté des sciences, Université de Sherbrooke 2500, boul. de l’Université, Sherbrooke (Qc), Canada, J1K 2R1 francois.dubeau@usherbrooke.ca

Paper published in the International Journal of Pure and Applied Mathematics, 85.5 (2013), 965-981.

AMS Subject Classification : 11B37, 65B99, 65D99, 65H05.

Key Words :Chebyshev-Halley iteration functions, asymptotic constant, order of convergence, local asymptotic constant, local order of convergence.

Summary

Methods for solving a nonlinear equation are classified by their order of convergence p and the number d of function (and derivatives) evaluations per step. Based on p and d, there are two efficiency measures defined by I = p/d (informational efficiency) and E = p^{1/d} (efficiency index) [12]. These measures do not depend on the function f(x) nor on the number of steps required to solve the problem within a given precision. Unfortunately, for methods of the same order p and demanding the same number of function evaluations d, these two measures are the same for these methods. For example, each iteration function (IF) of the Chebyshev-Halley family is of order p = 3 and requires d = 3 evaluations per step (evaluation of f(x), f^{(1)}(x), and f^{(2)}(x)).

Another measure introduced recently is the basin of attraction of a given IF ([10] and the references therein). The basin of attraction depends on f(x) and, for a given method of order p, the ”local order” of convergence in the basin is not necessarily p for the first steps of the method.

Moreover, since the number of steps required to reach a given precision is not known, it is difficult to classify methods with respect to the efficiency index, the informational efficiency, and even their basins of attraction (which depend on f(x)).

In many papers, to compare methods authors take one arbitrary initial point and study the error after the same number of steps or the number of steps required to get a given error bounds (see for examples [2, 11]). This number of step depends on how far the initial trial x_{0} is from the solution α, and the value of the asymptotic constant. For two methods of the same order p, the method having the smallest asymptotic constant will converge faster than the second method having the higher asymtotic constant, for a starting point x_{0} sufficiently close to the solution α. Unfortunately, as for the basin of attraction, the asymtotic constant depends on the function f(x).

One goal of this paper is to illustrate the role of the asymptotic constants in the rapidity of convergence of iterative methods and show that it is difficult to classify IFs based on the asymptotic constant and the basin of attraction.

In Section 2 we introduce definitions and basic results on asymptotic constants and order of convergence. In Section 3 we present a one parameter formula valid to describe each member of the Chebyshev-Halley family of IFs of order 3, and an expression for their asymptotic constants. In Section 4, to illustrate the points raised in the introduction about te comparison of IFs, we present numerical experiments using the Chebyshev-Halley family of IFs of order 3. At first, we apply the IFs on set of 5 test functions already used in [11] to compare similar IFs. We choose initial points x_{0} in the basin of attraction of the considered solution α and study the role of the asymptotic constant on the convergence speed. In second, we consider a form of particular test functions for which IFs of the Chebyshev-Halley family are of order p for arbitrary p ≥ 3. Finally we consider the n-th root computation problem of a real number to compare the asymptotic constant of the methods. Concluding remarks are given in Section 5.

References

[1] I.K. Argyros and F. Szidarovszky, The Theory and Applications of Iteration Methods, CRC Press, USA (1993).

[2] M. Basto, V. Semiao, and F.L. Calheiros, A new iterative method to compute nonlinear equations, Appl. Math. Comput., 173, No. 1 (2006), 468-483. http://dx.doi.org/10.1016/j.amc.2005.04.045

[3] E. Bodewig, Sur la méthode Laguerre pour l’approximation des racines de certaines équations algébriques et sur la critique d’Hermite, Indag. Math., 8 (1946), 570-580.

[4] F. Dubeau and C. Gnang, On the Chebyshev-Halley family of iteration functions and the n-th root computation problem, Int. J. Pure Appl. Math., 87, 3 (2013), to appear.

[5] W. Gander, On Halley’s iteration method, Amer. Math. Month., 92, No. 2 (1985), 131-134. http://dx.doi.org/10.2307/2322644

[6] J. Gerlach, Accelerated convergence in Newton’s method, SIAM Review, 36, No. 2 (1994), 272-276. http://dx.doi.org/10.1137/1036057

[7] J.M. Gutiérrez and M.A. Hernandez, A family of Chebyshev-Halley type methods in Banach spaces, Bull. Austral. Math. Soc., 55, No. 1 (1997), 113-130. http://dx.doi.org/10.1017/S0004972700030586

[8] J.M. Gutiérrez and M.A. Hernández, An accaleration of Newton’s method: Super-Halley method, Appl. Math. Comput., 117. No. 2-3 (2001), 223-239. http://dx.doi.org/10.1016/S0096-3003(99)00175-7

[9] J.M. Gutiérrez, M.A. Hernández, and M.-A. Salanova, Calculus of nth roots and third order iterative methods, Nonlinear analysis, 47, No. 4 (2001), 2875-2880. http://dx.doi.org/10.1016/S0362-546X(01)00408-4

[10] B. Neta, M. Scott, and C Chun, Basins of attraction for several methods to find simple roots of nonlinear equations, J. Appl. Math. Comput., 218, No. 21 (2012), 10548-10556. http://dx.doi.org/10.1016/j.amc.2012.04.017

[11] M.S. Petković, Comments on the Basto-Semiao-Calheiros root finding method, Appl. Math. Comput., 184, No. 2 (2007), 143-148. http://dx.doi.org/10.1016/j.amc.2006.05.201

[12] J.F. Traub, Iterative Methods for the Solution of Equations, Prentice-Hall, USA (1964). http://dx.doi.org/10.2307/2004117

[13] W. Werner, Some improvements of classical iterative methods for the solution of nonlinear equations, in Numerical Soution of Nonlinear equations, (Proc., Bremen, 1980), E.L. Allgower, K. Glashoff and H.O. Peitgen, eds, Lecture Notes in Math., 878, (1981), 427-440. http://dx.doi.org/10.1007/BFb0090691