Certified and Fast Computation of Supremum Norms of Approximation Errors
Sylvain Chevillard, Mioara Joldeş, Christoph Lauter · 2009
In many numerical programs there is a need for a high-quality floating-point approximation of useful functions f, such as such as exp, sin, erf. In the actual implementation, the function is replaced by a polynomial p, which leads to an approximation error (absolute or relative) epsiv = p - s or epsiv = p/f -1. The tight yet certain bounding of this error is an important step towards safe implementations.The problem is difficult mainly because that approximation error is very small and the difference p-f is subject to high cancellation. Previous approaches for computing the supremum norm in this degenerate case, have proven to be unsafe, not sufficiently tight or too tedious in manual work.We present a safe and fast algorithm that computes a tight lower and upper bound for the supremum norms of approximation errors. The algorithm is based on a combination of several techniques, including enhanced interval arithmetic, automatic differentiation and isolation of the roots of a polynomial. We have implemented our algorithm and give timings on several examples.