Back to the on-screen lesson · Print

Euler's method

Stepping along the tangent the equation hands you, the recurrence that generates the table, and why a global error of order $h$ makes accuracy expensive.

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 Euler's method by hand from an initial condition and a step size, generate the table of values it produces, explain why the local error is of order $h$ squared while the global error is only of order $h$, predict which side of the true solution the answer will fall on from the curvature, and say what step size a demand for a given improvement in accuracy costs.

2. What you already have

From the first lesson of this course you know that $y' = f(x, y)$ hands you a slope at every point of the plane, and that a solution is a curve tangent to that field everywhere. Every method so far has turned that into a formula. Most equations have no formula, and this lesson does the other thing you can do with a field of slopes, which is to walk through it.

3. Words this lesson uses

4. Walking along the tangent

The equation gives the slope at the point you are standing on. So take that slope, walk in a straight line for a short distance $h$, and ask again:

$$y_{n+1} = y_n + h\,f(x_n, y_n), \qquad x_{n+1} = x_n + h.$$

That is Euler's method, and it is the whole of it. No integral is evaluated and nothing is solved; the equation is simply consulted repeatedly.

How wrong is it? Taylor's theorem says

$$y(x_n + h) = y(x_n) + h\,y'(x_n) + \tfrac{1}{2}h^{2}y''(\xi),$$

and Euler keeps the first two terms. So one step, starting exactly, is wrong by about $\tfrac{1}{2}h^{2}y''$ — the local error is of order $h^{2}$.

But covering a fixed interval takes about $1/h$ steps, and the errors do not cancel. Multiplying an error of size $h^{2}$ by $1/h$ of them leaves a global error of order $h$. Euler's method is first order, and that is the number that matters: halving the step only halves the error.

The error also has a direction. On a convex solution the tangent lies below the curve, so every step lands low and the shortfall accumulates. That is a systematic bias, not noise, and it is why the answer can be wrong in a way that looks perfectly smooth and plausible.

5. Local against global, and why the orders differ

It is worth being careful about the two errors, because the difference of one power of $h$ between them is the entire reason Euler is as poor as it is.

The local error is what one step costs: $O(h^{2})$, by Taylor. A learner who computes that and stops has a very encouraging number — halve the step and one step becomes four times as accurate.

The global error is what the whole journey costs. To cross a fixed interval of length $L$ you take $L/h$ steps, each contributing about $h^{2}$, so the total is about $L h$. Halving the step halves the total, not quarters it: the steps became four times better and there are twice as many of them.

That trade — one power of $h$ lost to the number of steps — is universal. A method whose local error is $O(h^{p+1})$ has global error $O(h^{p})$, and the order of a method always refers to the global figure.

The chart runs Euler with step 0.5 on y' = y from y(0) = 1: each step follows the slope at its start, and the gap to the exact curve widens step by step.

6. Where this goes wrong

Using the exact solution inside the recurrence. Each step starts from the value the previous step produced, errors and all. Substituting the true value at each stage measures the local error only, and produces a table no run of the method would ever generate.

Rounding the intermediate values. The interesting error here is truncation, which exists in perfect arithmetic; rounding on top of it makes the two impossible to separate. Carry exact numbers where you can.

Believing a smooth answer. Euler's output is always smooth and always plausible, whether or not the step size was sane. Smoothness is not evidence.

Expecting a small step to fix everything. Beyond the accuracy question there is a stability question, which the last lesson of this unit is about, and on some problems it is the binding constraint.

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

Euler's method replaces the curve by a sequence of short straight segments, each following the slope the equation gives at its starting point.

1. Set up. Write $f(x, y)$, the starting point $(x_0, y_0)$, the step $h$, and the number of steps $\frac{X - x_0}{h}$ needed to reach the target $X$.
2. Slope. Evaluate $f(x_n, y_n)$ at the current point, using both coordinates.
3. Step. $y_{n + 1} = y_n + h\,f(x_n, y_n)$ and $x_{n + 1} = x_n + h$.
4. Repeat from the new point until $x$ reaches $X$.
5. Record each $(x_n, y_n)$ in a table; the table is the answer, and the last row is the estimate.

