Euler method

For integrating with respect to the Euler characteristic, see Euler calculus. For Euler's method for factorizing an integer, see Euler's factorization method.

Illustration of the Euler method. The unknown curve is in blue, and its polygonal approximation is in red.

In mathematics and computational science, the Euler method is a first-order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. It is the most basic explicit method for numerical integration of ordinary differential equations and is the simplest Runge–Kutta method. The Euler method is named after Leonhard Euler, who treated it in his book Institutionum calculi integralis (published 1768–70).

Informal geometrical description

Consider the problem of calculating the shape of an unknown curve which starts at a given point and satisfies a given differential equation. Here, a differential equation can be thought of as a formula by which the slope of the tangent line to the curve can be computed at any point on the curve, once the position of that point has been calculated.

The idea is that while the curve is initially unknown, its starting point, which we denote by $A_0,$ is known (see the picture on top right). Then, from the differential equation, the slope to the curve at $A_0$ can be computed, and so, the tangent line.

Take a small step along that tangent line up to a point $A_1.$ Along this small step, the slope does not change too much, so $A_1$ will be close to the curve. If we pretend that $A_1$ is still on the curve, the same reasoning as for the point $A_0$ above can be used. After several steps, a polygonal curve $A_0A_1A_2A_3\dots$ is computed. In general, this curve does not diverge too far from the original unknown curve, and the error between the two curves can be made small if the step size is small enough and the interval of computation is finite.

Formulation of the method

Illustration of numerical integration for the equation $y'=y, y(0)=1.$ Blue is the Euler method; green, the midpoint method; red, the exact solution, $y=e^t.$ The step size is h = 1.0.

The same illustration for h = 0.25. It is seen that the midpoint method converges faster than the Euler method.

Suppose that we want to approximate the solution of the initial value problem

$y'(t) = f(t,y(t)), \qquad \qquad y(t_0)=y_0.$

Choose a value $h$ for the size of every step and set $t_n = t_0 + nh$. Now, one step of the Euler method from t_n to t_n+1 = t_n + h is

$y_{n+1} = y_n + hf(t_n,y_n). \qquad \qquad$

The value of $y_n$ is an approximation of the solution to the ODE at time $t_n$: $y_n \approx y(t_n)$. The Euler method is explicit, i.e. the solution $y_{n+1}$ is an explicit function of $y_i$ for $i \leq n$.

While the Euler method integrates a first-order ODE, any ODE of order N can be represented as a first-order ODE: to treat the equation

