Validated solutions of initial value problems for ordinary differential equations

https://doi.org/10.1016/S0096-3003(98)10083-8Get rights and content

Abstract

Compared to standard numerical methods for initial-value problems (IVPs) for ordinary differential equations (ODEs), validated methods for IVPs for ODEs have two important advantages: if they return a solution to a problem, then (1) the problem is guaranteed to have a unique solution, and (2) an enclosure of the true solution is produced. The authors survey Taylor series methods for validated solutions of IVPs for ODEs, describe several such methods in a common framework, and identify areas for future research.

Introduction

We consider validated numerical methods for the solution of the autonomous initial-value problems (IVPs)y(t)=f(y),y(t0)=y0,where t∈[t0,T] for some T>t0. Here t0,T∈R, f∈Ck−1(D), DRn is an open set, f:DRn, and y0D. For expositional convenience, we consider only autonomous systems. This is not a restriction of consequence since a time-dependent system of ODEs can be converted into an autonomous system. Alternatively, the numerical methods discussed here can be extended easily to non-autonomous systems.

Our goal is to compute, at given points {tj} in (t0,T], an interval vector [yj] that is guaranteed to contain the true solution y(tj) of Eq. (1).

Standard numerical methods for IVPs for ordinary differential equations (ODEs) attempt to compute an approximate solution that satisfies a user-specified tolerance. These methods are usually robust and reliable for most applications, but it is easy to find examples for which they return very inaccurate results. On the other hand, if a validated method (also called an interval method) for IVPs for ODEs returns successfully, it not only produces a guaranteed error bound for the true solution, but also verifies that a unique solution to the problem exists.

There are situations when guaranteed error bounds are desired or needed. For example, a solution with a guaranteed error bound could be used to prove a theorem [1]. Also, some calculations may be critical to the safety or reliability of a system. It may therefore be necessary or desirable to ensure that a computed solution meets a user-specified accuracy requirement.

One reason why validated solutions to IVPs for ODEs have not been popular in the past is that their computation typically requires considerably more time than does the computation of standard methods. However, now that “chips are cheap”, it seems natural to shift the burden of determining the reliability of a numerical solution from the user to the computer – at least for many standard, computationally inexpensive problems.

In addition, there are situations where interval methods for IVPs for ODEs may not be computationally more expensive than standard methods. For example, many ODEs arising in practical applications contain parameters. Often these parameters cannot be measured exactly, but are known to lie in certain intervals, for example, as in economic models or in robot control problems. In these situations, a user might want to compute solutions for ranges of parameters. For such problems, standard numerical methods are often expensive, but interval methods can easily “capture” all the solutions at essentially no extra cost.

The purpose of this paper is to review the most significant developments in the area of validated solutions of IVPs for ODEs. We focus on the interval methods of Moore 2, 3, 4, Krückeberg [5], Eijgenraam [6], and Lohner 7, 8, 9, all of which are based on Taylor series. One reason for the popularity of this approach is the simple form of the error term for Taylor series methods. In addition, the Taylor series coefficients can be readily generated by automatic differentiation, the order of the method can be changed easily by adding or deleting Taylor series terms, and the stepsize can be changed without recomputing Taylor series coefficients.

Surveys of Taylor series and other interval methods can be found in 10, 11, 12, 13, 14, 15, 16. These papers give a “high-level” description of existing methods. The main contribution of our paper is that it provides a common framework for the Taylor series methods referenced above, allowing us to compare these schemes with one another in more detail and providing a basis for future work in this area. We also identify the difficulties that arise in validated solutions of IVP for ODEs.

A brief outline of the structure of this paper follows. In Section 2, we give the background that we need later. We introduce interval-arithmetic operations on real intervals, interval vectors, and interval matrices. We also define interval-valued functions, interval integration, and discuss a method for efficient generation of Taylor series coefficients. In Section 3, we state in more detail the IVP that is the subject of this paper. In Section 4, we present an overview of Taylor series methods for validated solutions of IVPs for ODEs. In Section 5, we examine three techniques for computing an a priori enclosure of the solution and selecting a stepsize: namely, the constant, Taylor series, and polynomial enclosure methods. In Section 6, we explain the so-called “wrapping effect”, consider it in linear systems, and discuss a class of problems where it does not appear. In Section 7, we describe five algorithms for computing a tight enclosure and reducing the wrapping effect: the algorithms of Moore, Krückeberg, Eijgenraam, Lohner, and an improvement of Lohner's algorithm due to Rihm [17]. In Section 8, we consider Eijgenraam's stepsize and order control strategies. In Section 9, we briefly describe a method based on controlling the defect of the computed solution.

