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.
To apply Sturm's theorem, you first construct a Sturm chain from a polynomial
.
A Sturm chain is the sequence of intermediary results when applying Euclid's algorithm to X and its derivative X1 = X'.
To obtain the Sturm chain, you compute
-
i.e., you successively take the remainders with polynomial division and change theirs signs. Each Xi is a polynomial of degree at least one, hence the algorithm terminates. Xr then is the GCD of X and its derivative. If X only had simple roots, it will be a constant. The Sturm chain then is
.
Let w(ξ) be the number of sign changes (zeroes are not counted) in the sequence
.
Sturm's theorem then states that for two real numbers
- a < b,
not roots of X, the number of roots in the interval
- [a,b]
is
- w(b) - w(a).
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, all real root of a polynomial with coefficients ai are in the interval [ - M,M], where
.
Alternatively, you can use the fact that for large x, the sign of a polynomial
is <
- math>\sgn(a_n)</math>,
whereas
- sgn(P( - x)) = sgn(( - 1)nan).
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.