Back to the on-screen lesson · Print

Improved Euler and Runge-Kutta

Evaluating the right-hand side several times inside one step and combining the slopes, and what each extra evaluation buys in order of accuracy.

Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.

1. What you will learn

By the end of this lesson you will be able to carry out an improved Euler step and a classical Runge-Kutta step by hand, say where each of the four slopes is evaluated and why the sequence cannot be rearranged, state the order of each method and the factor by which halving the step reduces its error, and compare two methods on a fixed budget of evaluations rather than on a fixed number of steps.

2. What you already have

You can run Euler's method and you know why it is first order: the local error is of size $h^{2}$, there are $1/h$ steps, and the product is $h$. You have also seen what that costs — ten times the work for one more decimal place. This lesson buys the same accuracy far more cheaply, and the idea it uses is not subtle.

3. Words this lesson uses

4. Asking the equation more than once per step

Euler's real fault is not that the step is a straight line; it is that the line's slope is taken at one end of an interval on which the slope is changing. The whole family of improvements comes from one idea: evaluate the right-hand side at several places in the step and combine.

Improved Euler (Heun). Take a trial Euler step to get a provisional value at the far end, evaluate the slope there, and use the average of the two:

$$k_1 = f(x_n, y_n), \quad k_2 = f(x_n + h,\ y_n + hk_1), \quad y_{n+1} = y_n + \tfrac{h}{2}(k_1 + k_2).$$

The symmetry of the average cancels the leading error term, and the method is second order: two evaluations a step, error proportional to $h^{2}$.

Classical Runge-Kutta. Four evaluations — left end, midpoint twice, right end — combined with Simpson's weights:

$$y_{n+1} = y_n + \frac{h}{6}\left(k_1 + 2k_2 + 2k_3 + k_4\right).$$

It is fourth order. Halving the step divides the error by sixteen.

5. What an order is worth, counted in evaluations

The fair comparison is not per step but per evaluation of the right-hand side, because that is what costs time in a real calculation.

Suppose a fixed budget of $N$ evaluations. Euler spends them on $N$ steps and achieves an error of about $C/N$. Runge-Kutta spends them on $N/4$ steps, each four times as long, and achieves an error of about $C'(4/N)^{4}$ — a factor involving $N^{4}$ in the denominator rather than $N$.

With a hundred evaluations that is roughly one per cent against one part in a million, and the gap widens with every evaluation added. The extra stages are not overhead; they are the entire reason the method is usable.

The pattern does stop. One evaluation buys one order up to four, and after that it does not: a fifth-order explicit method needs six stages, a sixth-order one needs seven. Four is where the exchange rate turns, and that is why almost every general-purpose solver has a fourth-order method at its core.

6. Where this goes wrong

Evaluating the stages out of order. $k_3$ uses a trial value built from $k_2$, and $k_4$ from $k_3$. Computing all four at the same $y_n$ gives a different method with a different, worse order.

Using $h$ where $h/2$ belongs. The middle stages advance $x$ by half a step and $y$ by half a step along the previous slope. Both halves matter.

Dividing by $4$ instead of $6$. The weights are $1, 2, 2, 1$, which sum to six, not four. It is an average of four numbers only in the sense that they are weighted, and the middle pair count double.

Reading the order as the factor. Halving the step for a fourth-order method gains sixteen, not four.

Assuming a high order makes a large step safe. Order is about accuracy; the next lesson is about the separate limit that stability imposes, and no amount of order removes it.

7. The method, step by step, and how to check it

A Runge-Kutta step is Euler's idea done more carefully: find a slope that represents the whole step, then move along it. The routine is fixed.

1. Tabulate $x_n$, $y_n$ and $h$. Write $\frac{h}{2}$ down too; it appears in two stages.
2. $k_1$ at the start, $(x_n, y_n)$.
3. $k_2$ at the midpoint $x_n + \frac{h}{2}$, with trial value $y_n + \frac{h}{2}k_1$.
4. $k_3$ at the same midpoint, with trial value $y_n + \frac{h}{2}k_2$.
5. $k_4$ at the far end $x_n + h$, with trial value $y_n + hk_3$.
6. Average and step: $y_{n + 1} = y_n + \frac{h}{6}(k_1 + 2k_2 + 2k_3 + k_4)$.

