About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 1994
Conference paper
Roots of a polynomial and its derivatives
Abstract
Suppose F(z) is a complex polynomial of degree n in one variable. It is known that if two roots of F lie in a disk of radius ρ, then a root of the first derivative F′ lies in a concentric disk of radius O(nρ). We give a generalization: if k+1 roots of F lie in a disk of radius ρ, and l satisfies 1≤l≤k, then at least k+1-l roots of the lth derivative F(l) lie in a disk of radius O((n-k)(k-l)ρ/√k+1), centered at the average of the k+1 roots. We further improve the bound when l = k. We give a lower bound of R = Ω(ρ√n(n-k)/(k+1)) for the case l = k. We give some applications to parallel root finding.