Certified and fast computation of supremum norms of approximation errors - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2008

Certified and fast computation of supremum norms of approximation errors

Résumé

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.
Beaucoup d’applications numériques nécessitent le calcul précis d’approximations en virgule flottante de fonctions f telles que exp, sin, erf. En pratique, dans l’implantation, la fonction est remplacée par un polynôme p, ce qui conduit à une erreur d’approximation (absolue ou relative) ε = p − f ou ε = p/f − 1. La majoration fine et néanmoins sûre de cette erreur est une étape importante lorsqu’on vise une implantation certifiée.La principale difficulté de ce problème vient du fait que l’erreur d’approximation est très petite et est calculée par une différence p − f qui cancelle énormément.Les précédentes approches pour calculer des normes sup sont donc insuffisantes dans ce cas bien précis : ou bien elles n’offrent pas la garantie de sécurité du résultat, ou bien elles donnent des majorations trop grossières, ou enfin elles nécessitent trop de travail manuel au cas par cas. Nous présentons un algorithme sûr et rapide pour calculer une minoration et une majoration fine de la norme sup d’erreurs d’approximation. L’algorithme s’appuie sur la combinaison de différentes techniques existantes, en particulier une arithmétique d’intervalle perfectionnée, de la différentiation automatique et l’isolation fine des racines d’un polynôme. Nous avons implémenté notre algorithme et nous donnons les temps d’exécution sur plusieurs exemples.
Fichier principal
Vignette du fichier
LIP-RR_2008-37.pdf (271.92 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102827 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102827 , version 1

Citer

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⟩
48 Consultations
140 Téléchargements

Partager

Gmail Facebook X LinkedIn More