Top

previous article Preconditioned quasi-compact boundary value met...

next article Optimal subsets in the stability regions of mul...

Activate PatentFit

Hint

Swipe to navigate through the articles of this issue

29-07-2019 | Original Paper | Issue 2/2020 Open Access

Interval methods of Adams-Bashforth type with variable step sizes

Journal:: Numerical Algorithms > Issue 2/2020

Authors:: Andrzej Marciniak, Malgorzata A. Jankowska

» View abstract Download PDF-version

Important notes

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

1 Introduction

Using computers and approximate methods to solve problems described in the form of ordinary differential equations, we usually provide all calculations in floating-point arithmetic. This arithmetic causes two kinds of errors: representation errors (most real numbers cannot be represented exactly) and rounding errors (differences between the calculated approximations of numbers and their exact mathematical values), which occur during floating-point operations. Using approximate methods, we introduce the third kind of errors—the errors of methods, usually called the truncation errors.

Interval arithmetic (see, e.g., [ 12, 31, 32, 37]) realized in floating-point computer arithmetic is a way to estimate two first kinds of errors. Applying interval methods to approximate the solution of the initial value problem in floating-point interval arithmetic (see, e.g., [ 11]) we can obtain enclosures of the solution in the form of intervals which contain both these errors and also the truncation error.

We can distinguish three main kinds of interval methods for solving the initial value problem: methods based on high-order Taylor series (see, e.g., [ 1, 2, 6, 15, 33, 34]), explicit and implicit methods of Runge-Kutta type ([ 9, 10, 22, 28, 30, 37]), and explicit and implicit multistep methods ([ 9, 17– 19, 22, 25, 26]), including interval predictor-corrector methods [ 27]. In interval methods based on Runge-Kutta and in interval multistep methods considered so far, a constant step size has been used. The methods based on high-order Taylor series use variable step sizes and seem to be the most universal. But it should be noted that in [ 25– 27] and [ 30] we have shown that in some cases the interval methods of the second and third kinds give better enclosures of the exact solutions. Therefore, it is worth to take into account also such methods.

In conventional multistep methods, a problem for changing step size was described firstly by F. Ceschino in [ 4], and developed further, among others, by C. V. D. Forrington [ 8] and F. T. Krogh [ 20]. In these methods by appropriate selection of step size, one can minimize the truncation error, i.e., obtain an approximate solution at some points (mesh points of a grid) with a tolerance given beforehand. Since in interval methods the truncation errors are included in interval enclosures of the exact solutions, the only reason to change a given step size is to decrease the widths of these enclosures. Although we consider only interval methods of Adams-Bashforth type, it seems that the presented procedure can be also applied to other interval multistep methods.

The paper is divided into seven sections. In Section 2, we shortly recall conventional Adams-Bashforth methods with variable step sizes. Interval versions of these methods are proposed in Section 3. Section 4 is the main section of this paper, in which we describe how to match the step size to obtain interval enclosures of the exact solution with a desired width. Since for simplicity in Sections 2– 4 we consider only one-dimensional initial value problem, in Section 5, we announce some remarks on solving systems of differential equations by interval Adams-Bashforth methods using our algorithm. In Section 6, we present some numerical examples, and in the last section, some conclusions are given.

2 Adams-Bashforth methods

Below we present briefly (on the basis of [ 11, p. III.5]) the methods of Adams-Bashforth (explicit multistep methods) ¹ with variable step sizes.

Let us consider the initial value problem ²

$$ y^{\prime}=f\left( t,y\right) ,\quad y\left( 0\right) =y_{0},\quad t\in \left[ 0,a\right]. $$

(1)

Let the set of points { t ₀, t ₁,…, t _k,…, t _m}, such that

$$ 0=t_{0}<t_{1}<{\ldots} <t_{k}<{\ldots} <t_{m}\leq a, $$

be a grid on the interval [0, a] (the points t _i are called the mesh points), and h _i = t _i − t _i− 1 ( i = 1,2,…, m) denote the step sizes. On the interval [ t _k− 1, t _k], the differential equation ( 1) is equivalent to

$$ y\left( t_{k}\right) =y\left( t_{k-1}\right) +\int\limits_{t_{k-1}}^{t_{k}}f\left( \tau ,y\left( \tau \right) \right) d\tau. $$

(2)

The integrand in ( 2) we approximate by the interpolation polynomial P( τ) of degree n − 1 in such a way that

$$ P\left( t_{k-j}\right) =f\left( t_{k-j},y\left( t_{k-j}\right) \right) ,\quad j=1,2,{\ldots} ,n. $$

Substituting τ = t _k− 1 + t h _k and using Newton’s interpolation formula, we can write the polynomial P ( τ) in the form

$$ \begin{array}{@{}rcl@{}} P\left( t_{k-1}+th_{k}\right) &=& f\left( t_{k-1},y\left( t_{k-1}\right) \right) +\left( t-t_{k-1}\right) \left[ t_{k-1},t_{k-2};f\right]\\ &&+\left( t-t_{k-1}\right) \left( t-t_{k-2}\right) \left[ t_{k-1},t_{k-2},t_{k-3};f\right]\\ &&+{\ldots} +\left( t-t_{k-1}\right) \left( t-t_{k-2}\right) {\cdots} \left( t-t_{k-n+1}\right) \left[ t_{k-1},t_{k-2},{\ldots} ,t_{k-n};f\right]\\ &=&\sum\limits_{j=0}^{n-1}\left[ t_{k-1},t_{k-2},{\ldots} ,t_{k-j-1};f\right] \prod\limits_{i=0}^{j-1}\left( t-t_{k-i-1}\right), \end{array} $$

where [ t _k− 1, t _k− 2,…, t _k−j− 1; f] denote the divided differences given by

$$ \begin{array}{@{}rcl@{}} \left[ t_{k-1},t_{k-2},{\ldots} ,t_{k-j-1};f\right] &=&\sum\limits_{i=k-1}^{k-j-1}\frac{f\left( t_{i},y\left( t_{i}\right) \right)}{\underset{l\neq i}{\prod\limits_{l=k-1}^{k-j-1}}\left( t_{i}-t_{l}\right) },\\ j &=& 1,2,{\ldots} ,n-1, \end{array} $$

(3)

which may be defined recursively by

$$ \begin{array}{@{}rcl@{}} &&{}\left[ t_{k-1};f\right] = f\left( t_{k-1},y\left( t_{k-1}\right) \right), \\ \left[ t_{k-1},t_{k-2},{\ldots} ,t_{k-j-1};f\right] &=& \frac{\left[ t_{k-1},t_{k-2},{\ldots} ,t_{k-j};f\right] -\left[ t_{k-2},t_{k-3},\ldots ,t_{k-j-1};f\right] }{t_{k-1}-t_{k-j-1}}, \\ &&{\kern4pt}j = 1,2,{\ldots} ,n-1. \end{array} $$

Let us denote

$$ \begin{array}{@{}rcl@{}} &&{\kern4.5pc}\varphi_{0}\left( k\right) = f\left( t_{k-1},y\left( t_{k-1}\right) \right), \\ &&\varphi_{j}\left( k\right) = \left[ t_{k-1},t_{k-2},{\ldots} ,t_{k-j-1};f \right] \prod\limits_{i=0}^{j-1}\left( t_{k}-t_{k-i-1}\right), \end{array} $$

(4)

$$ \begin{array}{@{}rcl@{}} &&{\kern4.6pc}g_{0}\left( k\right) = 1,\\ &&g_{j}\left( k\right) = \frac{1}{h_{k}}\int\limits_{t_{k-1}}^{t_{k}}\prod \limits_{i=0}^{j-1}\frac{t-t_{k-i-1}}{t_{k}-t_{k-i-1}}dt. \end{array} $$

(5)

Then, the formula ( 2) may be written as

$$ y\left( t_{k}\right) =y\left( t_{k-1}\right) +h_{k}\sum\limits_{j=0}^{n-1}g_{j}\left( k\right) \varphi_{j}\left( k\right) +\int\limits_{t_{k-1}}^{t_{k}}r_{n}\left( \tau \right) d\tau , $$

(6)

where r _n ( τ) denotes the interpolation error, and the integral over this error is the local truncation error. We have (see, e.g., [ 14, 35])

$$ \begin{array}{@{}rcl@{}} \int\limits_{t_{k-1}}^{t_{k}}r_{n}\left( \tau \right) d\tau &=&\frac{ y^{\left( n+1\right) }\left( \xi \right) }{n!}\int\limits_{t_{k-1}}^{t_{k}} \prod\limits_{i=1}^{n}\left( \tau -t_{k-i}\right) d\tau \\ &=&\frac{y^{\left( n+1\right) }\left( \xi \right) }{n!}h_{k}^{n+1}\int \limits_{0}^{_{1}}t\prod\limits_{i=2}^{n}\left( t+\frac{t_{k-1}-t_{k-i}}{ h_{k}}\right) dt, \end{array} $$

where ξ ∈ [ t _k−n, t _k] and y ^(n+ 1) ( ξ) = f ⁽ⁿ⁾ ( ξ, y ( ξ)). Thus, the formula ( 6) may be written in the form

$$ y\left( t_{k}\right) =y\left( t_{k-1}\right) +h_{k}\sum\limits_{j=0}^{n-1}g_{j}\left( k\right) \varphi_{j}\left( k\right) +h_{k}^{n+1}g_{n}\left( k\right) f^{\left( n\right) }\left( \xi ,y\left( \xi \right) \right), $$

(7)

where the values φ _j ( k) and g _j ( k) for j = 0,1,…, n − 1 are given by ( 4) and ( 5), respectively, and

$$ g_{n}\left( k\right) =\frac{1}{n!}\int\limits_{0}^{_{1}}t\prod\limits_{i=2}^{n}\left( t+\frac{t_{k-1}-t_{k-i}}{h_{k}}\right) dt. $$

(8)

The values φ _j ( k) and g _j ( k) for j = 0,1,…, n − 1 can be computed efficiently with recurrence relations [ 11, 13]. As an immediate consequence of ( 3), we have

$$ \begin{array}{@{}rcl@{}} &&{\kern15pt}\varphi_{0}\left( k\right) = \overline{\varphi }_{0}\left( k\right) =f\left( t_{k-1},y\left( t_{k-1}\right) \right), \\ &&{\kern1.6pc}\overline{\varphi }_{j}\left( k\right) = \overline{\varphi }_{j-1}\left( k\right) -\varphi_{j-1}\left( k-1\right), \\ &&\varphi_{j}\left( k\right) = \beta_{j}\left( k\right) \overline{\varphi } _{j}\left( k\right) ,\quad j=1,2,{\ldots} ,n-1, \end{array} $$

where the coefficients

$$ \beta_{j}\left( k\right) =\prod\limits_{i=0}^{j-1}\frac{t_{k}-t_{k-i-1}}{ t_{k-1}-t_{k-i-2}} $$

can be calculated by

$$ \begin{array}{@{}rcl@{}} &\beta_{0}\left( k\right) = 1, \\ &\beta_{j}\left( k\right) = \beta_{j-1}\left( k\right) \frac{t_{k}-t_{k-j} }{t_{k-1}-t_{k-j-1}},\quad j=1,2,{\ldots} ,n-1. \end{array} $$

The calculation of the coefficients g _j ( k) is more tricky [ 13, 21]. We introduce the q-fold integral

$$ c_{jq}\left( t\right) =\frac{\left( q-1\right) !}{{h_{k}^{q}}} \int\limits_{t_{k-1}}^{t}\int\limits_{t_{k-1}}^{\zeta_{q-1}}\ldots \int\limits_{t_{k-1}}^{\zeta_{1}}\prod\limits_{i=0}^{j-1}\frac{\xi_{0}-t_{k-i-1}}{t_{k}-t_{k-i-1}}d\xi_{0}d\xi_{1}{\ldots} d\xi_{q-1}. $$

It appears that

$$ g_{j}\left( k\right) =c_{j1}\left( t_{k}\right) ,\quad j=1,2,{\ldots} ,n-1, $$

where for the quantities c _jq ( t _k) we have the following recurrence relations:

