The use of
continued fractions for real-root isolation has been introduced by Vincent, although he credited
Joseph-Louis Lagrange for this idea, without providing a reference. For making an
algorithm of Vincent's theorem, one must provide a criterion for choosing the a_i 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 of degree , each interval is represented by a pair (A(x), M(x)), where is a polynomial of degree and M(x)=\frac{px+r}{qx+s} is a
Möbius transformation with integer coefficients. One has :A(x)=p(M(x)), and the interval represented by this data structure is the interval that has M(\infty)=\frac pq and M(0)=\frac rs as end points. The Möbius transformation maps the roots of in this interval to the roots of in . The algorithm works with a list of intervals that, at the beginning, contains the two intervals (A(x)=p(x), M(x)=x) and (A(x)=p(-x), M(x)=-x), 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 ). Then for each interval in the list, the algorithm remove it from the list; if the number of sign variations of the coefficients of 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 M(0) and M(\infty) is an isolating interval. Otherwise, one chooses a positive real number for dividing the interval into and , and, for each subinterval, one composes with a Möbius transformation that maps the interval onto , for getting two new intervals to be added to the list. In
pseudocode, this gives the following, where denotes the number of sign variations of the coefficients of the polynomial .
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 . In Vincent's papers, and in Uspensky's book, one has always , with the difference that Uspensky did not use Budan's theorem for avoiding further bisections of the interval associated to The drawback of always choosing is that one has to do many successive changes of variable of the form . These may be replaced by a single change of variable , but, nevertheless, one has to do the intermediate changes of variables for applying Budan's theorem. A way for improving the efficiency of the algorithm is to take for a lower bound of the positive real roots, computed from the coefficients of the polynomial (see
Properties of polynomial roots for such bounds). ==Bisection method==