In mathematics, the Sturm sequence of a univariate polynomial is a sequence of polynomials associated with and its derivative by a variant of Euclid's algorithm for polynomials. Sturm's theorem expresses the number of distinct real roots of 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. Applied to the interval of all the real numbers, it gives the total number of real roots of .
Whereas the fundamental theorem of algebra readily yields the overall number of complex roots, counted with multiplicity, it does not provide a procedure for calculating them. Sturm's theorem counts the number of distinct real roots and locates them in intervals. By subdividing the intervals containing some roots, it can isolate the roots into arbitrarily small intervals, each containing exactly one root. This yields the oldest real-root isolation algorithm, and arbitrary-precision root-finding algorithm for univariate polynomials.
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.
The Sturm sequence and Sturm's theorem are named after Jacques Charles François Sturm, who discovered the theorem in 1829.
The Sturm chain or Sturm sequence of a univariate polynomial with real coefficients is the sequence of polynomials
P0,P1,\ldots,
\begin{align} P0&=P,\\ P1&=P',\\ Pi+1&=-\operatorname{rem}(Pi-1,Pi), \end{align}
\operatorname{rem}(Pi-1,Pi)
Pi-1
Pi.
The number of sign variations at of the Sturm sequence of is the number of sign changes (ignoring zeros) in the sequence of real numbers
P0(\xi),P1(\xi),P2(\xi),\ldots.
Sturm's theorem states that, if is a square-free polynomial, the number of distinct real roots of in the half-open interval is (here, and are real numbers such that).
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). At the sign of a polynomial is the sign of its leading coefficient for a polynomial of even degree, and the opposite sign for a polynomial of odd degree.
In the case of a non-square-free polynomial, if neither nor is a multiple root of, then is the number of distinct real roots of .
The proof of the theorem is as follows: when the value of increases from to, it may pass through a zero of some
Pi
(Pi-1,Pi,Pi+1)
P0=P,
(P0,P1)
Suppose we wish to find the number of roots in some range for the polynomial
p(x)=x4+x3-x-1
\begin{align}p0(x)&=p(x)=x4+x3-x-1
3+3x | |
\\ p | |
1(x)&=p'(x)=4x |
2-1 \end{align}
The remainder of the Euclidean division of by is
-\tfrac{3}{16}x2-\tfrac{3}{4}x-\tfrac{15}{16};
2+\tfrac{3}{4}x+\tfrac{15}{16} | |
p | |
2(x)=\tfrac{3}{16}x |
p3(x)=-32x-64
p4(x)=-\tfrac{3}{16}
To find the number of real roots of
p0
V(-infty)-V(+infty)=3-1=2,
This can be verified by noting that can be factored as, where the first factor has the roots and, and second factor has no real roots. This last assertion results from the quadratic formula, and also from Sturm's theorem, which gives the sign sequences at and at .
Sturm sequences have been generalized in two directions. 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. It is also useful (see below) to consider sequences where the second polynomial is not the derivative of the first one.
A generalized Sturm sequence is a finite sequence of polynomials with real coefficients
P0,P1,...,Pm
\degPi<\degPi-1
Pm
The last condition implies that two consecutive polynomials do not have any common real root. In particular the original Sturm sequence is a generalized Sturm sequence, if (and only if) the polynomial has no multiple real root (otherwise the first two polynomials of its Sturm sequence have a common 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
x2
x2+1
In computer algebra, the polynomials that are considered have integer coefficients or may be transformed to have integer coefficients. The Sturm sequence of a polynomial with integer coefficients generally contains polynomials whose coefficients are not integers (see above example).
To avoid computation with rational numbers, a common method is to replace Euclidean division by pseudo-division for computing polynomial greatest common divisors. This amounts to replacing the remainder sequence of the Euclidean algorithm by a pseudo-remainder sequence, a pseudo remainder sequence being a sequence
p0,\ldots,pk
ai
bi
bipi+1
aipi-1
pi.
ai
bi;
ai
bi
ai=bi=1
ai=1
bi=-1
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
bi
ai.
For a polynomial with real coefficients, root isolation consists of finding, for each real root, an interval that contains this root, and no other roots.
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.
Root isolation is also useful for computing with algebraic numbers. For computing with algebraic numbers, a common method is to represent them as a pair of a polynomial to which the algebraic number is a root, and an isolation interval. For example
\sqrt2
(x2-2,[0,2]).
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.
For isolating the real roots, one starts from an interval
(a,b]
V(a)
V(b).
(a,b].
V(c)
(a,c]
(c,b],
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. If one knows an isolating interval for a root of the first polynomial, this allows also finding the sign of the second polynomial at this particular root of the first polynomial, without computing a better approximation of the root.
Let and be two polynomials with real coefficients such that and have no common root and has no multiple roots. In other words, and are coprime polynomials. 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 denote the number of sign variations at of a generalized Sturm sequence starting from and . If are two real numbers, then is the number of roots of in the interval
(a,b]