Why these weights. If $f$ does not depend on $y$, the step is $\int_{x_n}^{x_n + h} f(x)\,dx$, and the combination $\frac{h}{6}\left(f_{\text{left}} + 4f_{\text{mid}} + f_{\text{right}}\right)$ is Simpson's rule, with the $4$ split between the two midpoint stages. The midpoint carries the most weight because it is where the average slope of the step is best seen. When $f$ does depend on $y$, the trial values let each stage see the slope where the solution is likely to be, and a Taylor expansion shows that every error term up to $h^{4}$ cancels.

How to check the answer. Check that the four slopes change smoothly: for a well-behaved equation and a sensible $h$ they should be close to one another, and $k_2$ and $k_3$ usually closest of all. For $y' = y$, the step must multiply by $1 + h + \frac{h^{2}}{2} + \frac{h^{3}}{6} + \frac{h^{4}}{24}$, a quick test of the arithmetic. Over a run, halve $h$ and repeat: the two answers should agree to about one sixteenth of their difference from a run with $2h$, which is the fourth order showing itself, and the standard way to estimate the error without an exact solution.

8. In the world: keeping a satellite on its orbit

A satellite in a circular orbit moves so that its position satisfies, in suitable units, $x' = v$ and $v' = -x$: the solutions are circles, and the energy $x^{2} + v^{2}$ is constant. A solver that does not keep the energy constant puts the satellite on the wrong orbit, and the order of the method decides how fast it wanders.

One Euler step multiplies $x^{2} + v^{2}$ by exactly $1 + h^{2}$ (a short calculation from $x_{n + 1} = x_n + hv_n$ and $v_{n + 1} = v_n - hx_n$). With $h = 0.01$, one orbit takes $628$ steps and multiplies the energy by $1.0001^{628} \approx e^{0.0628} \approx 1.065$: the orbit's radius grows by about $3\%$ every revolution, and after a few dozen revolutions the simulated satellite has spiralled far out. Classical Runge-Kutta with the same step has an energy error per orbit of order $h^{4}$, about $10^{-8}$, so a simulated year of orbits stays on the right circle to many digits.

That comparison, first order against fourth, spent on the same number of steps, is why orbit determination, the software that tells ground stations where to point their dishes, uses high-order methods and never Euler.

9. In the world: the solver inside every scientific library

When a scientist calls solve_ivp in Python's SciPy or ode45 in MATLAB without choosing a method, they get an adaptive Runge-Kutta method: each step computes two estimates of different orders from the same slope evaluations, a fourth-order and a fifth-order one, and their difference estimates the error of the step. If it is larger than the tolerance the user asked for, the step is rejected and retried with a smaller $h$; if it is much smaller, the next step is made longer.

The payoff is that the step size follows the solution: long steps where it is smooth, short ones where it changes quickly, as when a comet swings close to the Sun. A fixed-step method must use the short step everywhere, and for an orbit that spends most of its time far from the Sun that can mean a hundred times the work. The idea rests entirely on this lesson: order tells how the error scales with $h$, and two orders computed together tell how big it is.

10. In the world: when the order stops paying

High order pays only when the solution is smooth. Across a sudden change, a switch in a circuit or an impact in a mechanism, every method's error jumps, and the fourth-order advantage is lost for the steps that straddle it. Engineering solvers therefore stop exactly at such events, restart from the new state, and let the order work on each smooth stretch separately.

11. In the world: how weather forecasts step forward

A weather model advances millions of coupled equations, one set per grid box, in steps of a few minutes, and most operational models use Runge-Kutta stages or close relatives of them. The cost of each stage is a full evaluation of the atmosphere's physics, so the balance this lesson describes, order bought with evaluations, is decided there in computer hours, and forecasting centres choose the method whose accuracy per evaluation is highest for their grid.

12. The trial value is a probe, not a prediction

