Remote Access Mathematics of Computation
Green Open Access

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
DOI: https://doi.org/10.1090/S0025-5718-1978-0486465-4
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, v. 47, 1919, pp. 161-271. 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. Serie Segunda Rev., v. 3, 1940, pp. 201-211. MR 0002590 (2:80a)
  • [5] H. RÅDSTRÖM, "On the iteration of analytic functions," Math. Scand., v. 1, 1953, pp. 85-92. MR 0056702 (15:115a)
  • [6] R. A. BROOKER, "The solution of algebraic equations on the EDSAC," Proc. Cambridge Philos. Soc., v. 48, 1952, pp. 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] ERNST SCHRÖDER, "Über unendlich viele Algorithmen zur auflösung der Gleichungen," Math. Ann., v. 23, 1870, pp. 317-365. MR 1509664
  • [10] A. S. HOUSEHOLDER, "Schröder and Trudi: a historical excursion," SIAM Rev., v. 16, 1974, pp. 344-348. MR 0359308 (50:11762)
  • [11] A. S. HOUSEHOLDER, Principles of Numerical Analysis, McGraw-Hill, New York, 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 & D. NUDDS, "The use of rational functions in the iterative solution of equations on a digital computer," Comput. J., v. 8, 1965, pp. 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: https://doi.org/10.1090/S0025-5718-1978-0486465-4
Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society