$y^{(N)}(t) = f(t, y(t), y'(t), \ldots, y^{(N-1)}(t))$,

we introduce auxiliary variables $z_1(t)=y(t), z_2(t)=y'(t),\ldots, z_N(t)=y^{(N-1)}(t)$ and obtain the equivalent equation

$\mathbf{z}'(t) = \begin{pmatrix} z_1'(t)\\ \vdots\\ z_{N-1}'(t)\\ z_N'(t) \end{pmatrix} = \begin{pmatrix} y'(t)\\ \vdots\\ y^{(N-1)}(t)\\ y^{(N)}(t) \end{pmatrix} = \begin{pmatrix} z_2(t)\\ \vdots\\ z_N(t)\\ f(t,z_1(t),\ldots,z_N(t)) \end{pmatrix}$

This is a first-order system in the variable $\mathbf{z}(t)$ and can be handled by Euler's method or, in fact, by any other scheme for first-order systems.

Example

Given the initial value problem

$y'=y, \quad y(0)=1,$

we would like to use the Euler method to approximate $y(3)$ using step size $h=1$.

The Euler method is

$y_{n+1} = y_n + hf(t_n,y_n). \qquad \qquad$

so first we must compute $f(t_0, y_0)$. In this simple differential equation, the function $f$ is defined by $f(t,y) = y$. We have

$f(t_0,y_0) = f(0,1) = 1. \qquad \qquad$

By doing the above step, we have found the slope of the line that is tangent to the solution curve at the point $(0,1)$. Recall that the slope is defined as the change in $y$ divided by the change in $t$, or $\Delta y/ \Delta t$.

The next step is to multiply the above value by the step size $h$.

$h \cdot f(y_0) = 1 \cdot 1 = 1. \qquad \qquad$

Since the step size is the change in $t$, when we multiply the step size and the slope of the tangent, we get a change in $y$ value. This value is then added to the initial $y$ value to obtain the next value to be used for computations.

$y_0 + hf(y_0) = y_1 = 1 + 1 \cdot 1 = 2. \qquad \qquad$

The above steps should be repeated to find $y_2$ and $y_3$.

$\begin{align} y_2 &= y_1 + hf(y_1) = 2 + 1 \cdot 2 = 4, \\ y_3 &= y_2 + hf(y_2) = 4 + 1 \cdot 4 = 8. \end{align}$

Due to the repetitive nature of this algorithm, it can be helpful to organize computations in a chart form, as seen below, to avoid making errors.

$n$	$y_n$	$t_n$	$f(t_n,y_n)$	$h$	$\Delta y$	$y_{n+1}$
0	1	0	1	1	1	2
1	2	1	2	1	2	4
2	4	2	4	1	4	8

The conclusion of this computation is that $y_3 = 8$.

Derivation

The Euler method can be derived in a number of ways. Firstly, there is the geometrical description mentioned above.

Another possibility is to consider the Taylor expansion of the function $y$ around $t_0$:

$y(t_0 + h) = y(t_0) + h y'(t_0) + \frac{1}{2}h^2 y''(t_0) + O(h^3).$

The differential equation states that $y'=f(t,y)$. If this is substituted in the Taylor expansion and the quadratic and higher-order terms are ignored, the Euler method arises. The Taylor expansion is used below to analyze the error committed by the Euler method, and it can be extended to produce Runge–Kutta methods.

A closely related derivation is to substitute the forward finite difference formula for the derivative,

$y'(t_0) \approx \frac{y(t_0+h) - y(t_0)}{h}$

in the differential equation $y' = f(t,y)$. Again, this yields the Euler method. A similar compution leads to the midpoint rule and the backward Euler method.

Finally, we can integrate the differential equation from $t_0$ to $t_0 + h$ and apply the fundamental theorem of calculus to get:

$y(t_0+h) - y(t_0) = \int_{t_0}^{t_0+h} f(t,y(t)) \,\mathrm{d}t.$

Now approximate the integral by the left-hand rectangle method (with only one rectangle):

$\int_{t_0}^{t_0+h} f(t,y(t)) \,\mathrm{d}t \approx h f(t_0, y(t_0)).$

Combining both equations, we find again the Euler method. This line of thought can be continued to arrive at various linear multistep methods.

Local truncation error

The local truncation error of the Euler method is error made in a single step. It is the difference between the numerical solution after one step, $y_1$, and the exact solution at time $t_1 = t_0+h$. The numerical solution is given by

$y_1 = y_0 + h f(t_0, y_0)). \quad$

For the exact solution, we use the Taylor expansion mentioned in the section Derivation above:

$y(t_0 + h) = y(t_0) + h y'(t_0) + \frac{1}{2}h^2 y''(t_0) + O(h^3).$

The local truncation error (LTE) introduced by the Euler method is given by the difference between these equations:

$\mathrm{LTE} = y(t_0 + h) - y_1 = \frac{1}{2} h^2 y''(t_0) + O(h^3).$

This result is valid if $y$ has a bounded third derivative.

This shows that for small $h$, the local truncation error is approximately proportional to $h^2$. This makes the Euler method less accurate (for small $h$) than other higher-order techniques such as Runge-Kutta methods and linear multistep methods, for which the local truncation error is proportial to a higher power of the step size.

A slightly different formulation for the local trunction error can be obtained by using the Lagrange form for the remainder term in Taylor's theorem. If $y$ has a continuous second derivative, then there exists a $\xi \in [t_0,t_0+h]$ such that

$\mathrm{LTE} = y(t_0 + h) - y_1 = \frac{1}{2} h^2 y''(\xi).$

In the above expressions for the error, the second derivative of the unknown exact solution $y$ can be replaced by an expression involving the right-hand side of the differential equation. Indeed, it follows from the equation $y'=f(t,y)$ that

$y''(t_0) = {\partial f\over\partial t}(t_0, y(t_0)) + {\partial f\over\partial y}(t_0, y(t_0)) \, f(t_0, y(t_0)).$

