Euler method
In mathematics and computational science, the Euler method (also called 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 treated it in his book "Institutionum calculi integralis" (published 1768–1870). 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 formula_1 is known (see the picture on top right). Then, from the differential equation, the slope to the curve at formula_2 can be computed, and so, the tangent line. Take a small step along that tangent line up to a point formula_3 Along this small step, the slope does not change too much, so formula_4 will be close to the curve. If we pretend that formula_4 is still on the curve, the same reasoning as for the point formula_2 above can be used. After several steps, a  polygonal curve formula_7 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: Choose a value formula_9 for the size of every step and set formula_10. Now, one step of the Euler method from formula_11 to formula_12 is: The value of formula_14 is an approximation of the solution to the ODE at time formula_11: formula_16. The Euler method is explicit, i.e. the solution formula_17 is an explicit function of  formula_18 for formula_19. While the Euler method integrates a first-order ODE, any ODE of order "N" can be represented as a system of first-order ODEs: to treat the equation we introduce auxiliary variables formula_21 and obtain the equivalent equation: This is a first-order system in the variable formula_23 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 we would like to use the Euler method to approximate formula_25. Using step size equal to 1 ("h" = 1). The Euler method is  so first we must compute formula_27. In this simple differential equation, the function formula_28 is defined by formula_29. We have By doing the above step, we have found the slope of the line that is tangent to the solution curve at the point formula_31. Recall that the slope is defined as the change in formula_32 divided by the change in formula_33, or formula_34. The next step is to multiply the above value by the step size formula_9, which we take equal to one here: Since the step size is the change in formula_33, when we multiply the step size and  the slope of the tangent, we get a change in formula_32 value. This value is then added to the initial formula_32 value to obtain the next value to be used for computations. The above steps should be repeated to find formula_41, formula_42 and formula_43. 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 formula_45. The exact solution of the differential equation is formula_46, so formula_47. Although the approximation of the Euler method was not very precise  in this specific case, particularly due to a large value step size formula_9, its behaviour is qualitatively correct as the figure shows. Using other step sizes. As suggested in the introduction, the Euler method is more accurate if the step size formula_9 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. The error recorded in the last column of the table is the difference between the exact solution at formula_50 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. Derivation. The Euler method can be derived in a number of ways. Firstly , there is the geometrical description above. Another possibility is to consider the Taylor expansion of the function formula_32 around formula_52: The differential equation states that formula_54. 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, in the differential equation formula_56. Again, this yields the Euler method. A similar  computation leads to the midpoint method and the backward Euler method. Finally, one can integrate the differential equation from formula_52 to formula_58 and apply the fundamental theorem of calculus to get: 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 the error made in a single step. It is the difference between the numerical solution after one step, formula_61, and  the exact solution at time formula_62. 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: This result is valid if formula_32 has a bounded third derivative. This shows that for small formula_9, the local truncation error is approximately proportional to formula_68. This makes the Euler method less accurate (for small formula_9) than other 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. If formula_32 has a continuous second derivative, then there exists a formula_71 such that In the above expressions for the error, the second derivative of the unknown exact solution formula_32 can be replaced by an expression involving the right-hand side of the differential equation. Indeed, it follows from the equation formula_54 that Global truncation error. The global truncation error is the error at  a fixed time formula_33, 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 formula_77, which is proportional to formula_78, and the error committed in each step is proportional to formula_68 (see the previous section). Thus, it is to be expected that the global truncation error will be proportional to formula_9. This intuitive reasoning can be made precise. If the solution formula_32 has a bounded second derivative  and formula_28 is Lipschitz continuous in its second argument, then the global truncation error (GTE) is bounded by where formula_84 is an upper bound on the second derivative of formula_32 on the given interval and formula_86 is the Lipschitz constant of formula_28. 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 formula_9. For this reason, the Euler method is said to be first order. 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 formula_90, which decays to zero as formula_91. However, if the Euler method is applied to this equation with step size formula_92, 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 formula_93, then the numerical solution does decay to  zero. If the Euler method is applied to the linear equation formula_94, then the numerical solution is unstable if the product formula_95 is outside the region illustrated on the right. This region is called the (linear) "stability region". In the example, formula_97 is −2.3, so if formula_98 then formula_99 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. In step "n" of the Euler method, the  rounding error is roughly of the magnitude ε"y" where ε is the machine epsilon. Assuming that the rounding errors are independent random variables, the expected total rounding error is proportional to formula_100. 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: This differs from the (standard, or forward) Euler method in that the function formula_28 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 formula_103 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 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. There are other modifications which uses techniques from compressive sensing to minimize memory usage In popular culture. In the film "Hidden Figures", Katherine Goble resorts to the Euler method in calculating the re-entry of astronaut John Glenn from Earth  orbit.