Sturm's theorem

Example

Suppose we wish to find the number of roots in some range for the polynomial ${\displaystyle p(x)=x^4+x^3-x-1}$. So

${\displaystyle \begin{array}{cc}{p}_0(x)& =p(x)=x^4+x^3-x-1\\ p_1(x)& =p^{\prime }(x)=4x^3+3x^2-1\end{array}}$

The remainder of the Euclidean division of p₀ by p₁ is ${\displaystyle -\frac{3}{16}{x}^2-\frac{3}{4}x-\frac{15}{16};}$ multiplying it by −1 we obtain

${\displaystyle p_2(x)=\frac{3}{16}{x}^2+\frac{3}{4}x+\frac{15}{16}}$.

Next dividing p₁ by p₂ and multiplying the remainder by −1, we obtain

${\displaystyle p_3(x)=-32x-64}$.

Now dividing p₂ by p₃ and multiplying the remainder by −1, we obtain

${\displaystyle p_4(x)=-\frac{3}{16}}$.

As this is a constant, this finishes the computation of the Sturm sequence.

To find the number of real roots of ${\displaystyle p_0}$ one has to evaluate the sequences of the signs of these polynomials at −∞ and ∞, which are respectively (+, −, +, +, −) and (+, +, +, −, −). Thus

${\displaystyle V(-\mathrm{\infty })-V(+\mathrm{\infty })=3-1=2,}$

where V denotes the number of sign changes in the sequence, which shows that p has two real roots.

This can be verified by noting that p(x) can be factored as (x² − 1)(x² + x + 1), where the first factor has the roots −1 and 1, 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 +∞.

Generalization

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

${\displaystyle P_0,P_1,\dots ,P_m}$

such that

• the degrees are decreasing after the first one: ${\displaystyle \mathrm{deg}{P}_i<\mathrm{deg}{P}_{i-1}}$ for i = 2, ..., m;
• ${\displaystyle P_m}$ does not have any real root or has no sign changes near its real roots.
• if P_i(ξ) = 0 for 0 < i < m and ξ a real number, then P_{i −1} (ξ) P_{i + 1}(ξ) < 0.

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 ${\displaystyle x^2}$ or ${\displaystyle x^2+1}$. 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.

Use of pseudo-remainder sequences

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 ${\displaystyle p_0,\dots ,p_k}$ of polynomials such that there are constants ${\displaystyle a_i}$ and ${\displaystyle b_i}$ such that ${\displaystyle b_i{p}_{i+1}}$ is the remainder of the Euclidean division of ${\displaystyle a_i{p}_{i-1}}$ by ${\displaystyle p_i.}$ (The different kinds of pseudo-remainder sequences are defined by the choice of ${\displaystyle a_i}$ and ${\displaystyle b_i;}$ typically, ${\displaystyle a_i}$ is chosen for not introducing denominators during Euclidean division, and ${\displaystyle b_i}$ is a common divisor of the coefficients of the resulting remainder; see Pseudo-remainder sequence for details.) For example, the remainder sequence of the Euclidean algorithm is a pseudo-remainder sequence with ${\displaystyle a_i=b_i=1}$ for every i, and the Sturm sequence of a polynomial is a pseudo-remainder sequence with ${\displaystyle a_i=1}$ and ${\displaystyle b_i=-1}$ for every i.

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 ${\displaystyle b_i}$ to be the opposite of the sign of the ${\displaystyle a_i.}$ This allows the use of Sturm's theorem with pseudo-remainder sequences.

Root isolation

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 ${\displaystyle \sqrt{2}}$ may be unambiguously represented by ${\displaystyle (x^2-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 ${\displaystyle (a,b]}$ containing all the real roots, or the roots of interest (often, typically in physical problems, only positive roots are interesting), and one computes ${\displaystyle V(a)}$ and ${\displaystyle V(b).}$ For defining this starting interval, one may use bounds on the size of the roots (see Properties of polynomial roots § Bounds on (complex) polynomial roots). Then, one divides this interval in two, by choosing c in the middle of ${\displaystyle (a,b].}$ The computation of ${\displaystyle V(c)}$ provides the number of real roots in ${\displaystyle (a,c]}$ and ${\displaystyle (c,b],}$ and one may repeat the same operation on each subinterval. When one encounters, during this process an interval that does not contain any root, it may be suppressed from the list of intervals to consider. When one encounters an interval containing exactly one root, one may stop dividing it, as it is an isolation interval. 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.

Application

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 P(x) and Q(x) be two polynomials with real coefficients such that P and Q have no common root and P has no multiple roots. In other words, P and P' Q 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 W(a) denote the number of sign variations at a of a generalized Sturm sequence starting from P and P' Q. If a < b are two real numbers, then W(a) – W(b) is the number of roots of P in the interval ${\displaystyle (a,b]}$ such that Q(a) > 0 minus the number of roots in the same interval such that Q(a) < 0. Combined with the total number of roots of P in the same interval given by Sturm's theorem, this gives the number of roots of P such that Q(a) > 0 and the number of roots of P such that Q(a) < 0.