Sturm’s theorem
This root-counting theorem was produced by the French mathematician Jacques Sturm in 1829.
Definition 1.
Let P(x) be a real polynomial in x, and define the
Sturm sequence of polynomials (P0(x),P1(x),…) by
P0(x) | = | P(x) | ||
P1(x) | = | P′(x) | ||
Pn(x) | = | -rem(Pn-2,Pn-1),n≥2 |
Here rem(Pn-2,Pn-1) denotes the remainder of the polynomial Pn-2 upon division by the polynomial Pn-1. The sequence terminates once one of the Pi is zero.
Definition 2.
For any number t, let varP(t) denote the number of sign changes in the sequence P0(t),P1(t),….
Theorem 1.
For real numbers a and b that are both not roots of P(x),
#{distinct real roots of P in (a,b)}=varP(a)-varP(b) |
In particular, we can count the total number of distinct real roots by looking at the limits as a→-∞ and b→+∞. The total number of distinct real roots will depend only on the leading terms of the Sturm sequence polynomials.
Note that deg Pn< deg Pn-1, and so the longest possible Sturm sequence has deg P+1 terms.
Also, note that this sequence is very closely related to the sequence of remainders generated by the Euclidean Algorithm; in fact, the term Pi is the exact same except with a sign changed when i≡2 or . Thus, the Half-GCD Algorithm may be used to compute this sequence. Be aware that some computer algebra systems may normalize remainders from the Euclidean Algorithm which messes up the sign.
For a proof, see Wolpert, N., “ http://web.archive.org/web/20050412175929/http://www.mpi-sb.mpg.de/ nicola/Vorlesung/sturm.psProof of Sturm’s Theorem”
Title | Sturm’s theorem |
---|---|
Canonical name | SturmsTheorem |
Date of creation | 2013-03-22 14:28:49 |
Last modified on | 2013-03-22 14:28:49 |
Owner | rspuzio (6075) |
Last modified by | rspuzio (6075) |
Numerical id | 14 |
Author | rspuzio (6075) |
Entry type | Theorem |
Classification | msc 11A05 |
Classification | msc 26A06 |
Related topic | EuclidsAlgorithm |
Defines | Sturm Sequence |