Isolating roots

Let $p(x)$ be a univariate polynomial of degree $d$ with real coefficients. By isolating the roots of $p$ we mean computing $d$ rational numbers $r_i,i=1\dots d$, that approximate its exact real and complex roots, and $d$ positive numbers that give some estimates of the accuracies.

For a square-free polynomial:

1. get an approximate of $p$ by dumping its coefficients;

2. compute some approximates of the roots $r_1^0,\dots,r_d^0$ (using, for instance, Maple function fsolve);

3. for each $i$, compute an estimate for the distance to the nearest root of $r_i^0$:
- compute $$\epsilon_i := \left\vert\frac{d\cdot p(r_i^0)}{p'(r_i^0)}\right\vert$$ (see [Strzebonski, 97)]) using erna arithmetic;
- set $\varepsilon_i$ to the sum of the absolute value of the dump of $\epsilon_i$ and its accuracy;

4. test the discs of centers $r_i^0$ and radii $\varepsilon_i$ for intersections; if any two discs intersect, refine the polynomial and repeat from step 2;

5. report the list of pairs $(r_i^0,\varepsilon_i)$.

In Step 4 from above, the decision is based on the knowledge that the polynomial is square-free: after a few steps of refining the approximations of the roots, their discs will contain only one exact root, and eventually they get disjoint.

Creating an erna object for the root of a polynomial

The initial approximation $(r_0,\varepsilon_0)$ of the root must be provided (it can be computed using sqFreePolRootsIsol). The method that gives better approximates is described in the following:

1. get a dump of the polynomial, and of its first derivative;

2. apply a Newton step to compute another value of the root, $r_1$, from the known value, $r_0$;

3. compute the distance $\varepsilon_1$ to the nearest exact root, using the same formula as before;

4. if this distance is greater than the tenth part of the accuracy of the known approximation, then refine the polynomial, its derivative, and go to step 2;

5. report $(r_1,\varepsilon_1)$.

Figure 3: Roots of polynomials with erna coefficients.