For integrating with respect to the Euler characteristic, see
Euler calculus. For Euler's method for factorizing an integer, see
Euler's factorization method.
In mathematics and computational science, the Euler method is a firstorder 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).^{[1]}
The Euler method is a firstorder 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 complicated methods.
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\backslash 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.^{[2]}
Formulation of the method
Suppose that we want to approximate the solution of the initial value problem
 $y\text{'}(t)\; =\; f(t,y(t)),\; \backslash qquad\; \backslash 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^{[3]}
 $y\_\{n+1\}\; =\; y\_n\; +\; hf(t\_n,y\_n).$
The value of $y\_n$ is an approximation of the solution to the ODE at time $t\_n$: $y\_n\; \backslash 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\; \backslash leq\; n$.
While the Euler method integrates a firstorder ODE, any ODE of order N can be represented as a firstorder ODE:
to treat the equation
 $y^\{(N)\}(t)\; =\; f(t,\; y(t),\; y\text{'}(t),\; \backslash ldots,\; y^\{(N1)\}(t))$,
we introduce auxiliary variables $z\_1(t)=y(t),\; z\_2(t)=y\text{'}(t),\backslash ldots,\; z\_N(t)=y^\{(N1)\}(t)$ and obtain
the equivalent equation
 $\backslash mathbf\{z\}\text{'}(t)$
= \begin{pmatrix} z_1'(t)\\ \vdots\\ z_{N1}'(t)\\ z_N'(t) \end{pmatrix}
= \begin{pmatrix} y'(t)\\ \vdots\\ y^{(N1)}(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 firstorder system in the variable $\backslash mathbf\{z\}(t)$ and can be handled by Euler's method or, in fact, by any other scheme for firstorder systems.^{[4]}
Example
Given the initial value problem
 $y\text{'}=y,\; \backslash quad\; y(0)=1,$
we would like to use the Euler method to approximate $y(4)$.^{[5]}
Using step size equal to 1 (h = 1)
The Euler method is
 $y\_\{n+1\}\; =\; y\_n\; +\; hf(t\_n,y\_n).\; \backslash qquad\; \backslash 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.\; \backslash qquad\; \backslash 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 $\backslash Delta\; y/\; \backslash Delta\; t$.
The next step is to multiply the above value by the step size $h$, which we take equal to one here:
 $h\; \backslash cdot\; f(y\_0)\; =\; 1\; \backslash cdot\; 1\; =\; 1.\; \backslash qquad\; \backslash 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\; \backslash cdot\; 1\; =\; 2.\; \backslash qquad\; \backslash qquad$
The above steps should be repeated to find $y\_2$, $y\_3$ and $y\_4$.
 $\backslash 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, \\
y_4 &= y_3 + hf(y_3) = 8 + 1 \cdot 8 = 16.
\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$ 
$\backslash 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

3 
8 
3 
8 
1 
8 
16

The conclusion of this computation is that $y\_4\; =\; 16$. The exact solution of the differential equation is $y(t)\; =\; e^t$, so $y(4)\; =\; e^4\; \backslash approx\; 54.598$. Thus, the approximation of the Euler method is not very good in this case. However, as the figure shows, its behaviour is qualitatively right.
Using other step sizes
As suggested in the introduction, the Euler method is more accurate if the step size $h$ 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.
step size 
result of Euler's method 
error

1 
16 
38.598

0.25 
35.53 
19.07

0.1 
45.26 
9.34

0.05 
49.56 
5.04

0.025 
51.98 
2.62

0.0125 
53.26 
1.34

The error recorded in the last column of the table is the difference between the exact solution at $t\; =\; 4$ 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 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 firstorder 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, higherorder methods such as Runge–Kutta methods or linear multistep methods, especially if a high accuracy is desired.^{[6]}
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\text{'}(t\_0)\; +\; \backslash frac\{1\}\{2\}h^2\; y$(t_0) + O(h^3).
The differential equation states that $y\text{'}=f(t,y)$. If this is substituted in the Taylor expansion and the quadratic and higherorder terms are ignored, the Euler method arises.^{[7]} 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\text{'}(t\_0)\; \backslash approx\; \backslash frac\{y(t\_0+h)\; \; y(t\_0)\}\{h\}$
in the differential equation $y\text{'}\; =\; f(t,y)$. Again, this yields the Euler method.^{[8]} A similar computation leads to the midpoint rule and the backward Euler method.
Finally, one 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)\; =\; \backslash int\_\{t\_0\}^\{t\_0+h\}\; f(t,y(t))\; \backslash ,\backslash mathrm\{d\}t.$
Now approximate the integral by the lefthand rectangle method (with only one rectangle):
 $\backslash int\_\{t\_0\}^\{t\_0+h\}\; f(t,y(t))\; \backslash ,\backslash mathrm\{d\}t\; \backslash approx\; h\; f(t\_0,\; y(t\_0)).$
Combining both equations, one finds again the Euler method.^{[9]} 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).\; \backslash 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\text{'}(t\_0)\; +\; \backslash 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:
 $\backslash mathrm\{LTE\}\; =\; y(t\_0\; +\; h)\; \; y\_1\; =\; \backslash frac\{1\}\{2\}\; h^2\; y$(t_0) + O(h^3).
This result is valid if $y$ has a bounded third derivative.^{[10]}
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 higherorder techniques such as RungeKutta 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 truncation 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 $\backslash xi\; \backslash in\; [t\_0,t\_0+h]$ such that
 $\backslash mathrm\{LTE\}\; =\; y(t\_0\; +\; h)\; \; y\_1\; =\; \backslash frac\{1\}\{2\}\; h^2\; y$(\xi). ^{[11]}
In the above expressions for the error, the second derivative of the unknown exact solution $y$ can be replaced by an expression involving the righthand side of the differential equation. Indeed, it follows from the equation $y\text{'}=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)).^{[12]}
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.^{[13]} The number of steps is easily determined to be $(tt\_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$.^{[14]}
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) is bounded by
 $\backslash text\{GTE\}\; \backslash le\; \backslash frac\{hM\}\{2L\}(e^\{L(tt\_0)\}1)\; \backslash qquad\; \backslash 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$.^{[15]}
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.^{[16]} 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.^{[17]}
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
 $y\text{'}\; =\; 2.3y,\; \backslash qquad\; y(0)\; =\; 1.$
The exact solution is $y(t)\; =\; e^\{2.3t\}$, which decays to zero as $t\; \backslash to\; \backslash infty$. However, if the Euler method is applied to this equation with step size $h=1$, then the numerical solution is qualitatively wrong: it oscillates and grows (see the figure). This is what it means to be unstable. If a smaller step size is used, for instance $h=0.7$, then the numerical solution does decay to zero.
If the Euler method is applied to the linear equation $y\text{'}\; =\; k\; y$, then the numerical solution is unstable if the product $hk$ is outside the region
 $\backslash \{\; z\; \backslash in\; \backslash mathbf\{C\}\; \backslash mid\; z+1\; \backslash le\; 1\; \backslash \},$
illustrated on the right. This region is called the (linear) instability region.^{[18]} In the example, $k$ equals −2.3, so if $h=1$ then $hk\; =\; 2.3$ which is outside the stability region, and thus the numerical solution is unstable.
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 εy_{n} 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εy_{0} 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 $\backslash varepsilon\; /\; \backslash sqrt\{h\}$.^{[19]}
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.^{[20]}
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:
 $y\_\{n+1\}\; =\; y\_n\; +\; h\; f(t\_\{n+1\},\; y\_\{n+1\}).$
This differs from the (standard, or forward) Euler method in that the function $f$ is evaluated at the end point of the step, instead of the starting point. The backward Euler method is an implicit method, meaning that the formula for the backward Euler method has $y\_\{n+1\}$ 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 semiimplicit 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:
 $y\_\{n+1\}\; =\; y\_n\; +\; h\; f\; \backslash Big(\; t\_n\; +\; \backslash tfrac12\; h,\; y\_n\; +\; \backslash tfrac12\; h\; f(t\_n,\; y\_n)\; \backslash Big).$
This leads to the family of Runge–Kutta methods.
The other possibility is to use more past values, as illustrated by the twostep Adams–Bashforth method:
 $y\_\{n+1\}\; =\; y\_n\; +\; \backslash tfrac32\; h\; f(t\_\{n\},\; y\_\{n\})\; \; \backslash tfrac12\; h\; f(t\_\{n1\},\; y\_\{n1\}).$
This leads to the family of linear multistep methods.
See also
Notes
References
External links
 Euler's Method for O.D.E.'s, by John H. Matthews, California State University at Fullerton.
Numerical integration 

 Firstorder methods  

 Secondorder methods  

 Higherorder methods  


This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.