In a number of our previous papers, we have proposed interval versions of multistep methods (explicit and implicit), including interval predictor-corrector methods, in which the step size was constant. In this paper, we present interval versions of Adams-Bashforth methods with a possibility to change step sizes. This possibility can be used to obtain interval enclosures of the exact solution with a width given beforehand.
Hinweise
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.
Anzeige
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)1 with variable step sizes.
Let the set of points {t0,t1,…,tk,…,tm}, 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 ti are called the mesh points), and hi = ti − ti− 1 (i = 1,2,…,m) denote the step sizes. On the interval [tk− 1,tk], the differential equation (1) is equivalent to
The values φj (k) and gj (k) for j = 0,1,…,n − 1 can be computed efficiently with recurrence relations [11, 13]. As an immediate consequence of (3), we have
are known, we denote fi = f (ti,yi) 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
If for each i = k,k − 1,…,k − n + 1 we have hi = 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]):
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) ∈ Y0 and the intervals Yk such that y (tk) ∈ Yk for k = 1,2,…,n − 1 are known. We can obtain such Yk 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)):
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 (ti,y (ti)) ∈ (Ti,Yi) fori = k − n,k − n + 1,…,k − 1,whereYi = Y (ti),then for anyj = 0,1,…,n − 1 we have
but—according to (14)—this is the interval Yn. 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 intervalsYkfork = 0,1,…,n − 1 are known,ti = h1 + h2 + … + hi ∈ Ti,i = 1,2,…,m (t0 = 0 ∈ T0 = [0,0]),and the intervalsYkfork = n,n + 1,…,mare obtained from (14), then
Since T0 = [0,0], i.e., w (T0) = 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 Yk 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 Yk, 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.,
Since Tk−j (j = 1,2,…,n) is only an interval representation of tk−j, we have w (Tk−j) ≈ 0. If we assume w (Tk−j) = 0 and take into account (42), then we have
The equation (43) presents a polynomial (with respect to h) of degree n + 1. Denoting this polynomial by pn+ 1 (hk), we look for hk > 0 such that pn+ 1 (hk) = 0. To find such an hk, one can use any method for finding roots of polynomials. Applying, for example, the Newton iterations we have
Note that in general, the real hk > 0, satisfying (43), may not exist. Since in (43) all coefficients near by any power of hk 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 Yk increase, then the successive step sizes hk must decrease (see Example 2 in Section 6). Moreover, if tm is the last tk, for which tk < a, and we want to achieve the end a of integration interval, then for the last integration step we should take hm+ 1 = a − tm.
According to the definitions of gn (k) and ρn (k) (see (8) and (33), respectively), it is difficult to write the general form of pn+ 1 (hk). For n ≤ 4, we have the following formulas:
Note that in the case of n > 1, the form of pn+ 1 (hk) 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
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 Yk = [Yk,(1),Yk,(2),…,Yk,(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(1),A(2),…,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
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.4
Taking m = 20 and h1 = 0.08, h2 = 0.07, h3 = 0.05, h4 = 0.09, h5 = 0.08, h6 = 0.07, h7 = 0.10, h8 = 0.08, h9 = 0.14, h10 = 0.09, h11 = 0.15, h12 = 0.11, h13 = 0.07, h14 = 0.10, h15 = 0.15, h16 = 0.12, h17 = 0.08, h18 = 0.12, h19 = 0.15, and h20 = 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(t20) ≈ 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)
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.
Fig. 1
Step size changes in problem (45) for the methods (16)–(19)
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
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 tm, 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 tm < 0.6 and at the final t = 0.6, where the last step size is equal to 0.6 − tm). 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 \}\)
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
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(5) (t) = f(4) (t,y). Since for the problem (47), we have
Table 5
Starting values for the method (19) and the problem (47)
Requiring 10− 8 for interval widths, taking Λ = 1, ε = 10− 18, step sizes h1 = h2 = h3 = 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 eps = 10− 12, then we achieve t ≈ 1.3991 (smaller t) after 4.758 s, and for eps = 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 (eps = 10− 8)
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 φ = φ0 cos (ut), where φ0 is an initial angle. Denoting y1 = φ′, y2 = φ and assuming that φ′(0) = 0, φ (0) = φ0, we can transform (49) into the following systems of differential equations of first order:
and consider the method (18). Assuming eps = 10− 8, taking Λ = 9.80665π/6, ε = 10− 18, step sizes h1 = h2 = 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)
Step size changes in problem (50)–(51) for the method (18)
×
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 tmax ≤ a. Unfortunately, very often we have tmax << 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.5 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 hmin, 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 hmin—continue calculations with h = hmin. 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 tmax ≤ a, but computing times may not be decreasing (compare the values of tmax and computing times in Example 3 for eps = 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 tmax for each value of eps. These times are also presented in Fig. 4, and we can see that for eps = 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
Fig. 4
CPU times for the method (19) and different values of eps
×
On the other hand, for some t < T ≤ a, where T denotes the smallest tmax 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.
Fig. 5
CPU times needed to achieve t = 1.3 for the methods (17), (18), and (19) and different values of eps
×
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.
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 function F(T,Y ) is continuous at (T0,Y0) if for every ε > 0 there is a positive number δ = δ(ε) such that d(F(T,Y ),F(T0,Y0)) < ε whenever d(T,T0) < δ and d(Y,Y0) < δ. 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.
