Multistep filtering operators for ordinary differential equations

Janssen, M. Deville, Yves [UCL] Van Hentenryck, P.

Interval methods for ordinary differential equations (ODEs) provide guaranteed enclosures of the solutions and numerical proofs of existence and unicity of the solution. Unfortunately, they may result in large over-approximations of the solution because of the loss of precision in interval computations and the wrapping effect. The main open issue in this area is to find tighter enclosures of the solution, while not sacrificing efficiency too much. This paper takes a constraint satisfaction approach to this problem, whose basic idea is to iterate a forward step to produce an initial enclosure with a pruning step that tightens it. The paper focuses on the pruning step and proposes novel multistep filtering operators for ODEs. These operators are based on interval extensions of a multistep solution that are obtained by using (Lagrange and Hermite) interpolation polynomials and their error terms. The paper also shows how traditional techniques (such as mean-value forms and coordinate transformations) can be adapted to this new context. Preliminary experimental results illustrate the potential of the approach, especially on stiff problems, well-known to be very difficult to solve.