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

Research output: Contribution to journalArticle

18 Citations (Scopus)

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 ≥ 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 nz n + . . . + a 0, a na 0 ≠ 0, for each m > 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 ≤ |z| ≤ U m}. In particular, L 2 = 1/2/max{|a k/a 0| 1/k: k = 1, . . ., n}, U 2 = 2 max{|a n-k/a n| 1/k: k = 1, . . ., n}; and L 3 = [(√5 - 1)/2]/max{(|a 1a k-1 - a 0a k|/|a 0 2|) 1/k:: k = 2, . . ., n + 1}, U 3 = [(√5 + 1)/2]max{(|a n-1a n-k+1 - a na n-k|/ |a n 2|) 1/k: k = 2, . . ., 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.

Original languageEnglish (US)
Pages (from-to)841-852
Number of pages12
JournalMathematics of Computation
Volume74
Issue number250
DOIs
StatePublished - Apr 1 2005

Fingerprint

Analytic function
Complex Polynomials
Polynomials
Lower bound
Iteration Function
Zero
Roots
Quadtree
Newton Iteration
Quadratic Polynomial
Tree Algorithms
Ring or annulus
Upper and Lower Bounds
Relationships
Family
Distinct
Converge
Computing
Arbitrary

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Applied Mathematics
  • Computational Mathematics

Keywords

  • Basic family
  • Fixed-points
  • Newton's method
  • Smale's separation lower bound

Cite this

@article{9ac7e0ea5d9a4903ad57228ee340dc1e,
title = "An infinite family of bounds on zeros of analytic functions and relationship to smale's bound",
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 ≥ 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 nz n + . . . + a 0, a na 0 ≠ 0, for each m > 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 ≤ |z| ≤ U m}. In particular, L 2 = 1/2/max{|a k/a 0| 1/k: k = 1, . . ., n}, U 2 = 2 max{|a n-k/a n| 1/k: k = 1, . . ., n}; and L 3 = [(√5 - 1)/2]/max{(|a 1a k-1 - a 0a k|/|a 0 2|) 1/k:: k = 2, . . ., n + 1}, U 3 = [(√5 + 1)/2]max{(|a n-1a n-k+1 - a na n-k|/ |a n 2|) 1/k: k = 2, . . ., 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.",
keywords = "Basic family, Fixed-points, Newton's method, Smale's separation lower bound",
author = "Bahman Kalantari",
year = "2005",
month = "4",
day = "1",
doi = "10.1090/S0025-5718-04-01686-2",
language = "English (US)",
volume = "74",
pages = "841--852",
journal = "Mathematics of Computation",
issn = "0025-5718",
publisher = "American Mathematical Society",
number = "250",

}

An infinite family of bounds on zeros of analytic functions and relationship to smale's bound. / Kalantari, Bahman.

In: Mathematics of Computation, Vol. 74, No. 250, 01.04.2005, p. 841-852.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An infinite family of bounds on zeros of analytic functions and relationship to smale's bound

AU - Kalantari, Bahman

PY - 2005/4/1

Y1 - 2005/4/1

N2 - 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 ≥ 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 nz n + . . . + a 0, a na 0 ≠ 0, for each m > 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 ≤ |z| ≤ U m}. In particular, L 2 = 1/2/max{|a k/a 0| 1/k: k = 1, . . ., n}, U 2 = 2 max{|a n-k/a n| 1/k: k = 1, . . ., n}; and L 3 = [(√5 - 1)/2]/max{(|a 1a k-1 - a 0a k|/|a 0 2|) 1/k:: k = 2, . . ., n + 1}, U 3 = [(√5 + 1)/2]max{(|a n-1a n-k+1 - a na n-k|/ |a n 2|) 1/k: k = 2, . . ., 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.

AB - 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 ≥ 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 nz n + . . . + a 0, a na 0 ≠ 0, for each m > 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 ≤ |z| ≤ U m}. In particular, L 2 = 1/2/max{|a k/a 0| 1/k: k = 1, . . ., n}, U 2 = 2 max{|a n-k/a n| 1/k: k = 1, . . ., n}; and L 3 = [(√5 - 1)/2]/max{(|a 1a k-1 - a 0a k|/|a 0 2|) 1/k:: k = 2, . . ., n + 1}, U 3 = [(√5 + 1)/2]max{(|a n-1a n-k+1 - a na n-k|/ |a n 2|) 1/k: k = 2, . . ., 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.

KW - Basic family

KW - Fixed-points

KW - Newton's method

KW - Smale's separation lower bound

UR - http://www.scopus.com/inward/record.url?scp=14944362608&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=14944362608&partnerID=8YFLogxK

U2 - 10.1090/S0025-5718-04-01686-2

DO - 10.1090/S0025-5718-04-01686-2

M3 - Article

VL - 74

SP - 841

EP - 852

JO - Mathematics of Computation

JF - Mathematics of Computation

SN - 0025-5718

IS - 250

ER -