Editing Sturm's theorem (section)

==Root isolation==

For a polynomial with real coefficients, ''root isolation'' consists of finding, for each real root, an interval that contains this root, and no other roots. 

This is useful for [[root-finding algorithm|root finding]], allowing the selection of the root to be found and providing a good starting point for fast numerical algorithms such as [[Newton's method]]; it is also useful for certifying the result, as if Newton's method converge outside the interval one may immediately deduce that it converges to the wrong root.

Root isolation is also useful for computing with [[algebraic numbers]]. For computing with algebraic numbers, a common method is to represent them as a pair of a polynomial to which the algebraic number is a root, and an isolation interval. For example <math>\sqrt 2</math> may be unambiguously represented by <math>(x^2-2, [0,2]).</math>

Sturm's theorem provides a way for isolating real roots that is less efficient (for polynomials with integer coefficients) than other methods involving [[Descartes' rule of signs]]. However, it remains useful in some circumstances, mainly for theoretical purposes, for example for algorithms of [[real algebraic geometry]] that involve [[infinitesimal]]s.<ref name=mpi>{{harv|de Moura|Passmore|2013}}</ref>

For isolating the real roots, one starts from an interval <math>(a,b]</math> containing all the real roots, or the roots of interest (often, typically in physical problems, only positive roots are interesting), and one computes <math>V(a)</math> and <math>V(b).</math> For defining this starting interval, one may use bounds on the size of the roots (see {{slink|Properties of polynomial roots|Bounds on (complex) polynomial roots}}). Then, one divides this interval in two, by choosing {{mvar|c}} in the middle of <math>(a,b].</math> The computation of <math>V(c)</math> provides the number of real roots in <math>(a,c]</math> and <math>(c,b],</math> and one may repeat the same operation on each subinterval. When one encounters, during this process an interval that does not contain any root, it may be suppressed from the list of intervals to consider. When one encounters an interval containing exactly one root, one may stop dividing it, as it is an isolation interval. The process stops eventually, when only isolating intervals remain. 

This isolating process may be used with any method for computing the number of real roots in an interval. Theoretical [[complexity analysis]] and practical experiences show that methods based on [[Descartes' rule of signs]] are more efficient. It follows that, nowadays, Sturm sequences are rarely used for root isolation.