Convergence of conservative schemes

The ultimate test of a numerical method is to establish its convergence to the analytical solution in the limit of grid refinement. Convergence proofs of numerical methods are also used to establish the existence of solutions to PDE. Let $u$ be the exact solution and $U$ the numerical solution. We are typically interested in an unsteady problem and assume that the solution is desired at time $T$. The numerical scheme is written as

$$U^{n+1} = H(U^n)$$ (1)

The local error or one-step error or truncation error is defined as

$$\tau^n = \frac{ H(u^n) - u^{n+1} }{\Delta t}$$ (2)

Contractive operators
The numerical solution operator $H(\cdot)$ is said to be contractive in some norm $\vert\vert \cdot \vert\vert$ if

$$\vert\vert H(U) - H(V) \vert\vert \le \vert\vert U - V \vert\vert$$ (3)

for any two grid functions $U$ and $V$. If the method is contractive then it is stable in this norm and we can obtain a bound on the global error

$$\begin{eqnarray*} E^{n+1} &=& U^{n+1} - u^{n+1} \\ &=& H(U^n) - u^{n+1} \\ &=&... ...) - u^{n+1} ] \\ &=& [ H(u^n + E^n) - H(u^n) ] + \Delta t\tau^n \end{eqnarray*}$$

$$\begin{eqnarray*} \vert\vert E^{n+1} \vert\vert &\le& \vert\vert H(u^n + E^n) - ... ...\vert\vert E^n \vert\vert + \Delta t\vert\vert \tau^n \vert\vert \end{eqnarray*}$$

By iterating we obtain

$$\vert\vert E^N \vert\vert \le \vert\vert E^o \vert\vert + \Delta t\sum^{N-1}_{n=0} \vert\vert \tau^n \vert\vert$$

Assume that the local truncation error is bounded by

$$\tau_o = \max_n \vert\vert \tau^n \vert\vert$$

Then we have

$$\begin{eqnarray*} \vert\vert E^N \vert\vert &\le& \vert\vert E^o \vert\vert + N\... ...\ &=& \vert\vert E^o \vert\vert + T \tau_o (N\Delta t= T) \end{eqnarray*}$$

The term $\vert\vert E^o \vert\vert$ measures the error in the initial data on the grid, and we require that $\vert\vert E^o \vert\vert \to 0$ as $\Delta t\to 0$ in order to be solving the correct initial-value problem. If the method is consistent, then also $\tau_o \to 0$ are $\Delta t\to 0$ and we have proved convergence. Moreover, if $\tau_o = O(\Delta t^s)$, then global error will have this same behaviour as $\Delta t\to 0$ (provided the initial data is sufficiently accurate), and the method has global order of accuracy $s$.

Actually a somewhat weaker requirement on the operator $H$ is sufficient for stability,

$$\vert\vert H(U) - H(V) \vert\vert \le (1 + \alpha \Delta t)\vert\vert U - V \vert\vert$$ (4)

where $\alpha$ is some constant independent of $\Delta t$ as $\Delta t\to 0$. If the above condition holds then we get

$$\vert\vert E^{n+1} \vert\vert \le (1 + \alpha \Delta t) \vert\vert E^n \vert\vert + \Delta t\vert\vert \tau^n \vert\vert$$

and so

$$\begin{eqnarray*} \vert\vert E^N \vert\vert &\le& (1 + \alpha \Delta t)^N \vert\... ... T} ( \vert\vert E^o \vert\vert + T \tau_o) (N\Delta t= T) \end{eqnarray*}$$

In this case the error may grow exponentially in time, but the key fact is that this growth is bounded independently of the time step $\Delta t$. For fixed $T$ we have a bound that goes to zero with $\Delta t$.

Convergence to weak solutions
One class of schemes which are contractive are monotone methods, see section (4) for definition of monotone property. Unfortunately this property holds only for certain first-order accurate methods (monotone methods are always first order accurate). Hence we need to look for some other stability condition and for conservation laws the condition of TVD or TVB is suitable since the exact solutions also have the same property, again see section (4). This approach has been successful only for scalar problems. For general systems of equations with arbitrary initial data no numerical method has been proved to be stable or convergent in general, although convergence results have been obtained in some special cases.

The solution is assumed to be piece-wise linear

