Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

An infinite family of bounds on zeros of analytic functions and relationship to Smale's bound


Author: Bahman Kalantari
Journal: Math. Comp. 74 (2005), 841-852
MSC (2000): Primary 12D10, 65H05, 30C15, 68Q25
DOI: https://doi.org/10.1090/S0025-5718-04-01686-2
Published electronically: May 28, 2004
Corrigendum: Math. Comp. 74 (2005), 2101.
MathSciNet review: 2114651
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Smale's analysis of Newton's iteration function induce a lower bound on the gap between two distinct zeros of a given complex-valued analytic function $f(z)$. In this paper we make use of a fundamental family of iteration functions $B_m(z)$, $m \geq 2$, to derive an infinite family of lower bounds on the above gap. However, even for $m=2$, where $B_2(z)$ coincides with Newton's, our lower bound is more than twice as good as Smale's bound or its improved version given by Blum, Cucker, Shub, and Smale. When $f(z)$ is a complex polynomial of degree $n$, for small $m$ the corresponding bound is computable in $O(n \log n)$ arithmetic operations. For quadratic polynomials, as $m$ increases the lower bounds converge to the actual gap. We show how to use these bounds to compute lower bounds on the distance between an arbitrary point and the nearest root of $f(z)$. In particular, using the latter result, we show that, given a complex polynomial $f(z)=a_n z^n + \cdots + a_0$, $a_na_0 \not=0$, for each $m \geq 2$ we can compute upper and lower bounds $U_m$ and $L_m$ such that the roots of $f(z)$ lie in the annulus $\{z : L_m \leq \vert z\vert \leq U_m\}$. In particular, $L_2={1 \over 2}/\max \{ \vert{{a_k} / {a_0}}\vert^{1/k}: k=1, \dots, n\}$, $U_2=2 \max \{ \vert{{a_{n-k}} / {a_n}}\vert^{1/k}: k=1, \dots, n\}$; and $L_3 =[(\sqrt{5}-1)/2] / \max \{ ({{\vert a_1a_{k-1}-a_0a_{k}\vert} / {\vert a_0^2\vert}})^{1/k}: k=2, \dots, n+1 \}$, $U_3 = [(\sqrt{5}+1)/2] \max \{ ({{\vert a_{n-1}a_{n-k+1}-a_na_{n-k}\vert} / {\vert a_n^2\vert}} )^{1/k}: k=2, \dots, n+1 \}$, where $a_{-1}=a_{n+1}=0$. An application of the latter bounds is within Weyl's classical quad-tree algorithm for computing all roots of a given complex polynomial.


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

  • 1. Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636
  • 2. Jean-Pierre Dedieu, Estimations for the separation number of a polynomial system, J. Symbolic Comput. 24 (1997), no. 6, 683–693. MR 1487794, https://doi.org/10.1006/jsco.1997.0161
  • 3. E. Halley, A new, exact, and easy method of finding roots of any equations generally, and that without any previous reduction, Philos. Trans. Roy. Soc. London, 18 (1694), 136-145.
  • 4. Peter Henrici, Applied and computational complex analysis, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Volume 1: Power series—integration—conformal mapping—location of zeros; Pure and Applied Mathematics. MR 0372162
  • 5. A. S. Householder, The numerical treatment of a single nonlinear equation, McGraw-Hill Book Co., New York-Düsseldorf-London, 1970. International Series in Pure and Applied Mathematics. MR 0388759
  • 6. B. Kalantari and I. Kalantari, High order iterative methods for approximating square roots, BIT 36 (1996), no. 2, 395–399. MR 1432256, https://doi.org/10.1007/BF01731991
  • 7. Bahman Kalantari, Iraj Kalantari, and Rahim Zaare-Nahandi, A basic family of iteration functions for polynomial root finding and its characterizations, J. Comput. Appl. Math. 80 (1997), no. 2, 209–226. MR 1455244, https://doi.org/10.1016/S0377-0427(97)00014-9
  • 8. Bahman Kalantari, On the order of convergence of a determinantal family of root-finding methods, BIT 39 (1999), no. 1, 96–109. MR 1682412, https://doi.org/10.1023/A:1022321325108
  • 9. Bahman Kalantari, Generalization of Taylor’s theorem and Newton’s method via a new family of determinantal interpolation formulas and its applications, J. Comput. Appl. Math. 126 (2000), no. 1-2, 287–318. MR 1806762, https://doi.org/10.1016/S0377-0427(99)00360-X
  • 10. B. Kalantari, Approximation of polynomial root using a single input and the corresponding derivative values, Technical Report DCS-TR 369, Department of Computer Science, Rutgers University, New Brunswick, New Jersey, 1998.
  • 11. B. Kalantari, Halley's method is the first member of an infinite family of cubic order root-finding methods, Technical Report DCS-TR 370, Department of Computer Science, Rutgers University, New Brunswick, New Jersey, 1998.
  • 12. Bahman Kalantari and Jürgen Gerlach, Newton’s method and generation of a determinantal family of iteration functions, J. Comput. Appl. Math. 116 (2000), no. 1, 195–200. MR 1741795, https://doi.org/10.1016/S0377-0427(99)00361-1
  • 13. Bahman Kalantari, New formulas for approximation of 𝜋 and other transcendental numbers, Numer. Algorithms 24 (2000), no. 1-2, 59–81. Computational methods from rational approximation theory (Wilrijk, 1999). MR 1784992, https://doi.org/10.1023/A:1019184908442
  • 14. B. Kalantari, On homogeneous linear recurrence relations and approximation of zeros of complex polynomials, in Unusual Applications in Number Theory (M.B. Nathanson, Ed.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 64, 2000, pp. 125-143.
  • 15. Bahman Kalantari and Seungyoung Park, A computational comparison of the first nine members of a determinantal family of root-finding methods, J. Comput. Appl. Math. 130 (2001), no. 1-2, 197–204. MR 1827980, https://doi.org/10.1016/S0377-0427(99)00383-0
  • 16. B. Kalantari and Y. Jin, On extraneous fixed-points of the basic family of iteration functions, BIT, 43 (2003), 453-458.
  • 17. B. Kalantari, Polynomiography: A new intersection between mathematics and art, Technical Report DCS-TR 506, Department of Computer Science, Rutgers University, New Brunswick, New Jersey, 2002 (www.polynomiography.com)
  • 18. B. Kalantari, A generalization of Smale's one-point theory for the basic family, Department of Computer Science, Rutgers University, New Brunswick, New Jersey, forthcoming.
  • 19. Victor Y. Pan, Solving a polynomial equation: some history and recent progress, SIAM Rev. 39 (1997), no. 2, 187–220. MR 1453318, https://doi.org/10.1137/S0036144595288554
  • 20. T. R. Scavo and J. B. Thoo, On the geometry of Halley’s method, Amer. Math. Monthly 102 (1995), no. 5, 417–426. MR 1327786, https://doi.org/10.2307/2975033
  • 21. E. Schröder, On infinitely many algorithms for solving equations (German), Math. Ann. 2 (1870) 317-365.(English translation by G.W. Stewart, TR-92-121, Institute for Advanced Computer Studies, University of Maryland, College Park, MD, 1992.)
  • 22. Mike Shub and Steven Smale, Computational complexity. On the geometry of polynomials and a theory of cost. I, Ann. Sci. École Norm. Sup. (4) 18 (1985), no. 1, 107–142. MR 803197
  • 23. Steve Smale, Newton’s method estimates from data at one point, The merging of disciplines: new directions in pure, applied, and computational mathematics (Laramie, Wyo., 1985) Springer, New York, 1986, pp. 185–196. MR 870648
  • 24. J. F. Traub, Iterative methods for the solution of equations, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964. MR 0169356
  • 25. Edward R. Vrscay and William J. Gilbert, Extraneous fixed points, basin boundaries and chaotic dynamics for Schröder and König rational iteration functions, Numer. Math. 52 (1988), no. 1, 1–16. MR 918313, https://doi.org/10.1007/BF01401018
  • 26. Tjalling J. Ypma, Historical development of the Newton-Raphson method, SIAM Rev. 37 (1995), no. 4, 531–551. MR 1368386, https://doi.org/10.1137/1037125
  • 27. H. Weyl, Randbemerkungen zu Hauptproblemen der Mathematik. II. Fundamentalsatz der Algebra und Grundlagen der Mathematik, Math. Z. 20 (1924), 142-150.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 12D10, 65H05, 30C15, 68Q25

Retrieve articles in all journals with MSC (2000): 12D10, 65H05, 30C15, 68Q25


Additional Information

Bahman Kalantari
Affiliation: Department of Computer Science, Rutgers University, New Brunswick, New Jersey 08903
Email: kalantar@cs.rutgers.edu

DOI: https://doi.org/10.1090/S0025-5718-04-01686-2
Keywords: Newton's method, Smale's separation lower bound, fixed-points, basic family
Received by editor(s): May 5, 2003
Received by editor(s) in revised form: October 2, 2003
Published electronically: May 28, 2004
Article copyright: © Copyright 2004 American Mathematical Society