Computing the nearest polynomial with a zero in a given domain by using piecewise rational functions

For a real univariate polynomial ff and a closed complex domain DD whose boundary CC is a simple curve parameterized by a univariate piecewise rational function, a rigorous method is given for finding a real univariate polynomial f̃ such that f̃ has a zero in DD and ‖f−f̃‖∞ is minimal. First, it is proved that the minimum distance between ff and polynomials having a zero at α∈Cα∈C is a piecewise rational function of the real and imaginary parts of αα. Thus, on CC, the minimum distance is a piecewise rational function of a parameter obtained through the parameterization of CC. Therefore, f̃ can be constructed by using the property that f̃ has a zero on CC and computing the minimum distance on CC. We analyze the asymptotic bit complexity of the method and show that it is of polynomial order in the size of the input.

► Given f∈R[x]f∈R[x] and D⊂CD⊂C, we propose a method for finding f̃∈R[x] with given conditions. ► The conditions are that f̃ has a zero in DD and that ‖f−f̃‖∞ is minimal. ► We show that Φ=min{g∣g(α)=0}‖f−g‖∞Φ=min{g∣g(α)=0}‖f−g‖∞ is a piecewise rational function of Reα and Imα. ► The method constructs f̃ by computing the minimum of ΦΦ on the boundary of DD. ► The bit complexity of the method is of polynomial order in the size of the input.