3
$\begingroup$

For the first-order explicit upwind scheme, it can be easily shown that, if one keeps the same grid size and progressively decreases the time step below the max allowed one (i.e. below CFL~1) the numerical diffusion increases with $(1-CFL$), see eq. 11.11 here). If I recall correctly, the same is also true for centered explicit schemes, as well as for higher order explicit schemes (both upwind and centered). Is there any similar result for implicit schemes? Or is numerical diffusion always decreasing with a decreasing time step for implicit schemes, also when you enter the region CFL<1?

$\endgroup$
5
  • $\begingroup$ For a fixed spatial scheme and a chosen mesh, your continuous problem is transformed into a "fixed" system of ODEs. These ODEs can then be solved by any integration method you like (implicit, explicit...). Decreasing the time step always improves the accuracy of the solution. Maybe my answer here can give you more insight as to why: scicomp.stackexchange.com/questions/37157/… $\endgroup$
    – Laurent90
    Apr 23 at 6:47
  • $\begingroup$ It is not true. For explicit schemes the solution is more diffusive by decreasing the time step, see equation 11.11 I linked on the question. That is pretty well known. Try to apply a simple scheme like 1st order upwind with Euler explicit and a smaller time step gives a less accurate solution. $\endgroup$
    – Millemila
    Apr 23 at 16:42
  • 1
    $\begingroup$ Well for the case of advection with uniform velocity on a uniform grid yes, then CFL=1 with explicit Euler yields the exact solution, because the "instability" due to the temporal scheme exactly compensates the "stabilization" (numerical diffusion) produced by the spatial scheme. But in more complicated problems this does not necessarily hold, especially for non-uniform meshes and problems where different components are advected at different speeds (Euler equations for instance)... $\endgroup$
    – Laurent90
    Apr 23 at 18:13
  • $\begingroup$ Mmm I still think it holds, since you need to fix the max allowable time step based on (i.e. as close as possible and slightly lower than) the fastest traveling wave (max eigenvalue of the matrix of the system). Therefore, when the time step is smaller than the max, all the other waves are traveling slower and then they are diffused. I never seen a proof of it, but I think what I am saying holds also in multiple dimensions and for any mesh and for any hyperbolic problem, as long as you have a single time step for the entire domain (i.e. you don't use local time stepping) $\endgroup$
    – Millemila
    Apr 23 at 18:48
  • $\begingroup$ To be precise, what I meant is "I still think it holds, since you need to fix the max allowable time step based on (i.e. as close as possible and slightly lower than) the fastest traveling wave (max eigenvalue of the system matrix). When the time step is smaller than the max, all the other waves are traveling slower and they are somewhat diffused. " $\endgroup$
    – Millemila
    Apr 23 at 18:56
2
$\begingroup$

Short Answer: There is no general result that would hold for all implicit schemes. The reason is that how your method behaves with respect to numerical diffusion depends on the specific combination of numerical time stepping scheme and spatial finite difference.

However, note that if your discretisation is consistent with your PDE and your PDE does not have diffusion, then numerical diffusion must vanish as $\Delta x, \Delta t \to 0$.

Longer answer: You may want to look up the concept of discrete dispersion relations. See for example Section 3.4.1 in the book by Durran. If you consider explicit Euler with first order upwind scheme

\begin{equation} \frac{u^{n+1}_j - u^n_j}{\Delta t} + c \frac{u^n_j - u^n_{j-1}}{\Delta x} = 0 \end{equation}

for the transport equation $u_t + c u_x = 0$ and insert a discrete plane wave

\begin{equation} u^n_j = e^{i (k \Delta x j - \omega \Delta t n)} \end{equation}

you get after some algebra that

\begin{equation} | A |^2 = 1 - 2 \nu (1 - \nu) \left(1 - \cos(k \Delta x) \right) \end{equation}

where $|A| = e^{i \text{Im}(\omega) \Delta t}$ is the so-called amplification factor and $\nu = c \Delta t / \Delta x$ is the CFL number. The amplification factor tells you what happens to the amplitude of your numerical solution:

  • $|A| > 1$ means it is growing and the scheme is unstable
  • $|A| = 1$ means it stays constant, the scheme is stable and there is no numerical diffusion
  • $|A| < 1$ means the scheme is stable but with numerical diffusion.

For your explicit Euler / upwind method, you find that for $\nu = 1$ you get $|A| = 1$ and for $\nu < 1$ you have $|A| < 1$ and thus numerical diffusion (numerical because your original PDE has no diffusion and amplitudes of solutions are constant).

However, this depends on the precise combination of time stepping method and finite difference. For example, explicit Euler with centred difference will always have $|A| > 1$ and thus be unconditionally unstable. If you use, e.g., trapezoidal rule with centred differences you get $|A| = 1$. For implicit Euler, you will always have $|A| < 1$.

I noted that in your comments you write "Therefore, when the time step is smaller than the max, all the other waves are traveling slower and then they are diffused." This is not diffusion but what is called numerical dispersion. It depends on whether the numerical scheme moves waves with a certain wave number at different speeds than your PDE. This can also be analysed via the discrete dispersion relation.

Partial answer to comment. You can use this methodology to address your question about implicit Euler with upwind. If you consider the method

\begin{equation} u^{n+1}_j - u^n_j + \nu \left( u^{n+1}_j - u^{n+1}_{j-1} \right) = 0 \end{equation}

with $\nu = c \Delta t / \Delta x$ and you plug in the discrete plane wave, you get

\begin{equation} \exp(-i \omega \Delta t) - 1 + \nu \exp(-i \omega \Delta t) \left( 1 - \exp(-i j \Delta x \right) = 0. \end{equation}

Let $\omega = a + i b$ so that $\exp(-i \omega \Delta t) = \exp(b \Delta t) \exp(-i a \Delta t) =: A \exp(-i a \Delta t)$ where $A$ is the amplification factor you are looking for. Then,

\begin{equation} A \exp(-i a \Delta t) - 1 + \nu A \exp(-i a \Delta t) \left( 1 - \exp(-i j \Delta x) \right) = 0. \end{equation}

You will have to solve this for $A$ somehow - useful tricks are mentioned in the Durran book. I am pretty sure the result will show that your diffusion increases as $\Delta t \to 0$ if you keep $\Delta x$ fixed.

Durran, Dale R., Numerical methods for fluid dynamics. With applications to geophysics., Texts in Applied Mathematics 32. Berlin: Springer (ISBN 978-1-4419-6411-3/hbk; 978-1-4614-2685-1/pbk; 978-1-4419-6412-0/ebook). xv, 516 p. (2010). ZBL1214.76001.

$\endgroup$
8
  • $\begingroup$ Thank you. The proof you showed is the same I linked in my question, although I agree it is more convenient to have it handy. What I meant with "Therefore, when the time step is smaller than the max, all the other waves are traveling slower and then they are diffused" was actually numerical diffusion, not dispersion. In an upwind scheme with Euler explicit, if you fix the time step for the fastest wave (for stability let's say CFL=0.95, using the fastest way to compute CFL) the slowest waves have A<<1 and then they are diffused more than the fastest wave. That is not dispersion. $\endgroup$
    – Millemila
    Apr 26 at 13:06
  • $\begingroup$ As for Euler implicit (since that is my still unanswered question): If we focus on 1st order upwind with Euler implicit for simplicity, do we still have that for CFL<<1 the scheme is more diffusive than CFL just below 1? $\endgroup$
    – Millemila
    Apr 26 at 13:09
  • $\begingroup$ As for the multiple-wave scenarios above, as I wrote I was speaking of a system of PDEs, so with multiple eigenvalues (wave speeds). $\endgroup$
    – Millemila
    Apr 26 at 13:12
  • $\begingroup$ If you have a linear system of PDEs, you can diagonalise the matrix, transform into eigencoordinates and look at each eigenvalue separately. For nonlinear problems, things become a lot more difficult. $\endgroup$
    – Daniel
    Apr 26 at 13:33
  • $\begingroup$ I know that. That is the basis of the statement I made above about diffusion, not dispersion. $\endgroup$
    – Millemila
    Apr 26 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.