Eulers 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 first-order piecewise approximation to the solution of the differential e quation. We can also think of our approximation as a discrete function, which is defined f or t hese approximated points. To make this discrete function a continuous function, we interpolate between each pair of these points with a line. 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 millions or billions of intervals (but then there are other practical issues to deal with, such as roundoff error, which do limit the number of intervals we can work with). 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 ∞. Due to these practical limitations more advanced numerical methods such as the Runge-Kutta are used to solve differential equations, rather than Euler’s method. Nevertheless, it is useful to consider Euler’s method because these other numerical methods are conceptually very similiar. Suppose we wish to solve the initial value problem dm = f (t), dt 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 . Since we will define m̂(t) on intervals of length ∆t, it will next be defined at m̂(t0 + ∆t), then m̂(t0 + 2∆t), and so on. If we know m̂(t) we find m̂(t + ∆t) by moving a distance ∆t along the line passing through (t, m̂(t)) with slope m0 (t), which is our approximate tangent line. In moving a distance ∆t along a line with slope m0 (t) we increase the value of our function by m0 (t)∆t, so we find that m̂(t + ∆t) = m̂(t) + m0 (t)∆t. The result is a discrete-time function, but it can be made into a continuous-time function through interpolation (see figure 1). This new continuous-time function is piecewise 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 1 m̂(t0 + 4∆t) m̂(t0 + 3∆t) m̂(t0 + 2∆t) m̂(t0 + ∆t) m̂(t) m(t) m(t0 ) t0 t0 + ∆t t0 + 2∆t x t0 + 3∆t t0 + 4∆t Figure 1: An illustration of Euler’s method. The dotted line represents the actual (unknown) solution to the differential equation. The solid function is an illustration of the approximate solution obtained through Euler’s method. where t ∈ [0, ∆t] (this restriction upon t ensures that t0 + t ∈ [t0 , t0 + ∆t]). This equation follows from the same observation as before, noting that the function value is increased by an amount m0 (t0 )t in moving a distance t along a line with slope m0 (t0 ). In order to find the value of the function at a distant point we simply move along a number of approximate tangent lines, repeating this same process. In moving from t0 to t0 + 4∆t, for instance, we find that m̂(t + 4∆t) = m̂(t0 ) + m0 (t0 )∆t + m0 (t0 + ∆t)∆t + m0 (t0 + 2∆t)∆t + m0 (t0 + 3∆t)∆t. In order to facilitate using Euler’s method by hand it is often helpful to use a chart. This process is outlined 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. Solving this initial value problem exactly we find V (t) = t2 + 2. This yields V (1) = 3, so Euler’s method provides a somewhat reasonable approximation, which would be greatly improved upon by decreasing the size of ∆t. Note that the exact solution t2 + 2 is concave up, which means that the value of the derivative is increasing along each interval. Thus, the value of the derivative at the beginning of an interval is smaller than the value of the derivative at all other points in the interval. The result is that Euler’s method continually underestimates the actual value of the function. 2 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 actual solution to this problem is given by P (t) = 1 − e−t , so we find the exact value P (2) = 0.86466. This is somewhat lower than our approximation. Note that the function 1 − e−t is concave down, so the value of the derivative is decreasing, meaning 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 solution. The above examples may seem somewhat artificial, in that it was easy enough (or even possible) to find an exact solution to the differential equation. There are some situations where we can use an infinite series or other method in order to find an exact solution, but the truth is that very few differential equations can be solved exactly. Thus, numerical methods such as Euler’s method are extremely important to solving practical problems. Consider the function 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 currently don’t have such a technique at our disposal. Instead, we can use Euler’s method to approximate a solution. Example 3. 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 3 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. This is particularly useful because anytime we measure physical data we only have values known over discrete-time intervals; ie. we do not have an exact function. 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 4. Suppose you have the following data for the velocity of an object. Find the distance it travels after 60 seconds. Time (seconds) 0 10 20 30 40 50 60 Velocity (m/s) 0 12 18 15 12 8 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 0 10 20 30 40 50 60 x̂(t) 0 0 120 300 450 570 660 v(t) 0 12 18 15 12 8 0 x̂(t + ∆t) = x̂(t) + v(t)∆t 0 + 0 · 10 = 0 0 + 12 · 10 = 120 120 + 18 · 10 = 300 300 + 15 · 10 = 450 450 + 12 · 10 = 570 570 + 8 · 10 = 660 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 . 4