# Root of a polynomial by Newton's method

This example deals with the improvement and optimization of an iterative algorithm by using CADNA features.

This program computes a root of the polynomial f(x) = 1.47*x**3 + 1.19*x**2 - 1.83*x + 0.45 by Newton's method. The sequence is initialized by x = 0.5.

The iterative algorithm x(n+1) = x(n) - f(x(n))/f'(x(n)) is stopped by the criterion |x(n)-x(n-1)|<=1.0e-12.

x( 33) = +4.285714285823216e-01
x( 34) = +4.285714285823216e-01

-----------------------------------------------------
Self-validation detection: ON
Mathematical instabilities detection : ON
Branching instabilities detection : ON
Intrinsic instabilities detection : ON
Cancellation instabilities detection : ON
-----------------------------------------------------
x( 23) = 0.428571437E+000
x( 24) = 0.42857143E+000
-----------------------------------------------------
There are 46 numerical instabilities
1 UNSTABLE BRANCHING(S)
45 LOSS(ES) OF ACCURACY DUE TO CANCELLATION(S)

With CADNA, one can see that 7 significant digits have been lost (despite the apparent stability).

By using the symbolic debugger, one can see that the last answer of the stopping criterion is not reliable.

CADNA allows to stop the algorithm when the subtraction x-y is no significant (there is no more information to compute at the next iteration).

Because of the instabilities detected by CADNA, a double root is suspected. One can simplify the fraction.

When these two transformations are done, the code is stabilized and the results are obtained with the best accuraccy of the computer. The exact value of the root is X_sol = 3/7 = 0.428571428571428571....
Now, we obtain:

-----------------------------------------------------
Self-validation detection: ON
Mathematical instabilities detection : ON
Branching instabilities detection : ON
Intrinsic instabilities detection : ON
Cancellation instabilities detection : ON
-----------------------------------------------------
x( 45) = 0.428571428571430E+000
x( 46) = 0.428571428571429E+000
-----------------------------------------------------