Real-root isolation

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, and, more specifically in <a href="/facts/Numerical_analysis/QT9cYa9z">numerical analysis</a> and <a href="/facts/Computer_algebra/hjun1KAX">computer algebra</a>, real-root isolation of a <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> consist of producing disjoint <a href="/facts/Interval_(mathematics)/e9se3vTe">intervals</a> of the <a href="/facts/Real_line/6eq42xX5">real line</a>, which contain each one (and only one) real <a href="/facts/Root_of_a_function/mlK3dhoT">root</a> of the polynomial, and, together, contain all the real roots of the polynomial.
Real-root isolation is useful because usual <a href="/facts/Root-finding_algorithm/IxTDkhBq">root-finding algorithms</a> for computing the real roots of a polynomial may produce some real roots, but, cannot generally certify having found all real roots. In particular, if such an algorithm does not find any root, one does not know whether it is because there is no real root. Some algorithms compute all complex roots, but, as there are generally much fewer real roots than complex roots, most of their computation time is generally spent for computing non-real roots (in the average, a polynomial of degree n has n complex roots, and only log n real roots; see <a href="/facts/Geometrical_properties_of_polynomial_roots/YKNYVKcj">Geometrical properties of polynomial roots § Real roots</a>). Moreover, it may be difficult to distinguish the real roots from the non-real roots with small imaginary part (see the example of <a href="/facts/Wilkinson%27s_polynomial/aeaxbl4B">Wilkinson's polynomial</a> in next section).
The first complete real-root isolation algorithm results from <a href="/facts/Sturm%27s_theorem/fn2MG3wu">Sturm's theorem</a> (1829). However, when real-root-isolation algorithms began to be implemented on <a href="/facts/Computer/SQe1aK05">computers</a> it appeared that algorithms derived from Sturm's theorem are less efficient than those derived from <a href="/facts/Descartes%27_rule_of_signs/DHgM49hn">Descartes' rule of signs</a> (1637).
Since the beginning of 20th century there has been much research activity for improving the algorithms derived from Descartes' rule of signs, getting very efficient implementations, and determining their <a href="/facts/Computational_complexity/Qenh22Ja">computational complexities</a>. The best implementations can routinely isolate real roots of polynomials of degree more than 1,000.

Real-root isolation open-in-new

Real-root isolation