↑ arvau

Wikipedia / Euler method

In mathematics and computational science, the Euler method (also called the forward 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 first proposed it in his book Institutionum calculi integralis (published 1768–1770).

The Euler method is a first-order method, which means that the 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.

Geometrical description

Purpose and why it works

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.

can be computed, and so, the tangent line.

above can be used. After several steps, a polygonal curve) 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.

First-order process

:

. The Euler method is explicit.

Higher-order process

defined as

, we implement the following formula until we reach the approximation of the solution to the ODE at the desired time:

These first-order systems can be handled by Euler's method or, in fact, by any other scheme for first-order systems.

First-order example

Given the initial value problem

.

Using step size equal to 1 (h = 1)

The Euler method is

. We have

.

, which we take equal to one here:

value to obtain the next value to be used for computations.

.

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., its behaviour is qualitatively correct as the figure shows.

Using other step sizes

is smaller. The table below shows the result with different step sizes. The top row corresponds to the example in the previous section, and the second row is illustrated in the figure. and the Euler approximation. In the bottom of the table, the step size is half the step size in the previous row, and the error is also approximately half the error in the previous row. This suggests that the error is roughly proportional to the step size, at least for fairly small values of the step size. This is true in general, also for other equations; see the section Global truncation error for more details.

Other methods, such as the midpoint method also illustrated in the figures, behave more favourably: the global 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, higher-order methods are employed such as Runge–Kutta methods or linear multistep methods, especially if a high accuracy is desired.

Higher-order example

For this third-order example, assume that the following information is given:

From this we can isolate y to get the equation:

desired.

Derivation

The Euler method can be derived in a number of ways.

This line of thought can be continued to arrive at various linear multistep methods.

Local truncation error

The local truncation error. The numerical solution is given by

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:

has a bounded third derivative.

. This makes the Euler method less accurate than higher-order techniques such as Runge–Kutta methods and linear multistep methods, for which the local truncation error is proportional to a higher power of the step size.

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 such that

that

Global truncation error

The global truncation error, after however many steps the method 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..

is Lipschitz continuous) is bounded by

. variable.

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.. For this reason, the Euler method is said to be first order.

Example

Thus we can find the error bound at t=2.5 and h=0.5:

Notice that t0.

Numerical stability

The Euler method can also be numerically unstable, especially for stiff equations, then the numerical solution does decay to zero.

illustrated on the right. This region is called the (linear) stability region. which is outside the stability region, and thus the numerical solution is unstable.

— means that the Euler method is not often used, except as a simple example of numerical integration. Frequently models of physical systems contain terms representing fast-decaying elements (i.e. with large negative exponential arguments). Even when these are not of interest in the overall solution, the instability they can induce means that an exceptionally small timestep would be required if the Euler method is used.

Rounding errors

of the Euler method, the rounding error is the machine epsilon. 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 above is the backward Euler method is evaluated at the end point of the step, instead of the starting point. The backward Euler method is an implicit method on both sides, so when applying the backward Euler method we have to solve an equation. This makes the implementation more costly.

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 This leads to the family of Runge–Kutta methods.

This leads to the family of linear multistep methods. There are other modifications which uses techniques from compressive sensing to minimize memory usage

In the film Hidden Figures, Katherine Johnson resorts to the Euler method in calculating the re-entry of astronaut John Glenn from Earth orbit.

See also

Notes

References