s'authentifier
version française rss feed

inria-00369511, version 1

Formal verification of exact computations using Newton's method

Nicolas Julien (Auteur à contacter de préférence) 1, Ioana Pasca () 1

Theorem Proving in Higher Order Logics 5674 (2009) 408-423

Résumé : We are interested in the certification of Newton's method. We use a formalization of the convergence and stability of the method done with the axiomatic real numbers of Coq's Standard Library in order to validate the computation with Newton's method done with a library of exact real arithmetic based on co-inductive streams. The contribution of this work is twofold. Firstly, based on Newton's method, we design and prove correct an algorithm on streams for computing the root of a real function in a lazy manner. Secondly, we prove that rounding at each step in Newton's method still yields a convergent process with an accurate correlation between the precision of the input and that of the result. An algorithm including rounding turns out to be much more efficient.

  • Domaine : Informatique/Calcul formel
  • Mots-clés : formal verification – Newton's method – exact real arithmetic – co-recursive algorithms
 
  • inria-00369511, version 1
  • oai:hal.inria.fr:inria-00369511
  • Contributeur : 
  • Soumis le : Vendredi 20 Mars 2009, 10:39:05
  • Dernière modification le : Mardi 22 Septembre 2009, 14:08:15
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...