$$ \begin{array}{@{}rcl@{}} &&{\kern1.8pc}c_{0q}\left( t_{k}\right) = \frac{1}{q},\quad c_{1q}\left( t_{k}\right) = \frac{1}{q\left( q+1\right) }, \\ &&c_{jq}\left( t_{k}\right) = c_{j-1,q}\left( t_{k}\right) -c_{j-1,q+1}\left( t_{k}\right) \frac{h_{k}}{t_{k}-t_{k-j}}. \end{array} $$

If the approximations

$$ y_{k-1},y_{k-2},{\ldots} ,y_{k-n} $$

of the exact values

$$ y\left( t_{k-1}\right) ,y\left( t_{k-2}\right) ,{\ldots} ,y\left( t_{k-n}\right) $$

are known, we denote f _i = f ( t _i, y _i) for i = k − n, k − n + 1,…, k − 1, and in the formula ( 7) we omit the truncation error, then we obtain the Adams-Bashforth methods with variable step sizes given by

$$ y_{k}=y_{k-1}+h_{k}\sum\limits_{j=0}^{n-1}g_{j}\left( k\right) \varphi_{j}\left( k\right). $$

(9)

In particular, from ( 9) we get:

n = 1

$$ y_{k}=y_{k-1}+h_{k}f_{k-1}, $$

(10)
n = 2

$$ y_{k}=y_{k-1}+h_{k}\gamma_{2k}, $$

(11)

where

$$ \gamma_{2k}=f_{k-1}+\frac{1}{2}\frac{h_{k}}{h_{k-1}}\left( f_{k-1}-f_{k-2}\right) , $$
n = 3

$$ y_{k}=y_{k-1}+h_{k}\gamma_{3k}, $$

(12)

where

$$ \begin{array}{@{}rcl@{}} \gamma_{3k} &=&\gamma_{2k}+\frac{1}{2}\left( 1-\frac{1}{3}\frac{h_{k}}{ h_{k}+h_{k-1}}\right) \frac{h_{k}}{h_{k-1}}\frac{h_{k}+h_{k-1}}{ h_{k-1}+h_{k-2}} \\ &&{\kern2.3pc}\times\left[ f_{k-1} -f_{k-2}-\frac{h_{k-1}}{h_{k-2}}\left( f_{k-2}-f_{k-3}\right) \right] , \end{array} $$
n = 4

$$ y_{k}=y_{k-1}+h_{k}\gamma_{4k}, $$

(13)

where

$$ \begin{array}{@{}rcl@{}} \gamma_{4k} &=&\gamma_{3k} \\ &&+\left[ \frac{1}{2}\left( 1 - \frac{1}{3}\frac{h_{k}}{h_{k}+h_{k-1}}\right) - \frac{1}{6}\left( 1-\frac{1}{2}\frac{h_{k}}{h_{k}+h_{k-1}}\right) \frac{h_{k}}{h_{k}+h_{k-1}+h_{k-2}}\right] \\ &&{\kern.6pc}\times \frac{h_{k}}{h_{k-1}}\frac{h_{k}+h_{k-1}}{h_{k-1}+h_{k-2}}\frac{ h_{k}+h_{k-1}+h_{k-2}}{h_{k-1}+h_{k-2}+h_{k-3}} \\ &&{\kern.6pc}\times \left\{ f_{k-1}-f_{k-2}-\frac{h_{k-1}}{h_{k-2}}\left( f_{k-2}-f_{k-3}\right) \right. \\ &&{\kern1.5pc}\left. -\frac{h_{k-1}}{h_{k-2}}\frac{h_{k-1}+h_{k-2}}{h_{k-2}+h_{k-3}} \left[ f_{k-2}-f_{k-3}-\frac{h_{k-2}}{h_{k-3}}\left( f_{k-3}-f_{k-4}\right) \right] \right\}. \end{array} $$

If for each i = k, k − 1,…, k − n + 1 we have h _i = h (a constant step size), then from the above formulas we obtain the following well-known conventional Adams-Bashforth methods (see, e.g., [ 3, 5, 11, 16, 38]):

n = 1 (Euler’s method)

$$ y_{k}=y_{k-1}+hf_{k-1}, $$
n = 2

$$ y_{k}=y_{k-1}+\frac{h}{2}\left( 3f_{k-1}-f_{k-2}\right) , $$
n = 3

$$ y_{k}=y_{k-1}+\frac{h}{12}\left( 23f_{k-1}-16f_{k-2}+5f_{k-3}\right) , $$
n = 4

$$ y_{k}=y_{k-1}+\frac{h}{24}\left( 55f_{k-1}-59f_{k-2}+37f_{k-3}-9f_{k-4}\right) . $$

3 Interval versions of Adams-Bashforth methods with variable step sizes

Let us denote:

Δ _t and Δ _y—bounded sets in which the function f ( t, y), occurring in ( 1), is defined, i.e.,

$$ {\Delta}_{t}=\left\{ t\in \mathbb{R}:0\leq t\leq a\right\},\quad {\Delta}_{y}=\left\{ y \in \mathbb{R}:\underline{b}\leq y\leq \overline{b},\right\}, $$
F ( T, Y)—an interval extension of f( t, y), where an interval extension of the function

$$ f:\mathbb{R}\times \mathbb{R}\supset {\Delta}_{t}\times {\Delta}_{y}\rightarrow \mathbb{R} $$

we call a function

$$ F:\mathbb{I}\mathbb{R}\times \mathbb{I}\mathbb{R}\supset \mathbb{I}{\Delta}_{t}\times \mathbb{I}{\Delta}_{y}\rightarrow \mathbb{I}\mathbb{R} $$

such that

$$ \left( t,y\right) \in \left( T,Y\right) \Rightarrow f\left( t,y\right) \in F\left( T,Y\right), $$

where $\mathbb {I}\mathbb {R}$ denotes the space of real intervals.
Ψ ( T, Y)—an interval extension of f ⁽ⁿ⁾ ( t, y ( t)) ≡ y ^(n+ 1) ( t),

and let us assume that:

the function F ( T, Y) is defined and continuous ³ for all T ⊂Δ _t and Y ⊂Δ _y,
the function F ( T, Y) is monotonic with respect to inclusion, i.e.,

$$ T_{1}\subset T_{2}\wedge Y_{1}\subset Y_{2}\Rightarrow F\left( T_{1},Y_{1}\right) \subset F\left( T_{2},Y_{2}\right), $$
for each T ⊂Δ _t and for each Y ⊂Δ _y, there exists a constant Λ > 0 such that

$$ w\left( F\left( T,Y\right) \right) \leq {\Lambda} \left( w\left( T\right) +w\left( Y\right) \right) , $$

where w ( A) denotes the width of the interval A,
the function Ψ ( T, Y) is defined for all T ⊂Δ _t and Y ⊂Δ _y,
the function Ψ ( T, Y) is monotonic with respect to inclusion.

Moreover, let us assume that y (0) ∈ Y ₀ and the intervals Y _k such that y ( t _k) ∈ Y _k for k = 1,2,…, n − 1 are known. We can obtain such Y _k by applying an interval one-step method, for example, an interval method of Runge-Kutta type (see, e.g., [ 9, 10, 22, 28, 30, 37]).

The interval methods of Adams-Bashforth type with variable step sizes we define as follows (compare ( 7)):

$$ \begin{array}{@{}rcl@{}} &{\kern-13.3pc}Y_{k} = Y_{k-1}+h_{k}\sum\limits_{j=0}^{n-1}g_{j}\left( k\right) {\Phi}_{j}\left( k\right) \\ &{\kern1.3pc}+h_{k}^{n+1}g_{n}\left( k\right) {\Psi} \left( T_{k-1}+\left[ -h_{k-n+1}-h_{k-n+2}-{\ldots} -h_{k-1},h_{k}\right] ,\right. \\ &{\kern6.6pc}Y_{k-1}+\left[ -h_{k-n+1}-h_{k-n+2}-{\ldots} -h_{k-1},h_{k}\right] \\ &{\kern.6pc}\left. \times F\left( {\Delta}_{t},{\Delta}_{y}\right) \right), \\ &{\kern-4.1pc}k = n,n+1,{\ldots} ,m, \end{array} $$

(14)

where g _j ( k) for j = 1,2,…, n − 1 is given by ( 5), g _n ( k)—by ( 8),

$$ \begin{array}{@{}rcl@{}} &{\Phi}_{0}(k) = F_{k-1},\\ &{\Phi}_{j}\left( k\right) = \left[ t_{k-1},t_{k-2},{\ldots} ,t_{k-j-1};F\right] \prod\limits_{i=0}^{j-1}\left( t_{k}-t_{k-i-1}\right), \\ &\left[ t_{k-1},t_{k-2},{\ldots} ,t_{k-j-1};F\right] = \sum\limits_{i=k-1}^{k-j-1}\frac{F_{i}}{\underset{l\neq i}{\prod\limits_{l=k-1}^{k-j-1}}\left( t_{i}-t_{l}\right) }, \\ &{\kern1.3pc}j = 1,2,{\ldots} ,n-1, \end{array} $$

(15)

and F _i = F ( T _i, Y _i) for i = k − n, k − n + 1,…, k − 1.

In particular, for a given n, we get the following methods (compare ( 10)–( 13)):

n = 1

$$ \begin{array}{@{}rcl@{}} Y_{k}&=&Y_{k-1}+h_{k}F_{k-1}\\ &&+\frac{{h_{k}^{2}}}{2}{\Psi} \left( T_{k-1}+\left[0,h_{k}\right] ,Y_{k-1}+\left[ 0,h_{k}\right] F\left( {\Delta}_{t},{\Delta}_{y}\right) \right), \end{array} $$

(16)
n = 2

$$ \begin{array}{@{}rcl@{}} &&Y_{k} = Y_{k-1}+h_{k}{\Gamma}_{2k}\\ &&{\kern1.7pc}+{h_{k}^{3}}g_{2}\left( k\right) {\Psi} \left( T_{k-1}+\left[ -h_{k-1},h_{k} \right] ,\right. \\ &&{\kern6.5pc}\left. Y_{k-1}+\left[ -h_{k-1},h_{k}\right] F\left( {\Delta}_{t},{\Delta}_{y}\right) \right), \end{array} $$

(17)

where

$$ \begin{array}{@{}rcl@{}} &{\Gamma}_{2k} = F_{k-1}+\frac{1}{2}\frac{h_{k}}{h_{k-1}}\left( F_{k-1}-F_{k-2}\right), \\ &{\kern-.1pc}g_{2}\left( k\right) = \frac{1}{2}\left( \frac{1}{3}+\frac{1}{2}\frac{ h_{k-1}}{h_{k}}\right), \end{array} $$
n = 3

$$ \begin{array}{@{}rcl@{}} Y_{k} &=& Y_{k-1}+h_{k}{\Gamma}_{3k} \\ &&+{h_{k}^{4}}g_{3}\left( k\right) {\Psi} \left( T_{k-1}+\left[ -h_{k-2}-h_{k-1},h_{k}\right] ,\right. \\ &&{\kern4.5pc}\left. Y_{k-1}+\left[ -h_{k-2}-h_{k-1},h_{k}\right] F\left( {\Delta}_{t},{\Delta}_{y}\right) \right), \end{array} $$

(18)

where

$$ \begin{array}{@{}rcl@{}} {\Gamma}_{3k} &=& {\Gamma}_{2k} \\ &&+\frac{1}{2}\left( 1-\frac{1}{3}\frac{h_{k}}{h_{k}+h_{k-1}}\right) \frac{ h_{k}}{h_{k-1}}\frac{h_{k}+h_{k-1}}{h_{k-1}+h_{k-2}} \\ &&{\kern.3pc}\times\left[ F_{k-1} -F_{k-2}-\frac{h_{k-1}}{h_{k-2}}\left( F_{k-2}-F_{k-3}\right)\right], \end{array} $$

$$ g_{3}\left( k\right) =\frac{1}{6}\left( \frac{1}{4}+\frac{1}{3}\frac{ 2h_{k-1}+h_{k-2}}{h_{k}}+\frac{1}{2}\frac{h_{k-1}}{h_{k}}\frac{ h_{k-1}+h_{k-2}}{h_{k}}\right) , $$
n = 4

