Euler’s Method

Euler’s Method Euler’s method is a numerical method for solving initial value problems. Euler’s method is based on the insight that some differential equations (which are the ones we can solve using Euler’s method) provide us with the slope of the function (at all points), while an initial value provides us with a point on the function. Using this information we can approximate the function with a tangent line at the point given by the initial value. As we have seen, the tangent line is only a good approximation over a small interval. Thus, after moving a small interval, we will want to construct a new tangent line. What happens when we move to the new point? Although we know the value of the derivative of the function at the new point, we do not know the exact value of the function. Thus, the best we can do is construct an approximate tangent line, using the actual slope of the function, and an approximation to the value of the function at point of tangency; the approximate value of the function is given by the previous tangent line approximation. Continuing in this fashion, we construct a piecewise-linear approximation to the solution of the differential equation. We can also think of our approximation as a discrete function, which is defined for these approximated points. To make this discrete function a continuous function, we interpolate linearly between each pair of these points (draw a line between them). Before we begin we should emphasize the limitations of Euler’s method are practical, not theoretical. In theory, we should be able to make the distance traveled along each tangent line as short as we like, making the approximation to the actual solution of the initial value problem as accurate as we like. The only reason we cannot do this in practice is because there is a limit to the number of computations we can perform. From a human perspective, it becomes unreasonable to look at more than 10-100 intervals. A computer might do well with billions of intervals. Even still, we would need to look in a limit as the length of the intervals approaches 0, which means the number of intervals approaches ∞. Suppose we wish to solve the initial value problem dm = f (t) dt with initial condition m(t0 ) = m0 . Our goal is to construct a function m̂(t) which approximates the actual solution. First we set m̂(t0 ) = m(t0 ) = m0 . We will define m̂(t) on intervals of ∆t, so it will next be defined at m̂(t0 + ∆t), then m̂(t0 + 2∆t), and so on. If we have m̂(t) we find m̂(t + ∆t) by moving along the line with slope m0 (t) (the slope of the line tangent to m(t)) passing through the point (t, m̂(t)) (which is an approximation of the point the tangent line really intersects). Doing so we find that m̂(t + ∆t) = m̂(t) + m0 (t)∆t where m0 (t) is given by the differential equation in the initial value problem. This is a discrete function which can be made continuous through linear interpolation. This continous function is defined on intervals, and for any point in the interval [t0 , t0 + ∆t] the function is given by m̂(t0 + t) = m̂(t0 ) + m0 (t0 )t where t ∈ [0, ∆t] (this restriction upon t ensures that t0 + t ∈ [t0 , t0 + ∆t]). This is exactly the equation of the approximate tangent line to the function m(t) at the point t0 (called the approximate tangent line because we use m̂(t0 ) rather than m(t0 ), which is an unknown, for our base point). By substituting ∆t into this equation we can verify m̂(t0 + ∆t) = m̂(t0 ) + m0 (t0 )∆t which is consistent with our discretely defined m̂(t). Although this is an iterative process, we can move directly to the solution after multiple intervals quite easily. For instance, m̂(t0 + 4∆t) = m̂(t0 ) + m0 (t0 )∆t + m0 (t0 + ∆t)∆t + m0 (t0 + 2∆t)∆t + m0 (t0 + 3∆t)∆t where we simply move along each of the approximate tangent lines all in one step. It is often easiest to solve problems of this type using a chart. We will outline this process in the following examples. Example 1 Apply Euler’s method to the differential equation dV = 2t dt within initial condition V (0) = 2. Approximate the value of V (1) using ∆t = 0.25. Solution We begin by setting V̂ (0) = 2. Next we construct the chart t 0 0.25 0.5 0.75 1 V̂ (t) 2 2 2.125 2.375 2.75 V 0 (t) = 2t 2·0=0 2 · 0.25 = 0.5 2 · 0.5 = 1 2 · 0.75 = 1.5 V̂ (t + ∆t) = V̂ (t) + V 0 (t)∆t 2 + 0 · 0.25 = 2 2 + 0.5 · 0.25 = 2.125 2.125 + 1 · 0.25 = 2.375 2.375 + 1.5 · 0.25 = 2.75 So we find that V (1) ≈ 2.75. It turns out that V (t) = t2 + 2 is the analytical solution to this differential equation, and V (1) = 3, so Euler’s method provides a somewhat reasonable approximation, which could be greatly improved upon by decreasing the size of ∆t. Example 2 Apply Euler’s method to the differential equation dP = e−t dt with the initial condition P (0) = 0. Approximate the value of P (2). Solution We begin by setting P̂ (0) = 0. We will use the time step ∆t = 0.5. Next we construct the chart t 0 0.5 1 1.5 2 P̂ (t) 0 0.5 0.80326 0.9872 1.09877 P 0 (t) = e−t e−0 = 1 e−0.5 ≈ 0.60653 e−1 ≈ 0.36788 e−1.5 ≈ 0.22313 P̂ (t + ∆t) = P̂ (t) + P 0 (t)∆t 0 + 1 · 0.5 = 0.5 0.5 + 0.60653 · 0.5 = 0.80326 0.80326 + 0.36788 · 0.5 = 0.98721 0.9872 + .22313 · 0.5 = 1.09877 The analytical solution to this problem is P (t) = 1 − e−t , so we find the exact value P (2) = 0.86466, which is somewhat lower than our approximation. By shrinking the size of the interval ∆t, we could calculate a more accurate estimate. In the first case above, we know the analytical solution is t2 + 2, which is concave up. The fact that the function is concave up means that the value for the derivative at the beginning of an interval is smaller than the value for the derivative at the end of the interval. The result is that Euler’s method continually underestimates the actual value of the result. In the second case, our function 1 − e−t is concave down, so the value of the derivative is decreasing, and the derivative at the beginning of an interval is always larger than at the end. For this reason, our Euler’s method approximation continues to overestimate the actual function. One might think to remedy this situation by using the slope at the end of an interval, rather than at the beginning. Let’s examine the first initial value problem, and make approximations using the slope at the end of each interval (note that when we do this our method has less and less resemblence to tangent line approximations). Example 3 Apply Euler’s method (using the slope at the right end points) to the differential equation dV = 2t dt within initial condition V (0) = 2. Approximate the value of V (1) using ∆t = 0.25. Solution We begin by setting V̂ (0) = 2. Next we construct the chart t 0 0.25 0.5 0.75 1 V̂ (t) 2 2 2.125 2.375 3.25 V 0 (t + ∆t) = 2t 2 · 0.25 = 0.5 2 · 0.5 = 1 2 · 0.75 = 1.5 2·1=2 V̂ (t + ∆t) = V̂ (t) + V 0 (t + ∆t)∆t 2 + 0.5 · 0.25 = 2.125 2.125 + 1 · 0.25 = 2.375 2.375 + 1.5 · 0.25 = 2.75 2.75 + 2 · 0.25 = 3.25 So we find that V (1) ≈ 3.25. As above, V (t) = t2 + 2 is the analytical solution to this differential equation, and V (1) = 3, so in this situation our estimate is high. If we were to continue with smaller and smaller ∆t intervals, we could get a better approximation from above and below. In truth, however, there are much better-suited algorithms to numerically solving differential equations. Most of these methods use the same basic idea as Euler’s method, but alter the process in order to make the method more accurate for the number of intervals used. For instance, the Runge-Kutta method uses weighted averages of the slope of the function at multiple points in a given interval (for instance, we may take a weighted average of the slope at the beginning, end, and midpoint of an interval, in order to estimate the next value of our approximate solution). We will not go into the details of actually solving differential equations using the Runge-Kutta method, but suffice ourselves to say that the method is conceptually similar to Euler’s method. The above examples may seem somewhat artificial, in that we already knew an analytic solution to the differential equation (which we can find using the indefinite integral). The truth of matter is, however, that many differential equations do not have a closed-form, analytic solution (which means there is no combination of elementary functions that when differentiated satisfy the differential equation). In some situations, we can get around this by looking at infinite series. However, if we can’t use some special trick, then the best we can do is look for a numerical solution. This is when the true utility of numerical methods shines. One example of such a function is x2 1 √ e− 2 2π which corresponds to a Gaussian, or normal distribution (such functions are ubiquitous in statistics, because they have a number of nice properties: the mean, median, and mode are the same, there is symmetry around the mean, and inflection points occurs one standard deviation away from the mean). This function can be integrated by using infinite series, but we are a long way away from being able to use any such technique. Instead, we can use Euler’s method to atleast approximate a solution. Example 4 Apply Euler’s method (using the slope at the right end points) to the differential equation t2 df 1 = √ e− 2 dt 2π within initial condition f (0) = 0.5. Approximate the value of f (1) using ∆t = 0.25. Solution We begin by setting fˆ(0) = 0.5. We will use the time step ∆t = 0.25. Next we construct the chart 2 t √1 e− 2 2π t fˆ(t) f 0 (t) = 0 0.25 0.5 0.75 1 0.5 0.59975 0.6964 0.7844 0.859684 0.399 0.3866 0.352 0.301137 fˆ(t + ∆t) = fˆ(t) + f 0 (t)∆t 0.5 + 0.399 · 0.25 = 0.59975 0.59975 + 0.3866 · 0.25 = 0.6964 0.6964 + 0.352 · 0.25 = 0.7844 0.7844 + 0.301137 · 0.25 = 0.859684 Right now we can’t verify this result, but with a little knowledge of statistics, we know that we should get a result of about 0.84. In this situation, Euler’s method provides us with a very accurate estimate. We can also used the idea of Euler’s method when we do not have a differential equation, but simply data. Suppose we have measured the velocity of an object at various times, and want to estimate the position. We know position is given by the differential equation dx = v(t) dt so we can perform Euler’s method, but rather than evaluating v(t) at the points of interest, we would just look up the value in a table. Example 5 Suppose you have the following data for the velocity of an object. Find the distance it travels after 60 seconds. Time (seconds) Velocity (m/s) 0 0 10 12 20 18 30 15 40 12 50 8 60 0 Solution Here we can construct our table as normal, simply using the values we already know for velocity. Since we are looking at distance traveled, we will let x(0)x̂(0) = 0. Our data comes in increments of 10, so we will let ∆t = 10. t x̂(t) v(t) x̂(t + ∆t) = x̂(t) + v(t)∆t 0 0 0 0 + 0 · 10 = 0 10 0 12 0 + 12 · 10 = 120 20 120 18 120 + 18 · 10 = 300 30 300 15 300 + 15 · 10 = 450 40 450 12 450 + 12 · 10 = 570 50 570 8 570 + 8 · 10 = 660 60 660 0 So we find that the object has traveled a total of 660 meters in 1 minute. Note that if we are only interested in the object’s position at t = 60, we can simply use the shortcut x̂(60) = x̂(0) + 10(v(10) + v(20) + v(30) + v(40) + v(50)) Finally, if we had uneven intervals of time, we could use the formula x̂(t + ∆t1 + ∆t2 ) = x̂(t) + v(t) · ∆t1 + v(t + ∆t1 ) · ∆t2