Editing Sturm's theorem (section)

{{Short description|Counting polynomial roots in an interval}}
In [[mathematics]], the '''Sturm sequence''' of a [[univariate polynomial]] {{mvar|p}} is a sequence of polynomials associated with {{mvar|p}} and its derivative by a variant of [[Euclid's algorithm for polynomials]]. '''Sturm's theorem''' expresses the number of distinct [[real number|real]] [[Root of a function|root]]s of {{mvar|p}} located in an [[interval (mathematics)|interval]] in terms of the number of changes of signs of the values of the Sturm 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 {{mvar|p}}.<ref name=bpr>{{harv|Basu|Pollack|Roy|2006}}</ref>

Whereas the [[fundamental theorem of algebra]] readily yields the overall number of [[complex number|complex]] roots, counted with [[multiplicity (mathematics)|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 arbitrarily small intervals, each containing exactly one root. This yields the oldest [[real-root isolation]] algorithm, and arbitrary-precision [[root-finding algorithm]] for univariate polynomials.

For computing over the [[real number|reals]], Sturm's theorem is less efficient than other methods based on [[Descartes' rule of signs]]. However, it works on every [[real closed field]], and, therefore, remains fundamental for the theoretical study of the [[computational complexity]] of [[decidability of first-order theories of the real numbers|decidability]] and [[quantifier elimination]] in the [[first order theory]] of real numbers.

The Sturm sequence and Sturm's theorem are named after [[Jacques Charles François Sturm]], who discovered the theorem in 1829.<ref>{{MacTutor Biography|id=Sturm|mode=cs1}}</ref>