Verified integration of ODEs. The numerical solution of initial
value problems (IVPs) for ODEs is one of the fundamental problems in
computation. Today, there are many well-established algorithms for
approximate solution of IVPs. However, traditional integration methods
usually provide only approximate values for the solution. Precise error
bounds are rarely available. The error estimates, which are sometimes
delivered, are not guaranteed to be accurate and are sometimes unreliable.
In contrast, verified integration computes guaranteed bounds for the
flow of an ODE, including all discretization and roundoff errors in the
computation. Originated by Moore in the 1960s, interval computations are
a particularly useful tool for this purpose.
Dependency Problem and Wrapping Effect. Unfortunately, the
results of interval arithmetic computations are sometimes affected by
overestimation, such that computed error bounds are over-pessimistic.
Overestimation is often caused by the \textit{dependency problem}, which
is the lack of interval arithmetic to identify different occurrences of
the same variable. For example, $x - x > = 0$ holds for each $x \in
[1,2]$, but $\bmx - \bmx$ for $\bmx = [1,2]$ yields $[-1,1]$. A second
source of overestimation is the wrapping effect, which appears
when intermediate results of a computation are enclosed into intervals.
Overestimations due to wrapping are one of the major problems in the
interval arithmetic treatment of ODEs. In verified integration,
overestimation may degrade the computed enclosure of the flow, enforce
miniscule step sizes, or even bring about premature abortion of an
integration.
Taylor Models. Berz and his co-workers have developed Taylor
model methods, which combine interval arithmetic with symbolic
computations. For the verified integration of IVPs, Taylor models supply
a comprehensive variety of applicable enclosure sets for the flow, which
is an effective means for reducing wrapping.
In our talk, we present Taylor model methods for the verified
integration of ODEs and compare them with well-known interval methods
for this task. Numerical examples for linear and nonlinear ODEs are given. |