$$ \begin{array}{@{}rcl@{}} Y_{k} &=& Y_{k-1}+h_{k}{\Gamma}_{4k} \\ &&+{h_{k}^{5}}g_{4}\left( k\right) {\Psi} \left( T_{k-1}+\left[ -h_{k-3}-h_{k-2}-h_{k-1},h_{k}\right] ,\right. \\ &&{\kern4.5pc}\left. Y_{k-1}+\left[ -h_{k-3}-h_{k-2}-h_{k-1},h_{k}\right] F\left( {\Delta}_{t},{\Delta}_{y}\right) \right), \end{array} $$

(19)

where

$$ \begin{array}{@{}rcl@{}} {\Gamma}_{4k} &=& {\Gamma}_{3k}\\ &&+\left[ \frac{1}{2}\left( 1-\frac{1}{3}\frac{h_{k}}{h_{k}+h_{k-1}}\right) - \frac{1}{6}\left( 1 - \frac{1}{2}\frac{h_{k}}{h_{k}+h_{k-1}}\right) \frac{h_{k}}{h_{k}+h_{k-1}+h_{k-2}}\right] \\ &&{\kern10pt} \times \frac{h_{k}}{h_{k-1}}\frac{h_{k}+h_{k-1}}{h_{k-1}+h_{k-2}}\frac{ h_{k}+h_{k-1}+h_{k-2}}{h_{k-1}+h_{k-2}+h_{k-3}} \\ &&{\kern10pt} \times \left\{ F_{k-1}-F_{k-2}-\frac{h_{k-1}}{h_{k-2}}\left( F_{k-2}-Ff_{k-3}\right) \right. \\ &&{\kern1.7pc}\left. -\frac{h_{k-1}}{h_{k-2}}\frac{h_{k-1}+h_{k-2}}{h_{k-2}+h_{k-3}} \left[ F_{k-2}-F_{k-3}-\frac{h_{k-2}}{h_{k-3}}\left( F_{k-3}-F_{k-4}\right) \right] \right\}, \end{array} $$

$$ \begin{array}{@{}rcl@{}} g_{4}\left( k\right) &=& \frac{1}{24}\left( \frac{1}{5}+\frac{1}{4}\frac{3h_{k-1}+2h_{k-2}+h_{k-3}}{h_{k}}\right.\\ &&{\kern16pt}+\frac{1}{3}\frac{h_{k-1}}{h_{k}}\frac{3h_{k-1}+4h_{k-2}+2h_{k-3}}{h_{k}}+ \frac{1}{3}\frac{h_{k-2}}{h_{k}}\frac{h_{k-2}+h_{k-3}}{h_{k}} \\ &&{\kern16pt}+\left. \frac{1}{2}\frac{h_{k-1}}{h_{k}}\frac{h_{k-1}+h_{k-2}}{h_{k}}\frac{ h_{k-1}+h_{k-2}+h_{k-3}}{h_{k}}\right). \end{array} $$

For the methods ( 14), we can prove that the exact solution of the initial value problem ( 1) belongs to the intervals (enclosures) obtained by these methods. Before that, it is convenient to present the following

Lemma

If ( t _i, y ( t _i)) ∈ ( T _i, Y _i) for i = k − n, k − n + 1,…, k − 1 , where Y _i = Y ( t _i) , then for any j = 0,1,…, n − 1 we have

$$ \varphi_{j}\left( k\right) \in {\Phi}_{j}\left( k\right). $$

(20)

Proof

Since F ( T, Y) is an interval extension of f ( t, y) and ( t _i, y ( t _i)) ∈ ( T _i, Y _i) for i = k − n, k − n + 1,…, k − 1, we can write

$$ f\left( t_{k-1-l},y\left( t_{k-1-l}\right) \right) \in F\left( T_{k-1-l},Y_{k-1-l}\right) ,\quad l=0,1,{\ldots} ,j. $$

This implies that

$$ \sum\limits_{i=k-1}^{k-j-1}\frac{f\left( t_{i},y\left( t_{i}\right) \right)}{\underset{l\neq i}{\prod\limits_{l=k-1}^{k-j-1}}\left( t_{i}-t_{l}\right)}\in \sum\limits_{i=k-1}^{k-j-1}\frac{F_{i}}{\underset{l\neq i}{\prod\limits_{l=k-1}^{k-j-1}}\left( t_{i}-t_{l}\right)}. $$

(21)

From ( 15) and ( 21), the relation ( 20) follows immediately. □

Theorem 1

If y (0) ∈ Y ₀ and y ( t _i) ∈ Y _i for i = 1,2,…, n − 1 , then for the exact solution y( t) of the initial value problem ( 1) we have

$$ y\left( t_{k}\right) \in Y_{k} $$

(22)

for k = n, n + 1,…, m, where Y _k = Y ( t _k) are obtained from the methods ( 14).

Proof

Let us consider the formula ( 7) for k = n. We have

$$ y\left( t_{n}\right) =y\left( t_{n-1}\right) +h_{n}\sum\limits_{j=0}^{n-1}g_{j}\left( n\right) \varphi_{j}\left( n\right) + h_{n}^{n+1}g_{n}\left( n\right) f^{\left( n\right) }\left( \xi ,y\left( \xi \right) \right), $$

(23)

where ξ ∈ [ t ₀, t _n]. From the assumption we get y ( t _n− 1) ∈ Y _n− 1, and from the Lemma it follows that

$$ h_{n}\sum\limits_{j=0}^{n-1}g_{j}\left( n\right) \varphi_{j}\left( n\right) \in h_{n}\sum\limits_{j=0}^{n-1}g_{j}\left( n\right) {\Phi}_{j}\left( n\right). $$

Applying Taylor’s formula, we get

$$ y\left( \xi \right) = y\left( t_{n-1}\right) +\left( \xi -t_{m-1}\right) y^{\prime }\left( t_{n-1}+\vartheta \left( \xi -t_{n-1}\right) \right), $$

(24)

where 𝜗 ∈ [0,1]. Due to ξ ∈ [ t ₀, t _n] and t _i = h ₁ + h ₂ + … + h _i for i = 1,2,…, m ( t ₀ = 0), we have

$$ \xi -t_{n-1}\in \left[ -h_{1}-h_{2}-{\ldots} -h_{n-1},h_{n}\right]. $$

(25)

Moreover, y ^′( t) = f ( t, y ( t)). Since

$$ f\left[ t_{n-1}+\vartheta \left( \xi -t_{n-1}\right) ,y\left( t_{n-1}+\vartheta \left( \xi -t_{n-1}\right) \right) \right] \in F\left( {\Delta}_{t},{\Delta}_{y}\right), $$

then

$$ y^{\prime }\left( t_{n-1}+\vartheta \left( \xi -t_{n-1}\right) \right) \in F\left( {\Delta}_{t},{\Delta}_{y}\right). $$

Taking into account the above considerations, from ( 24), we get

$$ y\left( \xi \right) \in Y_{n-1}+\left[ -h_{1}-h_{2}-{\ldots} -h_{n-1},h_{n} \right] F\left( {\Delta}_{t},{\Delta}_{y}\right). $$

(26)

As we assumed, Ψ is an interval extension of f ⁽ⁿ⁾ ( t, y). Hence, applying ( 25) and ( 26), we have

$$ \begin{array}{@{}rcl@{}} &&h_{n}^{n+1}g_{n}\left( n\right) f^{\left( n\right) }\left( \xi ,y\left( \xi \right) \right) \\ &&{\kern3.2pc}\in h_{n}^{n+1}g_{n}\left( n\right) {\Psi} \left( T_{n-1}+ \left[ -h_{1}-h_{2}-{\ldots} -h_{n-1},h_{n}\right] ,\right. \\ &&{\kern8.7pc}\left. Y_{n-1}+\left[ -h_{1}-h_{2}-{\ldots} -h_{n-1},h_{n}\right] \right) F\left( {\Delta}_{t},{\Delta}_{y}\right). \end{array} $$

Thus, we have shown that y ( t _n) belongs to the interval

$$ \begin{array}{@{}rcl@{}} Y_{n-1}&+&h_{n}\sum\limits_{j=0}^{n-1}g_{j}\left( n\right) {\Phi}_{j}\left( n\right) \\ &+&h_{n}^{n+1}g_{n}\left( n\right) {\Psi} \left( T_{n-1}+\left[ -h_{1}-h_{2}-{\ldots} -h_{n-1},h_{n}\right] ,\right. \\ &&{\kern4.5pc}\left. Y_{n-1}+\left[ -h_{1}-h_{2}-{\ldots} -h_{n-1},h_{n}\right] \right) F\left( {\Delta}_{t},{\Delta}_{y}\right), \end{array} $$

but—according to ( 14)—this is the interval Y _n. This conclusion ends the proof for k = n. In a similar way we can show the thesis of this theorem for k = n + 1, n + 2,…, m. □

Theorem 2

If the intervals Y _k for k = 0,1,…, n − 1 are known, t _i = h ₁ + h ₂ + … + h _i ∈ T _i , i = 1,2,…, m ( t ₀ = 0 ∈ T ₀ = [0,0]) , and the intervals Y _k for k = n, n + 1,…, m are obtained from ( 14) , then

$$ w\left( Y_{k}\right) \leq A\max_{q=0,1,{\ldots} ,n-1}w\left( Y_{q}\right) +B\max_{j=1,2,{\ldots} ,m-1}w\left( T_{j}\right) +Ch^{n}, $$

(27)

where

$$ h=\max_{k=n,n+1,{\ldots} ,m}h_{k}, $$

(28)

and the constants A, B, and C are independent of h.

Proof

Because of g _j ( k) > 0 for j = 0,1,…, n − 1 (see ( 5)) and g _n ( k) > 0 (see ( 8)), from ( 14), we get

$$ \begin{array}{@{}rcl@{}} &&w\left( Y_{k}\right) \leq w\left( Y_{k-1}\right) +h_{k}\sum\limits_{j=0}^{n-1}g_{j}\left( k\right) w\left( {\Phi}_{j}\left( k\right) \right) \\ &&{\kern2.4pc}+h_{k}^{n+1}g_{n}\left( k\right) \\ &&{\kern2.4pc}\times w\left( {\Psi} \left( T_{k-1}+\left[ -h_{k-n+1}-h_{k-n+2}-{\ldots} -h_{k-1},h_{k}\right] ,\right. \right. \\ &&{\kern3.3pc}\left. Y_{k-1}+\left[ -h_{k-n+1}-h_{k-n+2}-{\ldots} -h_{k-1},h_{k} \right] \right) \\ &&{\kern6pc}\times \left. \left. F\left( {\Delta}_{t},{\Delta}_{y}\right) \right) \right). \end{array} $$

(29)

We assumed that Ψ is monotonic with respect to inclusion. Moreover, if step sizes h _k−j for j = 0,1,…, n − 1 are such that satisfy the conditions

$$ \begin{array}{@{}rcl@{}} &&T_{k-1}+\left[ -h_{k-n+1}-h_{k-n+2}-{\ldots} -h_{k-1},h_{k}\right] \subset {\Delta}_{t}, \\ &&Y_{k-1}+\left[ -h_{k-n+1}-h_{k-n+2}-{\ldots} -h_{k-1},h_{k}\right] F\left( {\Delta}_{t},{\Delta}_{y}\right) \subset {\Delta}_{y}, \end{array} $$

then

$$ \begin{array}{@{}rcl@{}} &&{\Psi} \left( T_{k-1}+\left[ -h_{k-n+1}-h_{k-n+2}-{\ldots} -h_{k-1},h_{k}\right] ,\right. \\ &&{\kern.6pc}\left. Y_{k-1}+\left[ -h_{k-n+1}-h_{k-n+2}-{\ldots} -h_{k-1},h_{k}\right] F\left( {\Delta}_{t},{\Delta}_{y}\right) \right) \subset {\Psi}\left( {\Delta}_{t},{\Delta}_{y}\right). \end{array} $$

From the above inclusion, it follows that

$$ \begin{array}{@{}rcl@{}} &&w\left( {\Psi} \left( T_{k-1}+\left[ -h_{k-n+1}-h_{k-n+2}-{\ldots} -h_{k-1},h_{k} \right] ,\right. \right. \\ &&{\kern2.2pc}Y_{k-1}+\left[ -h_{k-n+1}-h_{k-n+2}-{\ldots} -h_{k-1},h_{k} \right] \\ &&{\kern4.3pc}\left. \left. \times F\left( {\Delta}_{t},{\Delta}_{y}\right) \right) \right) \leq w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right). \end{array} $$

(30)

If we denote

