Euler’s Method, Taylor Series Method, Runge Kutta …

1 Euler s Method, Taylor Series Method, RungeKutta methods , Multi-Step methods and :We start with the differential equationdy(t)dt=f(t,y(t))( )y(0) =y0 This equation can be nonlinear, or even a system of nonlinear equations (in which caseyisa vector andfis a vector ofndifferent functions).Numerical Solution of an ODE:The idea behind numerical solutions of aDifferentialEquationis to replace differentiation by differencing. A computer cannot differentiate but itcan easily do a difference. (Differentiation is a continuous process. Differencing is a discreteprocess.) Now we introduce the most important tool that will be used in this section. By thetime you ve mastered this section, you ll be able to doTaylor Expansionsin your sleep.(I am already doing Taylor expansions in your sleep, right?!) Taylor Series Expansion:You ll recall (?) from your calculus class that if a functiony(t)behaves nicely enough, then its Taylor Series expansion converges:y(t+ t)=y(t)+ ty (t)+12 t2y (t)+13!

2 T3y (t)+..The Taylor Series with remainder term isy(t+ t)=y(t)+ ty (t)+12 t2y (t)+13! t3y (t)+..+1n! tny(n)( )where is some value betweentandt+ t. You can truncate this for any value s Method:If we truncate the Taylor Series at the first termy(t+ t)=y(t)+ ty (t)+12 t2y ( ),we can rearrange this and solve fory (t)y (t)=y(t+ t) y(t) t+O( t).Now we can attempt to solve ( ) by replacing the derivative with a difference:y((n+ 1) t) y(n t)+ tf(n t,y(n t))Start withy(0) and step forward to solve for any s good about this? If theOterm is something nice looking, this quantity decayswith t,soifwetake tsmaller and smaller, this gets closer and closer to the real can go wrong? TheOterm may be ugly. The errors can accumulate as I step forward1in time. Also, even though this may be a good approximation fory (t) it may not convergeto the right solution. To answer these questions, we look at this scheme in :From now on, we ll callynthe numerical approximation to the solutiony(n t);tn=n t.

3 Euler s method can then be writtenyn+1=yn+ tf(tn,yn)n=1,..,N 1( )This method assumes that you can move from one location to the next using the slope givenby the equation ( ). We saw last time that when we do this, our errors will decay linearlywith t. We will show this again today, but in two steps, so that we can generalize it. Theproof should look very familiar!Local Truncation Error:To be able to evaluate what we expect the order of a methodto look like, we look at theLTE(t)=y(t+ t) y(t) t f(t,y(t)), is the residue when the exact solution of the ODE ( ) is plugged into the numericalscheme. Ifynis close toy(tn) then the LTE will be close to local truncation error represents the terms neglected by truncating the Taylor is not the error that we get from the method, ( the difference between the realsolution and the numerical solution) but will be I don t knowy(t), what is the use of this definition? (and if I do knowy(t), what doI need the method for?!).

4 It turns out that even without explicit knowledge of the solutionwe can still calculate the LTE and use it as an estimate and control of the error, by placingcertain smoothness assumptions ony(t) and using the Taylor , at timetn, Euler s method hasLocal Truncation Error:LTE=y(tn+ t) y(tn) t f(tn,y(tn)) =O( t),in other words, we can write thisy(tn+1)=y(tn)+ tf(tn,y(tn)) + course, the method isyn+1=y(tn)+ tf(tn,yn).Subtract these two,|y(tn+1) yn+1|=|y(tn) yn+ t(f(tn,y(tn)) f(tn,yn)) + tLTE| |y(tn) yn|+ t|f(tn,y(tn)) f(tn,yn)|+ t|LTE| |y(tn) yn|+ tL|y(tn) yn|+ t|LTE|.Becausefis Lipschitz continuous,|f(tn,y(tn)) f(tn,yn)y(tn) yn| so, if we let theGlobal Errorbeen=|y(tn) yn|, then we can bound the growth ofthis error:en+1 en(1+ tL)+LTE does this help us bound the method?Lemma:Ifzi+1 zi(1 +a t)+bThenzi eai t(z0+ba t)Proof:zi+1 zi(1 +a t)+b (zi 1(1 +a t)+b)(1 +a t)+b z0(1 +a t)i+1+b(1+(1+a t)..+(1+a t)i)=z0(1 +a t)i+1+b(1 +a t)i+1 11+a t 1 z0(1 +a t)i+1+ba t(1 +a t)i+1 (1 +a t)i+1(z0+ba t) ea t(i+1)(z0+ba t)sozi eai t(z0+ba t)Applying this lemma to the global error, we have|en| eLn t(|e0|+M2L t) Now, ifn t Tthen|en| eLT(|e0|+M2L t) and since|e0|= 0 we have:|en| eLT(M2L t).

