Certified and fast computation of supremum norms of approximation errors

Abstract : In many numerical programs there is a need for a high-quality floating-point approximation 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) epsilon = p-f or epsilon = 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 are given.
Type de document :
Communication dans un congrès
Javier D. Bruguera, Marius Cornea, Debjit DasSarma, John Harrison. 19th IEEE Symposium on Computer Arithmetic (ARITH 19), Jun 2009, Portland, United States. IEEE, pp.169 -- 176, 2009
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00334545
Contributeur : Sylvain Chevillard <>
Soumis le : lundi 27 octobre 2008 - 12:16:59
Dernière modification le : mardi 24 avril 2018 - 13:52:25
Document(s) archivé(s) le : lundi 7 juin 2010 - 18:52:54

Identifiants

  • HAL Id : ensl-00334545, version 1

Collections

Citation

Sylvain Chevillard, Mioara Joldes, Christoph Lauter. Certified and fast computation of supremum norms of approximation errors. Javier D. Bruguera, Marius Cornea, Debjit DasSarma, John Harrison. 19th IEEE Symposium on Computer Arithmetic (ARITH 19), Jun 2009, Portland, United States. IEEE, pp.169 -- 176, 2009. 〈ensl-00334545〉

Partager

Métriques

Consultations de la notice

507

Téléchargements de fichiers

341