Global truncation error

The global truncation error is the error at a fixed time $t$, after however many steps the methods needs to take to reach that time from the initial time. The global truncation error is the cumulative effect of the local truncation errors committed in each step. The number of steps is easily determined to be $(t-t_0)/h$, which is proportional to $1/h$, and the error committed in each step is proportional to $h^2$ (see the previous section). Thus, it is to be expected that the global truncation error will be proportional to $h$.

This intuitive reasoning can be made precise. If the solution $y$ has a bounded second derivative and $f$ is Lipschitz continuous in its second argument, then the global truncation error (GTE) satisfies the bound

$|\text{GTE}| \le \frac{hM}{2L}(e^{L(t-t_0)}-1) \qquad \qquad$

where $M$ is an upper bound on the second derivative of $y$ on the given interval and $L$ is the Lipschitz constant of $f$.

The precise form of this bound of little practical importance, as in most cases the bound vastly overestimates the actual error committed by the Euler method. What is important is that it shows that the global truncation error is (approximately) proportional to $h$. For this reason, the Euler method is said to be first order.

This also suggests that, as stated in the introduction, decreasing the step size can help to make the approximation more accurate and decrease the error between the two curves. The error to three decimal places for the example in the above section (with step size $h=1$) is the following:

$|\text{GTE}| = |e^3 - 8| = 12.086 \qquad \qquad$

When the step size is changed to $h=0.1$ our $y_3$ value becomes $17.449$. The error, then, for step size $h=0.1$ is the following:

$|\text{GTE}| = |e^3 - 17.449| = 2.637 \qquad \qquad$

Although the error has decreased, our approximation is still not particularly accurate. In addition, since the step size decreased with no change in the interval, the number of iterations has increased to thirty. While possible, it is no longer reasonable to do these computations by hand.

As the global error is proportional to $h$, this suggests that in the order of hundred thousand steps are needed to get an answer that is correct to three decimal places. The large number of steps, and thus high computation cost, supports the use of alternative, higher-order methods such as Runge–Kutta methods or linear multistep methods, espectially if a high accuracy is desired.

Numerical stability

The pink disk shows the stability region for the Euler method.

The Euler method can also be numerically unstable, especially for stiff equations, meaning that the numerical solution grows very large for equations where the exact solution does not.

If the Euler method is applied to the linear equation $y' = k y$, then the numerical solution is unstable if the product $hk$ is outside the region

$\{ z \in \mathbf{C} \mid |z+1| \le 1 \},$

illustrated on the right. This region is called the (linear) instability region.

This limitation—along with its slow convergence of error with h—means that the Euler method is not often used, except as a simple example of numerical integration. The instability can be avoided by using the Euler–Cromer algorithm.

See also

• Numerical methods for ordinary differential equations
• For numerical methods for calculating definite integrals, see Numerical integration
• Gradient descent similarly uses finite steps, here to find minima of functions
• Dynamic errors of numerical methods of ODE discretization

References

• Atkinson, Kendall A. (1989), An Introduction to Numerical Analysis (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-50023-0 .
• Ascher, Uri M.; Petzold, Linda R. (1998), Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 978-0-89871-412-8 .
• Butcher, John C. (2003), Numerical Methods for Ordinary Differential Equations, New York: John Wiley & Sons, ISBN 978-0-471-96758-3 .
• Hairer, Ernst; Nørsett, Syvert Paul; Wanner, Gerhard (1993), Solving ordinary differential equations I: Nonstiff problems, Berlin, New York: Springer-Verlag, ISBN 978-3-540-56670-0 .
• Iserles, Arieh (1996), A First Course in the Numerical Analysis of Differential Equations, Cambridge University Press, ISBN 978-0-521-55655-2 
• Stoer, Josef; Bulirsch, Roland (2002), Introduction to Numerical Analysis (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-95452-3 .
• Lakoba, Taras I. (2012), Simple Euler method and its modifications (Lecture notes for MATH334, University of Vermont), http://www.cems.uvm.edu/~lakobati/math337/notes_1.pdf, retrieved 29 February 2012 .

External links

• Euler's Method for O.D.E.'s