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 (ξ)$ 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]

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 $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 <

math>\sgn(a_n)</math>,

whereas

sgn(P ( - x)) = 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.

Categories: Theorems | Polynomials

Last updated: 05-17-2005 10:28:38

Sturm's theorem - Your Art History Reference Guide!