Euler method

In mathematics and computational science, the Euler method, named after Leonhard Euler, is a first order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. It is the most basic kind of explicit method for numerical integration for ordinary differential equations.

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.$ 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\_3dots$ 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 (although things are more complicated for stiff equations, as discussed below).

Derivation

We want to approximate the solution of the initial value problem:$y\text{'}(t)\; =\; f(t,y(t)),\; qquad\; qquad\; y(t\_0)=y\_0,$

by using the first two terms of the Taylor expansion of "y", which represents the linear approximation around the point (t₀,y(t₀)) . 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 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 in more than one variable by introducing $N-1$ further variables, $y\text{'}$, $y"$, ..., $y^\{(N)\}$, and formulating $N$ first order equations in these new variables. The Euler method can be applied to the vector $mathbf\{y\}(t)=(y(t),y\text{'}(t),y"(t),...,y^\{(N)\}(t))$ to integrate the higher-order system.

Error

The magnitude of the errors arising from the Euler method can be demonstrated by comparison with a Taylor expansion of "y". If we assume that $f(t)$ and $y(t)$ are known exactly at a time $t\_0,$ then the Euler method gives the approximate solution at time $t\_0+h$ as:

:$y(t\_0\; +\; h)\; =\; y(t\_0)\; +\; h\; f(t\_0,y(t\_0))\; =\; y(t\_0)\; +\; h\; y\text{'}(t\_0)\; ,\; qquad\; qquad$

(the second equality holds because "y" satisfies the differential equation $y\text{'}=f(t,\; y)$). In comparison, the Taylor expansion in $h$ about $t\_0$ gives:

:$y(t\_0\; +\; h)\; =\; y(t\_0)\; +\; h\; y\text{'}(t\_0)\; +\; frac\{1\}\{2\}h^2\; y"(t\_0)\; +\; O(h^3).$

The error introduced by the Euler method is given by the difference between these equations:

:$frac\{1\}\{2\}h^2\; y"(t\_0)\; +\; O(h^3).$

For small $h$, the dominant error per step is proportional to $h^2$. To solve the problem over a given range of $t$, the number of steps needed is proportional to $1/h$ so it is to be expected that the total error at the end of the fixed time will be proportional to $h$ (error per step times number of steps). For this reason, the Euler method is said to be first order. This makes the Euler method less accurate (for small $h$) than other higher-order techniques such as Runge-Kutta methods and linear multistep methods.

The Euler method can also be numerically unstable, especially for stiff equations. 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.

ee also

*Numerical integration of 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

External links

* [http://www.krellinst.org/UCES/archive/classes/CNA/dir2.4/uces2.4.html Initial Value Problems: Euler’s Method]
* [http://math.fullerton.edu/mathews/n2003/Euler'sMethodMod.html Euler's Method for O.D.E.'s]

References

* Ascher, Uri M.; Petzold, Linda Ruth. Computer methods for ordinary differential equations and differential-algebraic equations. 1998. SIAM. ISBN 0898714125