We started off with Euler's method. Runge-kutta we said we could improve the accuracy by adding stages at each time step that means additional evaluations of F. Now we're going to try a different way of improving the accuracy will use and some of the history of the solution. This is called a multistep method. For example we could say ui plus one is ui plus a combination of F at time i. And f at time i minus one. This looks like two evaluations of f. But if we're smart this evaluation of f could have been stored during the previous time step and so we don't have to recompute it. Some notation here to make things easier. F sub j means f at time t j and value uj. With that notation a general multi-step formula looks like this. U i plus one is a combination of UI and on back to u i minus k plus one. K is some positive integer plus h times a combination of F values at those same time levels. We have to start this formula at i equals k minus one so that we don't get any negative time indices. This wouldn't make any sense. And we call this a k step method. In order to do that first step with i equals k minus one. We would have references to U0 U1 and so on up to u k minus one. So we need these starting values to get going. Yo comes from the initial conditions. These others usually come from a Runge-Kutta formula. Once you've got those then you use the multi-step formula the rest of the way. There is an important distinction between different multi-step methods. If this leading BK constant is equal to 0 we say the method is explicit. If it's non-zero we say it's implicit >> This matters because u i plus one is actually hiding in two places and an implicit method. For example if we look at the easiest to implicit method which is called backward Euler. It looks a lot like the Euler method but we have an index i plus one instead of i on the F. This is a one-step method. And we can write out what all the constants are for it. In the general formula >> We say what exactly this f i plus one means. Then we see that UI plus one which is the thing we're trying to find at this timestep appears in two places. So to find it we now have to solve this equation which depending on f is probably a non-linear equation. If you as a vector then it's actually a system of equations. Let me describe two important families of multi-step methods though there are others. We have the atoms bash fourth method or family of methods. These all have a k minus one equal to one. And all the other a's are equal to 0. And either explicit methods. So bk is also 0. You get one of these for every value of k. And then a close relative or the atoms molten formulas. They have the same patterns in the a constants. But these are implicit methods and so the bk is non-zero. Here again is our general multi-step formula. It's quite cumbersome to write out every single time. So we do have a shorthand there called the generating polynomials of the method. We use the a constants to define a polynomial row of Z. And we use the B constants in the formula to define another polynomial sigma of z. So if we know rho and sigma than we know all these constants and then we can write out the full method. For instance going back to the backward Euler method. Which is actually the ends molten method of order one. Row of Z Z minus one. And sigma of Z is just Z. The other method the first method that I wrote out is actually the atoms bash worth method of order two. That has rho equal to z squared minus z and sigma equal to three have z minus a half. So for every method there are some simple properties. The degree of the row polynomial is equal to k which is the number of steps. Degree of sigma is also equal to K. If the method is implicit. And it's less than that. If the method is explicit. Another shorthand for describing these methods is called this tensile. It leaves out the constants and just shows the positions of things in time. So we have one column of U values in another column of f values. Time is increasing in the columns. So firm Adams batch worth method. We would use just two different values of u. And then we would use values of f starting at time TI and going back In an atom's molten method we use the same to you values but now we also use the f value at time i plus one. The empty symbols here represent things that are unknown. When we're trying to find a new time-step. We can define truncation error for multi-step methods. Much the same as we did for Runge-Kutta >> You plug in the exact solution u hat. Take the difference of the two sides of the formula and divide everything by h. So we can write this out in its full glory >> And then the idea as the Runge-Kutta is to expand all this around time TI and look for the leading power of h. For example let's look at the Add-ins molten method of order two. This is known as the trapezoid formula. It has rho equal to z minus one. That's a typo on the slide. It should say Z minus one. And sigma is equal to 1.5 plus 1.5 >> So we can write out what tau is for this method. And the trick here is to get rid of these Fs by using the fact that you had solves the differential equation. So the derivative of u hat is equal to f. So we'll replace the Fs by u hat primes. We expand everything in the first term around time TI. We get this mess. Inside the brackets we replace the f's. But now this u hat i plus one has to be expanded around time TI as well. So we apply Taylor's theorem again. So now if we look at this first term u hat i's cancel out >> Everything else is divided by h. And in the second term the u hat i primes combine everything else things around. Finally we see a bunch of stuff cancels out. And tau starts with constant times h squared times u hat triple prime. What we really care about here >> That the leading power of h is h squared. So we call this a second order accurate method. Finally let me say something about how these multi-step methods can be derived. It's a familiar pattern. We interpolate some data by a polynomial to represent a function that we don't know exactly. And then we do an operation on the interpolant and place of that function >> One way we might use this for example is to interpolate the values of u u i plus one UI going on back by a polynomial p of t. And then we will set p prime at t i plus one equal to F at time i plus one which is what the exact solution would satisfy. You work this out the resulting method is called a backward differentiation or a backward difference method. Another alternative is to use the fundamental theorem of calculus right write the difference of U hat values at the integral of its derivative but the derivative of u hat is f >> We don't know you had at all times so we don't know f at all times. But we know some values for f. So we'll replace this integrand by a polynomial interpolant of those values and integrate that. When you work that out you get in that it's bash worth method. And so on
FNC 6.6: Multistep methods
From Tobin Driscoll November 17, 2019
49 plays
49
0 comments
0
You unliked the media.