Certified and fast computation of supremum norms of approximation errors - Archive ouverte HAL Access content directly
Conference Papers Year : 2009

Certified and fast computation of supremum norms of approximation errors

(1) , (1) , (1)
1

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.
Fichier principal
Vignette du fichier
RR2008-37.lip.pdf (271.92 Ko) Télécharger le fichier
Vignette du fichier
example1.sollya (1.05 Ko) Télécharger le fichier
Vignette du fichier
example2.sollya (1.19 Ko) Télécharger le fichier
Vignette du fichier
example3.sollya (1.82 Ko) Télécharger le fichier
Vignette du fichier
example4.sollya (1020 B) Télécharger le fichier
Vignette du fichier
example5.sollya (1013 B) Télécharger le fichier
Vignette du fichier
example6.sollya (1 Ko) Télécharger le fichier
Vignette du fichier
example7.sollya (1020 B) Télécharger le fichier
Vignette du fichier
example8.sollya (1009 B) Télécharger le fichier
Vignette du fichier
example9.sollya (975 B) Télécharger le fichier
Vignette du fichier
findZerosFamilyOfPoly.sollya (8.61 Ko) Télécharger le fichier
Vignette du fichier
getTaylorPoly.sollya (5.62 Ko) Télécharger le fichier
Vignette du fichier
infinityNorm.sollya (1.79 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Format : Other
Loading...

Dates and versions

ensl-00334545 , version 1 (27-10-2008)

Identifiers

  • HAL Id : ensl-00334545 , version 1

Cite

Sylvain Chevillard, Mioara Maria Joldes, Christoph Lauter. Certified and fast computation of supremum norms of approximation errors. 19th IEEE Symposium on Computer Arithmetic (ARITH 19), Jun 2009, Portland, United States. pp.169 -- 176. ⟨ensl-00334545⟩
266 View
289 Download

Share

Gmail Facebook Twitter LinkedIn More