On efficient computation and asymptotic sharpness of Kalantari’s bounds for zeros of polynomials

Jin, Yi

doi:10.1090/S0025-5718-06-01868-0

On efficient computation and asymptotic sharpness of Kalantari’s bounds for zeros of polynomials
HTML articles powered by AMS MathViewer

by Yi Jin PDF

Math. Comp. 75 (2006), 1905-1912 Request permission

Abstract:

We study an infinite family of lower and upper bounds on the modulus of zeros of complex polynomials derived by Kalantari. We first give a simple characterization of these bounds which leads to an efficient algorithm for their computation. For a polynomial of degree $n$ our algorithm computes the first $m$ bounds in Kalantari’s family in $O(mn)$ operations. We further prove that for every complex polynomial these lower and upper bounds converge to the tightest annulus containing the roots, and thus settle a problem raised in Kalantari’s paper.

References

Peter Henrici, Applied and computational complex analysis, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Volume 1: Power series—integration—conformal mapping—location of zeros. MR 0372162
M. D. Hirschhorn, A proof in the spirit of Zeilberger of an amazing identity of Ramanujan, Math. Mag. 69 (1996), no. 4, 267–269. MR 1424441, DOI 10.2307/2690530
Bahman Kalantari, An infinite family of bounds on zeros of analytic functions and relationship to Smale’s bound, Math. Comp. 74 (2005), no. 250, 841–852. MR 2114651, DOI 10.1090/S0025-5718-04-01686-2
John Michael McNamee, A 2002 update of the supplementary bibliography on roots of polynomials, J. Comput. Appl. Math. 142 (2002), no. 2, 433–434. MR 1906741, DOI 10.1016/S0377-0427(01)00546-5
J. M. McNamee and M. Olhovsky, A comparison of a priori bounds on (real or complex) roots of polynomials, to appear in Proceedings of 17th IMACS World Congress, Paris, France, July 2005.
Maurice Mignotte, Mathematics for computer algebra, Springer-Verlag, New York, 1992. Translated from the French by Catherine Mignotte. MR 1140923, DOI 10.1007/978-1-4613-9171-5
Richard P. Stanley, Generating functions, Studies in combinatorics, MAA Stud. Math., vol. 17, Math. Assoc. America, Washington, D.C., 1978, pp. 100–141. MR 513004