Every method here computes intermediate values of $y$ and then discards them, and the standard error is to treat one of those as the answer — to take the Heun trial value as the new $y$, or to carry $k_2$'s trial point forward into the next step. They are not estimates of the solution at all; they exist solely to give the right-hand side somewhere to be evaluated, and the improved Euler trial point is deliberately the worst available estimate, because what is wanted from it is the slope at the far end and not the position. The second habit worth breaking is reading order as a promise about a single step. It is a statement about how the error scales as $h$ shrinks, and it says nothing about how good any particular step with any particular $h$ is — for that there is no substitute for running the calculation twice and comparing.

13. One Heun step against one Euler step

1. Take $y' = y$, $y(0) = 1$, $h = 0.5$. Take the Euler step as a trial.

   $k_1 = f(0, 1) = 1, \qquad \tilde{y} = 1 + 0.5 \times 1 = 1.5$

   The trial step is an Euler step: it is the provisional value at the far end.

2. Evaluate the slope at the trial point.

   $k_2 = f(0.5, 1.5) = 1.5$

   The slope at the far end of the step, as well as it can be estimated.

3. Average the two slopes and take the real step.

   $y_1 = 1 + \dfrac{0.5}{2}(1 + 1.5) = 1 + 0.25 \times 2.5 = 1.625$

   The average of the two end slopes is a better slope for the whole step than either end alone.

4. Compare both with the exact value.

   $e^{0.5} = 1.6487: \quad \text{Euler } 1.6487 - 1.5 = 0.149, \quad \text{Heun } 1.6487 - 1.625 = 0.024$

   Six times better for twice the work, on the very first step.

5. See where the improvement comes from.

   $1 + h + \dfrac{h^{2}}{2} = 1 + 0.5 + 0.125 = 1.625$

   For $y' = y$, Heun's step multiplies by the Taylor series of $e^{h}$ to second order; Euler's stops at first order. That extra term is the extra order.

14. A step Runge-Kutta gets exactly right

1. Take $y' = 3x$, $y(0) = 0$, $h = 2$. Evaluate the first slope, at $x = 0$.

   $k_1 = f(0, 0) = 3 \times 0 = 0$

   The right-hand side depends on $x$ only.

2. Evaluate the two midpoint slopes, at $x = 1$.

   $k_2 = f(1, \cdot) = 3, \qquad k_3 = f(1, \cdot) = 3$

   The right-hand side does not involve $y$, so the two midpoint stages agree whatever the trial values.

3. Evaluate the last slope, at $x = 2$.

   $k_4 = f(2, \cdot) = 6$

   A full step from the start.

4. Form the weighted average and step.

   $\dfrac{0 + 2 \cdot 3 + 2 \cdot 3 + 6}{6} = \dfrac{18}{6} = 3, \qquad y_1 = 0 + 2 \times 3 = 6$

   Simpson's weights $1, 2, 2, 1$.

5. Compare with the exact solution.

   $y = \tfrac{3}{2}x^{2} \quad\Rightarrow\quad y(2) = \tfrac{3}{2} \times 4 = 6$

   Exactly right, not by luck: with $f$ independent of $y$ the step is Simpson's rule, exact for cubics.

15. A full Runge-Kutta step on $y' = x + y$

1. Take $y' = x + y$, $y(0) = 1$, $h = 0.2$. First slope, at the start.

   $k_1 = f(0, 1) = 0 + 1 = 1$

   Both coordinates enter the slope.

2. Second slope: half a step along $k_1$, to $x = 0.1$.

   $k_2 = f(0.1,\ 1 + 0.1 \times 1) = f(0.1, 1.1) = 0.1 + 1.1 = 1.2$

   $\frac{h}{2} = 0.1$ moves both $x$ and the trial $y$.

3. Third slope: half a step along $k_2$, again at $x = 0.1$.

   $k_3 = f(0.1,\ 1 + 0.1 \times 1.2) = f(0.1, 1.12) = 1.22$

   The same midpoint with a better trial value.

4. Fourth slope: a full step along $k_3$, to $x = 0.2$.

   $k_4 = f(0.2,\ 1 + 0.2 \times 1.22) = f(0.2, 1.244) = 1.444$

   The full step uses $h = 0.2$.

5. Form the weighted average.

   $\dfrac{1 + 2(1.2) + 2(1.22) + 1.444}{6} = \dfrac{1 + 2.4 + 2.44 + 1.444}{6} = \dfrac{7.284}{6} = 1.214$

   Middle slopes counted twice, divided by six.

