Upper bounds on the values of the positive roots of polynomials

Abstract

This thesis describes new results on computing bounds on the values of the positive roots of polynomials. Bounding the roots of polynomials is an important sub-problem in many disciplines of scientific computing. Many numerical methods for finding roots of polynomials begin with an estimate of an upper bound on the values of the positive roots. If one can obtain a more accurate estimate of the bound, one can reduce the amount of work used in searching within the range of possible values to find the root (e.g. using a bisection method). Also, the computation of the real roots of higher degree univariate polynomials with real coeficients is based on their isolation. Isolation of the real roots of a polynomial is the process of finding real disjoint intervals such that each contains one real root and every real root is contained in some interval. To isolate the real positive roots, it is necessary to compute, in the best possible way, an upper bound on the value of the largest positive root. Although, several bounds are known, the first of which were obtained by Lagrange and Cauchy, this thesis revealed that there was much room for improvement on this topic. Today, two of the algorithms presented in this thesis, are regarded as the best (one of linear computational complexity and the other of quadratic complexity) and have already been incorporated in the source code of major computer algebra systems such as Mathematica and Sage. A certain part of this thesis is also devoted to the analytical presentation of the continued fraction real root isolation method. Its algorithm and its underlying components are presented thoroughly along with a new implementation of the method using the above mentioned bounds. Intensive computational tests verify that this implementation makes the continued fraction real root isolation method the fastest among its rivals. After almost thirty years of usage and development, the continued fractions real root isolation algorithm, introduced back in 1976 by A. Akritas, continues today to eficiently tackle a basic but still important mathematical problem, the solution of a polynomial equation. The revived interest in this algorithm is motivated by the need to solve, in real time, polynomial equations of higher degrees in such diverse scientificfields as control theory, financial theory, signal processing, robotics, computer vision, computer-aided-design, geometric modeling, industrial problems, to name a few. The usage of the continued fraction real root isolation algorithm from major commercial and open source mathematical solvers proves its robustness. This thesis has contributed towards this direction.