Certified and fast computation of supremum norms of approximation errors

Abstract : In many numerical programs there is a need for a high-quality floating-pointapproximation of useful functions f, such as exp, sin, erf. In the actual implementation,the function is replaced by a polynomial p, leading to an approximation error (absolute or relative) ε = p−f or ε = p/f−1. The tight yet certain bounding of this error is an important step towards safe implementations.The main difficulty of this problem is due to the fact that this approximation error is very small and the difference p − f is highly cancellating. In consequence,previous approaches for computing the supremum norm in this degenerate case, have proven to be either 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 timings on several examples aregiven.
Document type :
Reports
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102827
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 4:33:53 PM
Last modification on : Friday, April 19, 2019 - 1:38:16 AM

File

LIP-RR_2008-37.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102827, version 1

Collections

Citation

Sylvain Chevillard, Mioara Joldes, Christoph Lauter. Certified and fast computation of supremum norms of approximation errors. [Research Report] LIP RR-2008-37, Laboratoire de l'informatique du parallélisme. 2008, 2+11p. ⟨hal-02102827⟩

Share

Metrics

Record views

25

Files downloads

24