$$ \begin{array}{@{}rcl@{}} &&{\kern1.3pc}\alpha_{i0}(k)=1,\quad \alpha_{ij}(k) = \frac{\prod\limits_{l=0}^{j-1}\left( t_{k}-t_{k-l-1}\right)}{\underset{l\neq i}{\prod\limits_{l=k-1}^{k-j-1}}\left( t_{i}-t_{l}\right)},\\ &&i=k-1,k-2,\ldots,k-j-1,\quad j=1,2,{\ldots} n-1, \end{array} $$

then from ( 15) we have

$$ {\Phi}_{j}\left( k\right) =\sum\limits_{i=k-1}^{k-j-1}\alpha_{ij}\left( k\right) F_{i}. $$

(31)

But we also assumed that for the function F there exists a constant Λ > 0 such that

$$ w\left( F_{i}\right) \leq {\Lambda} \left( w\left( T_{i}\right) +w\left( Y_{i}\right) \right). $$

(32)

Therefore, from ( 29)–( 32), we get

$$ \begin{array}{@{}rcl@{}} w\left( Y_{k}\right) &\leq&w\left( Y_{k-1}\right) +h_{k}{\Lambda} \sum\limits_{j=0}^{n-1}g_{j}\left( k\right) \sum\limits_{i=k-1}^{k-j-1}\left\vert \alpha_{ij}\left( k\right) \right\vert \left( w\left( T_{i}\right) +w\left( Y_{i}\right) \right) \\ &&+h_{k}^{n+1}g_{n}\left( k\right) w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right) . \end{array} $$

If we denote

$$ \alpha_{j}\left( k\right) =\max_{i=k-1,k-2,{\ldots} ,k-j-1}\left\vert \alpha_{ij}\left( k\right) \right\vert , $$

then from the above inequality it follows that

$$ \begin{array}{@{}rcl@{}} w\left( Y_{k}\right) &\leq &w\left( Y_{k-1}\right) +h_{k}{\Lambda} \sum\limits_{j=0}^{n-1}g_{j}\left( k\right) \alpha_{j}\left( k\right) \sum\limits_{i=k-1}^{k-j-1}\left( w\left( T_{i}\right) +w\left( Y_{i}\right) \right) \\ &&+h_{k}^{n+1}g_{n}\left( k\right) w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right) , \end{array} $$

and denoting

$$ \rho_{n}\left( k\right) =\max_{j=0,1,{\ldots} ,n-1}\alpha_{j}\left( k\right), $$

(33)

we have

$$ \begin{array}{@{}rcl@{}} &&w\left( Y_{k}\right) \leq w\left( Y_{k-1}\right) +h_{k}{\Lambda} \rho_{n}\left( k\right) \sum\limits_{j=0}^{n-1}\sum\limits_{i=k-1}^{k-j-1}\left( w\left( T_{i}\right) +w\left( Y_{i}\right) \right) \\ &&{\kern3.1pc}+h_{k}^{n+1}g_{n}\left( k\right) w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right). \end{array} $$

(34)

But

$$ \begin{array}{@{}rcl@{}} \sum\limits_{j=0}^{n-1}\sum\limits_{i=k-1}^{k-j-1}\left( w\left( T_{i}\right) + w\left( Y_{i}\right) \right) &=&\sum\limits_{j=1}^{n}\left( n-j+1\right) \left( w\left( T_{k-j}\right) +w\left( Y_{k-j}\right) \right). \end{array} $$

Thus, from ( 34), we get

$$ \begin{array}{@{}rcl@{}} &&w\left( Y_{k}\right) \leq w\left( Y_{k-1}\right) +\sigma_{n}\left( h_{k}\right) \sum\limits_{j=1}^{n}\left( n-j+1\right) w\left( Y_{k-j}\right)\\ &&{\kern3.1pc}{+}\sigma_{n}\left( h_{k}\right) \sum\limits_{j=1}^{n}\left( n-j{+}1\right) w\left( T_{k-j}\right) {+}\sigma_{n}\left( h_{k}\right) w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right) , \end{array} $$

(35)

where

$$ \sigma_{n}\left( h_{k}\right) =h_{k}{\Lambda} \rho_{n}\left( k\right) ,\quad \sigma_{n}\left( h_{k}\right) =h_{k}^{n+1}g_{n}\left( k\right) . $$

(36)

From ( 35) for k = n, we obtain

$$ \begin{array}{@{}rcl@{}} &&w\left( Y_{n}\right) \leq \left[ 1+n\sigma_{n}\left( h_{n}\right) \right] w\left( Y_{n-1}\right) +\sigma_{n}\left( h_{n}\right) \sum\limits_{j=2}^{n}\left( n-j+1\right) w\left( Y_{n-j}\right)\\ &&{\kern3.2pc}+\sigma_{n}\left( h_{n}\right) \sum\limits_{j=1}^{n}\left( n-j+1\right) w\left( T_{n-j}\right) +\sigma_{n}\left( h_{n}\right) w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right) \\ &&{\kern2.2pc}\leq \left[ 1+n\sigma_{n}\left( h_{n}\right) \right] w\left( Y_{n-1}\right) +n\sigma_{n}\left( h_{n}\right) \sum\limits_{j=2}^{n}w\left( Y_{n-j}\right) \\ &&{\kern3.2pc}+n\sigma_{n}\left( h_{n}\right) \sum\limits_{j=1}^{n}w\left( T_{n-j}\right) +\sigma_{n}\left( h_{n}\right) w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right) \\ &&{\kern2.2pc}\leq \left[ 1+n\sigma_{n}\left( h_{n}\right) \right] \sum\limits_{j=1}^{n}w\left( Y_{n-j}\right) +n\sigma_{n}\left( h_{n}\right) \sum\limits_{j=1}^{n}w\left( T_{n-j}\right) \\ &&{\kern3.2pc}+\sigma_{n}\left( h_{n}\right) w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right), \end{array} $$

(37)

and using mathematical induction, one can prove that for each i = 1,2,…, m − 1 we have

$$ w\left( Y_{n+i}\right) \leq P_{ni}\sum\limits_{j=1}^{n}w\left( Y_{n-j}\right) +Q_{ni}\sum\limits_{j=1}^{n+i}w\left( T_{n+i-j}\right) +R_{ni}w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right) , $$

(38)

where

$$ \begin{array}{@{}rcl@{}} &&P_{ni} = \left[ 1+n\sigma_{n}\left( h_{n+i}\right) \right] \left( 1+P_{n,i-1}\right),\quad Q_{ni}=\left[ 1+n\sigma_{n}\left( h_{n+i}\right) \right] Q_{n,i-1}+n\sigma_{n}\left( h_{n+i}\right), \\ &&{\kern6.3pc}R_{ni} = \left[ 1+n\sigma_{n}\left( h_{n+i}\right) \right] R_{n,i-1}+\sigma_{n} \left( h_{n+i}\right), \\ &&{\kern3.2pc}P_{n0} = 1+n\sigma_{n}\left( h_{n}\right) ,\quad Q_{n0}=n\sigma_{n}\left( h_{n}\right) ,\quad R_{n0}=\sigma_{n}\left( h_{n}\right). \end{array} $$

It is self-evident that

$$ \sigma_{n}\left( h_{k}\right) \leq \sigma_{n}\left( h\right) =h{\Lambda} \rho_{n},\quad \sigma_{n}\left( h_{k}\right) \leq \sigma_{n}\left( h\right) =h^{n+1}g_{n}, $$

(39)

where

$$ \rho_{n}=\max_{k=n,n+1,{\ldots} ,m}\rho_{n}\left( k\right) ,\quad g_{n}=\max_{k=n,n+1,{\ldots} ,m}g_{n}\left( k\right), $$

and where h is given by ( 28). Hence,

$$ \begin{array}{@{}rcl@{}} P_{ni} &=& \sum\limits_{l=0}^{i}\left[ 1+n\sigma_{n} \left( h\right) \right]^{l+1}\leq \sum\limits_{l=0}^{i}\exp \left[ \left( l+1\right) n\sigma_{n} \left( h\right) \right] \leq \left( i+1\right) \exp \left[ \left( i+1\right) n\sigma_{n} \left( h\right) \right] \\ &&{}\leq \left( m-n+1\right) \exp \left[ \left( m-n+1\right) n\sigma_{n} \left( h\right) \right] \leq m\exp \left[ mn\sigma_{n} \left( h\right) \right] \\ &&{}\leq m\exp \left( m^{2}h{\Lambda} \rho_{n}\right) \leq m\exp \left( m^{2}a {\Lambda} \rho_{n}\right), \end{array} $$

and

$$ \begin{array}{@{}rcl@{}} Q_{ni} &=& \sum\limits_{l=0}^{i}\left[ 1+n\sigma_{n} \left( h\right) \right]^{l}n\sigma_{n} \left( h\right) =n\sigma_{n} \left( h\right) \sum\limits_{l=0}^{i}\left[ 1+n\sigma_{n} \left( h\right) \right]^{l}=\left[ 1+n\sigma_{n} \left( h\right) \right]^{i+1}-1 \\ &&{}\leq \exp \left[ \left( i+1\right) n\sigma_{n} \left( h\right) \right] -1\leq \exp \left[ \left( m-n+1\right) n\sigma_{n} \left( h\right) \right] -1\leq \exp \left[ mn\sigma_{n} \left( h\right) \right] - 1 \\ &&{}\leq \exp \left( m^{2}h{\Lambda} \rho_{n}\right) -1\leq \exp \left( m^{2}a {\Lambda} \rho_{n}\right) - 1, \end{array} $$

$$ \begin{array}{@{}rcl@{}} &&R_{ni} \leq \sum\limits_{l=0}^{i}\left[ 1+n\sigma_{n} \left( h\right) \right]^{l}n\sigma_{n} \left( h\right) =n\sigma_{n} \left( h\right) \sum\limits_{l=0}^{i} \left[ 1+n\sigma_{n} \left( h\right) \right]^{l} \\ &&{\kern1.4pc}=\frac{\sigma_{n} \left( h \right) }{ \rho_{n} \left( h\right) }\left\{ \left[ 1+n\sigma_{n} \left( h\right) \right]^{i+1}-1\right\} \leq h^{n}\frac{g_{n}}{{\Lambda} \rho_{n}}\left[ \exp \left( m^{2}a {\Lambda} \sigma_{n}\right) -1\right]. \end{array} $$

It means that from ( 38), we have

$$ \begin{array}{@{}rcl@{}} &&w\left( Y_{n+i}\right) \leq nm\exp \left( m^{2}a {\Lambda} \rho_{n}\right) \max_{q=0,1,{\ldots} ,n-1}w\left( Y_{q}\right) \\ &&{\kern3.8pc}+\left( n+i\right) \left[ \exp \left( m^{2}a {\Lambda} \rho_{n}\right)-1\right] \max_{j=0,1,{\ldots} ,m-1}w\left( T_{j}\right) \\ &&{\kern3.8pc}+h^{n}\frac{g_{n}}{{\Lambda} \rho_{n}}\left[ \exp \left( m^{2}a {\Lambda} \rho_{n}\right) -1\right] w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right). \end{array} $$

(40)

Since i ≤ m − n, then from ( 40), we finally get

$$ w\left( Y_{n+i}\right) \leq A\max_{q=0,1,{\ldots} ,n-1}w\left( Y_{q}\right) +B\max_{j=0,1,{\ldots} ,m-1}w\left( T_{j}\right) +Ch^{n} $$

(41)

for each i = 1,2,…, m − n, where

$$ \begin{array}{@{}rcl@{}} &&A = m^{2}\exp \left( m^{2}a {\Lambda} \rho_{n}\right) ,\quad B=m\left[ \exp \left( m^{2}a {\Lambda} \rho_{n}\right) -1\right], \\ &&{\kern4.1pc}C = \frac{g_{n}}{{\Lambda} \rho_{n}}\left[ \exp \left( m^{2}a {\Lambda} \rho_{n}\right) -1\right]. \end{array} $$

Since T ₀ = [0,0], i.e., w ( T ₀) = 0, for i = 1,2,…, m − n, the inequality ( 27) follows immediately from ( 41). For i = 0, the relation ( 41) follows directly from ( 37). □

4 Using variable step sizes

