1:42

We're going to focus on the initial value problem for an ODE of the form

Â dx/dt equals f of x,t.

Â We can think of that differential equation as defining a slope field in the xt

Â plane, that tells us how x changes with t, or at what rate.

Â Now given some

Â initial condition, x not, at an initial time T

Â naught. What we want to do is approximate the

Â final value, x star, at some final time,

Â t star. Now, we don't know the solution x of t,

Â and we're not going to be able to use calculus to get that analytic solution.

Â So what we're going to do is try to

Â approximate that final value, x star, as best we can.

Â To approximate, we're going to use sequences.

Â Let's begin, first of, all, along the time axis.

Â We're going to write a sequence, t sub n, that

Â goes from t0, t1, all the way to t, capital n,

Â where t not is the initial time, and t capital

Â N is our final time, t star. This is going to be a uniform

Â grid, meaning that we have a step size, h, equal

Â to the final time, minus the initial time, divided by capital

Â N. We are likewise going to approximate

Â the x values by a sequence x sub n where

Â x not is the initial condition on x and hopefully

Â our final x value x N is close enough to x

Â star that we have a good approximation.

Â The simplest way to do this is called Euler's method.

Â Perhaps you've seen it before, but we're going

Â to look at it from a discrete calculus perspective.

Â We're going to take our differential equation and discretize it using

Â sequences, and instead of derivatives,

Â differences, a literal quotient of differences.

Â What does this mean? While if we consider at

Â the nth time step that on the right we have f evaluated at

Â x sub n comma t sub n, on the

Â left we have the quotient of differences. Delta x is

Â x n plus 1 minus x n. Delta t is t n plus

Â 1 minus t. And of course,

Â since we're using a uniform grid, that delta t is simply equal

Â to hr step size. And now, with a little bit of

Â rearrangement, we obtain Euler's method,

Â this is an update rule. It tells you that if

Â you know X sub N and T sub N, you can obtain X sub N plus

Â 1 as XN plus H times F evaluated at XN coma TN.

Â That's the method, but what does it mean geometrically?

Â Well, if we are at time step T sub N and we have our approximation X sub N, we'd

Â like to get to an approximation TN plus 1. We don't know

Â the true solution that passes through that point, but we do

Â know the value of F there. That is telling us the slope, and what

Â Euler's Method is really doing is projecting forward 2 time T

Â sub N plus 1. At heart, Eulers Method is linearization.

Â So why does it work? Well,

Â it works because we repeat this at each time step, linearizing and approximating.

Â As we move from timestep to timestep, let's look at a simple example.

Â A differential equation that we already know how to solve, dx dt equals x.

Â We'll choose an initial time of 0, an initial value x knot

Â equal to 1. A final time T star equal to 1

Â is X star. Now we already know that the solution of

Â this equation is E to the T, so X star really should be E,

Â but let's see what happens when we chose a step size of H,

Â that is final time minus initial time over capital N.

Â In other words, 1 over capital N. Euler's Method

Â tells us that xn plus 1 equals xn plus h times f.

Â Add xn, tn. What's f in this case?

Â Oh, it's the right hand side of the ODE. In this case, just the x value.

Â So we can simplify Euler's update

Â rule to xn plus 1 equals

Â xn plus hxn. Factoring out the xn, we get quantity

Â 1 plus h times xn. Now we've seen

Â this before, this is really a recursion relation, E applied

Â to the sequence X equals quantity 1 plus H

Â times X. Now, you may recall from our lectures

Â on discreet calculus that we know how to solve such

Â simple recurrence relations. Sequence X is really

Â X naught times quantity one plus H to

Â the N. It is that coefficient of 1 plus H that

Â determines the solution. This means that our final value X sub

Â capital N is X naught times quantity 1 plus h to the capital n.

Â If we substitute in 1 over capital n for h, then we obtain something

Â that should look familiar. Quantity 1 plus

Â 1 over capital n to the capital n power. You may

Â recall that for n large, this is a very good approximation

Â to e, our desired final value. What

Â happens when we do an example, the answer to which we don't

Â already know. Consider dx, dt equals cosine

Â t plus sine of x, with an initial time.

Â Zero, an initial value of zero, and a final time of pi.

Â I don't know what the final value should be.

Â This is not a separable equation, and so we're going to fire up the computer

Â program in let's say five time steps and see what it says.

Â We will break up teh time interval into five equal

Â sub integrals and then use the method to

Â approximate what X sub five should be. And we get a

Â value of about 2.4. Now, that's with 5

Â time steps. If we use a greater number of time

Â steps, Euler's Method will return, hopefully,

Â a more accurate approximation to that final value.

