Preprint C198/2016
Methods for bounding and isolating the real roots of univariate polynomials
Eric Biagioli
Keywords:

This work addresses the problem of finding the real roots of univariate polynomials, covering two related subareas. One of them is related to the problem of computing an upper (lower) bound for the value of the maximum (minimum) positive root of a univariate polynomial. In this part, we present a detailed state-of-the art survey and we propose a method that improves the quality of the bounds produced by other existing methods, without introducing significative extra amount of computational effort. The other part is related to the problem of isolating the positive roots of a univariate polynomial P (i.e.: computing a set S of disjoint intervals, each one of them containing exactly one positive root of P , all positive roots of P being contained by some interval in S). In this part, the main results related to the problem are presented, explained and compared; and two results are introduced: one adaptation of one of the underlying theorems (Fourier’s theorem), which requires less amount of computational effort in the cases in which P is a fewnomial (i.e.: a sparse polynomial, a polynomial in which the degree is much higher than the number of terms), and is also introduced one method for root isolation which, while relying only on elementary and intuitive results, proves to have good performance in most of the testcases. In addition to our theoretical approach, implementations and extensive tests of our methods are presented. Along with these two mentioned results, we also expose two ideas that, although we have not been able to obtain concrete results from them, we find them promising. One of them is related to the Sturm idea, and the other is related to Fourier’s theorem.