7Implementation of ODE methods
IB Numerical Analysis
7.1 Local error estimation
The first problem we want to tackle is what
h
we should pick. Usually, when
using numerical analysis software, you will be asked for an error tolerance, and
then the software will automatically compute the required
h
we need. How is
this done?
Milne’s device is a method for estimating the local truncation error of a
multi-step method, and hence changing the step-length
h
(there are similar
techniques for Runge-Kutta methods, but they are more complicated). This uses
two multi-step methods of the same order.
To keep things simple, we consider the two-step Adams-Bashforth method.
Recall that this is given by
y
n+1
= y
n
+
h
2
(2f(t
n
, y
n
) − f(t
n−1
, y
n−1
)).
This is an order 2 error with
η
n+1
=
5
12
h
3
y
000
(t
n
) + O(h
4
).
The other multi-step method of order 2 is our old friend, the trapezoidal rule.
This is an implicit method
y
n+1
= y
n
+
h
2
(f(t
n
, y
n
) + f(t
n+1
, y
n+1
)).
This has a local truncation error of
η
n+1
= −
1
12
h
3
y
000
(t
n
) + O(h
4
).
The key to Milne’s device is the coefficients of h
3
y
000
(y
n
), namely
c
AB
=
5
12
, c
TR
= −
1
12
.
Since these are two different methods, we get different
y
n+1
’s. We distinguish
these by superscripts, and have
y(t
n+1
) − y
AB
n+1
' c
AB
h
3
y
000
(t
n
)
y(t
n+1
) − y
TR
n+1
' c
TR
h
3
y
000
(t
n
)
We can now eliminate some terms to obtain
y(t
n+1
) − y
TR
n+1
'
−c
TR
c
AB
− c
TR
(y
AB
n+1
− y
TR
n+1
).
In this case, the constant we have is
1
6
. So we can estimate the local truncation
error for the trapezoidal rule, without knowing the value of
y
000
. We can then
use this to adjust h accordingly.
The extra work we need for this is to compute numerical approximations
with two methods. Usually, we will use a simple, explicit method such as the
Adams-Bashforth method as the second method, when we want to approximate
the error of a more complicated but nicer method, like the trapezoidal rule.