A Global Error Bound for One Step Methods

6.3. A Global Error Bound for One Step Methods#

References:

All the methods seen so far for solving ODE IVP’s are one-step methods: they fit the general form

\[ U_{i+1} = F(t_i, U_i, h) \]

For example, Euler’s Method has

\[ F(t, U, h) = U + h f(t, U), \]

the Explicit Midpoint Method (Modified Euler) has

\[ F(t, U, h) = U + h f(t+h/2, U + hf(t, U)/2) \]

and even the Runge-Kutta method has a similar form, but it is long and ugly.

For these, there is a general result that gives a bound on the globl truncation error (“GTE”) once one has a suitable bound on the local truncation error (“LTE”). This is very useful, because bounds on the LTE are usually far easier to derive.

Theorem 6.1

When solving the ODE IVP

\[ du/dt = f(t, u),\quad u(a) = u_0 \]

on interval \(t \in [a, b]\) by a one step method, one has a bound on the local truncation error

\[ |e_i| = |U_{i+1} - u(t_i+h; t_i, U_i) = |F(t_i, U_i, h) - u(t_i + h; t_i, U_i)| \leq Ch^{p+1} = O(h^{p+1}) \]

and the ODE itself satisfies the Lipschitz Condition that for some constant \(K\),

\[ \left| \frac{\partial F}{\partial u}(t, u) \right| \leq K \]

then there is a bound on the global truncation error:

\[ | E_i | = |U_i - u(t_i; a, u_0)| \leq C \frac{e^{K (t_i - a)} - 1}{k} h^p, = O(h^p) \]

So yet again, there is a loss of one factor of \(h\) in going from local to global error, as first seen with the composite rules for definite integrals.

We saw a glimpse of this for Euler’s method, in the section Basic Concepts and Euler’s Method where the Taylor’s Theorem error formula canbe used to get the LTE bound

\[ |e_i| \leq C h^2 \text{ where } C = \frac{|u_0 e^{K(b - a)}|}{2} \]

and this leads to to GTE bound

\[ | E_i | \leq \frac{|u_0 e^{K(b - a)}|}{2} \frac{e^{K (t_i - a)} - 1}{k} h. \]

6.3.1. Order of accuracy for the basic Runge-Kutta type methods#

  • For Euler’s method, it was stated in section Basic Concepts and Euler’s Method, (and verified for the test case of \(du/dt = ku\)) that the global truncation error is of first order n step-size \(h\):

  • The Explicit (and Implicit) Trapezoid and Midpoint rules, the local truncation error is \(O(h^3)\) and so their global truncation error is \(O(h^2)\) — they are second order accurate, just as for the corresponding approximate integration rules.

  • The classical Runge-Kutta method, has local truncation error \(O(h^5)\) and so its global truncation error is \(O(h^4)\) — just as for the composite Simpson’s Rule, to which it corresponds for the “integration” case \(dy/dt = f(t)\).