First presenter Co-presenter(s)
Name :  Markus Neher * Name:   
E-mail: E-mail:  
Affiliation: Universitšt Karlsruhe (TH) Name:   
Department: Institute for Applied and Numerical Mathematics  E-mail:    
City: Name:   
State/Province:   E-mail:    
Country: Germany Name:   
Talk
Number:
02-04  E-mail:    
Session: 2- Interaction Between Computer Algebra and Interval Computations Schedule:
 
Room:
Thursday, 11:30
 
B-2624
Related website:  
Title of
presentation:
Verified Integration Methods for ODEs
Abstract:

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.