Sturm's theorem

From Wikipedia, the free encyclopedia

In mathematics, Sturm's theorem is a symbolic procedure to determine the number of unique real roots of a polynomial. It was named for its discoverer, Jacques Charles François Sturm.

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.

1 Sturm chains
2 Statement
3 Applications
4 Generalized Sturm chains
5 See also

[edit] Sturm chains

To apply Sturm's theorem, we first construct a Sturm chain or sequence from a square-free polynomial

$X=a_n x^n+\cdots +a_1 x+a_0.$

A Sturm chain or Sturm sequence is the sequence of intermediary results when applying Euclid's algorithm to X and its derivative X₁ = X′.

To obtain the Sturm chain, compute

$\begin{matrix} X_2&=&-{\rm rem}(X,X_1)\\ X_3&=&-{\rm rem}(X_1,X_2)\\ &\vdots&\\ 0&=&-{\rm rem}(X_{r-1},X_r), \end{matrix}$

That is, successively take the remainders with polynomial division and change their signs. Each X_i is a polynomial of degree at least one, hence the algorithm terminates. The final polynomial, X_r, is the GCD of X and its derivative. If X only has simple roots, X_r will be a constant. The Sturm chain then is

$X,X_1,X_2,\ldots,X_r . \,\!$

[edit] Statement

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

$X(\xi), X_1(\xi), X_2(\xi),\ldots, X_r(\xi), \,\!$

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

[edit] 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 a polynomial

$P(x)=a_n x^n+\cdots \,\!$

is sgn(a_n), whereas sgn(P(−x)) is sgn((−1)ⁿ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).