A constructive proof of the convergence of Kalantari's bound on polynomial zeros

2020/12/03 by Matt Hohertz, Hohertz, Matt
Computer Science · Mathematics · #Polynomial and algebraic computation #Iterative Methods for Nonlinear Equations #Algebraic Geometry and Number Theory

paper · pdf · doi:10.48550/arxiv.2012.02150

Abstract

In his 2006 paper, Jin proves that Kalantari's bounds on polynomial zeros, indexed by m ≤ 2 and called L_m and U_m respectively, become sharp as m→∞. That is, given a degree n polynomial p(z) not vanishing at the origin and an error tolerance ε> 0, Jin proves that there exists an m such that \fracL_mρ_min > 1-ε, where ρ_min := min_{ρ:p(ρ) = 0} |ρ|. In this paper we derive a formula that yields such an m, thereby constructively proving Jin's theorem. In fact, we prove the stronger theorem that this convergence is uniform in a sense, its rate depending only on n and a few other parameters. We also give experimental results that suggest an optimal m of (asymptotically) O((1)/(ε^d)) for some d ≪ 2. A proof of these results would show that Jin's method runs in O((n)/(ε^d)) time, making it efficient for isolating polynomial zeros of high degree.

Related

• A New Initial Approximation Bound in the Durand Kerner Algorithm for Finding Polynomial Zeros
• Boundary behavior of optimal polynomial approximants
• Upper Bounds on Resolvent Degree and Its Growth Rate
• Estimates for the asymptotic convergence factor of two intervals
• A lower bound for the norm of the minimal residual polynomial