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 1 Sturm chains 2 Statement 3 Applications 4 Generalized Sturm chains 5 See also

[edit] Sturm chains

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

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

[edit] Statement

Let σ(ξ) be the number of sign changes (zeroes are not counted) in the sequence

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 a_i are in the interval [−M,M], where

Alternatively, we can use the fact that for large x, the sign of

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

[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 (X₀,X₁,…,X_r) such that:

1. X(a)X(b) ≠ 0
2. sgn(X_r) is constant on [a,b]
3. 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.

[edit] See also

• Routh-Hurwitz theorem
• Descartes' rule of signs