License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITP.2019.8
URN: urn:nbn:de:0030-drops-110638
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11063/
Bréhard, Florent ;
Mahboubi, Assia ;
Pous, Damien
A Certificate-Based Approach to Formally Verified Approximations
Abstract
We present a library to verify rigorous approximations of univariate functions on real numbers, with the Coq proof assistant. Based on interval arithmetic, this library also implements a technique of validation a posteriori based on the Banach fixed-point theorem. We illustrate this technique on the case of operations of division and square root. This library features a collection of abstract structures that organise the specfication of rigorous approximations, and modularise the related proofs. Finally, we provide an implementation of verified Chebyshev approximations, and we discuss a few examples of computations.
BibTeX - Entry
@InProceedings{brhard_et_al:LIPIcs:2019:11063,
author = {Florent Br{\'e}hard and Assia Mahboubi and Damien Pous},
title = {{A Certificate-Based Approach to Formally Verified Approximations}},
booktitle = {10th International Conference on Interactive Theorem Proving (ITP 2019)},
pages = {8:1--8:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-122-1},
ISSN = {1868-8969},
year = {2019},
volume = {141},
editor = {John Harrison and John O'Leary and Andrew Tolmach},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11063},
URN = {urn:nbn:de:0030-drops-110638},
doi = {10.4230/LIPIcs.ITP.2019.8},
annote = {Keywords: approximation theory, Chebyshev polynomials, Banach fixed-point theorem, interval arithmetic, Coq}
}
Keywords: |
|
approximation theory, Chebyshev polynomials, Banach fixed-point theorem, interval arithmetic, Coq |
Collection: |
|
10th International Conference on Interactive Theorem Proving (ITP 2019) |
Issue Date: |
|
2019 |
Date of publication: |
|
05.09.2019 |
Supplementary Material: |
|
https://gitlab.inria.fr/amahboub/approx-models |