In conventional one- and multistep methods, the change of step size is used to obtain approximate solutions with a given tolerance (to decrease the truncation errors). In the case of multistep methods, it is worth to recommend the methods of Adams with variable step size of predictor-corrector type, in which the explicit methods of Adams-Bashforth are predictors and the implicit methods of Adams-Moulton are correctors. A usable algorithm based on these methods has been proposed by F. T. Krogh in [ 21], and appropriate procedures in Fortran programming language to implement this algorithm on computers have been published in the book [ 36] written by L. F. Shampine and M. K. Gordon.

In interval methods, all errors (representation, rounding, and truncation errors) are included in obtained enclosures of solutions. Thus, the only aim to choose an adequate step size is to decrease the width of interval enclosures.

To obtain interval enclosures of Y _k with a width eps giving beforehand, one can consider the inequality ( 27) and compare the right-hand side of it. But this inequality overestimates the width of Y _k, and a better way to do it is to take into consideration the relation ( 35).

Let us assume that the right-hand side ( 34) is equal to eps, i.e.,

$$ \begin{array}{@{}rcl@{}} w\left( Y_{k-1}\right) &+&\sigma_{n}\left( h_{k}\right) \sum\limits_{j=1}^{n}\left( n-j+1\right) w\left( Y_{k-j}\right)\\ &+&\sigma_{n}\left( h_{k}\right) \sum\limits_{j=1}^{n}\left( n-j+1\right) w\left( T_{k-j}\right) \\ &+& \sigma_{n}\left( h_{k}\right) w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right) = eps. \end{array} $$

(42)

Since T _k−j ( j = 1,2,…, n) is only an interval representation of t _k−j, we have w ( T _k−j) ≈ 0. If we assume w ( T _k−j) = 0 and take into account ( 42), then we have

$$ \begin{array}{@{}rcl@{}} &&h_{k}^{n+1}g_{n}\left( k\right) w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right)\\ &&+h_{k}{\Lambda} \rho_{n}\left( k\right) {\sum}_{j=1}^{n}\left( n-j+1\right) w\left( Y_{k-j}\right) +w\left( Y_{k-1}\right) - eps=0. \end{array} $$

(43)

The equation ( 43) presents a polynomial (with respect to h) of degree n + 1. Denoting this polynomial by p _n+ 1 ( h _k), we look for h _k > 0 such that p _n+ 1 ( h _k) = 0. To find such an h _k, one can use any method for finding roots of polynomials. Applying, for example, the Newton iterations we have

$$ h_{k}^{\left( s+1\right) }=h_{k}^{\left( s\right) }-\frac{p_{n+1}\left( h_{k}^{\left( s\right) }\right) }{p_{n+1}^{\prime }\left( h_{k}^{\left( s\right)}\right)},\quad s=0,1,\ldots, $$

(44)

where $h_{k}^{\left (0\right ) }$ is given (we can take $h_{k}^{\left (0\right ) }=h_{k-1}$). The process ( 44) is stopped when

$$ \left\vert h_{k}^{\left( s+1\right) }-h_{k}^{\left( s\right) }\right\vert <\varepsilon , $$

where ε denotes an accuracy given beforehand.

Note that in general, the real h _k > 0, satisfying ( 43), may not exist. Since in ( 43) all coefficients near by any power of h _k are positive, such a case occurs, for instance, when

$$ w\left( Y_{k-1}\right) - eps>0. $$

If this relation holds, we can try to increase eps or simply stop the calculations. Of course, if the widths of successive Y _k increase, then the successive step sizes h _k must decrease (see Example 2 in Section 6). Moreover, if t _m is the last t _k, for which t _k < a, and we want to achieve the end a of integration interval, then for the last integration step we should take h _m+ 1 = a − t _m.

According to the definitions of g _n ( k) and ρ _n ( k) (see ( 8) and ( 33), respectively), it is difficult to write the general form of p _n+ 1 ( h _k). For n ≤ 4, we have the following formulas:

n = 1

$$ p_{2}\left( h_{k}\right) =\frac{{h_{k}^{2}}}{12}w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right) +h_{k}{\Lambda} w\left( Y_{k-1}\right) +w\left( Y_{k-1}\right) -eps=0, $$
n = 2

$$ \begin{array}{@{}rcl@{}} &&p_{3}\left( h_{k}\right) =\frac{{h_{k}^{2}}}{12}\left( 2h_{k}+3h_{k-1}\right) w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right)\\ &&{\kern3.5pc}+{\Lambda} q_{2}\left( h_{k}\right) \left[ 2w\left( Y_{k-1}\right) +w\left( Y_{k-2}\right) \right] +w\left( Y_{k-1}\right) - eps=0, \end{array} $$

where

$$ q_{2}\left( h_{k}\right) =h_{k}\cdot \max \left\{ 1,\frac{h_{k}}{h_{k-1}} \right\} , $$
n = 3

$$ \begin{array}{@{}rcl@{}} p_{4}\left( h_{4}\right) &=&\frac{{h_{k}^{2}}}{72}\left[ 3{h_{k}^{2}}+4h_{k}\left( 2h_{k-1}+h_{k-2}\right) \right. \\ &&{\kern1.2pc}\left. +6h_{k-1}\left( h_{k-1}+h_{k-2}\right) \right] w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right) \\ &&+{\Lambda} q_{3}\left( h_{k}\right) \left[ 3w\left( Y_{k-1}\right) +2w\left( Y_{k-2}\right) +w\left( Y_{k-3}\right) \right] \\ &&+ w\left( Y_{k-1}\right) - eps=0, \end{array} $$

where

$$ q_{3}\left( h_{k}\right) =h_{k}\cdot \max \left\{ 1,\frac{h_{k}}{h_{k-1}}, \frac{h_{k}\left( h_{k}+h_{k-1}\right) }{h_{k-1}h_{k-2}}\right\} , $$
n = 4

$$ \begin{array}{@{}rcl@{}} p_{5}\left( h_{4}\right) &=&\frac{{h_{k}^{2}}}{1440}\left\{ 12{h_{k}^{3}}+15{h_{k}^{2}}\left( 3h_{k-1}+2h_{k-2}+h_{k-3}\right) \right.\\ &&{\kern2pc}+20h_{k}\left[ h_{k-1}\left( h_{k-1}+h_{k-2}\right) \right. \\ &&{\kern4.7pc}\left. +\left( 2h_{k-1}+h_{k-2}\right) \left( h_{k-1}+h_{k-2}+h_{k-3}\right) \right] \\ &&{\kern2pc}\left. +30h_{k-1}\left( h_{k-1}+h_{k-2}\right) \left( h_{k-1}+h_{k-2}+h_{k-3}\right) \right\} \\ &&{\kern2pc}\times w\left( {\Psi} \left( {\Delta}_{t},{\Delta}_{y}\right) \right) \\ &&+{\Lambda} q_{4}\left( h_{4}\right) \left[ 4w\left( Y_{k-1}\right) +3w\left( Y_{k-2}\right) +2w\left( Y_{k-3}\right) +w\left( Y_{k-4}\right) \right] \\ &&+w\left( Y_{k-1}\right) -eps=0, \end{array} $$

where

$$ \begin{array}{@{}rcl@{}} q_{4}\left( h_{k}\right) &=& h_{k}\cdot \max \left\{ 1, \frac{h_{k}}{h_{k-1}}, \frac{h_{k}\left( h_{k}+h_{k-1}\right) }{h_{k-1}h_{k-2}}, \right. \\ &&{\kern3pc}\frac{h_{k}\left( h_{k}+h_{k-1}\right) \left( h_{k}+h_{k-1}+h_{k-2}\right) }{ h_{k-1}h_{k-2}\left( h_{k-2}+h_{k-3}\right) }, \\ &&{\kern2.7pc}\left. \frac{h_{k}\left( h_{k}+h_{k-1}\right) \left( h_{k}+h_{k-1}+h_{k-2}\right) }{\left( h_{k-1}+h_{k-2}\right) h_{k-2}h_{k-3}} \right\}. \end{array} $$

Note that in the case of n > 1, the form of p _n+ 1 ( h _k) depends on which α _j ( k) ( j = 0,1,…, n − 1) is chosen (see ( 33)).

5 A note on a system of differential equations

For simplicity, we have considered only one-dimensional initial value problem. The methods ( 14) and the algorithm presented in Section 4 can be easily extended to systems of ordinary differential equations, i.e., to the initial value problem of the form

$$ \mathbf{y}^{\prime}=\mathbf{f}\left( t,\mathbf{y}\right) ,\quad \mathbf{y} \left( 0\right) =\mathbf{y}_{0},\quad t\in \left[ 0,a\right] , $$

where $\mathbf {y} \in \mathbb {R}^{N}$ and $\mathbf {f}: [0,a] \times \mathbb {R}^{N} \rightarrow \mathbb {R}^{N}$. In this case the formula ( 14) and the relation ( 22) in Theorem 1 should be written for each component of the interval vector Y _k = [ Y _k,(1), Y _k,(2),…, Y _k,(N)] ^T. In the inequality ( 27) and in the proof of Theorem 2, any number w( A) means $\max \limits _{i=1,2,{\ldots } ,N}w\left (A_{i}\right )$ for any vector A = [ A ₍₁₎, A ₍₂₎,…, A _(N)] ^T. The same concerns the equation ( 43) for calculating the step size in k th integration step. An example of two-dimensional problem, for which step size changing is applied, we present in the next section (Example 4).

6 Numerical examples

In the examples presented below, we have used our own implementation of floating-point interval arithmetic in Delphi Pascal. This implementation has been written in the form of a unit called IntervalArithmetic32and64, which current version is presented in [ 23]. This unit take advantage of the Delphi Pascal floating-point Extended type and makes it possible to represent any input numerical data in the form of a machine interval, perform all calculations in floating-point interval arithmetic, use some standard interval functions and give results in the form of proper intervals (if the ends of an interval are not the same machine numbers, one can see the difference in the output). All programs written in Delphi Pascal for the examples presented one can find in [ 24]. We have run these programs on Lenovo ^®; Z51 computer with Intel ^®;Core i7 2.4 GHz processor.

Example 1

At first, let us consider a commonly used test problem

$$ y^{\prime} = 0.5 y, \quad y(0)=1. $$

(45)

with the exact solution

$$ y=\exp(0.5 t). $$

(46)

Let us assume

$$ {\Delta}_{t}=\left\{ t\in \mathbb{R}:0\leq t\leq 2\right\},\quad {\Delta}_{y}=\left\{ y \in \mathbb{R}:1\leq y\leq \overline{2.72}\right\}, $$

where $\overline {x}$ denotes the smallest machine number greater or equal to x (similarly, by $\underline {x}$, we will denote the largest machine number less or equal to x). From ( 46), we obtain the results presented in Table 1. ⁴

Taking m = 20 and h ₁ = 0.08, h ₂ = 0.07, h ₃ = 0.05, h ₄ = 0.09, h ₅ = 0.08, h ₆ = 0.07, h ₇ = 0.10, h ₈ = 0.08, h ₉ = 0.14, h ₁₀ = 0.09, h ₁₁ = 0.15, h ₁₂ = 0.11, h ₁₃ = 0.07, h ₁₄ = 0.10, h ₁₅ = 0.15, h ₁₆ = 0.12, h ₁₇ = 0.08, h ₁₈ = 0.12, h ₁₉ = 0.15, and h ₂₀ = 0.10 by the methods ( 16)–( 19) at t = 2, we get enclosures of the exact solution presented in Table 2. The methods are very fast and for all of them the time of calculations (CPU time) is less then 1 s. Of course, for each method, the exact solution y( t ₂₀) ≈ 2.7182818284590452 is within the interval obtained. It should be added that if we use the interval methods of Adams-Bashforth type for greater n and very small step sizes we can obtain intervals with greater widths then presented in Table 2 (see [ 22, Example 4.5 in Sec. 4.7]). This is caused by a great number of calculations in these methods and by a significant increase of rounding errors following from that, which is not compensated for the method orders.

Table 2

Intervals obtained for the problem ( 45) at $t = 2$ by the methods ( 16)–( 19)

Method	$Y_{k}$	Width	CPU time
			(s)
