page_title: Real-root isolation
section_title: Vincent's and related theorems
hierarchical_section_title: Real-root isolation / Vincent's and related theorems
caption_attribution_description: English: Proof of vincent's theorem
context_page_description: In mathematics, and, more specifically in numerical analysis and computer algebra, real-root isolation of a polynomial consist of producing disjoint intervals of the real line, which contain each one real root of the polynomial, and, together, contain all the real roots of the polynomial.
  Real-root isolation is useful because usual root-finding algorithms for computing the real roots of a polynomial may produce some real roots, but, cannot generally certify having found all real roots. In particular, if such an algorithm does not find any root, one does not know whether it is because there is no real root. Some algorithms compute all complex roots, but, as there are generally much fewer real roots than complex roots, most of their computation time is generally spent for computing non-real roots. Moreover, it may be difficult to distinguish the real roots from the non-real roots with small imaginary part.
  The first complete real-root isolation algorithm results from Sturm's theorem.
context_section_description: Vincent's theorem (1834) provides a method for real-root isolation, which is at the basis of the most efficient real-root-isolation algorithms. It concerns the positive real roots of a square-free polynomial (that is a polynomial without multiple roots). If  is a sequence of positive real numbers, let 
  be the kth convergent of the continued fraction
  Vincent's theorem — Let  be a square-free polynomial of degree n, and  be a sequence of real numbers. For i = 1, 2,..., consider the polynomial
  Then, there is an integer k such that either  or the sequence of the coefficients of  has at most one sign variation.
  In the first case, the convergent cₖ is a positive root of  Otherwise, this number of sign variations (either 0 or 1) is the number of real roots of  in the interval defined by  and 
  For proving his theorem, Vincent proved a result that is useful on its own:
  Vincent's auxiliary theorem — If p(x) is a square-free polynomial of degree n, and a, b, c, d are nonnegative real numbers such that  is small enough (but not 0), then there is at most one sign variation in the coefficients of the polynomial
  and this number of sign variations is the number of real roots of p(x) in the open interval defined by  and 
  For working with real numbers, one may always choose c = d = 1, but, as effective computations are done with rational numbers, it is generally convenient to suppose that a, b, c, d are integers.
  The "small enough" condition has been quantified independently by Nikola Obreshkov, and Alexander Ostrowski:
  Theorem (Obreschkoff–Ostrowski) — The conclusion of Vincent's auxiliary result holds if the polynomial p(x) has at most one root α + iβ such that
  In particular the conclusion holds if
  where sep(p) is the minimal distance between two roots of p.
  For polynomials with integer coefficients, the minimum distance sep(p) may be lower bounded in terms of the degree of the polynomial and the maximal absolute value of its coefficients; see Properties of polynomial roots § Root separation. This allows the analysis of worst-case complexity of algorithms based on Vincent's theorems. However, Obreschkoff–Ostrowski theorem shows that the number of iterations of these algorithms depend on the distances between roots in the neighborhood of the working interval; therefore, the number of iterations may vary dramatically for different roots of the same polynomial.
  James V. Uspensky gave a bound on the length of the continued fraction (the integer k needed, in Vincent's theorem, for getting zero or one sign variations: 
  Theorem (Uspensky) — 
  Let p(x) be a polynomial of degree n, and sep(p) be the minimal distance between two roots of p. Let
  Then the integer k, whose existence is asserted in Vincent's theorem, is not greater than the smallest integer h such that 
  where  is the hth Fibonacci number.
caption: Obreschkoff–Ostrowski theorem: in blue and yellow, the regions of the complex plane where there should be no root for having 0  or 1 sign variation; on the left the regions excluded for the roots of p, on the right, the regions excluded for the roots of the transformed polynomial q; in blue, the regions that are excluded for having one sign variation, but allowed for zero sign variations.
exif: {"Image Software": "www.inkscape.org", "Image Tag 0x5110": "1", "Image Tag 0x5111": "3543", "Image Tag 0x5112": "3543"}