5 Compare this with the local error:LTE 12M twe see that the global error has thesame order as the local error with a different coefficient in the estimates. They are relatedby the Lipschitz constant L and the final time a schemer, is defined by|en|=O( tr). The higher the order of thescheme, the faster the error :The important thing to understand is that theLocal Truncation Errorisnot always an indicator of what theglobal errorwill do. Schemes that have the same orderof LTE and global error are good schemes. We need to define what makes the method havethe property that the global error will be of same order as the Series methods :To derive these methods we start with a Taylor Expansion:y(t+ t) y(t)+ ty (t)+12 t2y (t)+..+1r!y(r)(t) s say we want to truncate this at the second derivative and base a method on scheme is, then:yn+1=yn+fn t+f tn2 Taylor Series method can be written asyn+1=yn+ tF(tn,yn, t)whereF=f+12 tf . If we take the LTE for this scheme, we get (as expected)LTE(t)=y(tn+ t) y(tn) t f(tn,y(tn)) 12 tf (tn,y(tn)) =O( t2).

6 Of course, we designed this method to give us this order, so it shouldn t be a surprise!So the LTE is reasonable, but what about the global error? Just as in the Euler Forwardcase, we can show that the global error is of the same order as the LTE. How do we do this?We have two facts,y(tn+1)=y(tn)+ tF(tn,y(tn), t),andyn+1=yn+ tF(tn,yn, t)whereF=f+12 tf . Now we subtract these two|y(tn+1) yn+1|=|y(tn) yn+ t(F(tn,y(tn)) F(tn,yn)) + tLTE| |y(tn) yn|+ t|F(tn,y(tn)) F(tn,yn)|+ t|LTE|.Now, ifFis Lipschitz continuous, we can sayen+1 (1 + tL)en+ t|LTE|.Of course, this is the same proof as for Euler s method, except that now we are looking atF, notf, and theLTEis of higher order. We can do this no matter which Taylor seriesmethod we use, how many terms we go forward before we and Disadvantages of the Taylor Series Method:advantagesa) One step, explicitb) can be high orderc) easy to show that global error is the same order as LTEdisadvantages Needs the explicit form of derivatives MethodsTo avoid the disadvantage of the Taylor Series method, we canuse Runge - Kutta methods .

7 These are stillone stepmethods, but they depend on estimatesof the solution at different points. They are written out so that they don t look messy:Second Order Runge - Kutta methods :k1= tf(ti,yi)k2= tf(ti+ t,yi+ k1)yi+1=yi+ak1+bk2let s see how we can chose the parametersa,b, , so that this method has the highestorderLTEpossible. Take the Taylor expansions to express the LTE:k1(t)= tf(t,y(t))k2(t)= tf(t+ t,y+ k1(t)= t(f(t,y(t)+ft(t,y(t)) t+fy(t,y(t)) k1(t)+O( t2))LTE(t)=y(t+ t) y(t) t a tf(t,y(t)) t b t(ft(t,y(t)) t+fy(t,y(t) k1(t)+f(t,y(t)) t+O( t2)=y(t+ t) y(t) t af(t,y(t)) bf(t,y(t)) bft(t,y(t)) bfy(t,y(t) f(t,y(t)) +O( t2)=y (t)+12 ty (t) (a+b)f(t,y(t)) t(b ft(t,y(t)) +b f(t,y(t))fy(t,y(t)) +O( t2)=(1 a b)f+(12 b ) tft+(12 b ) tfyf+O( t2)So we wanta=1 b, = = Order Runge - Kutta methods :k1= tf(ti,yi)( )k2= tf(ti+12 t,yi+12k1)( )k3= tf(ti+12 t,yi+12k2)( )k4= tf(ti+ t,yi+k3)( )yi+1=yi+16(k1+k2+k3+k4)( )The second order method requires 2 evaluations offat every timestep, the fourth ordermethod requires 4 evaluations offat every timestep.))))))

8 In general:For anrth order Runge - Kutta method we need S(r) evaluations offfor each timestep, whereS(r)= rforr 4r+ 1 forr= 5 andr=6 r+ 2 forr 75 Practically speaking, people stop atr= of Runge - Kutta Methods1. One step method global error is of the same order as local Don t need to know derivatives Easy for Automatic Error Control .Automatic Error ControlUniform grid spacing in this case, time steps are good forsome cases but not always. Sometimes we deal with problems where varying the gridsizemakes sense. How do you know when to change the stepsize? If we have anrth order schemeand andr+ 1th order scheme, we can take the difference between these two to be the errorin the scheme, and make the stepsize smaller if we prefer a smaller error, or larger if we cantolerate a larger Automatic error control yo are computing a useless (r+1)th order shceme ..what a waste! But with Runge Kutta we can take a fifth order method and a fourth ordermethod, using the sameks.

9 Only a little extra work at each