14-15 May 2018
ENS de Lyon
Europe/Paris timezone

A Newton-like Validation Method for Chebyshev Approximate Solutions of Linear Ordinary Differential Equations

14 May 2018, 14:30
Amphi A (ENS de Lyon)

Amphi A

ENS de Lyon

46 allée d'Italie 69364 Lyon Cedex 07, France


Florent Bréhard (LAAS-CNRS Toulouse and CNRS, LIP - INRIA AriC / Plume - ENS de Lyon)


A wide range of efficient numerical routines exist for solving function space problems (ODEs, PDEs, optimization, etc.) when no closed form is known for the solution. While most applications prioritize efficiency, some safety-critical tasks, as well as computer assisted mathematics, need rigorous guarantees on the computed result. For that, rigorous numerics aims at providing numerical approximations together with rigorous mathematical statements about them, without sacrificing (too much) efficiency and automation. In the spirit of Newton-like validation methods (see for example [2]), we propose a fully automated algorithm which computes both a numerical approximate solution in Chebyshev basis and a rigorous uniform error bound for a restricted class of differential equations, namely Linear ODEs (LODEs). Functions are rigorously represented using Chebyshev models [1], which are a generalization of Taylor models [3] with better convergence properties. Broadly speaking, the algorithm works in two steps: (i) After applying an integral transform on the LODE, an infinite-dimensional linear almost-banded system is obtained. Its truncation at a given order N is solved with the fast algorithm of [4]. (ii) This solution is validated using a specific Newton-like fixed-point operator. This is obtained by approximating the integral operator with a finite-dimensional truncation, whose inverse Jacobian is in turn approximated by an almost-banded matrix, obtained with a modified version of the algorithm of [4]. A C library implementing this validation method is freely available online at https://gforge.inria.fr/projects/tchebyapprox/ [1] N. Brisebarre and M. Joldeş. Chebyshev interpolation polynomial-based tools for rigorous computing. In Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, pages 147-154. ACM, 2010. [2] J.-P. Lessard and C. Reinhardt. Rigorous numerics for nonlinear differential equations using Chebyshev series. SIAM J. Numer. Anal., 52(1):1-22, 2014. [3] K. Makino and M. Berz. Taylor models and other validated functional inclusion methods. International Journal of Pure and Applied Mathematics, 4(4):379-456, 2003. [4] S. Olver and A. Townsend. A fast and well-conditioned spectral method. SIAM Review, 55(3):462-489, 2013.


Mioara Joldes Nicolas Brisebarre

Presentation Materials

There are no materials yet.