Why the step is allowed. Taylor's theorem gives $y(x + h) = y(x) + hy'(x) + \frac{h^{2}}{2}y''(\xi)$, and the equation supplies $y'(x) = f(x, y)$. Euler keeps the first two terms and drops the last, so each step is wrong by about $\frac{h^{2}}{2}y''$: the local error. The sign of $y''$ says which way: when the solution bends up, every step undershoots.

Choosing $h$. Because the global error is roughly proportional to $h$, one run tells you the constant, and the constant tells you the step size a given accuracy needs. Halving $h$ doubles the work and halves the error, which is why better methods, in the next lesson, are worth their extra evaluations.

How to check the answer. Run the method twice, with $h$ and with $\frac{h}{2}$. The two answers should differ by about the error of the second, so their difference is an error estimate you can quote without knowing the exact solution. Check the arithmetic on each row by confirming that the change $y_{n + 1} - y_n$ has the sign of the slope at $(x_n, y_n)$. When an exact solution is available, compare with it and check that the error has the sign the curvature predicts.

8. In the world: every spreadsheet forecast is Euler's method

A spreadsheet that projects a loan balance month by month is running Euler's method, usually without saying so. A balance $B$ at an annual interest rate $r$, repaid at $P$ a year, obeys $B' = rB - P$. A monthly spreadsheet takes $h = \frac{1}{12}$ of a year and computes each row from the last: $B_{n + 1} = B_n + \frac{1}{12}(rB_n - P)$.

With $B_0 = 10\,000$, $r = 0.06$ and payments of $200$ a month, $P = 2400$ a year: $B_1 = 10\,000 + \frac{1}{12}(600 - 2400) = 10\,000 - 150 = 9850$. The next row takes the interest on $9850$, and so on. For a loan this is not an approximation at all, because the bank really does compute interest monthly: the discrete steps are the true process, and the differential equation is the approximation to them.

For a population, a temperature or a spreading infection the reverse holds: the process is continuous, and a daily or weekly spreadsheet is Euler's method with a large step, carrying an error that grows over the forecast. That is why epidemic forecasts made in spreadsheets drift from those made with proper solvers over weeks, and why the global error of this lesson, proportional to $h$, is worth knowing before trusting a long forecast.

9. In the world: physics in a video game

A video game moves every object sixty times a second, and the simplest physics engines use Euler steps with $h = \frac{1}{60}$ of a second. For an object falling from rest under gravity, the velocity update $v_{n + 1} = v_n - gh$ is exact, because the acceleration is constant. The position update $y_{n + 1} = y_n + v_nh$ is not: it uses the velocity at the start of each frame, which is always too slow.

After one second, sixty frames, the Euler position is $-gh^{2}(0 + 1 + \dots + 59) = -9.8 \times \frac{1}{3600} \times 1770 \approx -4.818$ metres, while the true fall is $\frac{1}{2}g = 4.9$ metres. The error, $0.082$ metres, is exactly $\frac{gh}{2}$ per second of fall, first order in $h$, as this lesson predicts. Games hide it by updating the velocity first and then using the new velocity for the position, a one-line change called the semi-implicit Euler method, which is also far more stable for springs and orbits. The choice between the two is a question of this unit's last lessons: accuracy per step and stability over many steps.

10. In the world: choosing a step before running a simulation

An engineer about to run a long simulation first runs it twice on a short stretch, with $h$ and with $\frac{h}{2}$, and compares. For a first-order method the difference between the two runs is about the error of the second, so it tells them how small $h$ must be for the accuracy they need, and so how long the full run will take. This cheap test, which needs no exact solution, is the everyday use of the order of a method.

11. A smaller step is not the same kind of improvement as a better method

