M427K Handout: Numerical MethodsSalman ButtApril 19, 2006Notes1. There will be a feedback session at the end of class today. Please say something besides themidterm being difficult.Euler’s MethodConsider the differential equation y0= f(t, y) with initial condition y(t0) = y0where f is acontinuous function on some domain (rectangle) in the ty-plane containing the point (t0, y0). Byour work before, we know there exists a unique solution φ(t) in some interval about t0. We wantto approximate φ(t) numerically instead of solving for it explicitly.Euler’s method is expressed by the equationIf we further assume we use a uniform step size h and we denote f (tn, yn) by fn, the above equationsbecomesIn Euler’s method, we m erely repeatedly evaluate these equations and use each evaluation in thenext step of the method. This gives a sequence of values y0, y1, y2, . . . corresponding to timest0, t1, t2, . . . . Euler’s method is simple to program and its pseudo-code is given as below:1Interpreting Euler’s MethodThere are three approaches to interpreting what Euler’s method does. Each of these interpre-tations sheds light on the method, but more importantly highlights how it can be improved. Theseinsights will be critical in improving Euler’s method, which we will take up later.Interpretation 1. We know there exists a solution φ(t) to our differential equation. Let’s plugit in to and evaluate it at the point t = tnto get φ0(tn) = f(tn, φ(tn)). We can approximate φ0(tn)by the forward difference quotientto get the approximationIf we replace φ(tn+1) and φ(tn) by their approximate values yn+1and yn, we get Euler’s methodabove.Interpretation 2. Observe that the equation φ0(t) = f(t, φ(t)) can be integrated from tnto tn+1:Evaluating this integral we findWe can approximate the integral on the right by the value f(t, φ(t)) takes on a particular pointt = tn. This amounts to a coarse approximation of the integral and yields the approximationAgain, replacing φ(tn+1) and φ(tn) by their approximations yn+1and ynyields Euler’s method.Interpretation 3. Finally let’s assume that φ(t) has a Taylor series about the point tn. So wecan writewhich is merelyIf we truncate this s eries after the first derivative and replace the φ’s by their approximate valuesy, we again have Euler’s formula.Error AnalysisThere are three types of error involved with numerical computations. The global truncationerror Enis the difference between the actual solution and the approximate solution predicted by2the numerical method:This error is caused by two facts: at each step, we have an approximate formula to determine yn+1.The second cause is the fact that the input data at each step is itself approximate, i.e. φ(tn) 6= ynin general. If we as sume that yn= φ(tn), i.e. our approximations are correct, the only error occursfrom using an approximate formula. This error is called the local truncation error and is denotedby en.Finally, there is the round-off error Rnwhich is directly related to the machine used to calculatethe approximate solutions:Thus the absolute value of the total error is given byWe can bound this using the triangle inequality:More details on bounding the local truncation error can be found on pp. 447-9, but we will notgo over that today.Adjusting Eul er: Backward Euler FormulaA simple adjustment to Interpretation 1 of Euler’s method from a forward difference quotientto a backward difference quotient yields a new method called the backward Euler method. Thatis, we use the equationto get an approximate formula. Substituting in our yn’s, we findAnd adjusting the index, we getThe difficulty of solving for yn+1depends entirely on the nature of f. The backward Eulermethod may sometimes be too difficult to do or may not provide any more accurate approxima-tions. So why do we discuss this method? It turns out this metho d is the simplest example of aclass of methods known as backward differentiation formulas that are very helpful in solving certaintypes of differential equations, so it is important that you are aware of this method.Adjusting Eul er: Heun Formula3This method is also referred to as the improved Euler method. It is derived by reconsideringInterpretation 2 of Euler’s method. Recall that the integral was grossly approximated by the valuef(tn, φ(tn)). What if we more accurately approximate this integral, say by the average of thefunction at the two endpoints:Using this approximation for the integral and plugging in our y’s, we have the approximate formulaObserve that this equation is an implicit equation in yn+1so solving this formula can prove difficult.But a small trick of replacing yn+1by the previous estimate yn+ hf (tn, yn) yields an explicitequation:This formula is know n as the Heun formula (or improved Euler formula). This is an improvementof the original Euler’s method (see p. 453 for an explanation), though it is now more computation-ally intensive because we have to evaluate f twice.Implementing this method is rather straightforward. We merely replace Step 6 in Euler’s methodby the following:Note that one can also vary the step size to achieve better results (both in accuracy andefficiency). A discussion of this can be found on p. 455 of the text, but we will not go over it sinceit is a rather fine argument and one with which we are not directly