$$U^\Delta(x,t) = U^n_i \textrm{for} (x,t) \in [x_{i-1/2}, x_{i+1/2}) \times [t^n, t^{n+1})$$

where the index $\Delta$ is used to denote the grid size $(\Delta x, \Delta t)$. We are interested in the behaviour of the above solution on a sequence of grids $\Delta_j = (\Delta x^j, \Delta t^j)$ with $\Delta x^j \to 0$, $\Delta t^j \to 0$ as $j \to \infty$.

One difficulty with conservation laws is that the global error

$$U^\Delta(x,t) - u(x,t)$$

is not well defined when the weak solution is not unique. Instead, we measure the global error in our approximation by the distance from $U^\Delta$ to the set of all weak solutions $W$,

$$W = \{ w : w \textrm{ is a weak solution to the conservation law } \}$$

To measure this distance we use the 1-norm

$$\vert\vert w \vert\vert _{1,T} = \int^T_0 \vert\vert w(\cdot... ...nt^\infty_{-\infty} \vert w(x,t) \vert \textrm{d}x \textrm{d}t$$

and the global error is defined as

$$d(U^\Delta, W) = \inf_{w \in W} \vert\vert U^\Delta - w \vert\vert _{1,T}$$

The convergence result takes the following form
If $U^\Delta$ is generated by a numerical method in conservation form, consistent with the conservation law, and if the method is stable in some appropriate sense, then

$$d(U^\Delta, W) \to 0 \textrm{ as } \Delta t\to 0$$

Note that this only ensures that the solutions converge to some weak solution but does not guarantee uniqueness. If the conservation law satisfies an entropy condition then the exact solution is unique. We can try to check whether the numerical solutions also satisfy a discrete form of the entropy condition which would ensure uniqueness of the numerical solution also.

Compactness and Total-variation stability
Compactness is a useful concept for non-linear equations. While compactness can be defined in many ways, the most useful definition in our case is that of sequential compactness. We say that a set $X$ is (sequentially) compact if given any sequence $(z_n)$ belonging to $X$ we can extract a sub-sequence $(z_{n_j})$ which converges to some element of $X$.

To prove convergence we must first ensure that the sequence of numerical solutions all belong to a compact set. The set of all functions with bounded 1-norm

$$L_{1,T} = \{v : \vert\vert v \vert\vert _{1,T} < \infty \}$$ (5)

is not compact. Reasons which prevent this set from being compact are unbounded support of the functions and highly oscillatory behaviour. To control the oscillations we impose a stability condition in the form of a bound on the Total-Variation, which is defined as

$$TV_T(v) = \limsup_{\epsilon \to 0} \frac{1}{\epsilon} \int^T_0 \int^\infty_{-\infty} \vert v(x+\epsilon, t) - v(x,t) \textrm{d}x \textrm{d}t$$

$$+ \limsup_{\epsilon \to 0} \frac{1}{\epsilon} \int^T_0 \int^\infty_{-\infty} \vert v(x, t+\epsilon) - v(x,t) \textrm{d}x \textrm{d}t$$ (6)

We now look for solutions which belong to the following compact space

$$K = \{v \in L_{1,T} : TV_T(v) \le R \textrm{ and } \textrm{supp}( v(\cdot, t) ) \subset [-M, M] \forall t \in [0,T] \}$$ (7)

where the positive constants $R$, $M$ depend on $T$ and the initial condition. Note that the conditions on total-variation and support of the function are also satisfied by the exact solution of the conservation law.

The numerical solution is piece-wise constant and its total-variation is given by

$$TV_T(U^\Delta) = \sum^{T/\Delta t}_{n=0} \sum^\infty_{i=-\in... ..._i - U^n_{i-1} \vert + \Delta x\vert U^{n+1}_i - U^n_i \vert ]$$ (8)

which can also be written as

$$TV_T(U^\Delta) = \sum^{T/\Delta t}_{n=0}[\Delta t TV(U^n) + \vert\vert U^{n+1} - U^n \vert\vert _1 ]$$ (9)

References

• This note is based on chapters 8 and 12 of
  RJ LeVeque, Finite volume methods for hyperbolic problems, Cambridge Univ Press, 2002.
• For the notions of convergence and compactness see
  W Rudin, Principles of Mathematical Analysis, McGraw Hill.
• For more on total variation, see the material on functions of bounded variation in
  Apostol, Mathematical Analysis.