Example

The program Test_Solve_UP is a general test program which enable to solve univariate polynomial whose coefficients are given in a file by increasing power of the unknown.

We use as example the Wilkinson polynomial of degree $n$ where $P$:

$$P= \prod_{i =1}^{i =n} (x-i)$$

It is well known that this polynomial is extremely ill-conditioned. For $n=12$ the coefficient of $x^{11}$ is 78. But if we modify this coefficient by $10^{-5}$ there is a big change in the roots, 4 of them becoming complex [4]. The general procedure leads to reasonable accurate result up to $n=18$. At $n=19$ although Kantorovitch theorem has determined interval solutions that indeed contain all the solutions, Newton method is unable to provide an accurate estimate of this root due to numerical errors.

For $n=10$ and if we are looking for the roots in the interval [0,2] the computation time is 90ms, for $n=15$ 190ms and 330ms for $n=20$. For the fast algorithm these times are: 10ms, 20ms, 30 ms Note that the best classical solving algorithm start to give inaccurate results for $n=22$ (between 12.5 and 18.5 the interval analysis algorithm finds the roots 13.424830, 13.538691, 15.477653, 15.498664, 17.554518, 17.553513) and give imaginary roots for $n=23$.