Chapter 10.2 - Time and Space Stepping Schemes: Explicit and Implicit Methods

0:06 We're going to continue with time and space stepping schemes and we're going to consider a really diverse number of ways both implicit and explicit methods that you can march yourself forward into the future. In particular, there's a lot of choice and flexibility you have in how you decide how you want to march forward. And eventually what we're going to have to really address is what are the appropriate methods we want to be using and then we're going to have to dig down on issues of stability. So different schemes that you might consider often the final choice of a scheme is directly related to the stability accuracy properties that you want to maintain in your solution technique.

0:52 So let's take a closer look at time spacing step time and space stepping schemes. And I want to start off with very simple models here. So let's start off with the easiest PD we could write down really which is the one oneway wave equation. So it's ut= cux. And what this admits is a traveling wave with speed c. So we know how to solve this analytically. And the question is how do we come up with a scheme that would solve this in a numerical method.

1:21 Okay. So first let's start off by doing center difference discretization of that space derivative. So all we do here for a derivative is use rise over run formula. Point in front minus point behind divide by two delta x. This is the first thing we learned in calculus in fact what we did with calculus is took the limit of this slope formula. Take delta x to zero and that's was the definition of the derivative. And now we're going backwards. We're saying let's undo that derivative and just give it as a difference formula. Okay, so that it gets set sets up to take care of the space derivative. And now what we want to do is take care of the time. So if we look at the time here, we want to now start looking at how do I differentiate in time. I can use several formulas. And what we're going to do here is again a slope formula where a point all we're going to do here is forward difference. So we're going to use the slope formula which involves the current point and the time point in front. So notice here this is the time point in front. This is the current point and I've already multiplied through by delta t. But this was just a slope formula which was the point in front minus the current point divided by delta t. And I rearranged it into this formula here. And the reason I arranged it here is I want to start to highlight sort of your stepping scheme of how you get into the future. So the superscripts here denote what time point you're at.

2:49 The subscripts denote the spatial position. So in space, so we're marching forward one step in time and I'm evaluating this right hand side at the current time point. And look how I'm using my neighbors to with the derivative. So this is a a very simple formula here. And now I'm going to rewrite it one last time simply by taking this delta t over 2 delta x and writing sorry delta c delta t over delta x is lambda. And it turns out this is an important quantity. This is called the CFL the current fried Louis condition number. And the CFL number is absolutely important for stability properties. And we're going to investigate this in detail in the next lecture. But for right now, you see that it's embedded right here in front of this term. So the way this scheme works, which is forward difference in time, center difference in space is right here. So you're using these three points to update solution one line into the future. So what I would do for every single point in the future, I'd go to the next point. Use the three previous points down here to get to this point, right? Go to the next point. use its neighbors here to get this point and so forth. So I'd walk across this entire line in time in order for me to take a step forward or produce the next line of solutions in time.

4:14 So that's the basic idea of this stepping scheme. Okay, let's solve the same problem again with a different method, different scheme. So in fact part of what this lecture is going to highlight is there are so many different ways that people have developed for solving for doing this method of lines for advancing solutions in time and so I'm going to show you a bunch of them here and many of these are developed because they have for certain problems not all problems but for certain problems they have exceptional accuracy and stability properties.

4:52 So for given a problem that you might have, one of your jobs is to figure out what is the best scheme for the PTE that I'm trying to solve. And there's a very big difference about what you would do with a wave equation versus for instance a heat equation in terms of stepping algorithms. So let me just show you continue to develop this for the one-way wave equation. So let's go back to what we had one-way wave equation. Again, I simply discretized center difference in space. But now what I'm going to do, I have to take care of this time derivative. I'm going to do center difference right here for the time derivative as well. So center difference, interestingly here, I'm at the current time point M. I'm using a point in the future and a point in the past. So that's the center difference. I use point front, point behind over two delta t, which allows me to write this scheme here. Again, there's the lambda, the CFL condition or CFL number. And what you're seeing here is the point in the future in the front in the future is equal to what it was a time point behind times the derivative calculation at the current time point. This is called leapfrog 22. The two and the two dictate that it's second order accurate in time, second order accurate in space and leapfrog because what you're doing is at the current point you're using the time point in the past to produce the future time point. So you're leaprogging over the current point that you have to see this in a picture. Let me just show you this. So this is the scheme in a picture. So notice you're at this point, you know, if you're going to produce this point here, you're not using this point here, which would seem natural as what we used before, but you're leaprogging it to produce an estimate of the future derivative. And this is called leaprog 22. So point of the future is what it was one time point ago plus the CFL number times your neighboring points at the current time.

