Sturm's theorem: Definition from Answers.com

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 Proof
4 Applications
5 Generalized Sturm chains
6 See also
7 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 $\operatorname{sign}(p_1(\xi))= \operatorname{sign}(p'(\xi));$
if $p i (ξ) = 0$ for $0 < i < m$ then $\operatorname{sign}(p_{i-1}(\xi))= -\operatorname{sign}(p_{i+1}(\xi));$
$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{align} 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{align}$

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 is square free, it has only has simple roots and shares no roots with its derivative, so p_m will be a non-zero constant. The Sturm chain then is

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

Incidentally, if p_m turned out to be zero, then p would not be square free, but p_m-1 would then be a non-trivial factor of p, so we could divide it out and calculate Sturm chains for both p_m-1 and p/p_m-1 (the later of which is guaranteed to be square free). Repeating this process, we can obtain a square free factorization for any polynomial p and a Sturm chain associated with each square free factor.

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

Proof

Since polynomials are continuous functions, any sign change must occur at a zero, so we need only consider the behavior of a Sturm chain around the zeros of its constituent polynomials.

First, let's note that two adjacent polynomials can not share a common zero. Instead, if p_i and p_i-1 were both zero at $ξ$ , then p_i+1 would also have to be zero at $ξ$ , since $\operatorname{sign}(p_{i-1}(\xi))= -\operatorname{sign}(p_{i+1}(\xi))$ . The zero would then propagate recursively down the chain and force p_m to be zero at $ξ$ , which can't happen since p_m is a non-zero constant.

Next, let's consider zeros of polynomials in the interior (i.e, $0 < i < m$ ) of the Sturm chain. If $p i (ξ) = 0$ , then we know from the previous paragraph that $p_{i-1}(\xi)\ne 0$ and $p_{i+1}(\xi)\ne 0$ . Futhermore, $\operatorname{sign}(p_{i-1}(\xi))= -\operatorname{sign}(p_{i+1}(\xi))$ , so in the vicinity of $ξ$ we've got a single sign change across p_i-1, p_i, p_i+1. In other words, sign changes in the interior of the Sturm chain do not affect the total number of sign changes across the chain.

Neither do sign changes at the bottom of the chain, since p_m is a non-zero constant, and thus never changes sign.

So only zeros in the original polynomial, at the top of the chain, can affect the total number of sign changes. Consider a zero at $ξ$ , so $p (ξ) = 0$ . Now p's derivative, which is p₁, must be non-zero at $ξ$ (since adjacent polynomials in the chain can't share common zeros), so p must be either increasing or decreasing at $ξ$ . If it's increasing, then its sign is changing from negative to positive as we move from left to right while its derivative (again, p₁) is positive, so the total number of sign changes decreases by one. Conversely, if it's decreasing, then its sign changes from positive to negative while its derivative is negative, so again the total number of sign changes decreases by one.

In summary, only sign changes of the original polynomial affect the total number of sign changes across the chain, and the total number of sign changes always decreases by one as we pass a zero. The theorem follows directly.

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.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	How can you solve norton theorem theven theorem and network problems easily? Read answer...
	How do you prove the hypotenuse leg theorem without using Pythagorean theorem? Read answer...
	You can use the Pythagorean theorem to solve problems that involve right triangles Provide an example of a day-to-day situation that involves triangles and the use of the theorem? Read answer...

	What is the relationship between Gauss theorem stokes's theorem and green's theorem?
	What is the relationship between the Green's Theorem Divergence Theorem and Stoke's Theorem?
	Last year ryan morgan discovered a theorem using a sketchpad. what was the theorem?

		Sci-Tech Dictionary. McGraw-Hill Dictionary of Scientific and Technical Terms. Copyright © 2003, 1994, 1989, 1984, 1978, 1976, 1974 by McGraw-Hill Companies, Inc. All rights reserved. Read more
		Wikipedia. This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Sturm's theorem". Read more

Sturm's theorem

Contents