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 . In this paper we make use of a fundamental family of iteration functions , , to derive an infinite family of lower bounds on the above gap. However, even for , where 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 is a complex polynomial of degree , for small the corresponding bound is computable in arithmetic operations. For quadratic polynomials, as 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 . In particular, using the latter result, we show that, given a complex polynomial , , for each we can compute upper and lower bounds and such that the roots of lie in the annulus . In particular, , ; and , , where . An application of the latter bounds is within Weyl's classical quad-tree algorithm for computing all roots of a given complex polynomial.

**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 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.

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