Logo

Numerical examples





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.

Without CADNA:

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

With CADNA:

-----------------------------------------------------
CADNA software
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
-----------------------------------------------------
CADNA software
There are 46 numerical instabilities
1 UNSTABLE BRANCHING(S)
45 LOSS(ES) OF ACCURACY DUE TO CANCELLATION(S)

Comments

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:

-----------------------------------------------------
CADNA software
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
-----------------------------------------------------
CADNA software
No instability detected


the classical FORTRAN source code..

the FORTRAN source code with CADNA..

the stabilized FORTRAN source code with CADNA..


More information can be requested to the CADNA team
Thanks to Baptiste Mary for the CADNA logo