Sturm's theorem

In mathematics, the Sturm sequence of a univariate polynomial p is a sequence of polynomials associated with p and its derivative by a variant of Euclid's algorithm for polynomials. Sturm's theorem expresses the number of distinct real roots of p located in an interval in terms of the number of changes of signs of the values of the Sturm's sequence at the bounds of the interval. Applied to the interval of all the real numbers, it gives the total number of real roots of p.

Whereas the fundamental theorem of algebra readily yields the overall number of complex roots, counted with multiplicity, it does not provide a procedure for calculating them. Sturm's theorem counts the number of distinct real roots and locates them in intervals. By subdividing the intervals containing some roots, it can isolate the roots into arbitrary small intervals, each containing exactly one root. This yields an arbitrary-precision numeric root finding algorithm for univariate polynomials.

Sturm's sequence and Sturm's theorems are named after Jacques Charles François Sturm.

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

of decreasing degree with these following properties:

Sturm's sequence is a modification of Fourier's sequence.

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

...
Wikipedia