Inverse function, Taylor’s expansion, and high-order algorithms for n-th root computation.

François Dubeau and Calvin Gnang

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

An extended version of this paper entitled ”Inverse function, Taylor’s expansion, and extended Schröder’s process” has been published in the International Journal of Computer Mathematics, http://dx.doi.org/10.1080/00207160.2013.833611.

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

Key Words : nth root, Schröder’s process, inverse function, Taylor’s expansion, high-order method.

Summary

The computation of the n-th root r^{1/n} of a strictly positive real number r has a long history [1, 14]. In more recent work, for example in [10] and [20], continued fraction expansions are used to derive methods to compute r^{1/2}. Also, in [12] methods similar to those presented in [20] are obtained as special case of a determinantal family of root-finding methods [11]. For the computation of n-th root third order and fourth order methods are presented in [6]. General high order methods can be derived from the application of Newton’s method to an appropriate modified function [2] or using a modified Newton’s method applied to the original function [7, 8]. These two approaches have been revisited in [3]. Using combinations of basic functions identified for methods proposed in [2, 7], new high-order methods are derived for the computation of r^{1/2} in [15].

The goal of this paper is twofold. The first contribution is the presentation of a simple way to obtain two known families of high order methods to compute r^{1/n} established by Dubeau [2] (Computing, 57 (1996), 365-369), and by Hernandez and Romero [7] (International Journal of Computer Mathematics, 81 (2004), 1001-1014). It happens that both methods are related to the Taylor’s expansion of an inverse function. Not only we show that the method [7, 8] can be derived in an elementary manner, but we also show that it is a simple application of the Schröder’s process dating from 1870 [16, 17], see also [19]. In both case, we also show that the process can be applied to find new higher order methods.

For the second contribution, we point out a general process to increase the rate of convergence of a fixed point method. Linear combinations of two methods of the same order m are considered to increase the order m to m + 1 by zero in the asymptotic constant.

References

[1] D.F. Bateman, A historical survey of solution by functional iteration, Mathematics Magazine, 62 (1989), 155-166.

[2] F. Dubeau, Algorithms for n-th root approximation, Computing, 57 (1996), 365-369.

[3] F. Dubeau, Newton’s method and high-order algorithms for the nth root computation, Journal of Computational and Applied Mathematics, 224 (2009), 66-76.

[4] E. Durand, Solutions numériques des équations algébriques, Tome 1, Masson et Cie, Paris, 1960.

[5] J. Gerlach, Accelerated convergence in Newton’s method, SIAM Review, 36 (1994), 272-276.

[6] J.M. Gutierrez, M.A. Hernandez, and M.A. Solanova, Calculus of nth roots and third order iterative methods, Nonlinear Analysis, 47 (2001), 2875-2880.

[7] M.A. Hernandez and N. Romero, High order algorithms for approximating nth roots, International Journal of Computer Mathematics, 81 (2004), 1001-1014.

[8] M.A. Hernandez and N. Romero, Accelerated convergence in Newton’s method for approximating square roots, Journal of Computational and Applied Mathematics, 177 (2005), 225-229.

[9] A.S. Househoulder, Principles of Numerical Analysis, McGraw Hill, Columbus, N.Y., 1953.

[10] K.R. Johnson, An iterative method for approximating square roots, Math. Mag., 62 (1989), 253-259.

[11] B. Kalantari, On the order of convergence of determinantal family of root-finding methods, BIT, 39 (1999), 96-109.

[12] B. Kalantari and I. Kalantari, High order methods for approximating square roots, BIT, 36 (1996), 395-399.

[13] D. Kincaid and W. Cheney, Numerical Analysis, Brooks/Cole Pub. Co., California, 1991.

[14] R.J. Knill, A modified Babylonian algorithm, American Mathematical Monthly, 99 (1992), 734-737.

[15] A.Y.Özban, New methods for approximating square roots, Applied mathematics and Computation, 175 (2006), 532-540.

[16] E. Schröder, Uber unendlich viele Algorithmen zur Auflosung der Gleichungen, Math. Ann., 2 (1870), 317-365.

[17] E. Schröder, On Infinitely Many Algorithms for Solving Equations, Translated by G.W. Stewart, Institute for advanced Computer Studies, TR-92-121 and TR-2990, University of Maryland, 1992.

[18] J. Stoer and R. Bulirsch, Introduction to Numerical Analysis, 2nd Ed., Springer-Verlag, N.Y., 1993.

[19] J.F. Traub, Iterative Methods for the Solution of Equations, Prentice-Hall, Englewood Cliffs, N.J., 1964.

[20] A.K. Yeyios, On two sequences of algorithms for approximating square roots, Journal of Computational and Applied Mathematics, 40 (1992), 63-72.