MIT OpenCourseWare http://ocw.mit.edu 18.034 Honors Differential Equations Spring 2009 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. LIMITATIONS OF EULER’S METHOD FOR NUMERICAL INTEGRATION LAURA EVANS. 1. Introduction Not all differential equations can be explicitly solved for y. This can be problematic if we need to know the value of y at a specific point. This is where methods of numerical integration are useful, as they allow us to estimate the value of y based on known initial conditions. One of these methods for numerical integration is Euler’s Method, which will be the subject of the following discussion. Although not the most accurate of methods, it is one of the simplest, which is useful when beginning to understand these methods. Essentially, the method works by finding the slope at a known, traveling in a small amount h in that direction, then calculating the new slope and traveling in the direction of the new slope, and so on. Euler’s method is an iterative method. Consider the initial value problem y�(x) = f(x,y(x)) (1) y(a) = y 0 We proceed in steps of size h, so x = a and x = x + h. For each 0 n+1 n step, then, y = y + hf(x ,y ) n+1 n n n This allows us to approximate the value of y at a point x, given the initial data. Because of its relative simplicity as a numerical method, Euler’s method is limited in its scope, as I will discuss in this paper1 . 2. Error Proposition 2.1. Euler’s method produces an answer with accuracy o(h). Date: May 18, 2007. 1This discussion is based on material found on Section 1.8 of Birkhoff Rota, with some inspiration for examples drawn from the Wikipedia entry on Euler’s Method. 1 2 LAURA EVANS. Proof. Consider the Taylor expansion of y(x) around a + h: y(a + h) = y(a)+ hy�(a)+ o(|h2|) But Euler’s method gives y(a + h) = y(a)+ hy�(a) Since the error is the difference between the two equations, we can see that the error in this first step is o(|h2|). The way Euler’s method is commonly used is to set h equal to some small fraction of the difference between the desired value and the known value. Thus, the number of steps needed to reach the desired value is o(| 1 |), so the total error accumulated upon reaching the desired value h is o(|h|). � One consequence of this is that if we want an additional decimal place of accuracy in our answer, we must use a new h that is one-tenth the original. This means we must do a significantly more calculations. Thus, we see that Euler’s method is not efficient for finding answers to a high accuracy. 3. Demonstration Let us observe the behavior of solutions found using Euler’s method on the equation y� = ky, with initial value y(0) = 1 for various values of k < 0 We know that this equation has solution y(x) = xkt, so we can compare the values given by this method to the real values. First, we will consider k = −1. The true values and the values given by Euler’s method with h = 0.5 are given below. x y y n 0 1 1 0.5 0.5 0.61 1 0.25 0.37 Clearly, this is not very accurate. We can improve its accuracy, as we saw above, by decreasing the value of h. The following table shows the same function, with h = 0.1 LIMITATIONS OF EULER’S METHOD FOR NUMERICAL INTEGRATION 3 x y y n 0 1 1 0.1 0.90 0.90 0.2 0.81 0.82 0.3 0.73 0.74 0.4 0.66 0.67 0.5 0.59 0.61 0.6 0.53 0.55 0.7 0.48 0.50 0.8 0.43 0.45 0.9 0.39 0.41 1 0.35 0.37 From this we see that the smaller value of h gives much more accurate values for y in our test case. In addition, we can see that the error does remain less than h, although it does increase as x increases. 4. Failure Now, let us consider the same equation as the previous section, but with larger values of |k|. In particular, we will look at k = −3, k = −11, and k = −21. First, we will use h = 0.5. Readers should note that all data in the following table is rounded to the second decimal place. k = −3 k = −11 k = −21 x y y y y y y n n n 0 1 1 1 1 1 1 0.5 0.70 0.22 -0.1 0 -1.1 0 1 0.49 0.05 0.01 0 1.21 0 The values for the first 2 k seem reasonable, but something seems off about the values that Euler’s method has given us for k = −21. Let’s decrease h to see if the problem goes away. Let’s set h equal to 0.1, as before. Again, values are rounded to the second decimal place. 4 LAURA EVANS. k = −3 k = −11 k = −21 x y y y y y y n n n 0 1 1 1 1 1 1 0.1 0.7 0.74 -.1 0.33 -1.1 0.12 0.2 0.49 0.55 0.01 0.11 1.21 0.01 0.3 0.34 0.41 0 0.04 -1.33 0 0.4 0.24 0.3 0 0.01 1.46 0 0.5 0.17 0.22 0 0 -1.61 0 0.6 0.12 0.17 0 0 1.77 0 0.7 0.08 0.12 0 0 -1.95 0 0.8 0.06 0.09 0 0 2.14 0 0.9 0.04 0.07 0 0 -2.36 0 1 0.03 0.05 0 0 2.59 0 From this, we can see that the problem has not gone away - in fact, it has gotten worse. Rather than approximating the curve, the values that Euler’s method gives for k = −21 oscillate around the curve, with growing amplitude. Holistically, it is easy to see what the problem is. When the method makes its ’step’ of length h, it assumes that y� will remain about constant over that small distance. However, this is not the case for y� = −21y. Over a distance h, y� changes relatively largely compared to h. The same is true whenever we have an equation of the form y� = ky, k � 0. We can expand this discussion to realize that whenever y� changes rapidly near y , Euler’s method will not be accurate. Thus, use of 0 Euler’s method should be limited to cases when max{|y��(x ±�)|} � ∞, 0 for some neighborhood � near x . 0 5. Improvements Euler’s method is a first order numerical approximation: each new value depends only on the value immediately before it. This is part of the reason that it can be affected as we saw previously. One way of improving Euler’s method is to use a second order ver­ sion: y(a) = y a y = hf(a,y ) 1 0 h y = y + (f(x ,y )+ f(x ,y )) n+2 n n n n+1 y+1 2 LIMITATIONS OF EULER’S METHOD FOR NUMERICAL INTEGRATION 5 Let us consider what y is in this version. 2 h y = y + (f(x ,y )+ f(x ,y )) 2 0 0 0 1 1 2 h = y + (y�(a)+ f(h,hf(a,y ))) a 0 2 h = y + (y�(a)+ f(h,hy�(a))) a 2 h = y + (y�(a)+ y�(a)+ hy��(a)) a 2 h2 = y + hy�(a)+ y��(a) a 2 This is only o(h3) away from the second order Taylor expansion of y(x) near a. By similar reasoning as the proof above, then, we can assume that this will yield much greater accuracy than the original, even with the same h. 6. Conclusion After this exploration of Euler’s method, we have learned several things about when it should be used and when other numerical meth­ ods would be more appropriate. In particular, Euler’s method is not the best choice when |y�| takes on large values near the initial data, nor when a computationally efficient method is required. Although we can improve the method slightly, by considering more than the immedi­ ately previous point, this improvement is limited. In many cases, then, Euler’s method is not the most appropriate numerical method.