A hybrid method for high precision calculation of polynomial real roots
George Ernest Collins, Werner Krandick · 1993
A straightforward implementation of Newton's method for polynomial real root calculation using exact arithmetic is inefficient. In each step the length of the iterate multiplies by the degree of the polynomial while its accuracy merely doubles. We present an exact algorithm which keeps the length of each iterate proportional to its accuracy. The resulting speed-up is dramatic. The average computing time can be further reduced by trying floating point computations. Several floating point Newton steps are executed; interval arithmetic is used to check whether the result is sufficiently close to the root; if this condition cannot be verified the exact algorithm is invoked. 1 Introduction Real roots of a univariate integral polynomial A can be calculated in two steps, called "root isolation" and "root refinement". Root isolation computes isolating intervals for the roots of A; those are intervals which contain exactly one polynomial root each. Root refinement refines an isolating interva...