Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

The construction of rational iterating functions


Author: W. F. Smyth
Journal: Math. Comp. 32 (1978), 811-827
MSC: Primary 30A20; Secondary 65E05
MathSciNet review: 0486465
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Suppose integers $ n \geqslant 1$ and $ \sigma \geqslant 2$ are given, together with n distinct points $ {z_2}, \ldots ,{z_n}$, in the complex plane. Define $ {\Phi _M} = {\Phi _M}(\sigma ;{z_1}, \ldots ,{z_n})$ to be the class of rational functions $ {\phi _{p,q}}(z) = {g_p}(z)/{h_q}(z)$ (where g and h are polynomials of degree $ p \geqslant 1$ and $ q \geqslant 1$, respectively) such that $ (1)\;p + q + 1 = M,(2)\;\phi $ when iterated converges with order $ \sigma $ at each $ {z_i}, i = 1, \ldots ,n$. Then if $ M < \sigma n,{\Phi _M}$ is null; if $ M = \sigma n$ $ {\Phi _M}$ contains exactly $ \sigma n$ elements. For every $ M \geqslant \sigma n$, we show how to construct all the elements of $ {\Phi _M}$ by expressing, for each choice of p and q which satisfies $ p + q + 1 = M$ , the coefficients of $ {g_p}$ and $ {h_q}$ in terms of $ M - \sigma n$ arbitrarily chosen values. In fact, these coefficients are expressed in terms of generalized Newton sums $ S_n^{j,k} = S_n^{j,k}({z_1}, \ldots ,{z_n})$, $ 1 \leqslant j \leqslant n,k \geqslant n$, which we show may be calculated by recursion from the normal Newton sums $ S_n^{j,n}$. Hence, given a polynomial $ {f_n}(z)$ with n distinct (unknown) zeros $ {z_1}, \ldots ,{z_n}$, we may construct all $ {\phi _{p,q}}(z)$ which converge to the $ {z_i}$ with order $ \sigma $ in the case $ \sigma = 2$, the choice $ p = n$, $ q = n - 1$, yields the Newton-Raphson iteration $ {\phi _{n,n - 1}} \in {\Phi _{2n}}$; the Schröder and König iterations are shown to be elements of $ {\Phi _{2(2\sigma - 3)(n - 1) + 2}}$ and $ {\Phi _{2(\sigma - 1)(n - 1) + 2}}$, respectively. We show by example that there exist cases in which $ {\phi _{n,n - 1}}$ has an undesirable property (attractive cycles) not shared by other iterating functions in the same class $ {\Phi _{2n}}$.


References [Enhancements On Off] (What's this?)

  • [1] GASTON JULIA, "Mémoires sur l'itération des fonctions rationnelles," J. Math. Pures Appl., v. 1, 1918, pp. 47-245.
  • [2] P. Fatou, Sur les équations fonctionnelles, Bull. Soc. Math. France 47 (1919), 161–271 (French). MR 1504787
  • [3] PAUL MONTEL, Leçons sur les Familles Normales de Fonctions Analytiques et Leurs Applications, Gauthier-Villars, Paris, 1927.
  • [4] Paul Montel, L’itération, Univ. Nac. La Plata. Publ. Fac. Ci. Fisicomat. Revista (2) 3 (1940), 201–211 (French). MR 0002590 (2,80a)
  • [5] Hans Rådström, On the iteration of analytic functions, Math. Scand. 1 (1953), 85–92. MR 0056702 (15,115a)
  • [6] R. A. Brooker, The solution of algebraic equations on the EDSAC, Proc. Cambridge Philos. Soc. 48 (1952), 255–270. MR 0046138 (13,691e)
  • [7] HUBERT CREMER, "Über die Iteration rationaler Funktionen," Jber. Deutsch. Math.-Verein., v. 9, 1952, pp. 185-210.
  • [8] H. S. HALL & S. R. KNIGHT, Higher Algebra, Macmillan, New York, 1950.
  • [9] E. Schröder, Ueber unendlich viele Algorithmen zur Auflösung der Gleichungen, Math. Ann. 2 (1870), no. 2, 317–365 (German). MR 1509664, http://dx.doi.org/10.1007/BF01444024
  • [10] A. S. Householder, Schröder and Trudi: a historical excursion, SIAM Rev. 16 (1974), 344–348. MR 0359308 (50 #11762)
  • [11] Alston S. Householder, Principles of numerical analysis, McGraw-Hill Book Company, Inc., New York-Toronto-London, 1953. MR 0059056 (15,470b)
  • [12] JAMES L. HOWLAND, Private communication, 1977.
  • [13] L. LEAU, "Étude sur les équations fonctionnelles," Ann. Fac. Sci. Univ. Toulouse, v. 11, 1897, pp. 22, 29-35.
  • [14] E. DURAND, Solutions Numériques des Équations Algébriques. I, Masson, Paris, 1960.
  • [15] P. Jarratt and D. Nudds, The use of rational functions in the iterative solution of equations on a digital computer, Comput. J. 8 (1965), 62–65. MR 0179936 (31 #4173)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 30A20, 65E05

Retrieve articles in all journals with MSC: 30A20, 65E05


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1978-0486465-4
PII: S 0025-5718(1978)0486465-4
Article copyright: © Copyright 1978 American Mathematical Society