Formalizations of error analysis in numerical analysis and floating-point arithmetic
Formalisations d’analyses d’erreurs en analyse numérique et en arithmétique à virgule flottante
Résumé
This thesis consists of three contributions related to the Coq formalization of error analysis in numerical analysis and floating-point arithmetic.First, we have exhibited an algorithm computing the average of two decimal floating-point numbers and have proved that this algorithm computes the correct rounding. We have formalized the algorithm and its correctness proof in the Coq proof assistant.The second contribution of the thesis is the analysis and the formalization of rounding error bounds associated to the implementation of Runge-Kutta methods applied to linear systems. We have proposed a generic methodology to build a bound on the error accumulated over the iterations, taking potential underflow and overflow into account. We have then instantiated this methodology forclassic Runge-Kutta methods, e.g. the Euler and RK2 methods. We have proposed a formalization of the results, including the definition of matrix norms, theproof of rounding error bounds for matrix operations and the formalization of the generic results and their instantiations.Finally, we have proposed a formalization of functional analysis results that serve as foundations for the finite element method. This formalization is based on the Coquelicot library and includes the theory of Hilbert spaces, the formal proof of the Lax--Milgram Theorem and the proof of completeness of finite dimensional subspaces of Hilbert spaces.
Cette thèse est constituée de trois contributions liées à la formalisation en Coq d'analyses d'erreurs dans les domaines de l'analyse numérique et de l'arithmétique à virgule flottante.Nous avons tout d'abord proposé un algorithme calculant la moyenne de deux nombres flottants décimaux et avons montré que cet algorithme fournissait l'arrondi correct. Nous avons formalisé l'algorithme et sa preuve de correction dans l'assistant de preuves Coq.La seconde contribution de la thèse est l'analyse et la formalisation de bornes sur les erreurs d'arrondi d'implémentations de méthodes de Runge-Kutta appliquées à des systèmes linéaires. Nous avons proposé une méthodologie générique permettant de construire une borne sur l'erreur d'arrondi accumulée au cours des itérations et qui tient compte d'éventuels dépassements de capacité. Nous avons ensuite appliquée la méthodologie à des méthodes de Runge-Kuttaclassiques, comme les méthodes d'Euler et de RK2. Nous avons proposé une formalisation de l'analyse, incluant la définition de normes matricielles, la démonstration de bornes sur les erreurs d'arrondi d'opérations matricielles etla formalisation des résultats génériques et de leur instanciation.Enfin, nous avons proposé la formalisation de résultats d'analyse fonctionnelle qui servent de fondements à la méthode des éléments finis. Cette formalisation repose sur la bibliothèque Coquelicot et inclut la théorie des espaces de Hilbert, la formalisation du théorème de Lax-Milgram et la preuve de complétude des sous-espaces de dimension finie d'espaces de Hilbert.
Origine | Version validée par le jury (STAR) |
---|
Loading...