Â And as we move towards, let's say, 80 times steps, we seem to be converging.

Â The final answer looks like it ought to be about 2.25, 2.24, something like that.

Â It's hard to say without running more examples.

Â Now why is it that Euler's

Â method works and seems to converge? How quickly does

Â it converge? Well, we're going to think from a Taylor's

Â series point of view, consider what happens when we

Â expand the solution X of T about T naught. X of

Â T naught of H is by, a Taylor series,

Â X naught plus H. Times the derivative of x with respect

Â to T, evaluated at T not, plus something in big O of H squared.

Â Now what's that derivative evaluated at T naught?

Â That is simply F at X naught, T naught.

Â And here, we see Euler's method hiding inside of

Â the Taylor Series. Euler's method is really just Taylor

Â expansion and dropping all of the terms of order to and greater.

Â Now, we say, because of this, that Euler's method is a first order method.

Â And that the error you make at each step is in big O of

Â h squared. Where h is our time step.

Â Remember.

Â Now, what is the net error when you do capital N such steps?

Â Well, it's capital n times something in big O of h squared.

Â You might think, ha, ha, capital n is a constant,

Â so I can forget about it, since we're doing big O.

Â No, capital N depends

Â on age. It's really some constant, the change in

Â time, divided by H. And so being careful,

Â we see that the net error is in big O of H

Â We'll look at two other methods for doing numerical ODEs.

Â The first is called the midpoint method. It begins easily enough

Â just like the Euler method, one projects forward.

Â Call this change in x that we get from Euler's method kappa.

Â Now, this is the midpoint method. So what we're going to do is take the time

Â value that is in between t sub n and t n plus one,

Â and try to approximate what the differential equation is doing there.

Â We will use evaluation at that midpoint to obtain a

Â new slope and pull that back to X of n, and then project

Â that forward at that midpoint slope to get x and plus 1.

Â Now, when we write all this out algebraically, it involves

Â this constant kappa and it looks a little bit complicated.

Â You don't have to memorize this, but what you do need to know is that this

Â is a second-order method. That means that

Â we're really doing a Taylor expansion, and keeping all the terms up

Â to, and including degree to the step error in the

Â midpoint method is in big O of h cubed, meaning that the net

Â error is in big O of h squared. This is a better

Â approximation at the expense of being algebraically more complex.

Â Now with that in mind, you might wonder, wouldn't it be possible

Â to do higher order approximations using midpoints, pulling it

Â back, and then evaluating again, pushing it forward, and pulling it back and

Â averaging everything all up together. Indeed, this is possible, and this

Â is a wonderful method called the Runge-Kutta method.

Â There's a lot of equations that go into this.

Â You don't have to memorize it. What you need to know is that first, this

Â exists And second, it's very helpful even if it seems

Â rather mysterious. This is a 4th order method.

Â Very good approximation.

Â Your step error is in big O of h to the 5th,

Â and your net error is in big O of h to the 4th.

Â Let's compare all these methods together in the

Â one simple example that we know how to solve.

Â Dx dt equals x with the initial time 0,

Â initial value 1 of final time 1, and our final

Â value, x star, which is known to be. We've

Â already seen what happens in the general case in Euler,

Â as H is going to 0. Let's be dumb, let's use

Â 1 step. We're going to take our step size H to be

Â equal to 1 In Euler's method,

Â what we get, well, we get, simply that

Â X1 equals 1 plus H times X not, since Xnot

Â is equal to 1, we get an approximation of 1 plus 1.

Â That's not a terrible approximation to e, given that we've

Â only done one step, but that's all we get from Euler.

Â Now, with the midpoint method, our kappa value.

Â We already know what that is.

Â That is equal to 1.

Â What happens when we take the formula for the midpoint method?

Â Well, we get a value of X1 equal to 1 plus

Â h times quantity x nought plus one-half

Â kappa. That means we get 1 plus 1 plus one-half.

Â That's a better approximation to A. Finally when we go all the

Â way and write down all of those formulae for the Runge-Kutta Fourth Order Method.

Â Then with a little bit of algebra, you'll see we get 1 plus 1

Â plus a half plus 1 6th plus 1 24th. And now

Â you see the pattern. These numerical methods are really

Â just giving higher and higher terms from the Taylor series.

Â Moral of our story is that, by looking

Â at things from a Taylor series point of view, you can understand errors.

Â We've now seen just a small taste of how

Â discrete or digital methods help us solve smooth calculus problems.

Â But this is, by no means, the only possible example.

Â In our next lesson, we'll consider how to

Â use the discreet calculus to solve problems involving

Â definite integrals.

Â