Sturm_sequence

Sturm sequence

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.

1 Sturm chains
2 Statement
3 Applications
4 Generalized Sturm chains
5 See also
6 External links

Sturm chains

A Sturm chain or Sturm sequence is a finite sequence of polynomials

$p_0, p_1, \dots p_m$

of decreasing degree with these following properties:

$p 0 = p$ is square free;
if $p (ξ) = 0$ , then $s i g n (p 1 (ξ)) = - s i g n (p'(ξ))$ ;
if $p i (ξ) = 0$ , then $p_{i-1}(\xi) \cdot p_{i+1}(\xi) < 0$ ;
$p m$ does not change its sign.

To obtain a Sturm chain Sturm himself proposed to choose the intermediary results when applying Euclid's algorithm to p and its derivative:

$\begin{matrix} p_0(x)&:=&p(x),\\ p_1(x)&:=&p'(x),\\ p_2(x)&:=&-{\rm rem}(p_0, p_1) &=& p_1(x) q_0(x)- p_0(x),\\ p_3(x)&:=&-{\rm rem}(p_1,p_2) &=& p_2(x) q_1(x) - p_1(x),\\ &\dots\\ 0&=&-{\rm rem}(p_{m-1}, p_m). \end{matrix}$

That is, successively take the remainders with polynomial division and change their signs. Since $\operatorname{deg}(p_{i+1}) < \operatorname{deg} (p_i)$ for $0 \le i < m$ , the algorithm terminates. The final polynomial, p_m, is the greatest common divisor of p and its derivative. Since p only has simple roots, p_m will be a constant. The Sturm chain then is

$p,p_1,p_2,\ldots,p_m . \,$

Statement

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

$p(\xi), p_1(\xi), p_2(\xi),\ldots, p_m(\xi), \,\!$

where p 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).

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

$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 $s i g n (a n)$ , whereas $s i g n (p ( - x))$ is $( - 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.

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

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:

X(a)X(b) ≠ 0
sign(X_r) is constant on a,b
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.

External links

C code from Graphic Gems by D.G. Hook and P.R. McAree.

Contents

Sturm chains

Statement

Applications

Generalized Sturm chains

See also

External links