Computing the nearest polynomial with a zero in a given domain by using piecewise rational functions
For a real univariate polynomial f and a closed complex domain D whose boundary C is a simple curve parameterized by a univariate piecewise rational function, a rigorous method is given for finding a real univariate polynomial (f) over tilde such that (f) over tilde has a zero in D and parallel to f -(f) over tilde parallel to(infinity)is minimal. First, it is proved that the minimum distance between f and polynomials having a zero at alpha is an element of C is a piecewise rational function of the real and imaginary parts of alpha. Thus, on C, the minimum distance is a piecewise rational function of a parameter obtained through the parameterization of C. Therefore, (f) over tilde can be constructed by using the property that (f) over tilde has a zero on C and computing the minimum distance on C. We analyze the asymptotic bit complexity of the method and show that it is of polynomial order in the size of the input. (C) 2011 Elsevier Ltd. All rights reserved.
polynomial zero perturbation l(infinity)-norm davenport-schinzel sequence