Sturm's theorem

From Wikipedia, the free encyclopedia

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.[citation needed]

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.

Contents

[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+\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 X1 = 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. Since \operatorname{deg} X_{i + 1} \le \operatorname{deg} X_i - 1 for 1 \le i < r, the algorithm terminates. The final polynomial, Xr, is the greatest common divisor of X and its derivative. Since X only has simple roots, Xr 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 distinct 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 ai 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

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

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

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 Xr (since it is the GCD of X and its derivative).

[edit] 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 (X0,X1,…,Xr) such that:

  1. X(a)X(b) ≠ 0
  2. sgn(Xr) is constant on [a,b]
  3. If Xi(ξ) = 0 for 1 ≤ i ≤ r−1, then Xi−1(ξ)Xi+1(ξ) < 0.

One can check that each Sturm chain is indeed a generalized Sturm chain.

[edit] See also