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.Fact|date=October 2007

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.

turm chains

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

: $X=a\_n\; x^n+ldots\; +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:

That is, successively take the remainders with polynomial division and change their signs. Since $operatorname\{deg\}\; X\_\{i\; +\; 1\}\; le\; operatorname\{deg\}\; X\_i\; -\; 1$ for , the algorithm terminates. The final polynomial, "X"_"r", is the greatest common divisor of "X" and its derivative. Since "X" only has simple roots, "X"_"r" will be a constant. The Sturm chain then is

:$X,X\_1,X\_2,ldots,X\_r\; .\; ,$

tatement

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 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\; .\; ,!$

Alternatively, we can use the fact that for large "x", the sign of:$P(x)=a\_n\; x^n+cdots\; ,!$ is sgn("a"_"n"), whereas sgn("P"(−"x")) is sgn((−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:
#"X"("a")"X"("b") ≠ 0
#sgn("X"_"r") is constant on ["a","b"]
#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.

ee 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

* [http://tog.acm.org/GraphicsGems/gems/Sturm/ C code] from Graphic Gems by D.G. Hook and P.R. McAree.