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

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. L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer-Verlag, New York, 1998.MR 99a:68070
  • 2. J.-P. Dediue, Estimation for the separation number of a polynomial system, J. Symbolic Computation 24 (1997), 683-693.MR 99b:65065
  • 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. P. Henrici, Applied and Computational Complex Analysis, Vol. I, Wiley, New York, 1974. MR 51:8378
  • 5. A.S. Householder, The Numerical Treatment of a Single Nonlinear Equation, McGraw-Hill, New York, 1970. MR 52:9593
  • 6. B. Kalantari, and I. Kalantari, High order iterative methods for approximating square roots, BIT 36 (1996), 395-399. MR 97k:65039
  • 7. B. Kalantari, I. Kalantari, and R. Zaare-Nahandi, A basic family of iteration functions for polynomial root finding and its characterizations, J. of Comp. and Appl. Math., 80 (1997), 209-226. MR 98d:65066
  • 8. B. Kalantari, On the order of convergence of a determinantal family of root-finding methods, BIT 39 (1999), 96-109. MR 2000b:65099
  • 9. B. Kalantari, Generalization of Taylor's theorem and Newton's method via a new family of determinantal interpolation formulas and its applications, J. of Comp. and Appl. Math., 126 (2000), 287-318.MR 2001m:41035
  • 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. B. Kalantari and J. Gerlach, Newton's method and generation of a determinantal family of iteration functions, J. of Comp. and Appl. Math., 116 (2000), 195-200. MR 2000k:65098
  • 13. B. Kalantari, New formulas for approximation of $\pi$and other transcendental numbers, Numerical Algorithms 24 (2000), 59-81. MR 2001h:11087
  • 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. B. Kalantari and S. Park, A computational comparison of the first nine members of a determinantal family of root-finding methods, J. of Comp. and Appl. Math., 130 (2001), 197-204. MR 2002b:65079
  • 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. V. Y. Pan, Solving a polynomial equation: some history and recent progress, SIAM Review, 39 (1997), 187-220.MR 99b:65066
  • 20. T. R. Scavo and J. B. Thoo, On the geometry of Halley's method, Amer. Math. Monthly, 102 (1995), 417-426. MR 96f:01019
  • 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. M. Shub and S. Smale, Computational complexity: On the geometry of polynomials and a theory of cost, Part I, Ann. Sci. Ecole Norm. Sup., 18 (1985), 107-142. MR 87m:68043
  • 23. S. Smale, Newton's method estimates from data at one point, in The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics, R. E. Ewing, K.I. Gross, C. F. Martin, eds., Springer-Verlag, New York, pp. 185-196, 1986. MR 88e:65076
  • 24. J. F. Traub, Iterative Methods for the Solution of Equations, Englewood Cliffs, NJ, Prentice Hall, 1964. MR 29:6607
  • 25. E. R. Vrscay and W. J. Gilbert, Extraneous Fixed Points, Basin Boundaries and Chaotic Dynamics for Schröder and König Iteration Functions, Numer. Math. 52, 1-16 (1988). MR 89b:30026
  • 26. T. J. Ypma, Historical development of Newton-Raphson method, SIAM Review, 37 (1995), 531-551. MR 97b:01003
  • 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

American Mathematical Society