From Rounding Error Estimation to Automatic Correction with AD
by
Philippe Langlois
ARENAIRE Project, CNRS/ENSL/INRIA, LIP, ENS de Lyon and INRIA Rhone-Alpes (France)

Using AD to estimate the rounding error propagation in numerical algorithms is very well described by M. Iri in AD'1991 conference proceedings (SIAM ed.). Iri shows that bounding elementary rounding errors (ERE) yields an absolute bound for the final error FE, that considering ERE as random variables gives a probabilistic estimate for FE, and how improve stopping criteria of iterative methods.

We propose a new application of AD to roundoff analysis providing an automatic correction of the first order effect of the elementary rounding errors. The key-idea is to compute these ERE.

With this correction, we improve the accuracy of final results and/or we stabilize numerical algorithms when the instability comes from the rounding errors. This is respectively illustrated with inner-product computation and polynomial multiple root finding with Newton's iteration.

We prove that such a linear correction provides a more general accuracy improvement that increasing the precision and also avoids the limitations of absolute bounding.

http://www.ens-lyon.fr/~plangloi/AD2000.htm

Date received: December 9, 1999