Consistency of upwind finite volume schemes

It is not a well known fact that upwind finite volume schemes on non-uniform grids are formally (in the sense of MPDE) inconsistent. Consider a single conservation in one dimension

$$\frac{\partial u}{\partial t} + \frac{\partial}{\partial x} f(u) = 0$$ (1)

and a flux-splitting

$$f(u) = f^+(u) + f^-(u)$$ (2)

where

$$\begin{array}{l} f^+ \textrm{ is a non-decreasing function} \\ f^- \textrm{ is a non-increasing function} \end{array}$$

Let the domain be divided into cells with centers $x_j$ and cell length $\Delta_j$. The finite volume scheme is given by

$$\frac{u^{n+1}_j - u^n_j}{\Delta t} + \frac{ f^n_{j + 1/2} - f^n_{j-1/2} }{ \Delta_j} = 0$$ (3)

with numerical flux function

$$f^n_{j + 1/2} = f^+(u^n_j) + f^-(u^n_{j+1})$$ (4)

We need some more definitions

$$\begin{eqnarray*} \Delta_{j+1/2} &=& \frac{1}{2}( \Delta_j + \Delta_{j+1}) \\ f... ...rm{d}}{\textrm{d}u}f^+(u) - \frac{\textrm{d}}{\textrm{d}u}f^-(u) \end{eqnarray*}$$

Assuming that the solution is smooth, we obtain the following modified partial differential equation (MPDE)

$$\frac{\partial u}{\partial t} + \frac{\partial }{\partial x}f(u) = TE_{visc} + TE_{cons} + TE_{hot}$$ (5)

The truncation error terms are as follows

$$\begin{eqnarray*} TE_{visc} &=& \frac{\Delta t}{2}\partial_x (f^{\prime^2}(u^n_j... ...lta_j} ) + O(\frac{\Delta^3_{j-1/2}}{\Delta_j} ) + O(\Delta t^2) \end{eqnarray*}$$

The above terms correspond respectively to the numerical viscosity of the scheme, to the consistency of the scheme, and to some higher-order terms. Note that the consistency term vanishes identically if uniform grids are considered. It can be expected to be negligible for smoothly varying grids. On the other hand if non-smooth grids are considered, the scheme is not consistent. As an example is the grid

$$......,\Delta x/2, \Delta x, \Delta x/2, \Delta x, \Delta x/2, ......$$

the consistency term is O(1) and it does not vanish even as $\Delta x$ tends to zero.

In practice however it has been found that solutions exhibit the expected accuracy even on non-uniform grids. This phenomenon is known as supraconvergence. Cockburn and Gremaud [1] give a numerical example to illustrate this phenomenon.

The following numerical example shows that the inconsistency of the scheme on rough grids does not prevent it from converging at the optimal rate. In Figure 1 below we display the performance of the Engquist-Osher scheme on the classical example of the Burger's equation with periodic boundary conditions and a sinusoidal initial condition.

About 400 randomly generated - and thus non smooth - grids were considered. The global $L^1$ - error at the final time is represented with respect to $\Delta x$, size of the largest element. In Figure 1 (left), the exact solution is smooth; the convergence rate is one. In Figure 1 (right), the exact solution exhibits a discontinuity but, interestingly enough, the scheme converges without any loss in the numerical rate of convergence. This shows that the (formal) truncation error is a poor indicator of the quality of a numerical algorithm.

They then go on to give a proper definition of truncation error and show that

.... the optimal rate of convergence of $(\Delta x)^{1/2}$ in $L^\infty(L^1)$ can be obtained, even for inconsistent schemes, because the consistency of the numerical flux and the fact that the scheme is written in conservation form allow the regularity properties of the numerical approximation to compensate for the lack of consistency of the scheme; the nonlinearity of the problem does not play any role in this mechanism.

So in practice, the order of accuracy of an upwind finite volume scheme is determined by the accuracy with which the flux integral is evaluated. This accuracy depends on the order of reconstruction/recovery (k, k=1 for constant in cell approximation, k=2 for linear approximation, etc.) and the order of Gaussian quadrature (which depends on the number of Guassian points $N_g$. Thus the practical order of accuracy (r) is

$$r = min( k, 2N_g)$$

Interestingly finite difference schemes are always consistent. To see this let us first write the conservation law (1) in the flux split form

$$\frac{\partial u}{\partial t} + \frac{\partial }{\partial x}f^+(u) + \frac{\partial }{\partial x}f^-(u) = 0$$ (6)

The first order upwind finite difference scheme is

$$\frac{u^{n+1}_j - u^n_j}{\Delta t} + \frac{ f^+_j - f^+_{j-1... ..._{j+1} - f^-_j }{ \frac{1}{2}( \Delta_{j} + \Delta_{j+1})} = 0$$ (7)

Since each of the finite difference terms in the above equation is first order accurate, the scheme is consistent. But unfortunately it cannot be written in conservative form. Consistent and conservative schemes are constructed in Rezgui et. al. [2], which also defines some measures of mesh distortion and their effect on solution accuracy.

References

1. Bernardo Cockburn and Pierre-Alain Gremaud, A priori error estimates for numerical methods for scalar conservation laws. Part II: Flux-splitting monotone schemes on irregular Cartesian grids.
2. Ali Rezgui, Paola Cinnella, Alain Lerat, Third-order accurate finite volume schemes for Euler computations on curvilinear meshes, Comp. and Fluids, 30, 2001.