Sturm's theorem

In mathematics, Sturm's theorem is a symbolic procedure to determine the number of distinct real roots of a polynomial. It was named for Jacques Charles François Sturm, though it had actually been discovered by Jean Baptiste Fourier; Fourier's paper, delivered on the eve of the French Revolution, was forgotten for many years.

Whereas the fundamental theorem of algebra readily yields the number of real or complex roots of a polynomial, counted according to their multiplicities, Sturm's theorem deals with real roots and disregards their multiplicities.

Sturm chains

A Sturm chain or Sturm sequence is a finite sequence of polynomials

$p_{0},p_{1},\dots p_{m}$

of decreasing degree with these following properties:

• $p_{0}=p$ is square free;
• if $p(\xi )=0$, then $sign(p_{1}(\xi ))=-sign(p'(\xi ))$;
• if $p_{i}(\xi )=0$, then $p_{i-1}(\xi )\cdot p_{i+1}(\xi )<0$;
• $p_{m}$ does not change its sign.

To obtain a Sturm chain Sturm himself proposed to choose the intermediary results when applying Euclid's algorithm to p and its derivative:

${\begin{matrix}p_{0}(x)&:=&p(x),\\p_{1}(x)&:=&p'(x),\\p_{2}(x)&:=&-{\rm {rem}}(p_{0},p_{1})&=&p_{1}(x)q_{0}(x)-p_{0}(x),\\p_{3}(x)&:=&-{\rm {rem}}(p_{1},p_{2})&=&p_{2}(x)q_{1}(x)-p_{1}(x),\\&\dots \\0&=&-{\rm {rem}}(p_{m-1},p_{m}).\end{matrix}}$

That is, successively take the remainders with polynomial division and change their signs. Since $\operatorname {deg} (p_{i+1})<\operatorname {deg} (p_{i})$ for $0\leq i<m$, the algorithm terminates. The final polynomial, p_m, is the greatest common divisor of p and its derivative. Since p only has simple roots, p_m will be a constant. The Sturm chain then is

$p,p_{1},p_{2},\ldots ,p_{m}.\,$

Statement

Let σ(ξ) be the number of sign changes (zeroes are not counted) in the sequence

$p(\xi ),p_{1}(\xi ),p_{2}(\xi ),\ldots ,p_{m}(\xi ),\,\!$

where p is a square-free polynomial. Sturm's theorem then states that for two real numbers a < b, the number of distinct roots in the half-open interval (a,b] is σ(a)−σ(b).

Applications

This can be used to compute the total number of real roots a polynomial has (to use, for example, as an input to a numerical root finder) by choosing a and b appropriately. For example, a bound due to Cauchy says that all real roots of a polynomial with coefficients a_i are in the interval [−M,M], where

$M=1+{\frac {\max _{i=0}^{n-1}|a_{i}|}{|a_{n}|}}.\,\!$

Alternatively, we can use the fact that for large x, the sign of

$p(x)=a_{n}x^{n}+\cdots \,\!$

is $sign(a_{n})$, whereas $sign(p(-x))$ is $(-1)^{n}a_{n}$.

In this way, simply counting the sign changes in the leading coefficients in the Sturm chain readily gives the number of distinct real roots of a polynomial.

We can also determine the multiplicity of a given root, say ξ, with the help of Sturm's theorem. Indeed, suppose we know a and b bracketing ξ, with σ(a)−σ(b) = 1. Then, ξ has multiplicity m precisely when ξ is a root with multiplicity m−1 of X_r (since it is the GCD of X and its derivative).

Generalized Sturm chains

Let ξ be in the compact interval [a,b]. A generalized Sturm chain over [a,b] is a finite sequence of real polynomials (X₀,X₁,…,X_r) such that:

1. X(a)X(b) ≠ 0
2. sign(X_r) is constant on [a,b]
3. If X_i(ξ) = 0 for 1 ≤ i ≤ r−1, then X_i−1(ξ)X_i+1(ξ) < 0.

One can check that each Sturm chain is indeed a generalized Sturm chain.

See also

• Routh-Hurwitz theorem
• Descartes' rule of signs
• D.G. Hook and P.R. McAree, "Using Sturm Sequences To Bracket Real Roots of Polynomial Equations" in Graphic Gems I (A. Glassner ed.), Academic Press, p. 416-422, 1990.

External links

• C code from Graphic Gems by D.G. Hook and P.R. McAree.