Sturm's theorem

Sturm's theorem counts the distinct real roots of a real polynomial in an interval by comparing sign variations in a sequence of polynomials built from it.

Sturm sequence: A sequence formed from a polynomial and its derivative by repeated signed Euclidean remainders. Its sign variations at interval endpoints are the quantities Sturm's theorem compares.
Real root: A real number at which a polynomial or other function equals zero. These are the solutions whose number the theorem determines inside an interval.
Real-root isolation: The task of finding disjoint intervals, each containing exactly one real root of a polynomial. Repeated Sturm counts let an algorithm subdivide intervals until every root is isolated.
Charles-François Sturm: A Swiss mathematician who introduced the theorem for counting real roots of algebraic equations. The theorem and its sequence are named for Sturm, whose work supplied the root-counting method.
Descartes' rule of signs: A rule bounding the number of positive real roots by the sign changes in a polynomial's coefficients. It offers a simpler bound but does not generally determine an exact count in an arbitrary interval.
Polynomial remainder theorem: A theorem stating that division of a polynomial by x−a leaves remainder equal to its value at a. Evaluating sequence polynomials at endpoints determines the signs used in the count.
Polynomial: An expression in variables formed from coefficients and nonnegative integer powers, combined by addition and multiplication. The theorem applies to real polynomials and constructs its sequence from their coefficients.
Exact real arithmetic: Computation with real algebraic quantities using finite symbolic representations and exact comparisons. Sturm counts can certify root locations without relying on approximate numerical values.
Theorem of Descartes: A rule giving an upper bound on positive real roots from sign changes in a polynomial's coefficients. Descartes' rule bounds positive roots, while Sturm's theorem gives an exact count on a chosen interval.
Budan's theorem: A theorem bounding the number of real roots in an interval using sign variations of successive derivatives at its endpoints. It gives bounds that can be less sharp than Sturm's exact count.

Linked from 4 pages