( 16)	[ 2.7169134040046282E + 0000, 2.7235393714205552E + 0000]	$\approx 6.63 \cdot 10^{-3}$	0.042
( 17)	[ 2.7179091592957537E + 0000, 2.7187125466868537E + 0000]	$\approx 8.03 \cdot 10^{-4}$	0.054
( 18)	[ 2.7182298899088899E + 0000, 2.7183323624455116E + 0000]	$\approx 1.02 \cdot 10^{-4}$	0.055
( 19)	[ 2.7182739085121117E + 0000, 2.7182894852166692E + 0000]	$\approx 1.56 \cdot 10^{-5}$	0.076

Example 2

Again, let us take into account the problem ( 45), but now let us apply the procedure for finding step sizes described in Section 4. For the same starting data as in Example 1, requiring 10 ^− 8 for interval widths and taking Λ = 0.5, ε = 10 ^− 18, $h_{1}^{\left (0\right ) }=0.08$, $h_{2}^{\left (0\right ) }=0.07$, $h_{3}^{\left (0\right ) }=0.05$, and $h_{4}^{\left (0\right ) }=0.09$ as initial approximations of step size for the first integration step for n = 1,2,3 and 4, respectively (for the next steps we have accepted $h_{k}^{\left (0\right ) }=h_{k-1}$), we have obtained (at the first and the last possible to calculate integration steps) the results presented in Table 3. The CPU times have been equal to 36.019 s for the method ( 16), 1.152 s for ( 17), 0.344 s for ( 18), and 0.415 s for the method ( 19). The changes of step sizes are shown in Fig. 1a–d.

Table 3

Intervals obtained for the problem ( 45) at the first and the last calculated integration steps by the methods ( 16)–( 19) with matching step sizes

Method	k	$t_{k}$	$Y_{k}$	Width
( 16)	1	$\approx $ 0.0002	[ 1.0001078385871569E + 0000, 1.0001078385888622E + 0000]	$\approx 1.71 \cdot 10^{-12}$
	15852	$\approx $ 1.5766	[ 2.1996396812768524E + 0000, 2.1996396912768528E + 0000]	$< 1.00 \cdot 10^{-8}$
( 17)	2	$\approx $ 0.0815	[ 1.0415997191016650E + 0000, 1.0415997197462058E + 0000]	$\approx 6.45 \cdot 10^{-10}$
	278	$\approx $ 0.8333	[ 1.5168547254474315E + 0000, 1.5168547354474316E + 0000]	$< 1.00 \cdot 10^{-8}$
( 18)	3	$\approx $ 0.1597	[ 1.0831027071336879E + 0000, 1.0831027083961128E + 0000]	$\approx 1.26 \cdot 10^{-9}$
	76	$\approx $ 0.6178	[ 1.3619093684910934E + 0000, 1.3619093784910935E + 0000]	$< 1.00 \cdot 10^{-8}$
( 19)	4	$\approx $ 0.2529	[ 1.1348046916372604E + 0000, 1.1348046936371020E + 0000]	$\approx 2.00 \cdot 10^{-9}$
	71	$\approx $ 0.6259	[ 1.3674527147839997E + 0000, 1.3674527247839998E + 0000]	$< 1.00 \cdot 10^{-8}$

Let us note that it is not possible to achieve the assumed end t = 2 of integration interval. In each method, the step size is decreased for following integration steps (excluding initial steps in two- and more step methods, where some fluctuations can be caused by initial data), but there exists a point t _m, after which further calculations are impossible. To counteract such a situation, one can increase the required widths of intervals or consider a limitation of integration interval. For instance, if for the problem ( 45) we assume t ≤ 0.6, then—for the same remaining initial data as previously—we obtain results presented in Table 4 (we present only intervals obtained at the last step for which t _m < 0.6 and at the final t = 0.6, where the last step size is equal to 0.6 − t _m). In order to achieved the point t = 0.6, the methods ( 16), ( 17), ( 18), and ( 19) have needed 10.274 s, 0.574 s, 0.138 s, and 0.073 s, respectively. As we could expect, the greater order of method has permitted to obtain results in smaller numbers of integration steps.

Table 4

Intervals obtained for the problem ( 45) with ${\Delta }_{t} = \left \{ t \in \mathbf {R}:0\leq t\leq \overline {0.6} \right \}$ and ${\Delta }_{y} = \left \{ y \in \mathbf {R}:1\leq y\leq \overline {2.72} \right \}$

Method	k	$t_{k}$	$Y_{k}$	Width
( 16)	3190	$\approx $ 0.60000	[ 1.3498581914855010E + 0000, 1.3498581958390336E + 0000]	$\approx 4.35 \cdot 10^{-9}$
	3191	0.60000	[ 1.3498588069670051E + 0000, 1.3498588113205398E + 0000]	$\approx 4.35 \cdot 10^{-9}$
( 17)	135	$\approx $ 0.59891	[ 1.3491258950165315E + 0000, 1.3491259025297920E + 0000]	$\approx 7.51 \cdot 10^{-9}$
	136	0.60000	[ 1.3498588036394939E + 0000, 1.3498588111590695E + 0000]	$\approx 7.52 \cdot 10^{-9}$
( 18)	32	$\approx $ 0.59894	[ 1.3491410173457222E + 0000, 1.3491410270971693E + 0000]	$\approx 9.75 \cdot 10^{-9}$
	33	0.60000	[ 1.3498588016695426E + 0000, 1.3498588114278859E + 0000]	$\approx 9.76 \cdot 10^{-9}$
( 19)	15	$\approx $ 0.59880	[ 1.3490512149587291E + 0000, 1.3490512245357438E + 0000]	$\approx 9.58 \cdot 10^{-9}$
	16	0.60000	[ 1.3498588016932220E + 0000, 1.3498588112774857E + 0000]	$\approx 9.58 \cdot 10^{-9}$

Example 3

For the initial value problem of the form (the problem A5 from [ 7, p. 23])

$$ y^{\prime }=\frac{y-t}{y+t},\quad y\left( 0\right) =4, $$

(47)

the solution is unknown. In [ 7], it is taken a = 20. In our methods, we cannot take this value, because for 0 ≤ t ≤ 20 we have − 1 < y < 6.3 and in the interval extension F (Δ _t,Δ _y) of f ( x, y) for Δ _t = { t ∈ R : 0 ≤ t ≤ 20} and Δ _y = { y ∈ R : − 1 ≤ y ≤ 6.3} we have a division by an interval containing zero (such an operation is not defined in proper interval arithmetic). Thus, we restrict these regions to

$$ {\Delta}_{t}=\left\{ t\in \mathbf{R}:0\leq t\leq 10\right\}, \quad {\Delta}_{y}=\left\{ y\in \mathbf{R}:4\leq y\leq \overline{6.3}\right\}. $$

Let us take the fourth-order method ( 19) with additional starting intervals given in Table 5. These intervals have been obtained by an interval version of conventional Runge-Kutta method (of fourth order) with an optimal step size for the first integration step (see [ 29] for details). For the method ( 19), we also need an interval extension of y ⁽⁵⁾ ( t) = f ⁽⁴⁾ ( t, y). Since for the problem ( 47), we have

Table 5

Starting values for the method ( 19) and the problem ( 47)

k	$t_{k}$	$Y_{k}$
0	0	[ $\underline {4.0000000000000000\mathrm {E}+0000}$, $\overline {4.0000000000000000\mathrm {E}+0000}$]
1	0.081746227283888863	[ $\underline {4.0801194662264153\mathrm {E}+0000}$, $\overline {4.0801194662264155\mathrm {E}+0000}$]
2	0.163492454567777736	[ $\underline {4.1571485011046702\mathrm {E}+0000}$, $\overline {4.1571485011046705\mathrm {E}+0000}$]
3	0.245238681851666599	[ $\underline {4.2313071906453238\mathrm {E}+0000}$, $\overline {4.2313071906453243\mathrm {E}+0000}$]

$$ f^{\left( 4\right) }\left( t,y\right) =\frac{40\left( y^{2}+t^{2}\right) }{ \left( y+t\right)^{9}}\left( 16y^{3}-13y^{2}t+10yt^{2}-3t^{3}\right), $$

this extension can be obtained easily.

Requiring 10 ^− 8 for interval widths, taking Λ = 1, ε = 10 ^− 18, step sizes h ₁ = h ₂ = h ₃ = 0.081746227283888863 and $h_{4}^{\left (0\right ) }=h_{3}$ as the initial approximation of step size for the first integration step, after 2.295 s, we have obtained the results presented in Table 6. Figure 2 shows the step size changes. Note that we are able to execute 464 integration steps and obtain the last interval for t ≈ 1.5476, but step sizes are small (and tend to zero) for t approximately greater than 1.54. If we assume e p s = 10 ^− 12, then we achieve t ≈ 1.3991 (smaller t) after 4.758 s, and for e p s = 10 ^− 4 we can achieve t ≈ 2.0843 (greater t) after 3.333 s (see Tables 7 and 8 for details).

Table 6

Intervals obtained for the problem ( 47) including the last calculated integration step by the method ( 19) with matching step sizes ( e p s = 10 ^− 8)

k	$t_{k}$	$Y_{k}$	Width
50	$\approx $ 0.69774	[ 4.5975465221505685E + 0000, 4.5975465243497029E + 0000]	$\approx 2.20 \cdot 10^{-9}$
100	$\approx $ 1.14965	[ 4.9030146239176995E + 0000, 4.9030146292963836E + 0000]	$\approx 5.38 \cdot 10^{-9}$
150	$\approx $ 1.47461	[ 5.0930266442612574E + 0000, 5.0930266533191654E + 0000]	$\approx 9.06 \cdot 10^{-9}$
200	$\approx $ 1.54340	[ 5.1304617719687623E + 0000, 5.1304617819135613E + 0000]	$\approx 9.94 \cdot 10^{-9}$
250	$\approx $ 1.54735	[ 5.1325793100365724E + 0000, 5.1325793200333748E + 0000]	$< 1.00 \cdot 10^{-8}$
464	$\approx $ 1.54759	[ 5.1327090107108448E + 0000, 5.1327090207108449E + 0000]	$< 1.00 \cdot 10^{-8}$

Table 7

Intervals obtained for the problem ( 47) with $eps = 10^{-12}$

k	$t_{k}$	$Y_{k}$	Width
200	$\approx $ 0.55405	[ 4.4886273748015889E + 0000, 4.4886273748017744E + 0000]	$\approx 1.85 \cdot 10^{-13}$
400	$\approx $ 0.85821	[ 4.7120930249268474E + 0000, 4.7120930249272235E + 0000]	$\approx 3.76 \cdot 10^{-13}$
600	$\approx $ 1.13809	[ 4.8958332122088699E + 0000, 4.8958332122095143E + 0000]	$\approx 6.44 \cdot 10^{-13}$
800	$\approx $ 1.36239	[ 5.0299271956108516E + 0000, 5.0299271956117965E + 0000]	$\approx 9.45 \cdot 10^{-13}$
900	$\approx $ 1.39889	[ 5.0507330026032329E + 0000, 5.0507330026042326E + 0000]	$< 1.00 \cdot 10^{-12}$
955	$\approx $ 1.39915	[ 5.0508805112730600E + 0000, 5.0508805112740601E + 0000]	$< 1.00 \cdot 10^{-12}$

Table 8

Intervals obtained for the problem ( 47) with $eps = 10^{-4}$

k	$t_{k}$	$Y_{k}$	Width
10	$\approx $ 0.67182	[ 4.5783575612188736E + 0000, 4.5783702917087973E + 0000]	$\approx 1.27 \cdot 10^{-5}$
20	$\approx $ 1.22301	[ 4.9478886689807839E + 0000, 4.9479228693528902E + 0000]	$\approx 3.42 \cdot 10^{-5}$
30	$\approx $ 1.62289	[ 5.1725533292643105E + 0000, 5.1726121849592280E + 0000]	$\approx 5.89 \cdot 10^{-5}$
100	$\approx $ 2.07277	[ 5.3895608440740060E + 0000, 5.3896595445228829E + 0000]	$\approx 9.87 \cdot 10^{-5}$
150	$\approx $ 2.08316	[ 5.3941735254856961E + 0000, 5.3942734009330229E + 0000]	$\approx 9.99 \cdot 10^{-5}$
632	$\approx $ 2.08426	[ 5.3946582071369410E + 0000, 5.3947582071369411E + 0000]	$< 1.00 \cdot 10^{-4}$

Example 4

Finally, consider the motion of a simple pendulum described by the equation