Because Euler is so easy to run, it is tempting to treat accuracy as a dial: unhappy with the answer, shrink the step. The arithmetic of the order says what that dial actually costs. Euler is first order, so each extra decimal place of accuracy costs ten times as many steps and ten times as many evaluations of the right-hand side; three more decimal places costs a thousand. A fourth-order method buys the same decimal place for about $1.8$ times as many steps. The second, quieter error is to confuse the two kinds of error: shrinking $h$ reduces truncation error and eventually increases the damage done by rounding, because there are more operations to round, so past some step size the answer stops improving and starts getting worse. The fix for a bad answer is usually a better method, not a smaller step.

12. Two steps, by hand, against the exact answer

1. Take $y' = y$, $y(0) = 1$, $h = 0.5$. Evaluate the slope at the start.

   $f(0, 1) = 1$

   The equation gives the slope at the current point; nothing else is used.

2. Take the first step along that slope.

   $y_1 = 1 + 0.5 \times 1 = 1.5 \ \text{at}\ x = 0.5$

   One consultation of the equation per step: $y_{n + 1} = y_n + hf(x_n, y_n)$.

3. Evaluate the slope at the new point.

   $f(0.5, 1.5) = 1.5$

   The step uses the value just produced, not the true one.

4. Take the second step.

   $y_2 = 1.5 + 0.5 \times 1.5 = 1.5 + 0.75 = 2.25 \ \text{at}\ x = 1$

   Each step multiplies by $1 + h = 1.5$ for this equation.

5. Compare with the exact answer.

   $e^{1} = 2.718\ldots, \qquad 2.718 - 2.25 = 0.468 \approx 17\%$

   The bias is systematic: every step took the slope at the left of an interval where the solution was steepening.

13. Halving the step, twice

1. On $[0, 1]$ with $h = 0.5$, Euler multiplies by $1.5$ twice.

   $1.5^{2} = 2.25, \qquad \text{error} = 2.718 - 2.25 = 0.468$

   For $y' = y$ each step multiplies by $1 + h$, so $n$ steps give $(1 + h)^{n}$.

2. Halve the step to $h = 0.25$: four steps.

   $1.25^{4} = 2.441, \qquad \text{error} = 2.718 - 2.441 = 0.277$

   Twice as many steps, each better.

3. Halve it again to $h = 0.125$: eight steps.

   $1.125^{8} = 2.566, \qquad \text{error} = 2.718 - 2.566 = 0.152$

   The same calculation with eight factors.

4. Compare successive errors.

   $\dfrac{0.277}{0.468} \approx 0.59, \qquad \dfrac{0.152}{0.277} \approx 0.55$

   Each halving of $h$ roughly halves the error, and the ratio approaches $\frac{1}{2}$ as $h$ shrinks.

5. Use the order to predict the cost of an error of $0.01$.

   $\text{error} \approx 1.2h \quad\Rightarrow\quad h \approx \dfrac{0.01}{1.2} \approx 0.008, \ \text{about } 120 \text{ steps}$

   From $0.152 \approx C \times 0.125$, $C \approx 1.2$. First order makes accuracy expensive: the order is a price list.

14. An equation with $x$ in it, checked against its solution

1. Take $y' = x - y$, $y(0) = 1$, $h = 0.1$. Evaluate the slope at the start.

   $f(0, 1) = 0 - 1 = -1$

   The slope needs both coordinates now.

2. Take the first step.

   $y_1 = 1 + 0.1 \times (-1) = 0.9 \ \text{at}\ x_1 = 0.1$

   A negative slope takes the value down.

3. Evaluate the slope at $(0.1, 0.9)$.

   $f(0.1, 0.9) = 0.1 - 0.9 = -0.8$

   The $x$ coordinate has moved on to $0.1$, and it enters the slope.

4. Take the second step.

   $y_2 = 0.9 + 0.1 \times (-0.8) = 0.9 - 0.08 = 0.82 \ \text{at}\ x_2 = 0.2$

   Two steps reach $x = 0.2$.

5. Find the exact solution by the integrating factor.

   $y' + y = x \;\Rightarrow\; (e^{x}y)' = xe^{x} \;\Rightarrow\; e^{x}y = (x - 1)e^{x} + C, \quad C = 2 \;\Rightarrow\; y = x - 1 + 2e^{-x}$

   Integration by parts gives $\int xe^{x}\,dx = (x - 1)e^{x}$; $y(0) = 1$ gives $-1 + C = 1$.