6:51 Now the implications of this scheme is if I'm going to march it forward I need two lines of solutions to produce the next line. So the nice advantage of the previous scheme is the current line of solutions is all you need to advance forward. This needs two lines of solutions to advance forward. Okay. All right. But again, part of why we do it is because we might have nice stability properties which we'll show that leapfrog in fact is very good for solving wave equations with wave behavior. Let's come back here. Same equation but now we can do something else. We can do improve our accuracy. So if you want to prove your accuracy, we can do something like a fourth order accurate different scheme for the first derivative. And here it is. And so when you put that in along with the center difference in time that we had before, here is your new scheme. This is called Leaprog 24. What we've done is we've improved the accuracy of the discretization in space to be fourth order accurate, but we're still using a second order accurate scheme in time. So that's leapfrog 24. Okay. a little bit more complicated scheme. I'm using more neighbors because that's what happens when you improve accuracy to finite differences. You're usually just using more neighbors. So, I've used more neighbors, but I've dropped my error from delta x^2 to delta x to the 4th, which is a big improvement in spatial error. Okay, my time stepping error is still delta t ^2, however. So, just keep that in mind as you do this.

8:33 Let's come up with a different scheme. This is called the lax windruff scheme. So this is a famous scheme and it was partly because people really liked its stability properties and it had some a little bit of artificial diffusion in the stepping so that it actually stabilized the scheme. So again back to the stability properties but I want to do how to develop this is just simply say I'm going to do a tailor expansion of u of t around t plus delta t. So if this here is just a tailaylor series expansion of the solution delta t into the future and then the question is what do I do with these here? So you know that what you're solving is in fact the one-way wave equation. So you know that u of t is equal to cux. Oh so if I have cux then I can discretise it and I'm going to put it right into this position here. But then I also have a second derivative in time. You can easily show if you take the derivative of this again to get the second derivative of u in time it's al it's equal to c ^2 u xxx and I can do a center difference scheme and put that in here to get up with this lax windruff scheme here. Notice there's still the CFL number floating throughout. I have a lambda here CFL number and CF number squared here. And now this is the lax windruff scheme for marching the solution forward in time. So now what we have is we've got four schemes. We have leaprog 22, we have forward diff oiler in time center difference in space. We have leaprock 24 lax windruff.

10:06 We're up to four schemes. let's do a fifth scheme. This is called the backward oiler scheme. So remember that before we took a center diff forward difference in time. But I always evaluate this at the current time point. But what if we evaluate this at the future time point? This may seem like a silly idea because that's exactly what we're trying to solve for. But the reason people like implicit schemes, in fact, let's work this all out. So now your stepper becomes this here where you're solving you know you're solving for the future in terms of the future. If you rearrange here's what you get here. This tells you that here's my current point, here's my future point.

10:48 And then this is just becomes an ax equal to b solve. So for the future points. Okay. So this is expensive. Before I just simply computed the future points. Now I've got to solve a matrix problem in order to get the future points. But the reason people like implicit schemes is they typically have amazing stability properties. So they're harder to solve, but you buy yourself stability. So, these are all the considerations and trade-offs you got to be thinking about when you come up with an appropriate scheme to solving your PEP.

11:22 keep going on schemes. So, we're up to five schemes. Here's scheme number six. These are called McCormic schemes or predictor correctors. So one of the things that you like about implicit schemes is their stability properties. But it's always hard to solve for the future in terms of the future and you have to solve this expensive ax equal to b. So what if I were to use the predictor corrector method has this idea that I'll predict the future and use that prediction in my implicit scheme.

11:53 So the way this goes is you first predict the future. So you use your standard scheme to predict the future like an oiler step into the future. And now that's a prediction for this future inside of your implicit scheme. So you predict the future and then you now make a correction to the future using the prediction of the future in this implicit scheme that you developed. So now you're no longer having to solve this ax equal to b. you're just using your prediction for the of the future in the right place in order to update the solution in the future.

12:27 So there's so many variants I covered six. There's so many more. People historically have really looked at this because what you want is the most accurate solution and the most stable algorithm possible to to march forward your solution. And this depends so much upon the actual PD that you're solving. you would use very different steppers for different PD classes. So oftentimes if you're looking at a problem that's been studied for quite a while, you want to look at the literature to see what are the methods that people have developed historically that are very stable, robust, and have high accuracy properties because probably they figured that out and you would want you like to use the best scheme right out of the box if you can. So just a little research will often show you what people have done in that area. So stability and accuracy, those are the things that we're really considering in going after solutions. And this is what we're going to be talking about throughout this set of lectures here on time and space stepping schemes.