Orateur
Florent Bréhard
(LAAS-CNRS Toulouse and CNRS, LIP - INRIA AriC / Plume - ENS de Lyon)
Description
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.
Co-auteurs
Mioara Joldes
Nicolas Brisebarre