6. Evaluate the exact solution at $x = 0.2$.

   $y(0.2) = 0.2 - 1 + 2e^{-0.2} = -0.8 + 2 \times 0.81873 = 0.83746$

   $e^{-0.2} \approx 0.81873$.

7. Compare, and read the sign of the error.

   $0.83746 - 0.82 = 0.01746$

   Euler is below again: $y'' = 1 - y' = 1 - x + y > 0$ here, so the solution bends upward and the left-end slope undershoots.

15. Your turn: two Euler steps on $y' = x + y$ with $y(0) = 1$ and $h = 0.5$

1. Evaluate the slope at $(0, 1)$ and step.

   $f(0, 1) = 0 + 1 = 1, \qquad y_1 = 1 + 0.5 \times 1 = 1.5$

   Both coordinates go into the right-hand side now.

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

   Evaluate the slope at $(0.5, 1.5)$ and step.

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

   Compare with the exact solution.

16. Guided practice

Put one step of Euler's method for $y' = 4y$, $y(0) = 2$, into the order it must be carried out.

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

• Evaluate the slope at the current point
• Multiply the slope by the step size
• Add that to the current value of $y$
• Advance $x$ by the step size
• Repeat from the new point

17. Guided practice

Complete the worked solution: two Euler steps on $y' = y$ with $y(0) = 3$ and $h = 0.5$.

1. Evaluate the slope at the starting point $(0, 3)$.

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

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

2. Multiply the slope by the step size to get the rise.

   $h \cdot f = 0.5 \times 3 = 1.5$

   A rate times a run is a rise.

3. Add the rise to the current value.

   $y_1 = 3 + 1.5 =$ _p

   The new value is the old value plus the rise, at $x = 0.5$.

4. Repeat from the new point: slope times step size, added to $y_1$.

   $y_2 = y_1 + 0.5 \times y_1 = y_1 \times 1.5 =$ _q

   The slope is re-evaluated at the new point, so the second step multiplies what the first produced.

18. Guided practice

Euler's method on $y' = y$ with $y(0) = 3$ returns values below the true solution at every step. Why?

• The tangent at the left end lies below a curve that bends upward, so each step lands low
• Rounding in the arithmetic happens to accumulate downward
• The direction of the error is random and this run happened to fall low
• The method evaluates the slope at the right-hand end of each step

19. Practice

Apply Euler's method to $y' = 4y$ with $y(0) = 1$ and step size $h = 0.5$. Fill in the value after each step.

20. Practice

Euler's method is applied to $y' = 3y$ with $y(0) = 6$ and step size $h = 0.5$. What is the value after two steps?

Answer:

21. Practice

A culture of bacteria, in millions, is fed a nutrient supply that increases steadily, so its size after $x$ hours obeys $y' = x + y$, and a lab spreadsheet forecasts it in half-hour steps. Apply Euler's method to $y' = x + y$ with $y(0) = 1$ and step size $h = 0.5$. Fill in the value after each of the three steps that reach $x = 1.5$.

22. Somewhere new

A run of Euler's method uses step size $h = 0.25$. You need the global error to come out $10$ times smaller. What step size does that take?

Answer:

23. Lesson test

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

24. Test question

A culture of bacteria, in millions, is fed a nutrient supply that increases steadily, so its size after $x$ hours obeys $y' = x + y$, and a lab spreadsheet forecasts it in half-hour steps. Apply Euler's method to $y' = x + y$ with $y(0) = 2$ and step size $h = 0.5$. Fill in the value after each of the three steps that reach $x = 1.5$.

25. What you can do now

You can run Euler's method by hand, say what its order is, and price the step size that a better answer would take. Say in your own words why the local and global errors differ by one power of the step size.

Working for the steps left to you

15. Your turn: two Euler steps on $y' = x + y$ with $y(0) = 1$ and $h = 0.5$, step 2

15. Your turn: two Euler steps on $y' = x + y$ with $y(0) = 1$ and $h = 0.5$, step 3