Sturm's theorem expresses the number of distinct real roots of p located in an interval in terms of the number of changes of signs of the values of the Sturm sequence at the bounds of the interval.
Sturm's theorem counts the number of distinct real roots and locates them in intervals.
For computing over the reals, Sturm's theorem is less efficient than other methods based on Descartes' rule of signs.
However, it works on every real closed field, and, therefore, remains fundamental for the theoretical study of the computational complexity of decidability and quantifier elimination in the first order theory of real numbers.
Sturm's theorem states that, if P is a square-free polynomial, the number of distinct real roots of P in the half-open interval (a, b] is V(a) − V(b) (here, a and b are real numbers such that a < b).
[1] The theorem extends to unbounded intervals by defining the sign at +∞ of a polynomial as the sign of its leading coefficient (that is, the coefficient of the term of highest degree).
In the case of a non-square-free polynomial, if neither a nor b is a multiple root of p, then V(a) − V(b) is the number of distinct real roots of P. The proof of the theorem is as follows: when the value of x increases from a to b, it may pass through a zero of some
Suppose we wish to find the number of roots in some range for the polynomial
Thus where V denotes the number of sign changes in the sequence, which shows that p has two real roots.
This last assertion results from the quadratic formula, and also from Sturm's theorem, which gives the sign sequences (+, –, –) at −∞ and (+, +, –) at +∞.
To define each polynomial in the sequence, Sturm used the negative of the remainder of the Euclidean division of the two preceding ones.
The theorem remains true if one replaces the negative of the remainder by its product or quotient by a positive constant or the square of a polynomial.
A generalized Sturm sequence is a finite sequence of polynomials with real coefficients such that The last condition implies that two consecutive polynomials do not have any common real root.
When computing the original Sturm sequence by Euclidean division, it may happen that one encounters a polynomial that has a factor that is never negative, such a
In this case, if one continues the computation with the polynomial replaced by its quotient by the nonnegative factor, one gets a generalized Sturm sequence, which may also be used for computing the number of real roots, since the proof of Sturm's theorem still applies (because of the third condition).
This may sometimes simplify the computation, although it is generally difficult to find such nonnegative factors, except for even powers of x.
To avoid computation with rational numbers, a common method is to replace Euclidean division by pseudo-division for computing polynomial greatest common divisors.
is a common divisor of the coefficients of the resulting remainder; see Pseudo-remainder sequence for details.)
Various pseudo-remainder sequences have been designed for computing greatest common divisors of polynomials with integer coefficients without introducing denominators (see Pseudo-remainder sequence).
They can all be made generalized Sturm sequences by choosing the sign of the
This is useful for root finding, allowing the selection of the root to be found and providing a good starting point for fast numerical algorithms such as Newton's method; it is also useful for certifying the result, as if Newton's method converge outside the interval one may immediately deduce that it converges to the wrong root.
Sturm's theorem provides a way for isolating real roots that is less efficient (for polynomials with integer coefficients) than other methods involving Descartes' rule of signs.
However, it remains useful in some circumstances, mainly for theoretical purposes, for example for algorithms of real algebraic geometry that involve infinitesimals.
The process stops eventually, when only isolating intervals remain.
This isolating process may be used with any method for computing the number of real roots in an interval.
Theoretical complexity analysis and practical experiences show that methods based on Descartes' rule of signs are more efficient.
It follows that, nowadays, Sturm sequences are rarely used for root isolation.
Generalized Sturm sequences allow counting the roots of a polynomial where another polynomial is positive (or negative), without computing these root explicitly.
This restriction does not really affect the generality of what follows as GCD computations allows reducing the general case to this case, and the cost of the computation of a Sturm sequence is the same as that of a GCD.
Let W(a) denote the number of sign variations at a of a generalized Sturm sequence starting from P and P' Q.