Topic 14.4: Multiple-Step Methods (Error Analysis)

Contents Previous Chapter Start of Chapter Previous Topic Introduction Notes Theory HOWTO Examples Engineering Error Questions Matlab Maple Next Topic Next Chapter

Consider the IVP

y(1)(t) = f(t, y(t))
y(a) = y0

where we are trying to approximate y(b). If we apply Euler's method with n steps, then the error on the ith interval is given by ½y(2)i)h2 where τi ∈ [ti − 1ti]. Thus, the cumulative error is:

If we factor out a ½h and rewrite the other h as (b - a)/n, then we get:

Using the definition of the average value, this simplifies to:

Thus, we can easily generalize this result to see that multiple-step methods will reduce the order of the error term by a factor of h. Thus, while a single step of 4th-order Runge Kutta is O(h5), multiple applications of 4th-order Runge Kutta is only O(h4). (Hence the name, 4th-order Runge Kutta.) A summary is shown in Table 1.

Table 1. Comparison of rates of convergence for single step and multiple steps.

MethodSingle StepMultiple Steps
Euler's methodO(h2)O(h)
Heun's methodO(h3)O(h2)
4th-order Runge KuttaO(h5)O(h4)

This suggests very strongly that it is that much more important to use the 4th-order Runge Kutta method when using multiple step methods.

To justify this statement, let us look at how the error decreases as the size of the interval is increased. We cannot, however, simply divide the interval into n sub-intervals and apply each method because Euler's method requires only one function evaluation, and 4th-order Runge Kutta requires four. Thus, Tables 1, 2, 3, and 4 look at how the error is reduced with a constant number of function evaluations.

Table 1. Four function evaluations.

MethodStepsError Reduction
Euler's41/4 = 0.25
Heun's21/22 = 0.25
4th-order Runge Kutta11

Table 2. Eight function evaluations.

MethodStepsError Reduction
Euler's81/8 = 0.125
Heun's41/42 = 0.0625
4th-order Runge Kutta21/24 = 0.0625

Table 3. Sixteen function evaluations.

MethodStepsError Reduction
Euler's161/16 = 0.0625
Heun's81/82 = 0.0156
4th-order Runge Kutta41/44 = 0.00391

Table 4. Thirty-two function evaluations.

MethodStepsError Reduction
Euler's321/32 = 0.03125
Heun's161/162 = 0.00391
4th-order Runge Kutta81/84 = 0.000244

Thus, while Euler's method with 32 sub-intervals and 4th-order Runge Kutta with 8 intervals both have the same number of evaluations, the error with Euler's method is reduced by only 0.03125 while the error with 4th-order Runge Kutta is reduced by 0.000244.

To visualize this, consider:

y(1)(t) = 1 + y2(t)
y(0) = 0

The correct answer is y(1) = tan(1) = 1.557407725.

With Euler's method, using four steps, we have:

y1 = 0.25
y2 = 0.515625
y3 = 0.8320922852
y4 = 1.255186678

The absolute error of this answer is 0.30.

With one step of 4th-order Runge Kutta, we have:

y1 = 1.535847982

The absolute error here is 0.022.

If however, we use 32 function evaluations, we have y32 = 1.497473902 which has an absolute error of 0.060 which is approximately 1/5 the error with 4 intervals.

With 8 steps of 4th-order Runge Kutta, we get that y8 = 1.557402847 which has an absolute error of 0.0000049 which is approximately 0.00022 that of the approximation with one step.

Copyright ©2005 by Douglas Wilhelm Harder. All rights reserved.