$$ \varphi^{\prime \prime }+u^{2}\sin \varphi =0, $$

(48)

where φ = φ ( t), $u=\sqrt {g/L}$, and where g is the gravitational acceleration at the Earth surface and L denotes the pendulum length. If we assume that the angle φ is small, i.e., sin φ ≈ φ, then the equation ( 48) can be reduced to the equation of simple harmonic motion

$$ \varphi^{\prime \prime }+u^{2} \varphi=0 $$

(49)

with the solution φ = φ ₀ cos ( u t), where φ ₀ is an initial angle. Denoting y ₁ = φ ^′, y ₂ = φ and assuming that φ ^′(0) = 0, φ (0) = φ ₀, we can transform ( 49) into the following systems of differential equations of first order:

$$ y_{1}^{\prime }=-u^{2}y_{2},\quad y_{2}^{\prime }=y_{1}, $$

(50)

with initial conditions

$$ y_{1}\left( 0\right) =0,\quad y_{2}\left( 0\right) =\varphi_{0}. $$

(51)

Let us take g = 9.80665, L = 1 and φ ₀ = π/6. Let

$$ \begin{array}{@{}rcl@{}} &&{\Delta}_{t}=\left\{ t\in \mathbb{R}:0\leq t\leq 2\right\} , \\ &&{\Delta}_{y}=\left\{ \left( y_{1},y_{2}\right) \in \mathbb{R}^{2}:\underline{-1.8} \leq y_{1}\leq \overline{1.8}, \underline{-0.6}\leq y_{2}\leq \overline{0.6}\right\} \end{array} $$

and consider the method ( 18). Assuming e p s = 10 ^− 8, taking Λ = 9.80665 π/6, ε = 10 ^− 18, step sizes h ₁ = h ₂ = 0.0001, $h_{3}^{\left (0\right ) }=h_{2}$ as the initial approximation of step size for the first integration step, and starting points given in Table 9, we have obtained the results presented in Table 10. The CPU time has been equal to 0.740 s. The changes of step size are shown in Fig. 3, from which it follows that for t approximately greater than 0.125 the step size is too small (tends to zero) to satisfactory continue the calculations. On the other hand, one can observe that—according to Theorem 1—the exact solution belongs to interval enclosures obtained.

Table 9

Starting values for the method ( 18) and the problem ( 50)–( 51)

k	$t_{k}$	$Y_{s} = Y_{sk}$
0	0	$Y_{1} = $ [ $\underline {0.0000000000000000\mathrm {E}+0000}$, $\hspace {0.2cm}\overline {0.0000000000000000\mathrm {E}+0000}$]
		$Y_{2} =$ [ $\underline {5.2359877559829887\mathrm {E}-0001}$, $\hspace {0.2cm}\overline {5.2359877559829888\mathrm {E}-0001}$]
1	0.0001	$Y_{1} =$ [ $\underline {-5.1347498487965657\mathrm {E}-0004},$ $\overline {-5.1347498487965656\mathrm {E}-0004}$]
		$Y_{2} = $ [ $\underline {5.2359874992454941\mathrm {E}-0001}$, $\hspace {0.2cm}\overline {5.2359874992454942\mathrm {E-}0001}$]
2	0.0002	$Y_{1} = $ $[\underline {-1.0269499194046190\mathrm {E}-0003}$, $\overline {-1.0269499194046189\mathrm {E}-0003}$]
		$Y_{2} = $ [ $\underline {5.2359867290330357\mathrm {E}-0001}$, $\hspace {0.2cm}\overline {5.2359867290330358\mathrm {E}-0001}$]

Table 10

Intervals obtained for the problem ( 50)–( 51) including the last calculated integration step by the method ( 18) with matching step sizes ( e p s = 10 ^− 8)

k	$t_{k}$	$Y_{k}$	Width
20	≈ 0.052266	$Y_{1} = [$− 2.6717739871166114E − 0001,− 2.6717739518323742E − 0001]	$\approx 3.53 \cdot 10^{-9}$
		$Y_{2} = [$ 5.1660096723952543E − 0001, 5.1660096833861906E − 0001]	$\approx 1.10 \cdot 10^{-9}$
40	≈ 0.098329	$Y_{1} = [$− 4.9695523554187293E − 0001,− 4.9695522814330236E − 0001]	$\approx 7.40 \cdot 10^{-9}$
		$Y_{2} = [$ 4.9897124759486593E − 0001, 4.9897124992870939E − 0001]	$\approx 2.33 \cdot 10^{-9}$
60	≈ 0.123971	$Y_{1} = [$− 6.2069000044409622E − 0001,− 6.2068999060901059E − 0001]	$\approx 9.84 \cdot 10^{-9}$
		$Y_{2} = [$ 4.8463438814236487E − 0001, 4.8463439125965848E − 0001]	$\approx 3.12 \cdot 10^{-9}$
80	≈ 0.125890	$Y_{1} = [$− 6.2979775595258544E − 0001,− 6.2979774595297822E − 0001]	$< 1.00 \cdot 10^{-8}$
		$Y_{2} = [$ 4.8343471268438440E − 0001, 4.8343471585460307E − 0001]	$\approx 3.17 \cdot 10^{-9}$
122	≈ 0.125895	$Y_{1} = [$− 6.2982173628611325E − 0001,− 6.2982172628611324E − 0001]	$< 1.00 \cdot 10^{-8}$
		$Y_{2} = [$ 4.8343152696498447E − 0001, 4.8343153013532947E − 0001]	$\approx 3.17 \cdot 10^{-9}$

The examples show that using the procedure for step size changing we can obtain interval enclosures of the exact solution with widths given beforehand for t _max ≤ a. Unfortunately, very often we have t _max << a. Of course, to reach a, we can always use a multistep method with constant step size and theorems similar to the Theorem 1 guarantee that the exact solution will be inside interval enclosures obtained. ⁵ We can also use a combination of methods with variable and constant step sizes. If we assume that the step size h cannot be less than some h _min, we can start calculations using a method which matches step sizes with a width of intervals given beforehand, and when the step size will be decreased to h _min—continue calculations with h = h _min. Of course, such a procedure does not guarantee that at t ≈ a we will obtain intervals with a given width, but it can significantly reduce the number of integration steps.

Some remarks concerning computing time for our methods should be given at the end. First of all, let us note that the Adams-Bashforth methods with step size changes are very fast (usually in the process ( 44), only a few iterations are needed to achieve a desired width eps of interval). Obviously, for a greater n (the number of method steps and the order of method), the computing time is less for a given t ≤ a. Moreover, for decreasing desired widths of intervals, we can observe decreasing values of t _max ≤ a, but computing times may not be decreasing (compare the values of t _max and computing times in Example 3 for e p s = 10 ^− 4,10 ^− 8 and 10 ^− 12). To confirm this observation, let us consider

Example 5

For the same problem as in Example 3 and for the same Δ _t and Δ _y, let us take different values of eps (from 10 ^− 2 to 10 ^− 13) in the method ( 19). In Table 11, we present the number of steps k and CPU times to achieve t _max for each value of eps. These times are also presented in Fig. 4, and we can see that for e p s = 10 ^− 8 the computing time is the smallest. It may be generalized: for each problem considered, there exists the smallest computing time for some eps.

Table 11

CPU times for the method ( 19) and different values of eps

eps	k	$t_{\max }$	CPU time
			(s)
10 ^− 2	842	$\approx $ 2.612638	4.411
10 ^− 3	731	$\approx $ 2.341260	3.751
10 ^− 4	632	$\approx $ 2.084259	3.333
10 ^− 5	557	$\approx $ 1.880208	2.816
10 ^− 6	503	$\approx $ 1.731451	2.502
10 ^− 7	472	$\approx $ 1.624865	2.352
10 ^− 8	464	$\approx $ 1.547588	2.295
10 ^− 9	489	$\approx $ 1.490991	2.433
10 ^− 10	559	$\approx $ 1.450758	2.704
10 ^− 11	705	$\approx $ 1.423210	3.496
10 ^− 12	955	$\approx $ 1.399150	4.758
10 ^− 13	1312	$\approx $ 1.321706	6.575

On the other hand, for some t < T ≤ a, where T denotes the smallest t _max common for different n and eps, the smaller computing times are obtained for greater values of n. For the problem considered, the methods ( 17) ( n = 2), ( 18) ( n = 3), and ( 19) ( n = 4), and t = 1.3 are shown in Fig. 5.

7 Conclusions

Until now, interval multistep methods (explicit and implicit) have been used only with a constant step size. Using variable step sizes and the procedure presented in Section 4 we can obtain interval enclosure of the exact solution with a width given beforehand. Although we have presented our algorithm only for interval methods of Adams-Bashforth type, it seems that the same procedure one can apply to other multistep methods, including interval predictor-corrector ones [ 27].

Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Footnotes

The term “Adams-Bashforth method” is often used only for the four-step explicit linear method, which is a special case of the class of methods that we consider in this paper. In [ 11], the methods considered here are called “explicit Adams methods,” but J. C. Butcher in [ 3, p. 143] used the same term as we use, since there are other similar linear explicit methods known as Adams-Nyström or simply Nyström methods (see, e.g., [ 3] or [ 13]).

The case when ( 1) presents a system of differential equations is discussed in Section 5

The function F( T, Y ) is continuous at ( T ₀, Y ₀) if for every ε > 0 there is a positive number δ = δ( ε) such that d( F( T, Y ), F( T ₀, Y ₀)) < ε whenever d( T, T ₀) < δ and d( Y, Y ₀) < δ. Here, d denotes the interval metric defined by $d(X_{1},X_{2})=\max \{|\underline {X}_{1}-\underline {X}_{2}|,|\overline {X}_{1}-\overline {X}_{2}|\}$, where $X_{1}=[\underline {X}_{1},\overline {X}_{1}]$ and $X_{2}=[\underline {X}_{2},\overline {X}_{2}]$ are two intervals.

The values of Y _k are presented in the form obtained in our programs.

Table 1

Starting values for Adams-Bashforth methods and the problem ( 45)

k	$t_{k}$	$h_{k}$	$y_{k}$	$Y_{k}$
0	0.00	–	$\approx $ 1	[ $\underline {1.0000000000000000\mathrm {E}+0000}$, $\overline {1.0000000000000000\mathrm {E}+0000}$]
1	0.08	0.08	$\approx $ 1.0408108	[ $\underline {1.0408107741923882\mathrm {E}+0000}$, $\overline {1.0408107741923883\mathrm {E}+0000}$]
2	0.15	0.07	$\approx $ 1.0778842	[ $\underline {1.0778841508846315\mathrm {E}+0000}$, $\overline {1.0778841508846315\mathrm {E}+0000}$]
3	0.20	0.05	$\approx $ 1.1051709	[ $\underline {1.1051709180756476\mathrm {E}+0000}$, $\overline {1.1051709180756477\mathrm {E}+0000}$]

For a number of interval multistep methods, such theorems have been presented in [ 9, 17– 19, 22, 25– 29, 37].

Our product recommendations

Premium-Abo der Gesellschaft für Informatik

Sie erhalten uneingeschränkten Vollzugriff auf alle acht Fachgebiete von Springer Professional und damit auf über 45.000 Fachbücher und ca. 300 Fachzeitschriften.

inform now

Berz, M., Hoffstätter, G.: Computation and application of Taylor polynomials with interval remainder bounds. Reliab. Comput. 4(1), 83–97 (1998) MathSciNetMATHCrossRef

Berz, M., Makino, K.: Performance of Taylor model methods for validated integration of ODEs. In: Dongarra, J., Madsen, K., Wasniewski, J. (eds.) Applied Parallel Computing. State of the Art in Scientific Computing, Lecture Notes in Computer Science, vol. 3732, pp 65–73 (2005)

Butcher, J.C.: The Numerical Analysis of Ordinary Differential Equations: Runge-Kutta and General Linear Methods. Wiley, Chichester (1987) MATH

Ceschino, F.: Modification de la Longueur du pas Dans L’intégration Numérique par les Méthodes à pas Líes. Chiffres 2, 101–106 (1961) MathSciNetMATH

Collatz, L.: The Numerical Treatment of Differential Equations, 3rd edn. Springer, Berlin (1959)

Corliss, G.F., Rihm, R.: Validating an a priori enclosure using high–order Taylor series. In: Scientific Computing, Computer Arithmetic, and Validated Numerics, pp 228–238. Akademie Verlag (1996)

