Polynomial and rational approximations and Schröder’s processes of the first and second kind

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

Submitted to publication.

AMS Subject Classification : 41A10, 41A20, 65B99, 65H05.

Key Words : Schröder’s processes, fixed point, polynomial, rational function, approximation.

Summary

In [10, 11], Schröder proposed two fixed point processes to find a simple root α of a nonlinear equation f(x) = 0. The iteration functions (IF) of arbitrary order p ≥ 2 associated to the two processes will be noted E_{p}(x) for the Schröder’s process of the first kind, and S_{p}(x) for the Schröder’s process of the second kind.

For the order 2 processes we have

E_{2}(x) = S_{2}(x) = N_{f}(x) = x = \frac{f(x)}{f^{(1)}(x)},

where N_{f}(x) is the Newton’s IF. In general for p > 2, the processes can be expressed as

(0.1)  E_{p}(x) = x − \frac{f(x)}{f^{(1)}(x)} Λ_{p−2}(ξ)|_{ξ=f(x)/f^{(1)}(x)} ,

and

(0.2)  S_{p}(x) = x − \frac{f(x)}{f^{(1)}(x)} [\frac{Γ_{p−3}(ξ)}{Γ_{p−2}(ξ)}]|_{ξ=f(x)/f^{(1)}(x)} ,

where Λ_{q}(ξ) and Γ_{q}(ξ) are polynomials of degree q ≥ 0, such that Λ_{q}(0) = 1 = Γ_{q}(0). We will describe these polynomials in Sections 3 and 4.

A question raised and discussed in [6, 8, 9] is to explain the possible link between the two processes. The main result of this paper is to show that E_{p}(x) is a polynomial approximation of S_{p}(x), that S_{p}(x) is a rational approximation of E_{p}(x), and explain the relation between the polynomials Λ_{p−2}(ξ), Γ_{p−3}(ξ) and Γ_{p−2}(ξ) in (0.1) and (0.2). In this paper we complete the work done in [8, 9].

In the next section we present some notations and definitions used in this paper. In Sections 3 and 4 we present the two Schröder’s processes and their corresponding polynomials Λ_{q}(ξ) and Γ_{q}(ξ). We prove the main result in the last section.

References

[1] T.M. Apostol, Calculating higher derivatives of inverses, American Mathematical Monthly, 107 (2000), 738-741.

[2] E. Bodewig, On types of convergence and on the behavior of approximations in the neighborhood of a multiple root of an equation, Quart. Appl. Math., 7 (1949), 325-333.

[3] W. Gander, On Halley’s iteration method, American Mathematical Monthly, 92 (1985), 131-134

[4] A.S. Househoulder, Principles of Numerical Analysis, McGraw Hill, Columbus, New York, 1953.

[5] W.P. Johnson, Combinatorics of higher derivatives of inverses, American Mathematical Monthly, 109 (2002), 273-277.

[6] B. Kalantari, I. Kalantari, and R. Zaare-Nahandi, A basic family of iteration functions for polynomial root-finding and its characterizations, Journal of computational and Applied Mathematics, 80 (1997), 209-226.

[7] M.S. Petković and D. Herceg, On rediscovered iteration methods for solving equations, Journal of Computational and Applied Mathematics, 107 (1999), 275-284.

[8] L.D. Petković and M.S. Petković, The link between Schröder’s iteration methods of the first and second kind, Novi Sad J. Math., 38 (2008), 55-63.

[9] M.S. Petković, L.D. Petković, and D. Herceg, On Schröder’s families of root-finding methods, Journal of Computational and Applied Mathematics, 233 (2010), 1755-1762.

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

[11] 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.

[12] M. Shub and S. Smale, Computation complexity: On the geometry of polynomials and the theory of cost I, Ann. Sci. École Norm. Sup., 18 (1985), 107-142.

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