Sturm's theorem

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

$X=a_{n}x^{n}+\ldots a_{1}x+a_{0}$.

A Sturm chain is the sequence of intermediary results when applying Euclid's algorithm to $X$ and its derivative $X_{1}=X'$.

To obtain the Sturm chain, you compute

${\begin{matrix}X_{2}&=&-{\rm {rem}}(X,X_{1})\\X_{3}&=&-{\rm {rem}}(X_{1},X_{2})\\&\ldots &\\0&=&-{\rm {rem}}(X_{r-1},X_{r}),\end{matrix}}$

i.e., you successively take the remainders with polynomial division and change theirs signs. Each $X_{i}$ is a polynomial of degree at least one, hence the algorithm terminates. $X_{r}$ 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

$X,X_{1},X_{2},\ldots ,X_{r}$.

Let $w(\xi )$ 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 )$.

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(a)-w(b)$.

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 $a_{i}$ are in the interval $[-M,M]$, where

$M=\max(1,\sum |a_{i}|)$.

Alternatively, you can use the fact that for large $x$, the sign of a polynomial

$P(x)=a_{n}x^{n}+\ldots$

is

$\operatorname {sgn}(a_{n})$,

whereas

$\operatorname {sgn}(P(-x))=\operatorname {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.