Enright, W.H., Pryce, H.D.: Two FORTRAN packages for assessing initial value methods. ACM Trans. Math. Softw. 13(1), 1–27 (1987) MATHCrossRef

Forrington, C.V.D.: Extension of the predictor–corrector method for the solution of systems of ordinary differential equations. Comput. J. 4(1), 80–84 (1961) MATHCrossRef

Gajda, K., Jankowska, M., Marciniak, A., Szyszka, B.: A survey of interval Runge-Kutta and multistep methods for solving the initial value problem. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Wasniewski, J. (eds.) Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science, vol. 4967, pp 1361–1371. Springer, Berlin (2008)

10.

Gajda, K., Marciniak, A., Szyszka, B.: Three-and four-stage implicit interval methods of Runge-Kutta type. Comput. Methods Sci. Technol. 6(1), 41–59 (2000) CrossRef

11.

Hairer, E., Nørsett, S.P., Wanner, G.: Solving Ordinary Differential Equations I – Nonstiff Problems. Springer, Berlin (1987) MATHCrossRef

12.

Hansen, E.R.: Topics in Interval Analysis. Oxford University Press, London (1969) MATH

13.

Henrici, P.: Discrete Variable Methods in Ordinary Differential Equations. Wiley, New York (1962) MATH

14.

Henrici, P.: Error Propagation in Difference Methods. Wiley, New York (1963) MATH

15.

Jackson, K.R., Nedialkov, N.S.: Some recent advances in validated methods for IVPs for ODEs. Appl. Numer. Math. 42(1–3), 269–284 (2002) MathSciNetMATHCrossRef

16.

Jain, M.K.: Numerical Solution of Differential Equations. Wiley, New York (1979) MATH

17.

Jankowska, M., Marciniak, A.: Implicit interval methods for solving the initial value problem. Comput. Methods Sci. Technol. 8(1), 17–30 (2002) CrossRef

18.

Jankowska, M., Marciniak, A.: On explicit interval methods of Adams-Bashforth type. Comput. Methods Sci. Technol. 8(2), 46–57 (2002) CrossRef

19.

Jankowska, M., Marciniak, A.: On two families of implicit interval methods of Adams-Moulton type. Comput. Methods Sci. Technol. 12(2), 109–113 (2006) CrossRef

20.

Krogh, F.T.: A variable step variable order multistep method for the numerical solution of ordinary differential equations. In: Information Processing 68. Proceedings of IFIP Congress 1968, pp 194–199. North-Holland, Amsterdam (1968)

21.

Krogh, F.T.: Changing step size in the integration of differential equations using modified divided differences. In: Proceedings of the Conference on the Numerical Solutions of ODE. Lecture Notes in Mathematics, 362, pp 22–71. Springer-Verlag, New York (1974)

22.

Marciniak, A.: Selected Interval Methods for Solving the Initial Value Problem. Publishing House of Poznan University of Technology, Poznan (2009). http://www.cs.put.poznan.pl/amarciniak/IMforIVP-book/IMforIVP.pdf

23.

Marciniak, A.: Interval Arithmetic Unit. http://www.cs.put.poznan.pl/amarciniak/IAUnits/IntervalArithmetic32and64.pas (2016)

24.

Marciniak, A.: Delphi Pascal programs for step size control in interval Adams–Bashforth methods. http//www.cs.put.poznan.pl/amarciniak/VSSABM-Examples (2019)

25.

Marciniak, A., Jankowska, M.A.: Interval versions for special kinds of explicit linear multistep methods (in review, available from the authors)

26.

Marciniak, A., Jankowska, M.A.: Interval versions of Milne’s multistep method. Numer. Algorithms 79(1), 87–105 (2018) MathSciNetMATHCrossRef

27.

Marciniak, A., Jankowska, M.A., Hoffmann, T.: On interval predictor–corrector methods. Numer. Algorithms 75(3), 777–808 (2017) MathSciNetMATHCrossRef

28.

Marciniak, A., Szyszka, B.: One-and two-stage implicit interval methods of Runge-Kutta type. Comput. Methods Sci. Technol. 5(1), 53–65 (1999) CrossRef

29.

Marciniak, A., Szyszka, B.: Interval Runge–Kutta methods with variable step sizes. Comput. Methods Sci. Technol. 25(1), 33–46 (2019) CrossRef

30.

Marciniak, A., Szyszka, B., Hoffmann, T.: An interval version of Kuntzmann–Butcher method for solving the initial value problem (in review, available from the authors)

31.

Moore, R.E.: Interval Analysis. Prentice-Hall, Englewood Cliffs (1966) MATH

32.

Moore, R.E.: Methods and applications of interval analysis. SIAM Society for Industrial & Applied Mathematics Philadelphia (1979)

33.

Nedialkov, N.S.: VNODE-LP – a validated solver for initial value problems in ordinary differential equations. Tech. Rep. CAS 06-06-NN, Department of Computing and Software, McMaster University, Hamilton (2006)

34.

Nedialkov, N.S., Jackson, K.R., Corliss, G.F.: Validated solutions of initial value problems for ordinary differential equations. Appl. Math. Comput. 105(1), 21–68 (1999) MathSciNetMATH

35.

Shampine, L.F.: Variable order Adams codes. Comput. Math. Appl. 44(5–6), 749–761 (2002) MathSciNetMATHCrossRef

36.

Shampine, L.F., Gordon, M.K.: Computer solution of ordinary differential equations freeman (1975)

37.

Shokin, Y.I.: Interval Analysis. Novosibirsk, Nauka (1981) MATH

38.

Stoer, J., Bulirsch, R.: Introduction to Numerical Analysis. Springer, Berlin (1983) MATH

Title: Interval methods of Adams-Bashforth type with variable step sizes
Authors:: Andrzej Marciniak
Malgorzata A. Jankowska
Publication date: 29-07-2019
DOI: https://doi.org/10.1007/s11075-019-00774-y
Publisher: Springer US
Journal: Numerical Algorithms
Issue 2/2020
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265

Premium Partner

Image Credits

k	\(t_{k}\)	\(Y_{k}\)
0	0	[ \(\underline {4.0000000000000000\mathrm {E}+0000}\), \(\overline {4.0000000000000000\mathrm {E}+0000}\)]
1	0.081746227283888863	[ \(\underline {4.0801194662264153\mathrm {E}+0000}\), \(\overline {4.0801194662264155\mathrm {E}+0000}\)]
2	0.163492454567777736	[ \(\underline {4.1571485011046702\mathrm {E}+0000}\), \(\overline {4.1571485011046705\mathrm {E}+0000}\)]
3	0.245238681851666599	[ \(\underline {4.2313071906453238\mathrm {E}+0000}\), \(\overline {4.2313071906453243\mathrm {E}+0000}\)]

k	\(t_{k}\)	\(Y_{k}\)	Width
50	\(\approx \) 0.69774	[ 4.5975465221505685E + 0000, 4.5975465243497029E + 0000]	\(\approx 2.20 \cdot 10^{-9}\)
100	\(\approx \) 1.14965	[ 4.9030146239176995E + 0000, 4.9030146292963836E + 0000]	\(\approx 5.38 \cdot 10^{-9}\)
150	\(\approx \) 1.47461	[ 5.0930266442612574E + 0000, 5.0930266533191654E + 0000]	\(\approx 9.06 \cdot 10^{-9}\)
200	\(\approx \) 1.54340	[ 5.1304617719687623E + 0000, 5.1304617819135613E + 0000]	\(\approx 9.94 \cdot 10^{-9}\)
250	\(\approx \) 1.54735	[ 5.1325793100365724E + 0000, 5.1325793200333748E + 0000]	\(< 1.00 \cdot 10^{-8}\)
464	\(\approx \) 1.54759	[ 5.1327090107108448E + 0000, 5.1327090207108449E + 0000]	\(< 1.00 \cdot 10^{-8}\)

k	\(t_{k}\)	\(Y_{k}\)	Width
200	\(\approx \) 0.55405	[ 4.4886273748015889E + 0000, 4.4886273748017744E + 0000]	\(\approx 1.85 \cdot 10^{-13}\)
400	\(\approx \) 0.85821	[ 4.7120930249268474E + 0000, 4.7120930249272235E + 0000]	\(\approx 3.76 \cdot 10^{-13}\)
600	\(\approx \) 1.13809	[ 4.8958332122088699E + 0000, 4.8958332122095143E + 0000]	\(\approx 6.44 \cdot 10^{-13}\)
800	\(\approx \) 1.36239	[ 5.0299271956108516E + 0000, 5.0299271956117965E + 0000]	\(\approx 9.45 \cdot 10^{-13}\)
900	\(\approx \) 1.39889	[ 5.0507330026032329E + 0000, 5.0507330026042326E + 0000]	\(< 1.00 \cdot 10^{-12}\)
955	\(\approx \) 1.39915	[ 5.0508805112730600E + 0000, 5.0508805112740601E + 0000]	\(< 1.00 \cdot 10^{-12}\)

k	\(t_{k}\)	\(Y_{k}\)	Width
10	\(\approx \) 0.67182	[ 4.5783575612188736E + 0000, 4.5783702917087973E + 0000]	\(\approx 1.27 \cdot 10^{-5}\)
20	\(\approx \) 1.22301	[ 4.9478886689807839E + 0000, 4.9479228693528902E + 0000]	\(\approx 3.42 \cdot 10^{-5}\)
30	\(\approx \) 1.62289	[ 5.1725533292643105E + 0000, 5.1726121849592280E + 0000]	\(\approx 5.89 \cdot 10^{-5}\)
100	\(\approx \) 2.07277	[ 5.3895608440740060E + 0000, 5.3896595445228829E + 0000]	\(\approx 9.87 \cdot 10^{-5}\)
150	\(\approx \) 2.08316	[ 5.3941735254856961E + 0000, 5.3942734009330229E + 0000]	\(\approx 9.99 \cdot 10^{-5}\)
632	\(\approx \) 2.08426	[ 5.3946582071369410E + 0000, 5.3947582071369411E + 0000]	\(< 1.00 \cdot 10^{-4}\)

k	\(t_{k}\)	\(Y_{s} = Y_{sk}\)
0	0	\(Y_{1} = \) [ \(\underline {0.0000000000000000\mathrm {E}+0000}\), \(\hspace {0.2cm}\overline {0.0000000000000000\mathrm {E}+0000}\)]
		\(Y_{2} =\) [ \(\underline {5.2359877559829887\mathrm {E}-0001}\), \(\hspace {0.2cm}\overline {5.2359877559829888\mathrm {E}-0001}\)]
1	0.0001	\(Y_{1} =\) [ \(\underline {-5.1347498487965657\mathrm {E}-0004},\) \(\overline {-5.1347498487965656\mathrm {E}-0004}\)]
		\(Y_{2} = \) [ \(\underline {5.2359874992454941\mathrm {E}-0001}\), \(\hspace {0.2cm}\overline {5.2359874992454942\mathrm {E-}0001}\)]
2	0.0002	\(Y_{1} = \) \([\underline {-1.0269499194046190\mathrm {E}-0003}\), \(\overline {-1.0269499194046189\mathrm {E}-0003}\)]
		\(Y_{2} = \) [ \(\underline {5.2359867290330357\mathrm {E}-0001}\), \(\hspace {0.2cm}\overline {5.2359867290330358\mathrm {E}-0001}\)]

Springer Professional

Hint

Swipe to navigate through the articles of this issue

Publisher’s note

1 Introduction

2 Adams-Bashforth methods

3 Interval versions of Adams-Bashforth methods with variable step sizes

4 Using variable step sizes

5 A note on a system of differential equations

6 Numerical examples

7 Conclusions

Publisher’s note

Our product recommendations

Premium-Abo der Gesellschaft für Informatik

Other articles of this Issue 2/2020

Global uniqueness and solvability of tensor complementarity problems for -tensors

Fractional collocation boundary value methods for the second kind Volterra equations with weakly singular kernels

A new modified three-step iteration method for G-nonexpansive mappings in Banach spaces with a graph

Three-step alternating iterations for index 1 and non-singular matrices

Parallelization, initialization, and boundary treatments for the diamond scheme

Preconditioned quasi-compact boundary value methods for space-fractional diffusion equations

Premium Partner