Section snippets

Interval arithmetic

The set of intervals on the real line R is defined byIR=[a]=[a,a]|a,aR,aa.If a=a then [a] is a thin interval; if a⩾0 then [a] is non-negative ([a]⩾0); and if a=−ā then [a] is symmetric. Two intervals [a] and [b] are equal if a=b and ā=b̄.

Let [a],[b]∈IR and ∗∈{+,−,×,/}. The interval-arithmetic operations are defined [4], pp. 8, 9, by[a]∗[b]=x∗y|x∈[a],y∈[b],0∉[b]when∗=/,which can be written in the equivalent form (we omit “×” in the notation):[a]+[b]=[a+b,ā+b̄],[a]−[b]=[ab̄,āb],[a][b]=[min

The initial value problem

We consider the set of autonomous initial value problemsy(t)=f(y),y(t0)∈[y0],where t∈[t0,T] for some T>t0. Here t0,T∈R, f∈Ck−1(D), DRn is open, f:DRn, and [y0]⊆D. This generalization of Eq. (1)permits the initial value y(t0) to be in an interval, rather than specifying a particular value. We assume that the representation of f contains only a finite number of constants, variables, elementary operations, and standard functions. Since we assume f∈Ck−1(D), we exclude functions that contain, for

A brief overview of Taylor series methods for the validated solution of IVPs for ODEs

In most validated methods for IVPs for ODEs, each step consists of two phases:

Algorithm I.

Compute a stepsize hj and an a priori enclosure [ỹj] of the solution such that y(t;tj,yj) is guaranteed to exist for all t∈[tj,tj+1] and all yj∈[yj], andy(t;tj,[yj])⊆[ỹj]forallt∈[tj,tj+1].Then, for t∈[tj,tj+1),y(t;t0,[y0])⊆[y(t)]≔[yj]+i=1k−1[yj]i(t−tj)i+[ỹj]k(t−tj)k.

Algorithm II.

Using [ỹj], compute a tighter enclosure [yj+1] of y(tj+1;tj,Uj). This two-phase process is similar to the

Algorithm I: Computing an a priori enclosure of the solution and selecting a stepsize

Suppose that at tj we have a tight enclosure [yj] of y(tj;t0,[y0]). In this section, we consider the problem: find a stepsize hj>0 and an a priori enclosure [ỹ(t)] such that for any yj∈[yj]y(t)=f(y),y(tj)=yjhas a unique solution y(t)∈[ỹ(t)] for t∈[tj,tj+1]. The methods which we describe for computing hj and [ỹ(t)] are based on the application of the Picard–Lindelöf operator(Ty)(t)=yj+∫tjtf(y(s))dsto appropriate sets of functions and the Banach fixed-point theorem.

Theorem 5.1 [Banach

The wrapping effect

Moore [4] noticed a difficulty arising in his method, the so-called wrapping effect. It can be illustrated by his example,y1=y2,y2=−y1.The solution of Eq. (57)with an initial condition y0 is given by y(t)=A(t)y0, whereA(t)=costsintsintcost.Let y0∈[y0]. The interval vector [y0]∈IR2 can be viewed as a rectangle in the (y1,y2) plane. At t1>t0, [y0] will be mapped by A(t1) into a rectangle of the same size, as shown in Fig. 1. If we want to enclose this rectangle in an interval vector, we have

Algorithm II: Computing a tight enclosure

Suppose that at the (j+1)st step we have a constant enclosure [ỹj] such thaty(t;tj,[yj])⊆[ỹj]forallt∈[tj,tj+1].Using [ỹj], Algorithm II computes a tighter enclosure [yj+1]⊆[ỹj], for whichy(tj+1;tj,Uj)⊆[yj+1].The main difficulty that arises in the second algorithm is controlling the wrapping effect.

Moore's method (see Section 5.3) computes [yj+1] by[yj+1]=[yj]+i=1k−1[yj]ihji+f[k]([ỹ1j])hjk=[yj]+i=1k−1f[i][yj]hji+f[k][ỹ1j]hjk,where [ỹj1] is given by Eq. (48). A disadvantage of using

Stepsize and order control

We describe Eijgenraam's [6], pp. 129–136, stepsize and order control mechanisms.

Defect-controlled solutions

The methods we discussed above produce an enclosure of the true solution. In this section, we describe a defect-controlled method [32] that produces an approximate solution which is the exact solution to a nearby problem. For a suitable problem and any user supplied tolerance, the method can ensure that the defect is less than the tolerance.

Let ỹ(t) be a continuous representation of a computed approximate numerical solution toy=f(y),y(t0)=y0.The defect of ỹ(t) is defined asδ(t)=ỹ(t)−f(ỹ

Some directions for future research

Compared to the standard numerical methods for IVPs for ODEs, little work has been done for the validated solution of ODEs. The most advanced (and probably the only) validated solver for ODEs is AWA [9]. As Corliss points out [36], “there is no widely available portable, production-quality software for validated solution of ODEs”. Such software should allow researchers to experiment easily with interval algorithms for ODEs and should be:

  • portable;

  • modular;

  • easy-to-modify; and

  • able to solve large

Acknowledgements

The authors would like to thank the late Prof. T.E. Hull for his careful reading of this paper and valuable suggestions. The authors would also like to thank Dr. J. Pryce. The discussions with him during his visit to Toronto helped us understand the subject better. His comments considerably improved the presentation of the material.

References (42)

  • G.F. Corliss

    Survey of interval algorithms for ordinary differential equations

    Appl. Math. Comput.

    (1989)
  • W.H. Enright

    A new error-control for initial value solvers

    Appl. Math. Comput.

    (1989)
  • Y.F. Chang et al.

    ATOMFT: Solving ODEs and DAEs using Taylor series

    Computers and Mathematics with Applications

    (1994)
  • H. Spreuer et al.

    On the existence and the verified determination of homoclinic and heteroclinic orbits of the origin for the Lorenz system

    Computing Suppl.

    (1993)
  • R.E. Moore, The automatic analysis and control of error in digital computation based on the use of interval numbers,...
  • R.E. Moore, Automatic local coordinate transformations to reduce the growth of error bounds in interval computation of...
  • R.E. Moore, Interval Analysis, Prentice-Hall, Englewood Cliffs, NJ,...
  • F. Krückeberg, Ordinary differential equations, in: E. Hansen (Ed.), Topics in Interval Analysis, Clarendon Press,...
  • P. Eijgenraam, The solution of initial value problems using interval arithmetic, Mathematical Centre Tracts No. 144,...
  • E. Adams, D. Cordes, R. Lohner, Enclosure of solutions of ordinary initial value problems and applications, in: E....
  • R.J. Lohner, Enclosing the solutions of ordinary initial and boundary value problems, in: E.W. Kaucher, U.W. Kulisch,...
  • R.J. Lohner, Einschließung der Lösung gewöhnlicher Anfangs– und Randwertaufgaben und Anwendungen, PhD thesis,...
  • H. Bauch et al.

    Solving ordinary initial value problems with guaranteed bounds

    Z. Angew. Math. Mech.

    (1989)
  • R.E. Moore, A survey of interval methods for differential equations, in: Proceedings of the 23rd Converence on Decision...
  • K.L.E. Nickel

    Using interval methods for the numerical solution of ODE's

    Z. Angew. Math. Mech.

    (1986)
  • R. Rihm, Interval methods for initial value problems in ODEs, in: J. Herzberger (Ed.), Topics in Validated...
  • H.J. Stetter, Algorithms for the inclusion of solutions of ordinary initial value problems, in: J. Vosmanský, M. Zlámal...
  • H.J. Stetter, Validated solution of initial value problems for ODEs, in: C. Ullrich (Ed.), Computer Arithmetic and...
  • R. Rihm

    On a class of enclosure methods for initial value problems

    Computing

    (1994)
  • G. Alefeld, J. Herzberger, Introduction to Interval Computations, Academic Press, New York,...
  • A. Neumaier, Interval Methods for Systems of Equations, Cambridge University Press, Cambridge,...
  • Cited by (314)

    • Towards an automatic uncertainty compiler

      2023, International Journal of Approximate Reasoning
    • Lie symmetries applied to interval integration

      2022, Automatica
      Citation Excerpt :

      The first two examples can be solved analytically and are given for ease of understanding. Examples 3 and 4 are more complex and we used the interval integration solver CAPD (Wilczak & Zgliczynski, 2011), but we could have used V-Node (Nedialkov, Jackson, & Corliss, 1999) or DynIbex (Sandretto & Chapoutot, 2016) instead. Due to the initial uncertainty, the fast explosion of the size of the tubes makes these solvers inefficient, when they are not combined with Lie symmetries as proposed here.

    View all citing articles on Scopus
    1

    This work was supported in part by the Natural Sciences and Engineering Research Council of Canada and the Information Technology Research Centre of Ontario.

    View full text