An infinite family of bounds on zeros of analytic functions and relationship to Smale’s bound
Authors: Kalantari Bahman 
Published: January 2005

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
)

f(z)

. In this paper we make use of a fundamental family of iteration functions

B
m

(
z
)

B_m(z)

,

m
≥
2

m \geq 2

, to derive an infinite family of lower bounds on the above gap. However, even for

m
=
2

m=2

, where

B
2

(
z
)

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
)

f(z)

is a complex polynomial of degree

n
n

, for small

m
m

the corresponding bound is computable in

O
(
n
log
⁡
n
)

O(n \log n)

arithmetic operations. For quadratic polynomials, as

m
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
)

f(z)

. In particular, using the latter result, we show that, given a complex polynomial

f
(
z
)
=

a
n

z
n

+
⋯
+

a
0

f(z)=a_n z^n + \cdots + a_0

,

a
n

a
0

≠
0

a_na_0 \not =0

, for each

m
≥
2

m \geq 2

we can compute upper and lower bounds

U
m

U_m

and

L
m

L_m

such that the roots of

f
(
z
)

f(z)

lie in the annulus

{
z
:

L
m

≤

|

z

|

≤

U
m

}

\{z : L_m \leq |z| \leq U_m\}

. In particular,

L
2

=

1
2

/

max
{

|

a
k

/

a
0

|

1

/

k

:
k
=
1
,
…
,
n
}

L_2={1 \over 2}/\max \{ |{{a_k} / {a_0}}|^{1/k}: k=1, \dots , n\}

,

U
2

=
2
max
{

|

a

n
−
k

/

a
n

|

1

/

k

:
k
=
1
,
…
,
n
}

U_2=2 \max \{ |{{a_{n-k}} / {a_n}}|^{1/k}: k=1, \dots , n\}

; and
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L 3 equals left-bracket left-parenthesis StartRoot 5 EndRoot minus 1 right-parenthesis slash 2 right-bracket slash max left-brace left-parenthesis StartAbsoluteValue a 1 a Subscript k minus 1 Baseline minus a 0 a Subscript k Baseline EndAbsoluteValue slash StartAbsoluteValue a 0 squared EndAbsoluteValue right-parenthesis Superscript 1 slash k Baseline colon k equals 2 comma ellipsis comma n plus 1 right-brace">

L
3

=
[
(

5

−
1
)

/

2
]

/

max
{
(

|

a
1

a

k
−
1

−

a
0

a

k

|

/

|

a
0
2

|

)

1

/

k

:
k
=
2
,
…
,
n
+
1
}

L_3 =[(\sqrt {5}-1)/2] / \max \{ ({{|a_1a_{k-1}-a_0a_{k}|} / {|a_0^2|}})^{1/k}: k=2, \dots , n+1 \}

,
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper U 3 equals left-bracket left-parenthesis StartRoot 5 EndRoot plus 1 right-parenthesis slash 2 right-bracket max left-brace left-parenthesis StartAbsoluteValue a Subscript n minus 1 Baseline a Subscript n minus k plus 1 Baseline minus a Subscript n Baseline a Subscript n minus k Baseline EndAbsoluteValue slash StartAbsoluteValue a Subscript n Superscript 2 Baseline EndAbsoluteValue right-parenthesis Superscript 1 slash k Baseline colon k equals 2 comma ellipsis comma n plus 1 right-brace">

U
3

=
[
(

5

+
1
)

/

2
]
max
{
(

|

a

n
−
1

a

n
−
k
+
1

−

a
n

a

n
−
k

|

/

|

a
n
2

|

)

1

/

k

:
k
=
2
,
…
,
n
+
1
}

U_3 = [(\sqrt {5}+1)/2] \max \{ ({{|a_{n-1}a_{n-k+1}-a_na_{n-k}|} / {|a_n^2|}} )^{1/k}: k=2, \dots , n+1 \}

, where

a

−
1

=

a

n
+
1

=
0

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.