Sturm’s theorem
This root-counting theorem was produced by the French mathematician Jacques Sturm in 1829.
Definition 1.
Let be a real polynomial in , and define the Sturm sequence of polynomials by
Here denotes the remainder of the polynomial upon division by the polynomial . The sequence terminates once one of the is zero.
Definition 2.
For any number , let denote the number of sign changes in the sequence .
Theorem 1.
For real numbers and that are both not roots of ,
In particular, we can count the total number of distinct real roots by looking at the limits as and . The total number of distinct real roots will depend only on the leading terms of the Sturm sequence polynomials.
Note that deg deg , and so the longest possible Sturm sequence has deg terms.
Also, note that this sequence is very closely related to the sequence of remainders generated by the Euclidean Algorithm; in fact, the term is the exact same except with a sign changed when 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 |