6. Take the step.

   $y_1 = 1 + 0.2 \times 1.214 = 1.2428$

   One step of the method, four evaluations of $f$.

7. Compare with the exact solution $y = 2e^{x} - x - 1$.

   $y(0.2) = 2 \times 1.221403 - 0.2 - 1 = 1.242806, \qquad \text{error} \approx 0.000006$

   The exact solution comes from the integrating factor, with $C = 2$ from $y(0) = 1$. Euler's step, $1 + 0.2 \times 1 = 1.2$, is out by $0.043$: seven thousand times worse for a quarter of the work.

16. Your turn: one improved Euler step on $y' = x + y$ from $(0, 1)$ with $h = 0.5$

1. Take the Euler trial step.

   $k_1 = f(0, 1) = 0 + 1 = 1, \qquad \tilde{y} = 1 + 0.5 \times 1 = 1.5$

   An Euler step, used only as a probe.

2. Your turn: work this step out. Its working is at the end of the packet.

   Evaluate the slope at the trial point.

3. Your turn: work this step out. Its working is at the end of the packet.

   Average the slopes and take the real step.

17. Guided practice

Match each method to the order of accuracy it achieves.

18. Guided practice

Complete the worked solution: one improved Euler step on $y' = x + y$ from $(0, 7)$ with $h = 1$.

1. Evaluate the slope at the starting point.

   $k_1 = f(0, 7) = 0 + 7 = 7$

   The equation gives the slope at any point you ask it about.

2. Take a trial Euler step of length $h = 1$ along $k_1$.

   $\tilde{y} = 7 + 1 \times k_1 =$ _t

   The trial step is only a probe for the slope at the far end.

3. Evaluate the slope at the trial point $(1, \tilde{y})$.

   $k_2 = f(1, \tilde{y}) = 1 + \tilde{y} =$ _k

   The right-hand side is $x + y$, with $x = 1$ at the far end.

4. Average the two slopes and take the real step from $7$.

   $y_1 = 7 + \dfrac{h}{2}(k_1 + k_2) =$ _y

   Averaging the slopes at both ends cancels the leading error of the Euler step.

19. Guided practice

What order of accuracy does the improved Euler method achieve?

• First order
• Second order
• Fourth order

20. Practice

Take one classical Runge-Kutta step on $y' = 2x$ from $x = 0$, $y = 4$, with step size $h = 2$. Fill in the four slopes and their weighted average.

21. Practice

You are using the classical Runge-Kutta method, which is of order $4$. If you halve the step size, by what factor does the global error fall?

Answer:

22. Practice

A colony of bacteria, in thousands, grows at a rate equal to its size per hour, $y' = y$; a biologist predicts its size two hours ahead with a single Runge-Kutta step. Take one classical Runge-Kutta step on $y' = y$ from $y(0) = 1$ with step size $h = 2$. Fill in the three later slopes and the value the step gives at $x = 2$.

23. Somewhere new

One classical Runge-Kutta step on $y' = 3x$ from $y = 5$ evaluates four slopes. Put them in the order they must be computed.

Number the steps in order (write the number in the box):

• The slope at the current point
• The slope at the midpoint, after half a step along the first
• The slope at the midpoint, after half a step along the second
• The slope at the right end, after a full step along the third

24. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

25. Test question

A colony of bacteria, in thousands, grows at a rate equal to its size per hour, $y' = y$; a biologist predicts its size two hours ahead with a single Runge-Kutta step. Take one classical Runge-Kutta step on $y' = y$ from $y(0) = 1$ with step size $h = 2$. Fill in the three later slopes and the value the step gives at $x = 2$.

26. What you can do now

You can take a Runge-Kutta step by hand and say what order each of these methods achieves. Say in your own words why the trial values computed inside a step are thrown away rather than carried forward.

Working for the steps left to you

16. Your turn: one improved Euler step on $y' = x + y$ from $(0, 1)$ with $h = 0.5$, step 2

16. Your turn: one improved Euler step on $y' = x + y$ from $(0, 1)$ with $h = 0.5$, step 3