[MUSIC] Hi, welcome again to this third week of the course, Simulation and Modeling of Natural Processes. In this module of the class, we'll talk about an alternative way of building a numerical scheme which is called an implicit way. So how does this work? First we can have a motivation. So we have several problems that can appear with the explicit numerical scheme. Here you have an example. So imagine that you have a differential equation which is simply s.= -10(s). So this differential equation has an analytical solution and it is simply decreasing exponential. So you see the analytical solution is s0 exp (-10t). When we do an explicit side margin to solve this equation, the numerical scheme we'll apply is s(t + delta t) = s(t)- 10 times s. So you see that now if delta t, so let's say imagine that we start at s0 = 1. [COUGH] If now delta t is too big, for instance bigger than one-tenth. What you see is that after the first iteration, you will reach a point where your solution is negative. So it can be really very negative for instance if delta t = 1, your s1 will be -9. Then if you go to the next step, what you will get is that the solution will grow positive again. And then again negative and positive until it might even increase in size so this variation can go bigger and bigger. And in the end, even become larger than the maximum value of a number you can represent on your computer. So this situation is illustrated on the image on the slide, where you see the black curve is the analytical solution of your differential equation, and you have three different cases. So one is with a deep delta t small enough so that the solution is relatively close to the analytical solution and then in the green and blue curves, we increase delta t. What you notice is that you have an oscillation of your numerical solution. In the green case, it seems that, in the end, the solutions still converges towards the exponential. Nevertheless, you see that the solution you get becomes even negative, which is not the case for this decreasing exponential normally. So, what you see then with the blue curve is that it oscillates but that these oscillation become bigger and bigger. And in the end, it even becomes so big that you can not see it on the picture but it will become bigger than the maximum number that we can represent on a computer. So what does that mean here? It means that with explicit diverging it is difficult to resolve with large delta t problems which are varying too fast in time. So why is that? The thing is that, since we are only using information at time t to guess the value at time t + delta t. If, in the interval, the variation is too big, there is no way we can guess the next value correctly. So how can we try to solve this problem? Let's go back to our tailor expansion we did in previous modules. So instead of evaluating with the tailor expansion S(j) + 1 as we did, let's try to evaluate Sj- 1. So in the first equation, you get these tailor expansion truncated at order one and what you get these that we have Sj- 1 = Sj- delta t times f(S, tj). [COUGH] Now, let's forget about the error term that is present here. And let's also rewrite this equation by letting the left-hand side become Sj + 1 so what we get is the following numerical scheme. So we'll have Sj + 1 = Sj + delta t of f(Sj + 1, tj + 1). So what you see here is that our scheme is not so, the evolution of Sj is not only governed by the value of Sj at the previous time step, it is also governed by f of Sj at the current time step. This way of doing the time margin is implicit because basically it requires to solve this equation, which can be implicit in most of the cases. So what do we gain now? So, let's go back to our example, and so you have on the right of the slide, a comparison between the two schemes. So on the right you have the explicit time margin, and on the left you have the implicit time margin. You see that the things you have to compute are quite different. Here, you don't need to solve an implicit equation, you simply need to solve an equation you can do it analytically, so it's not a big problem. So the implicit time scheme is that sj +1 = sj / (1 + 10 delta t), while for the explicit time scheme sj + 1 = sj (1- 10 delta t). So, on the left of the slide, you see the major difference. For the same delta t's as the ones I showed you in the first leg of this presentation, you see that there is no oscillation. Here the dashed green line is just to remind you the result with the explicit time scheme or the other with dotted points are with implicit time scheme. And we see here that there is no spurus oscillation and that the scheme is completely stable. So we solved the instability. The price we had to pay is that we had to solve this equation analytically before implementing the scheme. Okay, let's try to have an interpretation on why is the implicit time margin more stable? So on the left of your slide, you have a function which is the black line, which we are trying to approximate using an explicit time scheme. At step one, what you see, so you have a dot representing the value of the function. And basically, you will jump to the point 2 by using the derivative of this function at point 1. So you really have only the information you have at your current position to evaluate the value that you will jump to. Then you go to point 2 and it's again, the same. You will use the derivative you have on point 2 of your function to jump to point 3. In the implicit time margin now, what you do is that you use the derivative of your next time to evaluate by how much you must jump. So you have an idea of what is the target value you will go to. So you can anticipate in some sense fast variations of your function here. So to summarize the difference between explicit and implicit time schemes. In explicit time schemes, you solve an explicit equation. So, it's easier to do. It's easier to implement. It's almost always also faster but on the other hand, it can be not so stable. So, for instance, you cannot choose any delta t and still get a reasonable solution. On implicit margin, on the other hand, so you need to solve this usually implicit equations. So this is more complicated, not only conceptually but also to implement. How to do it is also sometimes a slower but you have a huge gain, you are unconditionally stable so you don't have to care that much about how much you will jump and you will still get a good solution. So on the two pictures on this slide, you saw the two different approaches. The dots on the left, the left picture, the dots are the resolution of the growth population problem with the explicit time scheme in the squares are obtained with the implicit time scheme. So, you see that all in all, the difference is not that huge in term of error. This can also be noticed on the right, where we measure the actual error committed by the two schemes. So both schemes, since are both of the same order of error, have pretty much the same error, and the conversions of their error is almost the same too. So really the real difference is about stability and how you can choose your delta t. Okay, with this, I end my presentation on these implicit schemes. And in the next module, I will talk about the integration of partial differential equations. So we'll add a bit of space dependence here. Thank you for your attention. [MUSIC]