Methods for locating real roots of a polynomial
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 (and only 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 (in the average, a polynomial of degree n has n complex roots, and only log "n" real roots; see ). Moreover, it may be difficult to distinguish the real roots from the non-real roots with small imaginary part (see the example of Wilkinson's polynomial in next section).
The first complete real-root isolation algorithm results from Sturm's theorem (1829). However, when real-root-isolation algorithms began to be implemented on computers it appeared that algorithms derived from Sturm's theorem are less efficient than those derived from Descartes' rule of signs (1637).
Since the beginning of 20th century there is an active research activity for improving the algorithms derived from Descartes' rule of signs, getting very efficient implementations, and computing their computational complexity. The best implementations can routinely isolate real roots of polynomials of degree more than 1,000.
Specifications and general strategy.
For finding real roots of a polynomial, the common strategy is to divide the real line (or an interval of it where root are searched) into disjoint intervals until having at most one root in each interval. Such a procedure is called root isolation, and a resulting interval that contains exactly one root is an isolating interval for this root.
Wilkinson's polynomial shows that a very small modification of one coefficient of a polynomial may change dramatically not only the value of the roots, but also their nature (real or complex). Also, even with a good approximation, when one evaluates a polynomial at an approximate root, one may get a result that is far to be close to zero. For example, if a polynomial of degree 20 (the degree of Wilkinson's polynomial) has a root close to 10, the derivative of the polynomial at the root may be of the order of formula_1 this implies that an error of formula_2 on the value of the root may produce a value of the polynomial at the approximate root that is of the order of formula_3 It follows that, except maybe for very low degrees, a root-isolation procedure cannot give reliable results without using exact arithmetic. Therefore, if one wants to isolate roots of a polynomial with floating-point coefficients, it is often better to convert them to rational numbers, and then take the primitive part of the resulting polynomial, for having a polynomial with integer coefficients.
For this reason, although the methods that are described below work theoretically with real numbers, they are generally used in practice with polynomials with integer coefficients, and intervals ending with rational numbers. Also, the polynomials are always supposed to be square free. There are two reasons for that. Firstly Yun's algorithm for computing the square-free factorization is less costly than twice the cost of the computation of the greatest common divisor of the polynomial and its derivative. As this may produce factors of lower degrees, it is generally advantageous to apply root-isolation algorithms only on polynomials without multiple roots, even when this is not required by the algorithm. The second reason for considering only square-free polynomials is that the fastest root-isolation algorithms do not work in the case of multiple roots.
For root isolation, one requires a procedure for counting the real roots of a polynomial in an interval without having to compute them, or, at least a procedure for deciding whether an interval contains zero, one or more roots. With such a decision procedure, one may work with a working list of intervals that may contain real roots. At the beginning, the list contains a single interval containing all roots of interest, generally the whole real line or its positive part. Then each interval of the list is divided into two smaller intervals. If one of the new intervals does not contain any root, it is removed from the list. If it contains one root, it is put in an output list of isolating intervals. Otherwise, it is kept in the working list for further divisions, and the process may continue until all roots are eventually isolated
Sturm's theorem.
The first complete root-isolation procedure results of Sturm's theorem (1829), which expresses the number of real roots in an interval in terms of the number of sign variations of the values of a sequence of polynomials, called "Sturm's sequence", at the ends of the interval. Sturm's sequence is the sequence of remainders that occur in a variant of Euclidean algorithm applied to the polynomial and its derivatives. When implemented on computers, it appeared that root isolation with Sturm's theorem is less efficient than the other methods that are described below. Consequently, Sturm's theorem is rarely used for effective computations, although it remains useful for theoretical purposes.
Descartes' rule of signs and its generalizations.
Descartes' rule of signs asserts that the difference between the number of sign variations in the sequence of the coefficients of a polynomial and the number of its positive real roots is a nonnegative even integer. It results that if this number of sign variations is zero, then the polynomial does not have any positive real roots, and, if this number is one, then the polynomial has a unique positive real root, which is a single root. Unfortunately the converse is not true, that is, a polynomial which has either no positive real root or has a single positive simple root may have a number of sign variations greater than 1.
This has been generalized by Budan's theorem (1807), into a similar result for the real roots in a half-open interval ("a", "b"]: If "f"("x") is a polynomial, and v is the difference between of the numbers of sign variations of the sequences of the coefficients of "f"("x" + "a") and "f"("x" + "b"), then v minus the number of real roots in the interval, counted with their multiplicities, is a nonnegative even integer. This is a generalization of Descartes' rule of signs, because, for b sufficiently large, there is no sign variation in the coefficients of "f"("x" + "b"), and all real roots are smaller than b.
Budan's may provide a real-root-isolation algorithm for a square-free polynomial (a polynomial without multiple root): from the coefficients of polynomial, one may compute an upper bound M of the absolute values of the roots and a lower bound m on the absolute values of the differences of two roots (see Properties of polynomial roots). Then, if one divides the interval [–"M", "M"] into intervals of length less than m, then every real root is contained in some interval, and no interval contains two roots. The isolating intervals are thus the intervals for which Budan's theorem asserts an odd number of roots.
However, this algorithm is very inefficient, as one cannot use a coarser partition of the interval [–"M", "M"], because, if Budan's theorem gives a result larger than 1 for an interval of larger size, there is no way for insuring that it does not contain several roots.
Vincent's and related theorems.
 ;templatestyles src="Template:Visible anchor/styles.css" / ;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 formula_4 is a sequence of positive real numbers, let 
formula_5
be the kth convergent of the continued fraction
formula_6
 ;templatestyles src="Math_theorem/styles.css" / ;
For proving his theorem, Vincent proved a result that is useful on its own:
 ;templatestyles src="Math_theorem/styles.css" / ;
Vincent's auxiliary theorem — \frac ac-\frac bd\right
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:
 ;templatestyles src="Math_theorem/styles.css" / ;
The conclusion of Vincent's auxiliary result holds if the polynomial "p"("x") has at most one root "α" + "iβ" such that
formula_7 that occur in his theorem. Vincent himself provided some choice (see below). Some other choices are possible, and the efficiency of the algorithm may depend dramatically on these choices. Below is presented an algorithm, in which these choices result from an auxiliary function that will be discussed later.
For running this algorithm one must work with a list of intervals represented by a specific data structure. The algorithm works by choosing an interval, removing it from the list, adding zero, one or two smaller intervals to the list, and possibly outputs an isolation interval.
For isolating the real roots of a polynomial "p"("x") of degree n, each interval is represented by a pair formula_8 where "A"("x") is a polynomial of degree n and formula_9 is a Möbius transformation with integer coefficients. One has 
formula_10
and the interval represented by this data structure is the interval that has formula_11 and formula_12 as end points. The Möbius transformation maps the roots of p in this interval to the roots of A in (0, +∞).
The algorithm works with a list of intervals that, at the beginning, contains the two intervals formula_13 and formula_14 corresponding to the partition of the reals into the positive and the negative ones (one may suppose that zero is not a root, as, if it were, it suffices to apply the algorithm to "p"("x")/"x"). Then for each interval ("A"("x"), "M"("x")) in the list, the algorithm remove it from the list; if the number of sign variations of the coefficients of A is zero, there is no root in the interval, and one passes to the next interval. If the number of sign variations is one, the interval defined by formula_15 and formula_16 is an isolating interval. Otherwise, one chooses a positive real number b for dividing the interval (0, +∞) into (0, b) and (b, +∞), and, for each subinterval, one composes M with a Möbius transformation that maps the interval onto (0, +∞), for getting two new intervals to be added to the list. In pseudocode, this gives the following, where var("A") denotes the number of sign variations of the coefficients of the polynomial A.
 function continued fraction is
 input: P(x), a square-free polynomial,
 output: a list of pairs of rational numbers defining isolating intervals
 /* "Initialization" */
 L := [(P(x), x), (P(–x), –x)] /* "two starting intervals" */
 Isol := [ ]
 /* Computation */
 while L ≠ [ ] do
 Choose (A(x), M(x)) in L, and remove it from L
 v := var("A")
 if v = 0 then exit /* no root in the interval */
 if v = 1 then /* isolating interval found */
 add (M(0), M(∞)) to Isol
 exit
 b := some positive integer
 B(x) = A(x + b)
 w := v – var(B)
 if B(0) = 0 then /* rational root found */
 add (M(b), M(b)) to Isol
 B(x) := B(x)/x
 add (B(x), M(b + x)) to L /* roots in (M(b), M(+∞)) */
 if w = 0 then exit /* Budan's theorem */ 
 if w = 1 then /* Budan's theorem again */ 
 add (M(0), M(b)) to Isol
 if w ; 1 then
 add ( A(b/(1 + x)), M(b/(1 + x)) )to L /* roots in (M(0), M(b)) */
The different variants of the algorithm depend essentially on the choice of b. In Vincent's papers, and in Uspensky's book, one has always "b" = 1, with the difference that Uspensky did not use Budan's theorem for avoiding further bisections of the interval associated to (0, b)
The drawback of always choosing "b" = 1 is that one has to do many successive changes of variable of the form "x" → 1 + "x". These may be replaced by a single change of variable "x" → "n" + "x",