![]() | ||
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).
Contents
- Informal geometrical description
- Example
- Using step size equal to 1 h 1
- Using other step sizes
- Derivation
- Local truncation error
- Global truncation error
- Numerical stability
- Rounding errors
- Modifications and extensions
- In popular culture
- References
The Euler method is a first-order method, which means that the local error (error per step) is proportional to the square of the step size, and the global error (error at a given time) is proportional to the step size. The Euler method often serves as the basis to construct more complex methods, e.g., predictor–corrector method.
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
Take a small step along that tangent line up to a point
Choose a value
The value of
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
we introduce auxiliary variables
This is a first-order system in the variable
Example
Given the initial value problem
we would like to use the Euler method to approximate
Using step size equal to 1 (h = 1)
The Euler method is
so first we must compute
By doing the above step, we have found the slope of the line that is tangent to the solution curve at the point
The next step is to multiply the above value by the step size
Since the step size is the change in
The above steps should be repeated to find
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.
The conclusion of this computation is that
Using other step sizes
As suggested in the introduction, the Euler method is more accurate if the step size
The error recorded in the last column of the table is the difference between the exact solution at
Other methods, such as the midpoint method also illustrated in the figures, behave more favorably: the error of the midpoint method is roughly proportional to the square of the step size. For this reason, the Euler method is said to be a first-order method, while the midpoint method is second order.
We can extrapolate from the above table that the step size needed to get an answer that is correct to three decimal places is approximately 0.00001, meaning that we need 400,000 steps. This large number of steps entails a high computational cost. For this reason, people usually employ alternative, higher-order methods such as Runge–Kutta methods or linear multistep methods, especially if a high accuracy is desired.
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
The differential equation states that
A closely related derivation is to substitute the forward finite difference formula for the derivative,
in the differential equation
Finally, one can integrate the differential equation from
Now approximate the integral by the left-hand rectangle method (with only one rectangle):
Combining both equations, one finds 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,
For the exact solution, we use the Taylor expansion mentioned in the section Derivation above:
The local truncation error (LTE) introduced by the Euler method is given by the difference between these equations:
This result is valid if
This shows that for small
A slightly different formulation for the local truncation error can be obtained by using the Lagrange form for the remainder term in Taylor's theorem. If
In the above expressions for the error, the second derivative of the unknown exact solution
Global truncation error
The global truncation error is the error at a fixed time
This intuitive reasoning can be made precise. If the solution
where
The precise form of this bound is 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
Numerical stability
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. This can be illustrated using the linear equation
The exact solution is
If the Euler method is applied to the linear equation
illustrated on the right. This region is called the (linear) instability region. In the example,
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.
Rounding errors
The discussion up to now has ignored the consequences of rounding error. In step n of the Euler method, the rounding error is roughly of the magnitude εyn where ε is the machine epsilon. Assuming that the rounding errors are all of approximately the same size, the combined rounding error in N steps is roughly Nεy0 if all errors points in the same direction. Since the number of steps is inversely proportional to the step size h, the total rounding error is proportional to ε / h. In reality, however, it is extremely unlikely that all rounding errors point in the same direction. If instead it is assumed that the rounding errors are independent rounding variables, then the total rounding error is proportional to
Thus, for extremely small values of the step size, the truncation error will be small but the effect of rounding error may be big. Most of the effect of rounding error can be easily avoided if compensated summation is used in the formula for the Euler method.
Modifications and extensions
A simple modification of the Euler method which eliminates the stability problems noted in the previous section is the backward Euler method:
This differs from the (standard, or forward) Euler method in that the function
Other modifications of the Euler method that help with stability yield the exponential Euler method or the semi-implicit Euler method.
More complicated methods can achieve a higher order (and more accuracy). One possibility is to use more function evaluations. This is illustrated by the midpoint method which is already mentioned in this article:
This leads to the family of Runge–Kutta methods.
The other possibility is to use more past values, as illustrated by the two-step Adams–Bashforth method:
This leads to the family of linear multistep methods.
In popular culture
In the film Hidden Figures, Katherine Johnson resorts to Euler's method in figuring out how to get astronaut John Glenn back down from orbit.