#  Stability analysis of the Eulerian-Lagrangian finite volume methods for
nonlinear hyperbolic equations in one space dimension ††thanks: The first
author was supported by Simons Foundarion 961585. The second and last author
were supported by NSF grant NSF-DMS-2111253, Air Force Office of Scientific
Research FA9550-22-1-0390 and Department of Energy DE-SC0023164.

Yang Yang, Jiajie Chen, Jing-Mei Qiu Department of Mathematical Sciences,
Michigan Technological University, Houghton, MI 49931, USA.
<EMAIL_ADDRESS>of Mathematics, University of Delaware,
Newark, DE 19716, USA. E-mail<EMAIL_ADDRESS>Department of Mathematics,
University of Delaware, Newark, DE 19716, USA. E-mail<EMAIL_ADDRESS>
Abstract: In this paper, we construct a novel Eulerian-Lagrangian finite
volume (ELFV) method for nonlinear scalar hyperbolic equations in one space
dimension. It is well known that the exact solutions to such problems may
contain shocks though the initial conditions are smooth, and direct numerical
methods may suffer from restricted time step sizes. To relieve the
restriction, we propose an ELFV method, where the space-time domain was
separated by the partition lines originated from the cell interfaces whose
slopes are obtained following the Rakine-Hugoniot junmp condition.
Unfortunately, to avoid the intersection of the partition lines, the time step
sizes are still limited. To fix this gap, we detect effective troubled cells
(ETCs) and carefully design the influence region of each ETC, within which the
partitioned space-time regions are merged together to form a new one. Then
with the new partition of the space-time domain, we theoretically prove that
the proposed first-order scheme with Euler forward time discretization is
total-variation-diminishing and maximum-principle-preserving with at least
twice larger time step constraints than the classical first order Eulerian
method for Burgers’ equation. Numerical experiments verify the optimality of
the designed time step sizes.

Keywords: finite volume method, Eulerian-Lagrangian, nonlinear hyperbolic
equations, stability analysis, total variation diminishing, maximum-principle
AMS(2000) Subject Classifications:  65M08, 65M12

##  1 Introduction

Nonlinear hyperbolic equations have many significant applications in traffic
flow, large scale supply-chains, compressible gas dynamics, magneto-
hydrodynamics and continuum physics, etc. It is well known that the exact
solutions for nonlinear hyperbolic equations may develop shocks though the
initial condition is sufficiently smooth, and direct high-order numerical
methods may yield oscillatory approximations near the shocks. Therefore,
numerical methods for nonlinear hyperbolic conservation laws are challenging
to design.

Finite volume (FV) methods are of great interesting in solving nonlinear
hyperbolic equations [8]. The methods apply numerical fluxes to guarantee the
local mass conservation. Traditional FV methods are coupled with strong-
stability-preserving (SSP) Runge-Kutta (RK) time discretization, and they may
suffer from the limited time step sizes [4]. There are several previous
attempts in the literature to relieve the restriction. For example, in [10] a
third-order Godunov-type scheme with total variation bounded property is
proposed for conservation laws with large time stepping sizes. However, the
scheme in [10] relies on an extra tracking of characteristics via the Lax-Hopf
formula. Another attempt was to design the Eulerian-Lagrangian (EL) FV [6, 7,
9] and the EL discontinuous Galerkin (DG) methods [2]. Yet, many of these
existing research are designed for linear or nonlinear transport dominated
models without shocks, i.e. crossing of characteristics. In the EL framework,
often times the Rankine-Hugoniot (R-H) jump condition was used to approximate
the speed of the characteristic lines, giving a partition of the space-time
domain between the current and next time levels. It is easy to show that if
the characteristics do not intersect, the numerical approximations from the
first-order spatial discretization and Euler forward time integration is
total-variation-diminishing (TVD) and maximum-principle-preserving (MPP) (see
Lemma 3.2). Unfortunately, in the presence of shocks, to avoid the
intersection of the characteristic lines, the time step sizes are still
restricted. There is little previous works in resolving such an issue and
theoretically discussing the precise upper bound of the time step sizes for EL
methods with the presence of shocks.

In this paper, we develop a novel EL FV method using a uniform mesh for 1D
nonlinear hyperbolic problems with the consideration of shocks. A brief
outline of the algorithm is as follows:

  1. 1.

Partition space-time regions by approximating characteristic lines with the
R-H jump condition from cell interfaces. We name the characteristic lines as
partition lines in the rest of the paper.

  2. 2.

Detect effective troubled cells (ETCs), on which the partition lines
originated from cell boundaries intersect within a pre-determined time step
size or the difference between the numerical approximations in the ETC and its
neighbor cell is larger than some threshold.

  3. 3.

Construct the influence region of each ETC (see Definition 3.2).

  4. 4.

Merge the cells within the influence region of each ETC to form a larger one.
In general, the partition lines based on the new partition will not intersect
under the original time step size.

  5. 5.

Keep the original numerical fluxes at the boundaries of the merged cell.

  6. 6.

Update numerical solutions by using the EL FV method [9] on the new mesh.

  7. 7.

Map the numerical solutions to the background uniform distributed cells.

There are two main challenging aspects that we need to address in designing
effective EL FV methods.

  * •

The size of the influence region is not easy to determine. Intuitively, the
larger the influence region, the larger the time step size are allowed to
avoid the intersection of partition lines. On the other hand, large influence
regions may yield poor resolutions near the ETCs that often involve shocks. In
Section 3.2, via manipulated simple examples, we demonstrate that if the
influence region is larger than some threshed, further enlargement of the
influence region will not result in the increase in time step sizes if the
influence regions of the ETCs do not intersect. The influence region we
proposed mainly contains five cells centered at the ETC. In some special
cases, we may need to include one more cell in the influence region to gain
the TVD property or reduce one cell in the influence region to gain better
resolution. See Definition 3.2 for the detailed construction of the influence
region for each ETC.

  * •

Determine the precise upper bound for the time step size with TVD and MPP for
the first-order scheme. On one hand, with merged cells in the influence
region, the original piece-wise constant numerical approximation is being
$L^{2}$ projected to a new constant; and the R-H jump condition will yield new
slopes for the partition lines for the merged region. On the other hand, we
intend to keep the partition lines and the numerical fluxes at boundaries of
the influence region for better resolution. With the new average value in the
merged cell, but the original partition lines and numerical fluxes, the
classical TVD analysis cannot be applied. To fix this gap, i.e. to enable the
use of classical TVD analysis, we reassign the numerical solutions on cells of
the influence region according to the following principles:

    1. (a)

The reassigned numerical solutions on the influence region conserves the
“total mass” within the influence region;

    2. (b)

The total variation of reassigned numerical solutions is no larger than the
original one to guarantee the TVD property;

    3. (c)

The reassigned numerical solutions are MPP;

    4. (d)

The partition lines determined from the R-H condition originated from the
interior cell interfaces of the influence region, as well as the two
boundaries of the influence region based on the updated numerical
approximations, do not intersect within the pre-determined time step size.

The above considerations guide the design of influence region with provable
stability properties. In particular, to keep the original numerical flux at
the two boundaries of the influence region, reassigned solutions on the two
boundary cells of the influence region have to stay the same. Moreover, since
we need to keep the “total mass”, the influence region must contain more than
three cells. Due to symmetry, most the influence regions we construct contain
five cells. However, in some extreme cases, we may need to merge one more cell
next to the boundary or in some unlikely mild cases, we can merge one less
cell (See Definition 3.2).

With suitable construction of the influence region, it is possible to apply
the idea for the traditional EL FV method to update the solution and
theoretically find the optimal time step size for the TVD and MPP properties.
The theoretical analysis is achieved by designing suitable admissible set
based on the properties (a)-(d) given above, and find optimal reassigned
values of solutions on the interior of the influence region to satisfy the
last criteria. Note that the above strategy to reassign numerical solutions is
only for the sake of numerical analysis to obtain the upper bound on the time
step constraint (see Theorem 3.1). In the numerical implementation, one would
simply first perform the merging of influence regions of ETCs; followed by a
first order EL FV method on the updated mesh.

The rest of the paper is organized as follows. We develop the EL FV methods in
Section 2. The stability analysis without and with the merging strategy will
be presented in Section 3. Numerical experiments will be given in Section 4 to
verify the theoretical analysis. We will end with concluding remarks in
Section 5.

##  2 The Eulerian-Lagrangian finite volume formulation

In this section, we propose the FV spatial discretization with Euler forward
time discretization under the EL framework for scalar nonlinear hyperbolic
equations in one space dimension with merging strategy, extending the work
proposed in [2]. The precise definition of the terminologies used in
constructing the numerical method will be summarized in the end of this
section.

We consider the following nonlinear hyperbolic equation

$\left\\{\begin{array}[]{l}u_{t}+f(u)_{x}=0.\\\
u(x,0)=u_{0}\end{array}\right.$ (2.1)

subject to periodic boundary conditions and assume $b\leq u_{0}\leq a$. We
give a partition of the computational domain $\Omega=[0,2\pi]$ as

$0=x_{\frac{1}{2}}<x_{\frac{3}{2}}<\cdots<x_{N+\frac{1}{2}}=2\pi,$

and denote $I_{j}=[x_{j-\frac{1}{2}},x_{j+\frac{1}{2}}]$ as the cells with
length $\Delta x_{j}=x_{j+\frac{1}{2}}-x_{j-\frac{1}{2}}$. In this paper, we
consider uniform mesh and denote $\Delta x=\Delta x_{j}$, $j=1,\cdots,N$. Let
$t^{n}$ be the $n-$th time level and denote $\Delta t^{n}=t^{n+1}-t^{n}$ as
the time step size. In this paper, we consider uniform partition of the time
domain, and use $\Delta t$ for the time step size. However, this assumption is
not essential. Finally, we denote $\tilde{\lambda}=\frac{\Delta t}{\Delta x}$.

The EL FV scheme starts from constructing a partition of the space-time domain
$\Omega_{j}$’s (see figure 1), followed by a forward Euler update of the
solution on a non-uniform mesh $I_{j}^{*}$’s, and an $L^{2}$ re-projection to
obtain the solution on the original uniform mesh $I_{j}$’s. The specific
procedure is outlined below.

$\Omega_{j}$
$t^{n}$$t^{n+1}$$x_{j-\frac{1}{2}}^{\star}$$x_{j+\frac{1}{2}}^{\star}$$x_{j-\frac{1}{2}}$
$x_{j+\frac{1}{2}}$$\widetilde{I}_{j}(t^{n})=I_{j}$$\widetilde{I}_{j}(t^{n+1})=I_{j}^{\star}$$\widetilde{I}_{j}(t)$$\nu_{j-\frac{1}{2}}$
$\nu_{j+\frac{1}{2}}$ Figure 1: Illustration for the space-time region for the
EL FV formulation.

  1. 1.

Given the numerical approximations $u$ at $t^{n}$. We use
$\nu_{j+\frac{1}{2}}$ to be an approximation of the local characteristics
speed of the original problem (2.1) at $x_{j+\frac{1}{2}}$. In this paper, we
take

$\nu_{j+\frac{1}{2}}=\begin{cases}\frac{[f]}{[u]}|_{{j+\frac{1}{2}}},&\text{if}\
u_{j+\frac{1}{2}}^{+}\neq u_{j+\frac{1}{2}}^{-},\\\
f^{\prime}\left(u_{j+\frac{1}{2}}\right),&\text{otherwise},\end{cases}$ (2.2)

where $[u]=u^{+}-u^{-}$ is the jump of $u$, with $u^{+}$ and $u^{-}$ being the
right and left limit of the reconstructed numerical approximation $u$ at the
cell interface.

  2. 2.

Draw partition lines originated from $x_{j\pm\frac{1}{2}}$ with speed
$\nu_{j\pm\frac{1}{2}}$. If the numerical cell average in $I_{j}$ is
significantly larger than that in the right neighbor or significantly smaller
than that in the left neighbor, or the partition lines intersect before
$t=t^{n+1}$, then $I_{j}$ is defined as a troubled cell. In the latter case,
we compute the time that the intersection appears, i.e. to find
$t^{\star}_{j}$ such that

$x_{j-\frac{1}{2}}+\nu_{j-\frac{1}{2}}t^{\star}=x_{j+\frac{1}{2}}+\nu_{j+\frac{1}{2}}t^{\star}.$

Otherwise, we define
$I_{j}^{\star}=[x^{\star}_{j-\frac{1}{2}},x^{\star}_{j+\frac{1}{2}}]$ as the
line segment between the two partition lines at $t=t^{n+1}$ with length
$\Delta x^{\star}_{j}=x^{\star}_{j+\frac{1}{2}}-x^{\star}_{j-\frac{1}{2}}$,
and define $t^{\star}_{j}=\Delta t$. It is easy to see

$\Delta x_{j}^{\star}=\Delta x+\nu_{j+\frac{1}{2}}\Delta
t-\nu_{j-\frac{1}{2}}\Delta t.$ (2.3)

The region enclosed by the two partition lines, $I_{j}$ and $I_{j}^{\star}$ is
called the space-time domain $\Omega_{j}$. Moreover, we define
$\tilde{I}_{j}(t)$ as the line segment between the two partition lines at time
$t\in[t^{n},t^{n+1}]$, and the left and right endpoints are
$\tilde{x}_{j-\frac{1}{2}}(t)$ and $\tilde{x}_{j+\frac{1}{2}}(t)$,
respectively.

  3. 3.

For each troubled cell $I_{i}$, we construct the influence region of $I_{i}$.
In general, we choose the influence region to be

$I_{i-m},\cdots,I_{i},\cdots,I_{i+m}$ (2.4)

with some $m$. In some special circumstances, the influence region may contain
one more cell or one less cell. The precise construction of the influence
region will be given in Definition 3.2. Then we merge the cells in the
influence region and denote the new cell as $I_{i}$. If there is another
troubled cell between $I_{i-1}$ and $I_{i+1}$, we can select $I_{i}$ as the
effective troubled cell (ETC) and the influence region is designed based on
$I_{i}$ only. If an influence region does not overlap with that of other
troubled cells, then we say the corresponding troubled cell is isolated.
Otherwise, we combine the overlapping influence regions together. In Figure 2
we illustrate the merging of five cells in the influence region of an isolated
ETC (region bounded in red lines).

Figure 2: The general case (case I4 in Def. 3.2) of merging of influence
region for an isolated troubled cell.

  4. 4.

After merging the cells, we can construct the first order EL FV scheme on the
updated space time domain $\Omega_{j}$ by integrating (2.1) over $\Omega_{j}$
to obtain

$\displaystyle 0=$
$\displaystyle\int_{t^{n}}^{t^{n+1}}\int_{\widetilde{I}_{j}(t)}u_{t}\
dxdt+\int_{t^{n}}^{t^{n+1}}\int_{\widetilde{I}_{j}(t)}f(u)_{x}\ dxdt$
$\displaystyle=$
$\displaystyle\int_{t^{n}}^{t^{n+1}}\left[\frac{d}{dt}\int_{\widetilde{I}_{j}(t)}u\
dx-\left(\left.\nu u\right|_{\widetilde{x}_{j+\frac{1}{2}}}-\left.\nu
u\right|_{\widetilde{x}_{j-\frac{1}{2}}}\right)+\left(\left.f\right|_{\widetilde{x}_{j+\frac{1}{2}}}-\left.f\right|_{\widetilde{x}_{j-\frac{1}{2}}}\right)\right]\
dt.$ (2.5)

Considering the differential form of (2.5), we have

$\frac{d}{dt}\int_{\widetilde{I}_{j}(t)}u\ dx+\left.\left(f-\nu
u\right)\right|_{\widetilde{x}_{j+\frac{1}{2}}}-\left.\left(f-\nu
u\right)\right|_{\widetilde{x}_{j-\frac{1}{2}}}=0.$ (2.6)

Let

$F_{j\pm\frac{1}{2}}(u)\doteq f(u)-\nu_{j\pm\frac{1}{2}}u,$ (2.7)

we can rewrite (2.6) as

$\frac{d}{dt}\int_{\widetilde{I}_{j}(t)}u\
dx+\left.\hat{F}\right|_{\widetilde{x}_{j+\frac{1}{2}}(t)}-\left.\hat{F}\right|_{\widetilde{x}_{j-\frac{1}{2}}(t)}=0.$
(2.8)

The proposed EL FV method with Euler forward time discretization is

$\Delta x_{j}^{\star}\bar{u}^{\star}_{j}-\Delta x\bar{u}_{j}+\Delta
t\left(\hat{F}_{j+\frac{1}{2}}-\hat{F}_{j-\frac{1}{2}}\right)=0.$

where $\bar{u}_{j}$ and $\bar{u}_{j}^{\star}$ are the numerical cell averages
on $I_{j}$ at time level $n$ and $I_{j}^{\star}$ at time level $n+1$,
respectively. $\hat{F}$ is the numerical flux given as

$\hat{F}_{j+\frac{1}{2}}=\frac{1}{2}\left(F_{j+\frac{1}{2}}(u^{-}_{j+\frac{1}{2}})+F_{j+\frac{1}{2}}(u^{+}_{j+\frac{1}{2}})-\alpha_{j+\frac{1}{2}}(u^{+}_{j+\frac{1}{2}}-u^{-}_{j+\frac{1}{2}})\right).$

Due to (2.2) we have

$F_{j+\frac{1}{2}}(u_{j+\frac{1}{2}}^{-})\stackrel{{\scriptstyle\eqref{eq:
F}}}{{=}}f(u^{-}_{j+\frac{1}{2}})-\nu_{j+\frac{1}{2}}u^{-}_{j+\frac{1}{2}}\stackrel{{\scriptstyle\eqref{nu}}}{{=}}f(u^{+}_{j+\frac{1}{2}})-\nu_{j+\frac{1}{2}}u^{+}_{j+\frac{1}{2}}\stackrel{{\scriptstyle\eqref{eq:
F}}}{{=}}F_{j+\frac{1}{2}}(u^{+}_{j+\frac{1}{2}}):=F_{j+\frac{1}{2}},$

leading to

$\hat{F}_{j+\frac{1}{2}}=F_{j+\frac{1}{2}}-\frac{1}{2}\alpha_{j+\frac{1}{2}}(u^{+}_{j+\frac{1}{2}}-u^{-}_{j+\frac{1}{2}}).$

We can show that the numerical flux given in (2.10) is consistent, by checking
that
$\hat{F}_{j+\frac{1}{2}}(u,u)=F_{j+\frac{1}{2}}(u)=f(u)-\nu_{j+\frac{1}{2}}u.$
In this paper, we consider $f$ to be differentiable and strictly convex. For a
monotone numerical flux, we choose

$\alpha_{j+\frac{1}{2}}=\max\\{f^{\prime}(u^{+}_{j+\frac{1}{2}})-\nu_{j+\frac{1}{2}},\nu_{j+\frac{1}{2}}-f^{\prime}(u^{-}_{j+\frac{1}{2}}),0\\}.$

  5. 5.

Finally, we map the solution back to the original background uniform mesh by
an $L^{2}$ projection.

If we consider the Burger’s equation, i.e. $f(u)=\frac{u^{2}}{2}$, the EL FV
scheme for the Burgers’ equation is given as

$\Delta x_{j}^{\star}{u}^{\star}_{j}-\Delta x{u}_{j}+\Delta
t\left(\hat{F}_{j+\frac{1}{2}}-\hat{F}_{j-\frac{1}{2}}\right)=0,$ (2.9)

where

$\hat{F}_{j+\frac{1}{2}}=F_{j+\frac{1}{2}}-\frac{1}{2}\alpha_{j+\frac{1}{2}}(u_{j+1}-u_{j}),$
(2.10)

with

$F_{j+\frac{1}{2}}(u)=\frac{u^{2}}{2}-\nu_{j+\frac{1}{2}}u,\quad
F_{j+\frac{1}{2}}=F_{j+\frac{1}{2}}(u_{j})=F_{j+\frac{1}{2}}(u_{j+1}),$ (2.11)

and

$\alpha_{j+\frac{1}{2}}=\max\left\\{\frac{u_{j+1}-u_{j}}{2},0\right\\},\quad\nu_{j+\frac{1}{2}}=\frac{u_{j+1}+u_{j}}{2}.$
(2.12)

The choice of $\alpha$ in (2.12) is 0 if the local Riemann problem at the cell
interface yields a shock wave, i.e. $u_{j+1}<u_{j}$. Since we use Rankine-
Hugoniut jump condition to construct the partition line, no penalty is
necessary in this case. However, for rarefaction waves, the traditional Lax-
Friedrichs flux should be applied, and $\alpha$ is not 0. In the rest of the
paper, we consider first-order spatial discretization and Burgers’ equation
for simplicity, while the algorithm and theoretical results can be extended to
general strictly convex flux function $f$.

##  3 The stability analysis for Burger’s equation

In this section, we proceed to prove the stability of the proposed scheme for
Burger’s equation under suitable time step size. We consider the TVD stability
and the maximum-principle of the numerical approximations. Suppose
$u=\\{u_{j}\\}_{j=1}^{N}$ is the numerical approximation for the problems with
compact support, then we define

$TV(u)=\sum_{j=1}^{N}|u_{j+1}-u_{j}|$

as the total variation of $u$. For periodic boundary conditions, the
definition is similar. A scheme is TVD if $TV(u^{n+1})\leq TV(u^{n})$.
Moreover, suppose the initial condition $u_{0}$ satisfies $b\leq u^{0}\leq a$,
then we say the numerical solutions are MPP if $b\leq u^{n}\leq a$ for all
$n>0$. We first prove that if no troubled cells exist corresponding to the
case of $m=0$ as in eq. (2.4) (a typical situation before a shock appears),
the first-order scheme is TVD and MPP. Then we consider the general case with
merge of influence region corresponding to $m=2$ (a typical situation with the
presence of shocks).

###  3.1 Preliminary results for $m=0$

In this subsection, we consider a special case that $m=0$, i.e. no cells
merge, and try to prove some preliminary results. The most useful lemma to
obtain the TVD stability is the following generalized Harten’s Lemma extending
the results given in [5].

######  Lemma 3.1.

Suppose the solution to problem (2.1) has compact support or satisfies
periodic boundary conditions. If the scheme can be written as

$u^{n+1}_{j}=u_{j}+\lambda_{j}\left(C_{j+\frac{1}{2}}\Delta_{+}u_{j}-D_{j-\frac{1}{2}}\Delta_{-}u_{j}\right)$

where

$\Delta_{+}u_{j}=u_{j+1}-u_{j},\quad\Delta_{-}u_{j}=u_{j}-u_{j-1}.$

and $C_{j+\frac{1}{2}}\geq 0$, $D_{j+\frac{1}{2}}\geq 0$, $\lambda_{j}\geq 0$,
$\lambda_{j}C_{j+\frac{1}{2}}+\lambda_{j+1}D_{j+\frac{1}{2}}\leq 1$, then the
scheme is TVD.

###### Proof.

We apply the $\Delta_{+}$ operator, then

$\displaystyle\Delta_{+}u_{j}^{n+1}$ $\displaystyle=$
$\displaystyle\Delta_{+}u_{j}+\lambda_{j+1}C_{j+\frac{3}{2}}\Delta_{+}u_{j+1}-\lambda_{j}C_{j+\frac{1}{2}}\Delta_{+}u_{j}-\lambda_{j+1}D_{j+\frac{1}{2}}\Delta_{-}u_{j+1}+\lambda_{j}D_{j-\frac{1}{2}}\Delta_{-}u_{j}$
$\displaystyle=$
$\displaystyle\Delta_{+}u_{j}+\lambda_{j+1}C_{j+\frac{3}{2}}\Delta_{+}u_{j+1}-\lambda_{j}C_{j+\frac{1}{2}}\Delta_{+}u_{j}-\lambda_{j+1}D_{j+\frac{1}{2}}\Delta_{+}u_{j}+\lambda_{j}D_{j-\frac{1}{2}}\Delta_{+}u_{j-1}$
$\displaystyle=$
$\displaystyle(1-\lambda_{j}C_{j+\frac{1}{2}}-\lambda_{j+1}D_{j+\frac{1}{2}})\Delta_{+}u_{j}+\lambda_{j+1}C_{j+\frac{3}{2}}\Delta_{+}u_{j+1}+\lambda_{j}D_{j-\frac{1}{2}}\Delta_{+}u_{j-1}$

Therefore,

$\displaystyle\sum_{j}|\Delta_{+}u_{j}^{n+1}|$ $\displaystyle\leq$
$\displaystyle\sum_{j}(1-\lambda_{j}C_{j+\frac{1}{2}}-\lambda_{j+1}D_{j+\frac{1}{2}})|\Delta_{+}u_{j}|+\sum_{j}\lambda_{j+1}C_{j+\frac{3}{2}}|\Delta_{+}u_{j+1}|+\sum_{j}\lambda_{j}D_{j-\frac{1}{2}}|\Delta_{+}u_{j-1}|$
$\displaystyle=$
$\displaystyle\sum_{j}(1-\lambda_{j}C_{j+\frac{1}{2}}-\lambda_{j+1}D_{j+\frac{1}{2}})|\Delta_{+}u_{j}|+\sum_{j}\lambda_{j}C_{j+\frac{1}{2}}|\Delta_{+}u_{j}|+\sum_{j}\lambda_{j+1}D_{j+\frac{1}{2}}|\Delta_{+}u_{j}|$
$\displaystyle=$ $\displaystyle\sum_{j}|\Delta_{+}u_{j}|.$

∎

######  Lemma 3.2.

Suppose the solution to problem (2.1) has compact support. Assume
$\\{\Omega_{j}\\}_{j=1}^{N}$ is the partition of the space-time domain
$\Omega\times[t^{n},t^{n+1}]$ with no trouble cells. If the initial condition
$u_{0}$ satisfies $b\leq u_{0}\leq a$, then the first-order numerical
approximation obtained from (2.9) is TVD and MPP under the condition that
$\Delta t\leq\lambda\Delta x.$ Hence the EL FV scheme with a final step of
$L^{2}$ projection to the uniform background cells is TVD and MPP.

###### Proof.

We apply (2.3) to (2.9) to obtain

$\Delta x_{j}^{\star}u^{\star}_{j}=(\Delta
x_{j}^{\star}-\nu_{j+\frac{1}{2}}\Delta t+\nu_{j-\frac{1}{2}}\Delta
t)u_{j}-\Delta t\left(\hat{F}_{j+\frac{1}{2}}-\hat{F}_{j-\frac{1}{2}}\right),$

which further yields

$u^{\star}_{j}=u_{j}+\lambda_{j}\left[(\hat{F}_{j-\frac{1}{2}}+\nu_{j-\frac{1}{2}}u_{j})-(\hat{F}_{j+\frac{1}{2}}+\nu_{j+\frac{1}{2}}u_{j})\right].$

where $\lambda_{j}=\frac{\Delta t}{\Delta x^{\star}_{j}}.$ By using (2.10), we
have

$u^{\star}_{j}=u_{j}+\lambda_{j}\left[\left(F_{j-\frac{1}{2}}-\frac{1}{2}\alpha_{j-\frac{1}{2}}(u_{j}-u_{j-1})+\nu_{j-\frac{1}{2}}u_{j}\right)-\left(F_{j+\frac{1}{2}}-\frac{1}{2}\alpha_{j+\frac{1}{2}}(u_{j+1}-u_{j})+\nu_{j+\frac{1}{2}}u_{j}\right)\right].$

Thanks to (2.11), we obtain

$\displaystyle u^{\star}_{j}$ $\displaystyle=$ $\displaystyle
u_{j}+\lambda_{j}\left[\left(f(u_{j})-\frac{1}{2}\alpha_{j-\frac{1}{2}}(u_{j}-u_{j-1})\right)-\left(f(u_{j})-\frac{1}{2}\alpha_{j+\frac{1}{2}}(u_{j+1}-u_{j})\right)\right]$
$\displaystyle=$ $\displaystyle
u_{j}+\frac{\lambda_{j}}{2}\left[\alpha_{j+\frac{1}{2}}(u_{j+1}-u_{j})-\alpha_{j-\frac{1}{2}}(u_{j}-u_{j-1})\right]$
$\displaystyle=$
$\displaystyle\frac{\lambda_{j}}{2}\alpha_{j+\frac{1}{2}}u_{j+1}+\left(1-\frac{\lambda_{j}}{2}\alpha_{j+\frac{1}{2}}-\frac{\lambda_{j}}{2}\alpha_{j-\frac{1}{2}}\right)u_{j}+\frac{\lambda_{j}}{2}\alpha_{j-\frac{1}{2}}u_{j-1}.$

By Lemma 3.1, to obtain TVD and MPP numerical approximations, we need

$\frac{\lambda_{j}}{2}\alpha_{j+\frac{1}{2}}+\frac{\lambda_{j+1}}{2}\alpha_{j+\frac{1}{2}}\leq
1,\quad\frac{\lambda_{j}}{2}\alpha_{j+\frac{1}{2}}+\frac{\lambda_{j}}{2}\alpha_{j-\frac{1}{2}}\leq
1,$

and the sufficient conditions are

$\alpha_{j+\frac{1}{2}}\lambda_{j}\leq
1,\quad\alpha_{j-\frac{1}{2}}\lambda_{j}\leq 1.$ (3.1)

We consider $\alpha_{j+\frac{1}{2}}\lambda_{j}\leq 1$ only, and the other
condition can be obtained following the same lines. Moreover, we assume
$\alpha_{j+\frac{1}{2}}\neq 0$, i.e.
$\alpha_{j+\frac{1}{2}}=\frac{u_{j+1}-u_{j}}{2}$, with $u_{j+1}>u_{j}$. It is
easy to verify that

$\displaystyle\alpha_{j+\frac{1}{2}}\lambda_{j}\leq 1$
$\displaystyle\Leftrightarrow$ $\displaystyle\frac{\Delta t}{\Delta
x+\nu_{j+\frac{1}{2}}\Delta t-\nu_{j-\frac{1}{2}}\Delta
t}\leq\frac{2}{u_{j+1}-u_{j}}$ $\displaystyle\Leftrightarrow$
$\displaystyle\frac{u_{j+1}-u_{j}}{2}\Delta t\leq\Delta
x+\frac{u_{j+1}+u_{j}}{2}\Delta t-\frac{u_{j}+u_{j-1}}{2}\Delta t$
$\displaystyle\Leftrightarrow$ $\displaystyle\frac{u_{j-1}-u_{j}}{2}\Delta
t\leq\Delta x$

Since $I_{j}$ is not a troubled cell, then
$u_{j-1}-u_{j}\leq\frac{2}{\lambda}.$ If $u_{j-1}-u_{j}\leq 0$, then we have
$\frac{u_{j-1}-u_{j}}{2}\Delta t\leq 0\leq\Delta x$. If $u_{j-1}-u_{j}>0$,
then $\frac{u_{j-1}-u_{j}}{2}\Delta t\leq\Delta x,$ Finally, it is easy to see
that the $L^{2}$ projection to the background mesh in the final step preserves
the maximum-principle and does not increase the total variation for first-
order schemes. We complete the proof. ∎

###  3.2 The main theorem with merging regions around trouble cells

In the previous subsection, we discussed the case with $m=0$. In practice, a
limited time step size is necessary, since the characteristics may quickly
intersect near the shocks. To obtain larger time steps, we consider merging
cells by first categorizing trouble cells, then identifying ETCs, followed by
defining the corresponding influence regions.

######  Definition 3.1.

Suppose $u_{j-1},\ u_{j},\ u_{j+1}$ are the numerical approximations on
$I_{j-1},\ I_{j},I_{j+1},$ respectively. $I_{j}$ is called a troubled cell of
type I for $\lambda$ if

$u_{j-1}>u_{j+1}+\frac{2}{\lambda}.$ (3.2)

Here $\lambda$ is associated with an upper bound for time step constraint as
in $\Delta t\leq\lambda\Delta x$. In addition, $I_{j}$ is called a troubled
cell of type II for $\lambda$ if it is not a troubled cell of type I one and
satisfies

$u_{j-1}>u_{j}+\frac{2}{\lambda},\textrm{ and }u_{j-1}\geq u_{j+1}\geq u_{j}.$
(3.3)

and $I_{j}$ is called a troubled cell of type III for $\lambda$ if it is not a
troubled cell of type I one and satisfies

$u_{j}>u_{j+1}+\frac{2}{\lambda},\textrm{ and }u_{j}\geq u_{j-1}\geq u_{j+1},$
(3.4)

Moreover, $I_{j}$ is called a troubled cell of type IV for $\lambda$ if it is
not a troubled cell of type I or type II and

$u_{j-1}>u_{j}+\frac{2}{\lambda},$ (3.5)

and $I_{j}$ is called a troubled cell of type V for $\lambda$ if it is not a
troubled cell of type I or type III and

$u_{j}>u_{j+1}+\frac{2}{\lambda}.$ (3.6)

Figure 3: Diagrams of different types of trouble cells in Definition 3.1.

In the definition of troubled cells given above, condition (3.2) is triggered
if the partition lines originated from $x_{j\pm\frac{1}{2}}$ intersect at
$t<t^{n}+\lambda\Delta x$, while (3.3), (3.4), (3.5) and (3.6) are used for
strong shock waves generated at the cell interfaces. Finally, (3.5) and (3.6),
though unlikely appear together, may be encountered in a rarefaction wave with
strong numerical oscillations. It is easy to show that the above conditions to
categorize troubled cells are mutually exclusive. Figure 3 illustrates various
situations corresponding to different types of trouble cells. If two troubled
cells are connected, we will design the influence region based on one of the
troubled cells, and such a troubled cell is defined as an ETC. The ETCs are
selected sequentially from left to right as follows: We search the
computational domain from left to right, if the first troubled cell, say
$I_{j-1}$, is a troubled cell of type V, then $I_{j}$ is denoted as an ETC.
Otherwise $I_{j-1}$ is defined as an ETC.  Once an ETC $I_{j}$ is identified,
we define its influence region $R_{j}$ as below.

######  Definition 3.2.

Suppose $I_{j}$ is an ETC, and the numerical approximations on cell $I_{i}$,
$i=j-3,\cdots,j+3$ are $s_{\ell},$ $z_{\ell}$, $z_{1}$, $z_{2}$, $z_{3}$,
$z_{r}$, $s_{r}$, respectively. Assume the initial condition is bounded by
$a\geq u_{0}\geq b$, then the influence region is defined as follows

  1. I1:

If $I_{j}$ is a troubled cell of type IV, then $I_{j-1}$ is a troubled cell of
type V, and the influence region contains $I_{i}$, $i=j-2,\cdots,j+1$.

  2. I2:

Assume $A=z_{1}+z_{2}+z_{3}>\frac{7a+5b}{4}$, if $z_{r}<\frac{a+3b}{4}$ or
$s_{r}+z_{r}<\frac{a+3b}{2}$, then the influence region contains $I_{i}$,
$i=j-2\cdots,j+3$.

  3. I3:

Assume $A=z_{1}+z_{2}+z_{3}<\frac{5a+7b}{4}$, if $z_{\ell}>\frac{3a+b}{4}$ or
$s_{\ell}+z_{\ell}>\frac{3a+b}{2}$, then the influence region contains
$I_{i}$, $i=j-3\cdots,j+2$.

  4. I4:

In all other cases, the influence region contains $I_{i}$, $i=j-2,\cdots,j+2.$

We say the ETC $I_{j}$ is isolated if $R_{j}$ does not overlap with influence
regions of any other ETCs.

Now, we can state the main theorem.

######  Theorem 3.1.

Consider the hyperbolic conservation law (2.1) with $f(u)=\frac{u^{2}}{2}$,
initial condition $u_{0}(x)$. Suppose the solution to problem (2.1) has
compact support or satisfies periodic boundary conditions, $a\geq u_{0}(x)\geq
b$, and the time step size satisfies

$\Delta t<\lambda\Delta x\quad\textrm{with}\quad\lambda=\frac{4}{a-b}.$ (3.7)

If the influence region of each ETC is given in Definition 3.2 and all the
ETCs are isolated, then the numerical approximations obtained from the first-
order EL FV scheme (2.9) is TVD and MPP.

######  Remark 3.1.

In the above theorem, we can choose $a$ and $b$ to be the local maximum and
minimum in the influence region of the ETC and the two neighboring cells of
the influence region. For example, if the influence region of the ETC $I_{i}$
contains $I_{i-2}$, $I_{i-1}$, $I_{i}$, $I_{i+1}$, $I_{i+2}$, then we take

$a_{i}=\max_{j=0,\pm 1,\pm 2,\pm 3}\\{u_{i+j}\\},\quad b_{i}=\min_{j=0,\pm
1,\pm 2,\pm 3}\\{u_{i+j}\\},$

and the conclusion is also correct under the condition

$\Delta t<\lambda\Delta
x\quad\textrm{with}\quad\lambda=\frac{4}{\max_{i}\\{a_{i}-b_{i}\\}}.$

The proof is straightforward since if we merge 5 cells and the information to
be used contains the cells in the influence region and the two neighboring
cells. This can also be observed from the proof in Section 3.3.2. The time
stepping constraint in (3.7) is at least twice as large as the standard CFL
condition.

###  3.3 Proof of Theorem 3.1

####  3.3.1 The basic ideas and a simple case

In this subsection, we proceed to discuss the case when we merge four to six
cells according to the Definition 3.2 for the influence region. Most cases, we
will merge five cells and suppose the numerical approximations in those five
cells are $z_{\ell}$, $z_{1}$, $z_{2}$, $z_{3}$, $z_{r}$, respectively from
left to right. Then after the merge, the only information to be used for time
evolution is the average of these five values
$\frac{z_{\ell}+z_{1}+z_{2}+z_{3}+z_{r}}{5}$. Therefore, we can redefine those
five values according to the criteria (a)-(d) outlined in the introduction,
such that no troubled cells exist in the influence region, keeping the
original average value. Obviously, we cannot modify the characteristic speed
at the boundary of the influence region, i.e. the values of $z_{\ell}$ or
$z_{r}$, since we cannot modify the numerical fluxes at those two boundaries.
Therefore, we will adjust $z_{1}$, $z_{2}$, $z_{3}$ to $r_{1}$, $r_{2}$,
$r_{3}$, keeping their average, preserving the maximum-principle and reducing
the original total variation. We will show adjustment strategies in finding
$r_{1}$, $r_{2}$, $r_{3}$, so that no more troubled cells exist. From there,
Lemma 3.2 can be applied to prove the TVD property. Finally, we will briefly
discuss what if the ETCs are not isolated.

We first show a simple case to find $\\{r_{1},r_{2},r_{3}\\}$ when the ETC is
a trouble cell of type IV in Theorem 3.2.

######  Theorem 3.2.

Suppose $I_{j}$ is a troubled cell of type IV and it is an ETC, then $I_{j-1}$
is a troubled cell of type V. Assume the numerical approximations on $I_{i}$,
$i=j-2,\cdots,j+1$ are $z_{1}$, $z_{2}$, $z_{3}$, $z_{4}$, respectively, and
$b\leq z_{i}\leq a$. Then $b\leq z_{1}\leq z_{3}\leq z_{2}\leq z_{4}\leq a.$
We can define $r_{i}=z_{i}$, $i=1,4$, and $r_{2}=z_{3}$, $r_{3}=z_{2}$. With
the newly defined $\\{r_{i}\\}_{i=1}^{4}$, we have

$b\leq r_{1}\leq r_{2}\leq\frac{a+b}{2}\leq r_{3}\leq r_{4}\leq a,\quad
TV(z_{1},z_{2},z_{3},z_{4})\geq TV(r_{1},r_{2},r_{3},r_{4}).$

$I_{j-1}$ and $I_{j}$ are no longer troubled cells. If $I_{j+1}$ is a troubled
cell and the numerical approximation on $I_{j+2}$ is $z_{r}$, then
$z_{4}>z_{r}+\frac{2}{\lambda}$; moreover, it is not a troubled cell of type
V. If $I_{j-2}$ is a troubled cell and the numerical approximation on
$I_{j-3}$ is $z_{\ell}$, then $z_{\ell}>z_{1}+\frac{2}{\lambda}$; moreover it
is not a troubled cell of type IV.

###### Proof.

The proof follows from definition 3.1 and is straightforward. The last two
statements on trouble cells can be obtained following the same line; we will
only prove the former statement for simplicity. Clearly, $I_{j+1}$ can only be
a troubled cell of type I, III and V. If it is a troubled cell of type III and
V, then $z_{4}>z_{r}+\frac{2}{\lambda}$ is automatically true. Otherwise, we
have $r_{4}\geq r_{3}>z_{r}+\frac{2}{\lambda}$. Finally, if $I_{j+1}$ is a
troubled cell of type V, then $\frac{a+b}{2}\leq r_{3}\leq
z_{r}<z_{4}-\frac{2}{\lambda}\leq\frac{a+b}{2}$, which is a contradiction. ∎

######  Remark 3.2.

In the above theorem, the properties of the potential troubled cells on the
boundaries of the influence region are for discussing the case of non-isolated
ETCs.

####  3.3.2 Adjustment from $z_{1}$, $z_{2}$, $z_{3}$ to $\tilde{z}_{1}$,
$\tilde{z}_{2}$, $\tilde{z}_{3}$ with TVD property

When an ETC is not a troubled cell of type IV, the design and analysis of the
adjustment strategy is rather involved. We will first identify some special
values of $\\{\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3}\\}$ provided in Table
1 to simplify the discussion of adjustment strategy for
$\\{r_{1},r_{2},r_{3}\\}$ in the next subsection.

Suppose $I_{j}$ is an ETC for $\lambda$, the numerical approximations in the
five merged cells and the two neighboring cells are $s_{\ell}$, $z_{\ell}$,
$z_{1}$, $z_{2}$, $z_{3}$, $z_{r}$, $s_{r}$, respectively from left to right.
Moreover, we denote the cells to be $I_{j-3},$ $\cdots,$ $I_{j+3}$ from left
to right. The following lemma is used to find $r$’s with the minimum total
variation.

######  Lemma 3.3.

Suppose $\max\\{z_{1},z_{2}\\}\geq\max\\{z_{2},z_{3}\\}$ and
$r_{1}=\max\\{z_{1},z_{2},z_{3}\\}$, $r_{3}=\min\\{z_{1},z_{2},z_{3}\\}$,
$r_{2}=z_{1}+z_{2}+z_{3}-r_{1}-r_{3}$, then
$TV(z_{\ell},r_{1},r_{2},r_{3},z_{r})\leq
TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})$.

###### Proof.

It is easy to see that $r_{1}\geq r_{2}\geq r_{3}$. There are several cases to
be discussed.

  1. 1.

$r_{1}=z_{1}$, then

$TV(z_{\ell},r_{1},r_{2},r_{3},z_{r})=TV(z_{\ell},z_{1},r_{3},z_{r})\leq\max\\{TV(z_{\ell},z_{1},z_{2},z_{r}),TV(z_{\ell},z_{1},z_{3},z_{r})\\}\leq
TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})$

  2. 2.

$r_{1}=z_{2}$. Since $I_{j}$ is an ETC, then by Definition 3.1, $I_{j}$ can be
a troubled cell of type I, II or III. Therefore, $r_{3}\neq z_{1}$, leading to
$r_{3}=z_{3}$, $r_{2}=z_{1}$ and $z_{2}\geq z_{1}\geq z_{3}$. Then we have

$TV(z_{\ell},r_{1},r_{2},r_{3},z_{r})=TV(z_{\ell},z_{2},z_{1},z_{3},z_{r})=TV(z_{\ell},z_{2},z_{3},z_{r})\leq
TV(z_{\ell},z_{1},z_{2},z_{3},z_{r}).$

∎

Since $I_{j}$ is an ETC, we will merge at least five cells and redefine the
values of $z_{1}$, $z_{2}$ and $z_{3}$. Based Lemma 3.3, we assume

$z_{1}\geq z_{2}\geq z_{3},\quad z_{1}\geq z_{3}+\frac{2}{\lambda}.$

We first design the admissible set as

$G=\left\\{(z_{1},z_{2},z_{3}):a\geq z_{1}\geq z_{2}\geq z_{3}\geq b,\
z_{1}\geq z_{3}+\frac{2}{\lambda}\right\\}.$

The following lemmas will be used to find the possible upper and lower bounds
of $z_{1}$ and $z_{3}$.

######  Lemma 3.4.

Suppose $(z_{1},z_{2},z_{3})\in G$ and $\lambda=\frac{4}{a-b}$, then we have

$z_{1}\geq\frac{a+b}{2},\quad z_{3}\leq\frac{a+b}{2},\quad\frac{a+5b}{2}\leq
A=z_{1}+z_{2}+z_{3}\leq\frac{5a+b}{2}.$

###### Proof.

The proof follows from direct computation. Actually,

$z_{1}\geq z_{3}+\frac{2}{\lambda}\geq b+\frac{a-b}{2}=\frac{a+b}{2}.$

Similarly,

$z_{3}\leq z_{1}-\frac{2}{\lambda}\leq a-\frac{a-b}{2}=\frac{a+b}{2}.$

Finally,

$A=z_{1}+z_{2}+z_{3}\leq a+a+\frac{a+b}{2}=\frac{5a+b}{2},$

and

$A=z_{1}+z_{2}+z_{3}\geq\frac{a+b}{2}+b+b=\frac{a+5b}{2}.$

∎

######  Lemma 3.5.

Suppose $\frac{a+5b}{2}\leq A\leq\frac{5a+b}{2}$ and $\lambda=\frac{4}{a-b}$,
then

$\frac{1}{3}A+\frac{2}{3\lambda}\leq
a,\quad\frac{1}{3}A-\frac{2}{3\lambda}\geq
b,\quad\frac{1}{3}A-\frac{4}{3\lambda}\leq\frac{a+b}{2}=a-\frac{2}{\lambda},\quad
A-\frac{3a+b}{2}\leq a,\quad A-\frac{a+3b}{2}\geq b.$

###### Proof.

The proof follows from direct computation, so we skip it. ∎

To ensure that the total variation does not increase, we aim to minimize
$TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})$ in the admissible set $G$. Define
$A=z_{1}+z_{2}+z_{3}$, we can choose $z_{1}$, $z_{2}$, $z_{3}$ in $G$ to
achieve the minimum total variation $TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})$
following Table 1, where the conditions cover all the possibilities, yet may
not be mutually exclusive, since we do not have the relationship between
$z_{\ell}$ and $z_{r}$. The result is given in the following theorem.

Case | Conditions | $z_{1}$ | $z_{2}$ | $z_{3}$
---|---|---|---|---
1 | $A\geq 3z_{\ell}-\frac{2}{\lambda}$ | $\tilde{z}_{1}=z_{r}+\frac{2}{\lambda}$ | $\tilde{z}_{2}=A-2z_{r}-\frac{2}{\lambda}$ | $\tilde{z}_{3}=z_{r}$
$z_{3}\geq z_{r}$, $\frac{1}{3}A-\frac{4}{3\lambda}\leq z_{r}$
2 | $A\geq 3z_{\ell}-\frac{2}{\lambda}$ | $\tilde{z}_{1}=\frac{a+b}{2}$ | $\tilde{z}_{2}=A-\frac{a+3b}{2}$ | $\tilde{z}_{3}=b$
$z_{3}\leq z_{r}$, $A\leq a+2b$
3 | $A\geq 3z_{\ell}-\frac{2}{\lambda}$ | $\tilde{z}_{1}=\frac{1}{3}A+\frac{2}{3\lambda}$ | $\tilde{z}_{2}=\frac{1}{3}A+\frac{2}{3\lambda}$ | $\tilde{z}_{3}=\frac{1}{3}A-\frac{4}{3\lambda}$
all other possibilities
4 | $A\leq 3z_{r}+\frac{2}{\lambda}$ | $\tilde{z}_{1}=z_{\ell}$ | $\tilde{z}_{2}=A-2z_{\ell}+\frac{2}{\lambda}$ | $\tilde{z}_{3}=z_{\ell}-\frac{2}{\lambda}$
$z_{1}\leq z_{\ell}$, $\frac{1}{3}A+\frac{4}{3\lambda}\geq z_{\ell}$
5 | $A\leq 3z_{r}+\frac{2}{\lambda}$ | $\tilde{z}_{1}=a$ | $\tilde{z}_{2}=A-\frac{3a+b}{2}$ | $\tilde{z}_{3}=\frac{a+b}{2}$
$z_{1}\geq z_{\ell}$, $A\geq 2a+b$
6 | $A\leq 3z_{r}+\frac{2}{\lambda}$ | $\tilde{z}_{1}=\frac{1}{3}A+\frac{4}{3\lambda}$ | $\tilde{z}_{2}=\frac{1}{3}A-\frac{2}{3\lambda}$ | $\tilde{z}_{3}=\frac{1}{3}A-\frac{2}{3\lambda}$
all other possibilities
7 | $3z_{r}+\frac{2}{\lambda}\leq A\leq 3z_{\ell}-\frac{2}{\lambda}$ | $z_{r}+\frac{2}{\lambda}\leq\tilde{z}_{1}\leq\frac{1}{3}A+\frac{4}{3\lambda}$ | $\tilde{z}_{2}=A-2\tilde{z}_{1}+\frac{2}{\lambda}$ | $\tilde{z}_{3}=\tilde{z}_{1}-\frac{2}{\lambda}$
$z_{\ell}\geq z_{r}+\frac{2}{\lambda}$ | $\frac{1}{3}A+\frac{2}{3\lambda}\leq\tilde{z}_{1}\leq z_{\ell}$ | $=A-2\tilde{z}_{3}-\frac{2}{\lambda}$
8 | $3z_{r}+\frac{2}{\lambda}\leq A\leq 3z_{\ell}-\frac{2}{\lambda}$ | $\tilde{z}_{1}=z_{r}+\frac{2}{\lambda}$ | $\tilde{z}_{2}=A-\tilde{z}_{1}-\tilde{z}_{3}$ | $\tilde{z}_{3}=z_{r}$
$z_{\ell}\leq z_{r}+\frac{2}{\lambda}\leq a,\ z_{1}\geq z_{\ell}$
9 | $3z_{r}+\frac{2}{\lambda}\leq A\leq 3z_{\ell}-\frac{2}{\lambda}$ | $\tilde{z}_{1}=a$ | $\tilde{z}_{2}=A-\frac{3a+b}{2}$ | $\tilde{z}_{3}=\frac{a+b}{2}$
$a\leq z_{r}+\frac{2}{\lambda},\ z_{1}\geq z_{\ell}$
10 | $3z_{r}+\frac{2}{\lambda}\leq A\leq 3z_{\ell}-\frac{2}{\lambda}$ | $\tilde{z}_{1}=z_{\ell}$ | $\tilde{z}_{2}=A-\tilde{z}_{1}-\tilde{z}_{3}$ | $\tilde{z}_{3}=z_{\ell}-\frac{2}{\lambda}$
$z_{\ell}\leq z_{r}+\frac{2}{\lambda},\ z_{1}\leq z_{\ell}$
Table 1: Summary of the values of $\tilde{z}_{1}$, $\tilde{z}_{2}$,
$\tilde{z}_{3}$ yielding minimum total variation in the admissible set $G$.

######  Theorem 3.3.

Let $z_{\ell},z_{1},z_{2},z_{3},z_{r}\in[b,a]$ be the numerical approximations
within five adjacent cells from left to right, such that $\frac{a+5b}{2}\leq
A=z_{1}+z_{2}+z_{3}\leq\frac{5a+b}{2}$, then we can define
$\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3}$ in the admissible set $G$
following Table 1 such that
$TV(z_{\ell},\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3},z_{r})\leq
TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})$. In addition, the chosen
$\tilde{z}_{1}$, $\tilde{z}_{2}$, $\tilde{z}_{3}$ satisfy
$\tilde{z}_{1}\geq\frac{a+b}{2}$, $\tilde{z}_{3}\leq\frac{a+b}{2}$ and
$\tilde{z}_{1}=\tilde{z}_{3}+\frac{2}{\lambda}$.

###### Proof.

$\tilde{z}_{1}=\tilde{z}_{3}+\frac{2}{\lambda}$ can be observed from Table 1
directly. $\tilde{z}_{1}\geq\frac{a+b}{2}$, $\tilde{z}_{3}\leq\frac{a+b}{2}$
can be obtained by Lemma 3.4. Now we proceed to demonstrate how to find the
$\tilde{z}_{i}^{\prime}s$, $i=1,2,3$. We consider different cases one by one
and use Lemma 3.5.

  * •

Cases 1, 2 and 3. Since $\displaystyle 3z_{\ell}-\frac{2}{\lambda}\leq
A=z_{1}+z_{2}+z_{3}\leq 3z_{1}-\frac{2}{\lambda},$ then

$z_{1}\geq\frac{1}{3}A+\frac{2}{3\lambda}\geq z_{\ell}.$

Hence

$TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})=|z_{\ell}-z_{1}|+|z_{1}-z_{3}|+|z_{3}-z_{r}|=z_{1}-z_{\ell}+z_{1}-z_{3}+|z_{3}-z_{r}|.$

Then we have two possibilities:

    1. 1.

If $z_{3}\leq z_{r}$, then

$TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})=z_{1}-z_{\ell}+z_{1}-z_{3}+z_{r}-z_{3}=2(z_{1}-z_{3})-z_{\ell}+z_{r}\geq\frac{4}{\lambda}-z_{\ell}+z_{r}.$

      1. (a)

If $\frac{1}{3}A-\frac{4}{3\lambda}\geq b$, i.e. $A\geq a+2b$, then we can
take

$\tilde{z}_{1}=\frac{1}{3}A+\frac{2}{3\lambda}\in[z_{\ell},z_{1}],\quad\tilde{z}_{3}=\frac{1}{3}A-\frac{4}{3\lambda},\quad\tilde{z}_{2}=\frac{1}{3}A+\frac{2}{3\lambda}\in[\tilde{z}_{3},\tilde{z}_{1}]$

        1. i.

If $\frac{1}{3}A-\frac{4}{3\lambda}\leq z_{r}$, then $\tilde{z}_{3}\leq
z_{r}$. Therefore

$TV(z_{\ell},\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3},z_{r})=\tilde{z}_{1}-z_{\ell}+\tilde{z}_{1}-\tilde{z}_{3}+z_{r}-\tilde{z}_{3}=\frac{4}{\lambda}-z_{\ell}+z_{r}\leq
TV(z_{\ell},z_{1},z_{2},z_{3},z_{r}).$

        2. ii.

If $\frac{1}{3}A-\frac{4}{3\lambda}\geq z_{r}$, then $\tilde{z}_{3}\geq
z_{r}\geq z_{3}$. Therefore,

$TV(z_{\ell},\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3},z_{r})=\tilde{z}_{1}-z_{\ell}+\tilde{z}_{1}-\tilde{z}_{3}+\tilde{z}_{3}-z_{r}\leq
z_{1}-z_{\ell}+z_{1}-z_{3}\leq TV(z_{\ell},z_{1},z_{2},z_{3},z_{r}),$

where in the first inequality we used the fact that $z_{1}\geq\tilde{z}_{1}$
and $z_{3}\leq z_{r}$.

      2. (b)

If $A\leq a+2b$, then $\frac{1}{3}A-\frac{4}{3\lambda}\leq b$ leading to
$\frac{1}{3}A+\frac{2}{3\lambda}\leq\frac{a+b}{2}$. We take

$\tilde{z}_{1}=\frac{a+b}{2}\in[z_{\ell},z_{1}],\quad\tilde{z}_{3}=b,\quad\tilde{z}_{2}=A-\tilde{z}_{1}-\tilde{z}_{3}=A-\frac{a+3b}{2}$

It is easy to see
$\displaystyle\tilde{z}_{3}=b=\frac{a+5b}{2}-\frac{a+3b}{2}\leq\tilde{z}_{2}\leq
a+2b-\frac{a+3b}{2}=\frac{a+b}{2}=\tilde{z}_{1}$. Moreover,

$TV(z_{\ell},\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3},z_{r})=\tilde{z}_{1}-z_{\ell}+\tilde{z}_{1}-\tilde{z}_{3}+z_{r}-\tilde{z}_{3}=\frac{4}{\lambda}-z_{\ell}+z_{r}\leq
TV(z_{\ell},z_{1},z_{2},z_{3},z_{r}).$

    2. 2.

If $z_{3}\geq z_{r}$, then $\displaystyle z_{1}\geq z_{r}+\frac{2}{\lambda},\
z_{r}\leq z_{3}\leq\frac{a+b}{2}=a-\frac{2}{\lambda}$ and

$TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})=z_{1}-z_{\ell}+z_{1}-z_{3}+z_{3}-z_{r}=2z_{1}-z_{\ell}-z_{r}.$

Therefore, we need to choose the smallest possible $z_{1}$.

      1. (a)

If $\frac{1}{3}A-\frac{4}{3\lambda}\geq z_{r}$, then we can take

$a\geq z_{1}\geq\tilde{z}_{1}=\frac{1}{3}A+\frac{2}{3\lambda}\geq
z_{\ell},\quad\tilde{z}_{3}=\frac{1}{3}A-\frac{4}{3\lambda}\geq z_{r}\geq
b,\quad\tilde{z}_{2}=\frac{1}{3}A+\frac{2}{3\lambda}\in[\tilde{z}_{3},\tilde{z}_{1}].$

      2. (b)

If $\frac{1}{3}A-\frac{4}{3\lambda}\leq z_{r}\leq a-\frac{2}{\lambda}$, then
we have

$z_{1}\geq z_{3}+\frac{2}{\lambda}\geq z_{r}+\frac{2}{\lambda}.$

        1. i.

If $z_{r}\leq\frac{1}{3}A-\frac{2}{3\lambda}$, then we can choose

$a\geq
z_{1}\geq\tilde{z}_{1}=z_{r}+\frac{2}{\lambda}\geq\frac{1}{3}A+\frac{2}{3\lambda}\geq
z_{\ell},\quad\tilde{z}_{3}=z_{r}\geq
b,\quad\tilde{z}_{2}=A-2z_{r}-\frac{2}{\lambda}.$

Since $\frac{1}{3}A-\frac{4}{3\lambda}\leq z_{r}$, then

$\tilde{z}_{2}=A-2z_{r}-\frac{2}{\lambda}\leq
3z_{r}+\frac{4}{\lambda}-2z_{r}-\frac{2}{\lambda}=z_{r}+\frac{2}{\lambda}=\tilde{z}_{1}.$

Moreover, since $z_{r}\leq\frac{1}{3}A-\frac{2}{3\lambda}$, then

$\tilde{z}_{2}=A-2z_{r}-\frac{2}{\lambda}\geq
3z_{r}+\frac{2}{\lambda}-2z_{r}-\frac{2}{\lambda}=z_{r}=\tilde{z}_{3}.$

        2. ii.

If $\displaystyle z_{r}>\frac{1}{3}A-\frac{2}{3\lambda}$, we cannot find any
$z_{1}$, $z_{2}$, $z_{3}$ in $G$. Actually, since $z_{3}\geq z_{r}$ and
$z_{1}\geq z_{3}+\frac{2}{\lambda}$, then

$z_{r}\leq z_{3}\leq z_{2}=A-z_{1}-z_{3}\leq
A-2z_{r}-\frac{2}{\lambda}<3z_{r}+\frac{2}{\lambda}-2z_{r}-\frac{2}{\lambda}=z_{r},$

which is a contradiction.

  * •

Cases 4, 5 and 6. The proof for Cases 4, 5 and 6 can be obtained following
that for Cases 1, 2 and 3 with some minor changes, so we skip it.

  * •

Case 7. If $\displaystyle 3z_{r}+\frac{2}{\lambda}\leq A\leq
3z_{\ell}-\frac{2}{\lambda}$ and $\displaystyle z_{\ell}\geq
z_{r}+\frac{2}{\lambda}$. We take $\tilde{z}_{1}$ such that

$z_{r}+\frac{2}{\lambda}\leq\tilde{z}_{1}\leq\frac{1}{3}A+\frac{4}{3\lambda},\quad\frac{1}{3}A+\frac{2}{3\lambda}\leq\tilde{z}_{1}\leq
z_{\ell},$

and $\displaystyle\tilde{z}_{3}=\tilde{z}_{1}-\frac{2}{\lambda}$,
$\displaystyle\tilde{z}_{2}=A-\tilde{z}_{1}-\tilde{z}_{3}.$ We will show that
such a selection of $\tilde{z}_{1}$, $\tilde{z}_{2}$, $\tilde{z}_{3}$ is in
$G$.

    1. 1.

Since $\displaystyle 3z_{r}+\frac{2}{\lambda}\leq A$, then
$\displaystyle\frac{1}{3}A+\frac{4}{3\lambda}\geq
z_{r}+\frac{2}{3\lambda}+\frac{4}{3\lambda}=z_{r}+\frac{2}{\lambda}.$
Moreover, since $\displaystyle A\leq 3z_{\ell}-\frac{2}{\lambda}$, then
$\displaystyle\frac{1}{3}A+\frac{2}{3\lambda}\leq z_{\ell}$. In addition, it
is easy to see that
$\displaystyle\frac{1}{3}A+\frac{2}{3\lambda}\leq\frac{1}{3}A+\frac{4}{3\lambda}$
and based on the assumption that $\displaystyle z_{\ell}\geq
z_{r}+\frac{2}{\lambda}$, we have the existence of $\tilde{z}_{1}$.

    2. 2.

By direct computation, we have

$\tilde{z}_{2}=A-\tilde{z}_{1}-\tilde{z}_{3}=A-2\tilde{z}_{1}+\frac{2}{\lambda}\leq
3\tilde{z}_{1}-\frac{2}{\lambda}-2\tilde{z}_{1}+\frac{2}{\lambda}=\tilde{z}_{1},$

and

$\tilde{z}_{2}=A-2\tilde{z}_{1}+\frac{2}{\lambda}\geq
3\tilde{z}_{1}-\frac{4}{\lambda}-2\tilde{z}_{1}+\frac{2}{\lambda}=\tilde{z}_{3}.$

Finally, since $\tilde{z}_{1}\leq z_{\ell}\leq a$ and
$\tilde{z}_{3}=\tilde{z}_{1}-\frac{2}{\lambda}\geq z_{r}\geq b$. Therefore, we
conclude that $\tilde{z}_{1}$, $\tilde{z}_{2}$, $\tilde{z}_{3}$ are chosen
from $G$. Finally, we will show that such a selection yields the minimum total
variation. Actually, since $\tilde{z}_{1}\leq z_{\ell}$ and
$\tilde{z}_{3}=\tilde{z}_{1}-\frac{2}{\lambda}\geq z_{r}$, we have
$z_{\ell}\geq\tilde{z}_{1}\geq\tilde{z}_{2}\geq\tilde{z}_{3}\geq z_{r}$.
Clearly, the total variation is the minimum, which is $z_{\ell}-z_{r}.$

  * •

Cases 8 and 9. Since $z_{1}\geq z_{\ell}$, then
$TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})=z_{1}-z_{\ell}+z_{1}-z_{3}+|z_{3}-z_{r}|.$

    1. 1.

If $z_{r}+\frac{2}{\lambda}\leq a$, we take

$\tilde{z}_{1}=z_{r}+\frac{2}{\lambda}\in[z_{\ell},a],\quad\tilde{z}_{3}=z_{r}\geq
b,\quad\tilde{z}_{2}=A-\tilde{z}_{1}-\tilde{z}_{3}.$

We need to show that the selection is in $G$. Actually, since $A\geq
3z_{r}+\frac{2}{\lambda}$, then

$\tilde{z}_{2}=A-\tilde{z}_{1}-\tilde{z}_{3}=A-2z_{r}-\frac{2}{\lambda}\geq
3z_{r}+\frac{2}{\lambda}-2z_{r}-\frac{2}{\lambda}=z_{r}=\tilde{z}_{3}.$

Moreover, since $A\leq 3z_{\ell}-\frac{2}{\lambda}$ and $z_{\ell}\leq
z_{r}+\frac{2}{\lambda}$, then $A\leq 3z_{r}+\frac{4}{\lambda},$ leading to

$\tilde{z}_{2}=A-2z_{r}-\frac{2}{\lambda}\leq
3z_{r}+\frac{4}{\lambda}-2z_{r}-\frac{2}{\lambda}=z_{r}+\frac{2}{\lambda}=\tilde{z}_{1}.$

Therefore, $(\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3})\in G$. Next, we
consider the TV. It is easy to see that

$TV(z_{\ell},\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3},z_{r})=\tilde{z}_{1}-z_{\ell}+\tilde{z}_{1}-\tilde{z}_{3}=z_{r}-z_{\ell}+\frac{4}{\lambda}.$

      1. (a)

If $z_{3}\leq z_{r}$, then

$TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})=z_{1}-z_{\ell}+z_{1}-z_{3}+z_{r}-z_{3}=2(z_{1}-z_{3})-z_{\ell}+z_{r}\geq\frac{4}{\lambda}-z_{\ell}+z_{r}=TV(z_{\ell},\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3},z_{r}).$

      2. (b)

If $z_{3}\geq z_{r}$, then $z_{1}\geq z_{3}+\frac{2}{\lambda}\geq
z_{r}+\frac{2}{\lambda}.$ Therefore,

$TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})=z_{1}-z_{\ell}+z_{1}-z_{3}+z_{3}-z_{r}=2z_{1}-z_{\ell}-z_{r}\geq\frac{4}{\lambda}-z_{\ell}+r_{r}=TV(z_{\ell},\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3},z_{r}).$

    2. 2.

If $z_{r}+\frac{2}{\lambda}\geq a$, then $z_{r}\geq\frac{a+b}{2}\geq z_{3}$.
Hence

$TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})=z_{1}-z_{\ell}+z_{1}-z_{3}+z_{r}-z_{3}\geq\frac{4}{\lambda}+z_{r}-z_{\ell}.$

We take

$\tilde{z}_{1}=a,\quad\tilde{z}_{3}=\frac{a+b}{2},\quad\tilde{z}_{2}=A-\frac{3a+b}{2}\leq
a=\tilde{z}_{1}.$

Moreover, $\displaystyle\tilde{z}_{2}=A-\frac{3a+b}{2}\geq
3z_{r}+\frac{2}{\lambda}-\frac{3a+b}{2}\geq\frac{3a+3b}{2}+\frac{a-b}{2}-\frac{3a+b}{2}=\frac{a+b}{2}=\tilde{z}_{3}.$
Therefore, $(\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3})\in G$. Finally,

$TV(z_{\ell},\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3},z_{r})=\tilde{z}_{1}-z_{\ell}+\tilde{z}_{1}-\tilde{z}_{3}+z_{r}-\tilde{z}_{3}=\frac{4}{\lambda}+z_{r}-z_{\ell}\leq
TV(z_{\ell},z_{1},z_{2},z_{3},z_{r}).$

  * •

Case 10. Since $z_{1}\leq z_{\ell}$ and $z_{\ell}\leq
z_{r}+\frac{2}{\lambda}$, then

$z_{3}\leq z_{1}-\frac{2}{\lambda}\leq z_{\ell}-\frac{2}{\lambda}\leq
z_{r}+\frac{2}{\lambda}-\frac{2}{\lambda}=z_{r}.$

Hence,

$TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})=z_{\ell}-z_{1}+z_{1}-z_{3}+z_{r}-z_{3}=z_{\ell}+z_{r}-2z_{3}\geq
z_{\ell}+z_{r}-2(z_{\ell}-\frac{2}{\lambda})=\frac{4}{\lambda}+z_{r}-z_{\ell}.$

We take

$\tilde{z}_{1}=z_{\ell}\leq
a,\quad\tilde{z}_{3}=z_{\ell}-\frac{2}{\lambda}\geq
z_{1}-\frac{2}{\lambda}\geq
b,\quad\tilde{z}_{2}=A-\tilde{z}_{1}-\tilde{z}_{3}.$

We first show that such a selection is in $G$. Since $\displaystyle A\leq
3z_{l}-\frac{2}{\lambda}$, then

$\tilde{z}_{2}=A-\tilde{z}_{1}-\tilde{z}_{3}\leq
3z_{l}-\frac{2}{\lambda}-\tilde{z}_{1}-\tilde{z}_{1}+\frac{2}{\lambda}=\tilde{z}_{1}.$

On the other hand, since $\displaystyle A\geq 3z_{r}+\frac{2}{\lambda}$ and
$\displaystyle z_{\ell}\leq z_{r}+\frac{2}{\lambda}$, then $\displaystyle
A\geq
3z_{\ell}-\frac{6}{\lambda}+\frac{2}{\lambda}=3z_{\ell}-\frac{4}{\lambda}.$
Therefore,

$\tilde{z}_{2}=A-\tilde{z}_{1}-\tilde{z}_{3}\geq
3z_{\ell}-\frac{4}{\lambda}-z_{\ell}-z_{\ell}+\frac{2}{\lambda}=z_{\ell}-\frac{2}{\lambda}=\tilde{z}_{3}.$

Finally, since $\displaystyle z_{r}\geq
z_{\ell}-\frac{2}{\lambda}=\tilde{z}_{3},$ then

$TV(z_{\ell},\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3},z_{r})=\tilde{z}_{1}-\tilde{z}_{3}+z_{r}-\tilde{z}_{3}=z_{\ell}-z_{\ell}+\frac{2}{\lambda}+z_{r}-z_{\ell}+\frac{2}{\lambda}=\frac{4}{\lambda}+z_{r}-z_{\ell}\leq
TV(z_{\ell},z_{1},z_{2},z_{3},z_{r}).$

∎

####  3.3.3 Adjustment from $\tilde{z}_{1}$, $\tilde{z}_{2}$, $\tilde{z}_{3}$
to $r_{1}$, $r_{2}$, $r_{3}$ with TVD property

We summarized all the possible cases that yielding minimum total variation in
$G$ in Table 1. Now we only need to discuss the $\tilde{z}_{i}^{\prime}s$,
$i=1,2,3$, given in Table 1. We can proceed to redefine the numerical
approximations within the influence region such that the new total variation
is no larger than those given in Theorem 3.3. We assume the redefined values
are $r_{1}$, $r_{2}$ and $r_{3}$, respectively. In order to simplify the
discussion, we always assume

$r_{1}\geq r_{2}\geq r_{3}.$

Before we state the next lemma, we would like to define a negative fraction as
$+\infty$ in the rest of the paper.

######  Lemma 3.6.

Suppose $r_{1}$, $r_{2}$, $r_{3}$ are the modified numerical approximations in
cells $I_{j-i},$ $I_{j},$ $I_{j+1}$, then the partition lines originated from
$x_{i-\frac{1}{2}}$, $i=j-2,\cdots,j+3$ do not intersect under the condition

$\tilde{\lambda}<2\min\left\\{\frac{1}{s_{\ell}-r_{1}},\frac{1}{z_{\ell}-r_{2}},\frac{1}{r_{1}-r_{3}},\frac{1}{r_{2}-z_{r}},\frac{1}{r_{3}-s_{r}}\right\\}.$

###### Proof.

Suppose the partition lines originated from $x_{j\pm\frac{1}{2}}$ do not
intersect, then we have $\displaystyle\frac{r_{1}+r_{2}}{2}\Delta t<\Delta
x+\frac{r_{2}+r_{3}}{2}\Delta t,$ which further implies
$\displaystyle(r_{1}-r_{3})\Delta t<2\Delta x.$ Clearly, if $r_{1}-r_{3}\leq
0$, then the two characteristics never intersect, and the time should be
$+\infty.$ Otherwise, we need $\displaystyle\Delta t<\frac{2\Delta
x}{r_{1}-r_{3}}$, and a sufficient condition is
$\displaystyle\tilde{\lambda}<\frac{2}{r_{1}-r_{3}}$. The other terms on the
right-hand side can be obtained following the same lines. ∎

The above lemma has the following straightforward corollary.

######  Corollary 3.1.

Suppose the numerical approximations are within the interval $[b,a]$, if

$r_{1}\geq\frac{a+b}{2},\quad r_{3}\leq\frac{a+b}{2},\quad
r_{1}-r_{3}\leq\frac{2}{\lambda},\quad
z_{\ell}-r_{2}\leq\frac{2}{\lambda},\quad r_{2}-z_{r}\leq\frac{2}{\lambda},$
(3.8)

then $\displaystyle s_{\ell}-r_{1}\leq\frac{2}{\lambda},\
r_{3}-s_{r}\leq\frac{2}{\lambda}$ and the partition lines originated from
$x_{i-\frac{1}{2}}$, $i=j-2,\cdots,j+3$ do not intersection under the
condition (3.7).

###### Proof.

The two inequalities are straightforward, hence we skip the details. We first
consider the three missing terms in Lemma 3.6 one by one.

  1. 1.

$\displaystyle\frac{1}{s_{\ell}-r_{1}}.$

    1. (a)

If $s_{\ell}\leq r_{1}$, then $\displaystyle\frac{1}{s_{\ell}-r_{1}}=\infty$,
and it does not contribute anything in the time step restriction.

    2. (b)

If $s_{\ell}\geq r_{1}$, then

$s_{\ell}-r_{1}\leq a-\frac{a+b}{2}=\frac{a-b}{2}.$

Since $\lambda=\frac{4}{a-b}$, then $\displaystyle\frac{1}{s_{\ell}-r_{1}}$
does not contribute anything in the time step restriction.

  2. 2.

$\displaystyle\frac{1}{r_{3}-s_{r}}.$ The analysis can be obtained following
the same lines given for $\displaystyle\frac{1}{s_{\ell}-r_{1}}$, so we skip
it.

  3. 3.

$\displaystyle\frac{1}{r_{1}-r_{3}}.$ Since $\displaystyle 0\leq
r_{1}-r_{3}\leq\frac{2}{\lambda}$, then
$\displaystyle\frac{1}{r_{1}-r_{3}}\geq\frac{\lambda}{2}$. Therefore,
$\displaystyle\frac{1}{r_{1}-r_{3}}$ does not contribute anything in the time
step restriction.

  4. 4.

$\displaystyle\frac{1}{z_{\ell}-r_{2}}$ and
$\displaystyle\frac{1}{r_{2}-z_{r}}$. The analyses can be obtained following
the same lines given for $\displaystyle\frac{1}{r_{1}-r_{3}}.$ So we skip
them.

∎

The above corollary is quite helpful in finding suitable numerical
approximations within the influence region such that the partition lines do
not intersect among the cases in Table 1. However, two choices of
$\tilde{z}_{i}^{\prime}s$ needs special treatments. We state the technique for
the two special cases in Theorem 3.4-3.5 and the summary for all the cases in
Theorem 3.6.

We would like to start from some special cases in Table 1. For simplicity of
presentation, we drop the tilde and use $z_{i}$ for $\tilde{z}_{i}$,
$i=1,2,3$.

######  Theorem 3.4.

Suppose $I_{j}$ is an ETC, and the influence region is given by Case I4: in
Definition 3.2. If $\lambda=\frac{4}{a-b}$, then we can find $r_{1}$, $r_{2}$,
$r_{3}$ defined in cells $I_{j-1},$ $I_{j}$, $I_{j+1}$, respectively, such
that

$a\geq r_{1}\geq r_{2}\geq r_{3}\geq b,\quad
s_{\ell}-r_{1}\leq\frac{2}{\lambda},\quad
z_{\ell}-r_{2}\leq\frac{2}{\lambda},\quad
r_{1}-r_{3}\leq\frac{2}{\lambda},\quad r_{2}-z_{r}\leq\frac{2}{\lambda},\quad
r_{3}-s_{r}\leq\frac{2}{\lambda}$

under one of the following conditions

  1. 1.

$\displaystyle z_{1}=z_{2}=\frac{1}{3}A+\frac{2}{3\lambda}$, $\displaystyle
z_{3}=\frac{1}{3}A-\frac{4}{3\lambda}$, with $\displaystyle\frac{7a+5b}{4}\geq
A\geq a+2b$.

  2. 2.

$\displaystyle z_{1}=z_{2}=\frac{1}{3}A+\frac{2}{3\lambda}$, $\displaystyle
z_{3}=\frac{1}{3}A-\frac{4}{3\lambda}$, with $\displaystyle\frac{7a+5b}{4}\leq
A\leq\frac{5a+b}{2}$, $\displaystyle z_{r}\geq\frac{a+3b}{4}$ and
$\displaystyle s_{r}+z_{r}\geq\frac{a+3b}{2}$.

  3. 3.

$\displaystyle z_{1}=\frac{1}{3}A+\frac{4}{3\lambda}$, $\displaystyle
z_{2}=z_{3}=\frac{1}{3}A-\frac{2}{3\lambda}$, with
$\displaystyle\frac{5a+7b}{4}\leq A\leq 2a+b$.

  4. 4.

$\displaystyle z_{1}=\frac{1}{3}A+\frac{4}{3\lambda}$, $\displaystyle
z_{2}=z_{3}=\frac{1}{3}A-\frac{2}{3\lambda}$, with
$\displaystyle\frac{5a+7b}{4}\geq A\geq\frac{a+5b}{2}$, $\displaystyle
z_{\ell}\leq\frac{3a+b}{4}$ and $\displaystyle
s_{\ell}+z_{\ell}\leq\frac{3a+b}{2}$.

In addition, the proposed numerical approximations satisfy

$\sum_{j=1,2,3}z_{j}=\sum_{j=1,2,3}r_{j},\quad
TV(z_{\ell},z_{1},z_{2},z_{3},z_{r})\geq
TV(z_{\ell},r_{1},r_{2},r_{3},z_{r}).$

Moreover, after updating the numerical approximations, $I_{i}$,
$i=j-1,\cdots,j+1$ are not troubled cells. If $I_{j-2}$ is a troubled cell, it
can only be a troubled cell of type II or IV. If $I_{j+2}$ is a troubled cell,
it can only be a troubled cell of type III or V.

###### Proof.

We consider conditions 1 and 2 only, and the proof for conditions 3 and 4 can
be obtained following the same line. We verify the conditions in Corollary
3.1.

  1. 1.

Suppose $\displaystyle a+2b\leq A\leq\frac{7a+5b}{4}$, then

$z_{2}+z_{3}=\frac{1}{3}A+\frac{2}{3\lambda}+\frac{1}{3}A-\frac{4}{3\lambda}=\frac{2}{3}A-\frac{2}{3\lambda}\leq\frac{7a+5b}{6}-\frac{a-b}{6}=a+b,$

and

$z_{2}=\frac{1}{3}A+\frac{2}{3\lambda}\geq\frac{a+2b}{3}+\frac{a-b}{6}=\frac{a+b}{2}.$

We take $r_{1}=z_{1}=z_{2}\geq\frac{a+b}{2}$, $r_{2}=\frac{a+b}{2}$,
$r_{3}=z_{2}+z_{3}-r_{2}\in[z_{3},r_{2}]$, to get

$\sum_{j=\ell,1,2,3,r}z_{j}=\sum_{j=\ell,1,2,3,r}r_{j}.$

Moreover, following direct computation, we can get

$b\leq z_{3}\leq r_{3}=z_{2}+z_{3}-r_{2}\leq\frac{a+b}{2}\leq z_{1},\quad
r_{1}-r_{3}\leq z_{1}-z_{3}=\frac{2}{\lambda},$

and

$z_{\ell}-r_{2}\leq a-\frac{a+b}{2}=\frac{a-b}{2}=\frac{2}{\lambda},\quad
r_{2}-z_{r}\leq\frac{a+b}{2}-b=\frac{a-b}{2}=\frac{2}{\lambda}.$

Finally,

$TV(z_{\ell},r_{1},r_{2},r_{3},z_{r})=TV(z_{\ell},z_{1},r_{3},z_{r})\leq
TV(z_{\ell},z_{1},r_{3},z_{3},z_{r})=TV(z_{\ell},z_{1},z_{3},z_{r})=TV(z_{\ell},z_{1},z_{2},z_{3},z_{r}).$

  2. 2.

Suppose $\displaystyle\frac{7a+5b}{4}\leq A\leq\frac{5a+b}{2}$. Then
$\displaystyle
z_{2}+z_{3}=\frac{2}{3}A-\frac{2}{3\lambda}\geq\frac{2}{3}\frac{7a+5b}{4}-\frac{2}{3}\frac{a-b}{4}=a+b$,
leading to $\displaystyle z_{2}\geq\frac{a+b}{2},$ and $z_{\ell}-z_{2}\leq
a-\frac{a+b}{2}=\frac{2}{\lambda}$. We use the following procedure to find
$r_{j}^{\prime}s$, $j=1,2,3$.

    1. (a)

If $z_{2}\leq z_{r}+\frac{2}{\lambda}$, then we can take $r_{j}=z_{j}$,
$j=1,2,3$.

    2. (b)

If $z_{2}>z_{r}+\frac{2}{\lambda}$, then we take $r_{1}=z_{1},$
$r_{2}=z_{r}+\frac{2}{\lambda}$ and $r_{3}=z_{2}+z_{3}-r_{2}.$ Clearly, we
have $r_{2}<z_{2}=r_{1}$ and $r_{3}>z_{3}$, leading to
$r_{1}-r_{3}<\frac{2}{\lambda}$ and $z_{\ell}-r_{2}\leq
a-z_{r}-\frac{2}{\lambda}\leq a-b-\frac{2}{\lambda}=\frac{2}{\lambda}.$ Since

$z_{2}+z_{3}=\frac{2}{3}A-\frac{2}{3\lambda}\leq\frac{5a+b}{3}-\frac{a-b}{6}=\frac{3a+b}{2}=\frac{a+3b}{2}+(a-b)\leq
2z_{2}+\frac{4}{\lambda}=2r_{2},$

then $r_{3}=z_{2}+z_{3}-r_{2}\leq r_{2}.$ Moreover,

$r_{3}-s_{r}=z_{2}+z_{3}-r_{2}-s_{r}=z_{2}+z_{3}-z_{r}-\frac{2}{\lambda}-s_{r}\leq
a+\frac{a+b}{2}-\frac{a-b}{2}-\frac{a+3b}{2}=\frac{a-b}{2}=\frac{2}{\lambda},$

and

$TV(z_{\ell},r_{1},r_{2},r_{3},z_{r})=TV(z_{\ell},z_{1},r_{3},z_{r})\leq
TV(z_{\ell},z_{1},r_{3},z_{3},z_{r})=TV(z_{\ell},z_{1},z_{3},z_{r})=TV(z_{\ell},z_{1},z_{2},z_{3},z_{r}).$

  3. 3.

Finally, based on the construction of $r_{1},$ $r_{2}$, $r_{3}$, we can see
that $I_{j-1}$, $I_{j}$, $I_{j+1}$ are not troubled cells. Since
$r_{1}\geq\frac{a+b}{2}$, then $I_{j-2}$ can only be troubled cells of type II
or IV. Finally, since $r_{3}\leq\frac{a+b}{2}$, then $I_{j+2}$ can only be a
troubled cell of type III and V.

∎

######  Theorem 3.5.

Suppose $I_{j}$ is an ETC, and the influence region is given by Case I2 in
Definition 3.2. If $\lambda=\frac{4}{a-b}$, then we can find $r_{1}$, $r_{2}$,
$r_{3}$, $r_{r}$ defined in cells $I_{j-1},$ $I_{j}$, $I_{j+1}$, $I_{j+2}$,
respectively, such that

$a\geq r_{1}\geq r_{2}\geq r_{3}\geq b,\quad r_{1}\geq\frac{a+b}{2},\quad
z_{\ell}-r_{2}\leq\frac{2}{\lambda},\quad
r_{1}-r_{3}\leq\frac{2}{\lambda},\quad r_{2}-r_{r}\leq\frac{2}{\lambda},\quad
r_{3}-s_{r}\leq\frac{2}{\lambda},\quad b\leq r_{r}\leq\frac{a+b}{2}$

under the conditions that

$z_{1}=z_{2}=\frac{1}{3}A+\frac{2}{3\lambda},\quad
z_{3}=\frac{1}{3}A-\frac{4}{3\lambda},\quad\frac{7a+5b}{4}<A\leq\frac{5a+b}{2},$

and one of the following two inequalities

$s_{r}+z_{r}<\frac{a+3b}{2},\quad z_{r}<\frac{a+3b}{4}.$

In addition, the proposed numerical approximations satisfy

$\sum_{j=1,2,3,r}z_{j}=\sum_{j=1,2,3,r}r_{j},\quad
TV(z_{\ell},z_{1},z_{2},z_{3},z_{r},s_{r})\geq
TV(z_{\ell},r_{1},r_{2},r_{3},r_{r},s_{r}).$

Moreover, after updating the numerical approximations, $I_{i}$,
$i=j-1,\cdots,j+2$ are not troubled cells. If $I_{j+3}$ is a troubled cell, it
can only be a troubled cell of type III or V. If $I_{j-2}$ is a troubled cell,
it can only be a troubled cell of type II and IV. Similarly, by choosing the
influence region as Case I2 in Definition 3.2, we can find $r_{\ell}$,
$r_{1}$, $r_{2}$, $r_{3}$ defined in cells $I_{j-2}$, $I_{j-1},$ $I_{j}$,
$I_{j+1}$, respectively, such that

$a\geq r_{1}\geq r_{2}\geq r_{3}\geq b,\quad a\geq
r_{\ell}\geq\frac{a+b}{2},\quad s_{\ell}-r_{1}\leq\frac{2}{\lambda},\quad
r_{\ell}-r_{2}\leq\frac{2}{\lambda},\quad
r_{1}-r_{3}\leq\frac{2}{\lambda},\quad r_{2}-z_{r}\leq\frac{2}{\lambda},\quad
r_{3}\leq\frac{a+b}{2}$

under the conditions that

$z_{1}=\frac{1}{3}A+\frac{4}{3\lambda},\quad
z_{2}=z_{3}=\frac{1}{3}A-\frac{2}{3\lambda},\quad\frac{5a+7b}{4}>A\geq\frac{a+5b}{2}.$

and one of the following two inequalities

$z_{\ell}>\frac{3a+b}{4},\quad s_{\ell}+z_{\ell}>\frac{3a+b}{2}.$

In addition, the proposed numerical approximations satisfy

$\sum_{j=\ell,1,2,3}z_{j}=\sum_{j=\ell,1,2,3}r_{j},\quad
TV(s_{\ell},z_{\ell},z_{1},z_{2},z_{3},z_{r})\geq
TV(s_{\ell},r_{\ell},r_{1},r_{2},r_{3},z_{r}).$

Moreover, after updating the numerical approximations, $I_{i}$,
$i=j-2,\cdots,j+1$ are not troubled cells. If $I_{j+2}$ is a troubled cell, it
can only be a troubled cell of type III or V. If $I_{j-3}$ is a troubled cell,
it can only be a troubled cell of type II and IV.

###### Proof.

We consider Case I2 in Definition 3.2 only, and the proof for Case I3 can be
obtained following the same lines with some minor changes. We construct the
$r_{i}^{\prime}s$, $i=1,2,3,r$ as follows.

  1. 1.

Define $\tilde{z}_{j}=z_{j}$, $j=1,r$ and $\tilde{z}_{3}=\frac{a+b}{2}\geq
z_{3}$, $\tilde{z}_{2}=z_{2}+z_{3}-\tilde{z}_{3}>\frac{a+b}{2}$. Clearly,
$z_{2}\geq\tilde{z}_{2}\geq\tilde{z}_{3}\geq z_{3}$. Moreover, we define
$r_{j}=\tilde{z}_{j}$, $j=1,3$.

  2. 2.

If $\tilde{z}_{2}\geq\frac{a+b}{2}+\frac{1}{\lambda}$ and
$\tilde{z}_{r}\leq\frac{a+b}{2}-\frac{1}{\lambda}$, define
$r_{2}=\tilde{z}_{2}-\frac{1}{\lambda}$ and
$r_{r}=\tilde{z}_{r}+\frac{1}{\lambda}.$ Clearly,

$a\geq r_{1}=z_{1}=z_{2}\geq\tilde{z}_{2}\geq
r_{2}\geq\frac{a+b}{2}=r_{3}=\tilde{z}_{3}\geq
r_{r}\geq\tilde{z}_{r}=z_{r}\geq b.$

By Lemma 3.4, we know $r_{1}=z_{1}\geq\frac{a+b}{2}$. Since
$r_{3}=\frac{a+b}{2}$, we have

$r_{1}-r_{3}\leq a-\frac{a+b}{2}=\frac{a+b}{2}\leq\frac{2}{\lambda},\quad
r_{3}-s_{r}\leq\frac{a+b}{2}-b=\frac{a-b}{2}=\frac{2}{\lambda}.$

Since $r_{2}\geq\frac{a+b}{2}$, then $z_{\ell}-r_{2}\leq
a-\frac{a+b}{2}=\frac{a+b}{2}\leq\frac{2}{\lambda}$. Moreover,

$r_{2}-r_{r}=\tilde{z}_{2}-\frac{1}{\lambda}-\tilde{z}_{r}-\frac{1}{\lambda}\leq
z_{2}-z_{r}-\frac{2}{\lambda}\leq a-b-\frac{2}{\lambda}=\frac{2}{\lambda}.$

Clearly,

$\sum_{j=\ell,1,2,3,r}z_{j}=\sum_{j=\ell,1,2,3,r}\tilde{z}_{j}=\sum_{j=\ell,1,2,3,r}r_{j}.$

Finally,

$\displaystyle
TV(z_{\ell},z_{1},z_{2},z_{3},z_{r},s_{r})=TV(z_{\ell},z_{1},z_{2},\tilde{z}_{2},\tilde{z}_{3},z_{3},z_{r},s_{r})\geq
TV(z_{\ell},\tilde{z}_{1},\tilde{z}_{2},\tilde{z}_{3},\tilde{z}_{r},s_{r})$
$\displaystyle=$ $\displaystyle
TV(z_{\ell},r_{1},\tilde{z}_{2},r_{2},r_{3},r_{r},\tilde{z}_{r},s_{r})\geq
TV(z_{\ell},r_{1},r_{2},r_{3},r_{r},s_{r}).$

  3. 3.

If $\tilde{z}_{2}\leq\frac{a+b}{2}+\frac{1}{\lambda}$ and
$\tilde{z}_{r}\leq\frac{a+b}{2}-\frac{1}{\lambda}$, define
$r_{2}=\frac{a+b}{2}$ and $r_{r}=\tilde{z}_{2}+\tilde{z}_{r}-r_{2}$. Clearly,

$\tilde{z}_{2}\geq r_{2}=\frac{a+b}{2}=r_{3}=\tilde{z}_{3}\geq
r_{r}\geq\tilde{z}_{r}=z_{r}\geq b.$

Moreover, $r_{2}-r_{r}\leq\frac{a+b}{2}-b=\frac{a-b}{2}\leq\frac{2}{\lambda}.$
All the other inequalities are exactly the same as in case 2.

  4. 4.

If $\tilde{z}_{2}\geq\frac{a+b}{2}+\frac{1}{\lambda}$ and
$\tilde{z}_{r}\geq\frac{a+b}{2}-\frac{1}{\lambda}$, define
$r_{r}=\frac{a+b}{2}$ and $r_{2}=\tilde{z}_{2}+\tilde{z}_{r}-r_{r}$. Clearly,

$\tilde{z}_{2}\geq r_{2}\geq
r_{3}=\tilde{z}_{3}=\frac{a+b}{2}=r_{r}\geq\tilde{z}_{r}\geq b.$

Moreover, $r_{2}-r_{r}\leq
a-\frac{a+b}{2}=\frac{a-b}{2}\leq\frac{2}{\lambda}.$ All the other
inequalities are exactly the same as in case 2.

  5. 5.

If $\tilde{z}_{2}\leq\frac{a+b}{2}+\frac{1}{\lambda}$ and
$\tilde{z}_{r}\geq\frac{a+b}{2}-\frac{1}{\lambda}$, define
$r_{2}=\tilde{z}_{2}$ and $r_{r}=\tilde{z}_{r}$. Clearly,

$\tilde{z}_{2}=r_{2}\geq r_{3}=\tilde{z}_{3}\geq
r_{r}=\tilde{z}_{r},\quad\frac{a+b}{2}\geq\frac{a+3b}{2}-s_{r}>r_{r}=z_{r}\geq
b.$

Here we use the fact that $\tilde{z}_{r}=z_{r}<\frac{a+b}{2}$. Moreover,
$r_{2}-r_{r}\leq\frac{a+b}{2}+\frac{1}{\lambda}-\frac{a+b}{2}+\frac{1}{\lambda}=\frac{2}{\lambda}.$
All the other inequalities are exactly the same as in the above case.

  6. 6.

Finally, based on the construction given above and $r_{r}\leq\frac{a+b}{2}$,
it is easy to see $I_{i}$, $i=j-1,\cdots,j+2$ are not troubled cells after the
modification, Since $r_{1}\geq\frac{a+b}{2}$, and $r_{r}\leq\frac{a+b}{2}$,
then $I_{j-2}$ can only be a troubled cell of type II and IV and $I_{j+3}$ can
only be a troubled cell of type III and V.

∎

######  Theorem 3.6.

Suppose the numerical approximations are within the interval $[b,a]$, and
$I_{j}$ is an ETC. The numerical approximations on $I_{j-3},\cdots,I_{j+3}$
are $s_{\ell}$, $z_{\ell}$, $z_{1}$, $z_{2}$, $z_{3}$, $z_{r}$, $s_{r}$,
respectively, with $z_{1}\geq z_{2}\geq z_{3}$ and $z_{1}\geq
z_{3}+\frac{2}{\lambda}$. The influence region is given in Definition 3.2. If
we take $\lambda=\frac{4}{a-b}$, then we can find $r_{\ell},$ $r_{1}$,
$r_{2}$, $r_{3}$, $r_{r}$ defined in cells $I_{j-2},$ $\cdots,$ $I_{j+2}$,
respectively, without changing the numerical approximations on the boundary
cells in the influence region, such that the proposed new numerical
approximations satisfy

$\sum_{j=\ell,1,2,3,r}z_{j}=\sum_{j=\ell,1,2,3,r}r_{j},\quad
TV(s_{\ell},z_{\ell},z_{1},z_{2},z_{3},z_{r},s_{r})\geq
TV(s_{\ell},r_{\ell},r_{1},r_{2},r_{3},r_{r},s_{r}).$

Moreover, one of the possible troubled cell in the influence region is the one
on the right boundary and it can only be a troubled cell of type III or V. The
other possible troubled cell in the influence region is the one on the left
boundary and it can only be a troubled cell of type II or IV. Finally, the
partition lines at the boundaries of the influence region keep the same.

###### Proof.

We have demonstrated some partial results in Theorems 3.4 and 3.5. Now we will
show that if the influence region is given as Case I4 in Definition 3.2, then
the adjusted numerical approximations satisfy

$a\geq r_{1}\geq r_{2}\geq r_{3}\geq b,\quad r_{1}\geq\frac{a+b}{2},\quad
r_{3}\leq\frac{a+b}{2},\quad r_{1}-r_{3}\leq\frac{2}{\lambda},\quad
z_{\ell}-r_{2}\leq\frac{2}{\lambda},\quad r_{2}-z_{r}\leq\frac{2}{\lambda}.$

We discuss the cases given in Table 1.

  * •

Case 1. We take $r_{i}=z_{i}$, with $i=1,2,3$. Then we only need to show
$z_{\ell}-r_{2}\leq\frac{2}{\lambda},\ r_{2}-z_{r}\leq\frac{2}{\lambda}$.
Actually,

$r_{2}-z_{r}=z_{2}-z_{r}=z_{2}-z_{3}\leq z_{1}-z_{3}=\frac{2}{\lambda}.$

Finally, since $3z_{\ell}\leq A+\frac{2}{\lambda}\leq 3z_{1}$, then

$z_{\ell}-r_{2}=z_{\ell}-z_{2}\leq z_{1}-z_{2}\leq
z_{1}-z_{3}\leq\frac{2}{\lambda}.$

  * •

Case 2. We take $r_{i}=z_{i}$, with $i=1,2,3$. It is easy to see that
$z_{1}\geq z_{\ell}$. We follow the same analysis in Case 1 except

$r_{2}-z_{r}=z_{2}-z_{r}\leq
z_{1}-z_{r}\leq\frac{a+b}{2}-b\leq\frac{a-b}{2}=\frac{2}{\lambda}.$

  * •

Case 3. By Lemma 3.4 and Theorems 3.4 and 3.5, we only assume
$\displaystyle\frac{a+5b}{2}\leq A<a+2b$, and take $r_{i}=z_{i}$, with
$i=1,2,3$. We follow the same analysis in Case 1 except

$r_{2}-z_{r}=\frac{1}{3}A+\frac{2}{3\lambda}-z_{r}\leq\frac{a+2b}{3}+\frac{2}{3\lambda}-b=\frac{a-b}{3}+\frac{2}{3\lambda}\leq\frac{4}{3\lambda}+\frac{2}{3\lambda}=\frac{2}{\lambda}.$

  * •

Cases 4, 5 and 6. The proof is similar to Cases 1, 2 and 3, so we skip it.

  * •

Case 7. We consider three possibilities.

    1. 1.

If $\displaystyle\frac{1}{3}A+\frac{2}{3\lambda}\geq z_{r}+\frac{2}{\lambda}$,
then we can take $\displaystyle z_{1}=\frac{1}{3}A+\frac{2}{3\lambda}$,
$\displaystyle z_{2}=\frac{1}{3}A+\frac{2}{3\lambda}$, $\displaystyle
z_{3}=\frac{1}{3}A-\frac{4}{3\lambda}$. Since $\displaystyle A\geq
3z_{r}+\frac{4}{\lambda}\geq 3b+a-b=a+2b,$ the conclusion follows from
Theorems 3.4 and 3.5.

    2. 2.

If $\displaystyle\frac{1}{3}A+\frac{4}{3\lambda}\leq z_{\ell}$, then we can
take $\displaystyle z_{1}=\frac{1}{3}A+\frac{4}{3\lambda}$, $\displaystyle
z_{2}=\frac{1}{3}A-\frac{2}{3\lambda}$, $\displaystyle
z_{3}=\frac{1}{3}A-\frac{2}{3\lambda}$. Since $\displaystyle A\leq
3z_{\ell}-\frac{4}{\lambda}\leq 3a-(a-b)=2a+b,$ the conclusion follows from
Theorems 3.4 and 3.5.

    3. 3.

If $\displaystyle\frac{1}{3}A+\frac{2}{3\lambda}\leq z_{r}+\frac{2}{\lambda}$
and $\displaystyle\frac{1}{3}A+\frac{4}{3\lambda}\geq z_{\ell}$, then we can
take $\displaystyle z_{1}=z_{r}+\frac{2}{\lambda}$, $\displaystyle
z_{3}=z_{r}$, $\displaystyle z_{2}=A-2z_{r}-\frac{2}{\lambda}$, which returns
to case 1. We can following the same proof to obtain all the required
inequalities except $\displaystyle r_{\ell}-z_{r}\leq\frac{2}{\lambda}$, where
a special condition was used for $z_{\ell}$ in case 1. Based on the
assumptions, we have

$\frac{1}{3}A+\frac{2}{3\lambda}\leq z_{r}+\frac{2}{\lambda}=z_{1}\leq
z_{\ell}\leq\frac{1}{3}A+\frac{4}{3\lambda},$

which further implies

$z_{\ell}+2z_{r}\leq
3\cdot\left(\frac{1}{3}A+\frac{4}{3\lambda}\right)-2\cdot\frac{2}{\lambda}=A.$

Then we have

$z_{\ell}-r_{2}=z_{\ell}-z_{2}=z_{\ell}-\left(A-2z_{r}-\frac{2}{\lambda}\right)=z_{\ell}-A+2z_{2}+\frac{2}{\lambda}\leq\frac{2}{\lambda}.$

  * •

Case 8. We take $r_{i}=z_{i}$, with $i=1,2,3$. We follow the same analysis in
Case 1 except

$z_{\ell}-r_{2}=z_{\ell}-z_{2}\leq
z_{r}+\frac{2}{\lambda}-z_{3}=\frac{2}{\lambda}.$

  * •

Case 9. We take $r_{i}=z_{i}$, with $i=1,2,3$. We follow the same analysis in
Case 1 except

$z_{\ell}-r_{2}=z_{\ell}-z_{2}\leq z_{1}-z_{2}\leq\frac{2}{\lambda},$

and

$r_{2}-z_{r}=z_{2}-z_{r}=A-\frac{3a+b}{2}-z_{r}\leq
3z_{\ell}-\frac{2}{\lambda}-\frac{3a+b}{2}-a+\frac{2}{\lambda}\leq
2a-\frac{3a+b}{2}=\frac{2}{\lambda}.$

  * •

Case 10. We take $r_{i}=z_{i}$, with $i=1,2,3$. We follow the same analysis in
Case 1 except

$z_{\ell}-r_{2}=z_{1}-z_{2}\leq z_{1}-z_{3}=\frac{2}{\lambda},$

and

$r_{2}-z_{r}=z_{2}-z_{r}\leq z_{2}-z_{\ell}+\frac{2}{\lambda}\leq
z_{1}-z_{\ell}+\frac{2}{\lambda}=z_{\ell}-z_{\ell}+\frac{2}{\lambda}=\frac{2}{\lambda}.$

Following the same analysis in Theorem 3.5, we can show that the only possible
troubled cell are located at the boundaries of the influence region and
determine the possible types of the troubled cells, hence we skip the details.
Moreover, since we did not modify the boundary cells, the partition lines keep
the same at the two boundaries of the influence region. ∎

####  3.3.4 From Theorem 3.6 to prove Theorem 3.1

With all the preparation given above, we can prove Theorem 3.1. Actually, by
Theorem 3.6 and Corollary 3.1, we can redefine the numerical approximations
within the influence region such that the only possible troubled cells in the
influence regions are those at the boundaries, if $\Delta t<\lambda\Delta x$
with $\lambda=\frac{4}{a-b}$, and the troubled cells are mainly due to the
strong shocks at the boundaries of the influence region. Such troubled cell or
its neighbor, which were not updated, will be defined as an ETC, and the
influence region of the new ETC will overlap with tht of the originial one,
which contradicts the assuption that the ETCs are isolated. Therefore, no
troubled cells exist in whole computational domain. Moreover, by Lemma 3.2,
the numerical scheme is TVD and MPP. Finally, we will perform the $L^{2}$
projection which keeps the maximum-principle and such procedure will not
increase the total variation, and keeps the physical bounds for first-order
schemes, hence we finish the proof.

###  3.4 The stability analysis if the ETCs are not isolated

In Theorem 3.1, we assume the ETCs are isolated. In practice, if there is only
one shock in the exact solution, this assumption may be reasonable. However,
if two shocks are interacting, then the ETCs may not be isolated. In this
case, we may merge more cells. Based on the construction of the ETCs, we
consider the cells to the right of the influence region only. Suppose the 5
cells, with the ETC as the center, in the influence region and the 5 cells on
the right are given as
$r_{\ell},r_{1},r_{2},r_{3},r_{r},s_{1},s_{2},s_{3},s_{4},s_{5}$ from left to
right, where $r^{\prime}s$ are the updated numerical approximations in the
influence region given in Theorem 3.6. For simplicity, we do not distinguish
the troubled cells and the numerical approximations in the cells, e.g. we say
$s_{1}$ is a troubled cell if $s_{1}$ is the numerical approximation in the
troubled cell. The procedure is given as follows:

  1. 1.

The influence region contains four cells, $r_{\ell}$, $r_{1}$, $r_{2}$,
$r_{3}$. We search the cells from $r_{3}$ to the right, and select the ETC
following the procedure in Section 2.

  2. 2.

The influence region contains five cells, $r_{\ell}$, $r_{1}$, $r_{2}$,
$r_{3}$, $r_{r}$ or six cells biased to the left. We search the cells from
$r_{r}$ to the right, and select the ETC following the procedure in Section 2.

  3. 3.

The influence region contains six cells, $r_{\ell}$, $r_{1}$, $r_{2}$,
$r_{3}$, $r_{r}$, $s_{1}$. We search the cells from $s_{1}$ to the right, and
select the ETC following the procedure in Section 2.

  4. 4.

If the influence regions of the two ETCs are overlapping, we will merge the
two influence regions together.

######  Theorem 3.7.

We can modify the $s_{i}^{\prime}s$ to be merged given above such that no
troubled cells exist in the new influence region, except possibly the one on
the right boundary of the new influence region. Therefore, after the whole
procedure, the numerical approximations obtained from the first-order EL FV
scheme satisfy the maximum-principle and they are total variation diminishing.

###### Proof.

We will show that the procedure of merging the new influence region into the
original one and updating the numerical approximations based on the new
influence region will not create any new troubled cells in the original
influence region.

Actually, following the procedure given in Theorem 3.6 and Theorem 3.2, the
only possible new troubled cell that can be created by the new influence
region is the one on the left boundary and it must be associated with a strong
shock at the left boundary. However, we do not update the numerical
approximation next to the left boundary, hence such a troubled cell is not
created by the procedure of the new ETC but exists before we select the new
ETC. Without loss of generality, we assume $r_{2}$ is the ETC whose influence
region does not overlap with any other ETCs on its left. Then the left
boundary of the influence region of $r_{2}$ is a troubled cell. However, this
violates the selection procedure of the troubled cells given in Section 2.

Finally, for periodic boundary conditions, it is possible that the last ETC
may interact with the first ETC. By the strategies of merging overlapping
influence regions, no troubled cells exist between the first and last ETCs in
the computational domain. By the same analysis given above, the last ETC will
not create any new troubled cells at the right boundary of its influence
region. So we complete the proof.

∎

Therefore, based on the above analysis, we can merge the influence regions of
all non-isolated ETCs together.

##  4 Numerical experiments

###  4.1 One-dimensional test results

In this subsection, we present several numerical examples on one-dimensional
Burger’s equation

$u_{t}+(\frac{u^{2}}{2})_{x}=0.$ (4.1)

The time-stepping size $\Delta t$ is defined by

$\Delta t=\frac{C}{\max\\{u_{0}\\}-\min\\{u_{0}\\}}\cdot\Delta x,$ (4.2)

where $u_{0}$ is the initial conditions. When $0<C<4$, the TVD stability is
guaranteed from the main Theorem. The classical $CFL$ number is defined as

$CFL=\frac{\Delta t}{\Delta x}\cdot\max\lvert f^{\prime}(u)\rvert.$

Below $N$ is the number of cells used, and $T$ is the final evolving time.

######  Example 4.1.

(Accuracy test). We consider the Burgers’ equation with the initial condition
$u_{0}(x)=\sin(x)$ on the domain $x\in[0,2\pi]$ with periodic boundary
conditions. To ensure that the TVD property is preserved, it is noted that the
CFL number must not exceed 2. This is due to the restriction on the time-
stepping size $\Delta t$ specified in equation (4.2).

In our tests, we evaluate the method at $T=0.8$ (before the shock) and $T=1.3$
(after the shock), where the shock is located at $x=\pi$. Table 2 shows the
results of the mesh refinement study. With a CFL number of 1.95 (or $C=3.9$ in
equation (4.2)), we compute the $L^{1}$ error of the solution on the entire
domain (for the case before the shock) and on
$x\in[0,\pi-0.1]\cup[\pi+0.1,2\pi]$ (for the case after the shock). The
results indicate that the proposed scheme has achieved the desired first-order
convergence. Figure 5 plots the errors versus CFL numbers. We set the total
number of cells to be 200 and compute the $L^{1}$ errors for CFL numbers
ranging from 0.05 to 8.25 (or equivalently, $C\in[0.1,16.5]$). It is observed
that the $L^{1}$ errors remain at an excellent level, even when the CFL number
is relatively large. The decrease in error with the increase of CFL (for CFL
less than 1) is likely due to the decrease in the number of time steps when
the CFL is larger, leading to a reduced accumulation of global error. Finally,
Figure 5 shows the total variations versus time when $C=3.9$. The proposed
scheme is observed to exhibit the desired TVD property.

Table 2: Exa.4.1. Mesh refinement study, $CFL=1.95$. | T=0.8 | T=1.3
---|---|---
N |  $L^{1}$ error | order |  $L^{1}$ error | order
$100$ | 4.91e-03 | – | 3.49e-03 | –
$200$ | 2.76e-03 | 0.83 | 1.91e-03 | 0.87
$300$ | 1.97e-03 | 0.83 | 1.25e-03 | 1.06
$400$ | 1.63e-03 | 0.64 | 9.43e-04 | 0.97

Figure 4: CFL vs. error plot for Example 4.1.

Figure 5: History of total variation for Example 4.1.

######  Example 4.2.

(1D Riemann problems). We consider the Burgers’ equation (4.1) with Riemann
initial condition

$u_{0}(x)=\left\\{\begin{aligned} 2&,&x\leq 0,\\\
-1&,&\text{otherwise,}\end{aligned}\right.$ (4.3)

where $x\in[-\pi,\pi]$, and a constant boundary condition. The final time
$T=3.6$ and numerical mesh is $N=100$. This test is to verify that the maximum
time-stepping size in Theorem 3.1 is sharp. Figure 7 shows the history of
solutions’ total variations under different choices of $C$. When $C=0.8$
($CFL=\frac{8}{15}$), we observed that no cell-merging process occurred, and
the total variations maintained constant. When $C$ equals $2.6$, $3.9$, and
$4$ (or equivalently $CFL=\frac{26}{15}$, $2.6$, and $\frac{8}{3}$ ), the
cell-merging process is triggered, yet the total variations remain constant.
Finally, when $C$ exceeded 4, e.g. $C=4.9$, the total variations are observed
to increase, i.e. the TVD property is violated. We present the TVD property of
the solution with $C=3.9$ in Figure 7.

Figure 6: Example 4.2 with initial condition (4.3). Total variation history
for different $C$.

Figure 7: Example 4.2 with initial condition (4.3).

Next we present the results for the case of rarefaction wave with the initial
condition

$u_{0}(x)=\left\\{\begin{aligned} -1&,&x\leq 0,\\\
1&,&\text{otherwise,}\end{aligned}\right.$ (4.4)

where $x\in[-\pi,\pi]$. We let $T=1.3$, $N=100$, and $CFL=1.95$ (or $C=3.9$).
In fact, there is no time step limitation for the rarefaction wave problems
since it does not need to merge the cells. Here we choose the $C=3.9$ to keep
the consistency with the Theorem. The solution is plotted in Figure 9. An
excellent resolution is observed even under a relatively large $\Delta t$.
Total variations of each time step are also shown in Figure 9. The total
variation stays constant over time as expected.

Figure 8: Example 4.2 with initial condition (4.4).

Figure 9: Example 4.2 with initial condition (4.4). Total variation over time.

Next, We present an extreme case to show the necessity of Cases I2 and I3 in
Definition 3.2. Consider the initial condition

$u_{0}(x)=\left\\{\begin{aligned} 2&,&x\leq 0,\\\ -0.6&,&0<x\leq\Delta x,\\\
-2&,&\text{otherwise,}\end{aligned}\right.$ (4.5)

where $x\in[-\pi,\pi]$. We set final time $T=3$ and $N=100$. We test this
initial condition with the merging procedure following case I4 in Definition
3.2, that is the merging procedure combines only five cells under any
circumstances. We choose $C=3.4$, $3.6$ and $3.9$ ($CFL=1.7$, $1.8$, and
$1.95$) to compute the total variations at each time step. In Figure 11, the
initial total variation is $4$, and the total variation increases starting
from the second step. As a result, the TVD property no longer holds, even
though the constant $C$ is less than 4. To provide a comparison, we also test
the same initial data again, but this time the merging procedure includes the
Definition 3.2. In Figure 11, we choose the same time-stepping size as in
Figure 11, i.e., $C=3.4$, $3.6$ and $3.9$ ($CFL=1.7$, $1.8$, and $1.95$). The
TVD property is obtained in Figure 11. Thus, the Definition 3.2 is critical to
obtain the optimal time-stepping size.

Figure 10: Exa.4.2. Initial condition of (4.5). The numerical solution at
$T=3$, $N=100$. Merging procedure excludes Def. 3.2.

Figure 11: Exa.4.2. Initial condition of (4.5). The numerical solution at
$T=3$ and $N=100$. Merging procedure includes Def. 3.2.

###  4.2 Two-dimensional test results

The proposed first order scheme can be extended to two-dimensional Burger’s
equation,

$u_{t}+(\frac{u^{2}}{2})_{x}+(\frac{u^{2}}{2})_{y}=0,$ (4.6)

in a dimensional splitting fashion. The dimensional splitting method solves a
2D equation by alternating between solving two 1D equations, where we apply
the first-order scheme to each one-dimensional equation via the Strang
splitting. A detailed time splitting strategy under the EL FV framework can be
found in [9]. All examples in the following use a constant boundary condition
consistent with the Riemann initial condition. $N_{x}$ and $N_{y}$ are the
cell numbers of $x,y$-direction respectively. The time-stepping size $\Delta
t$ is bounded by,

$0<\Delta t<\frac{4\cdot min\\{\Delta x,\Delta
y\\}}{max\\{u_{0}\\}-min\\{u_{0}\\}}.$

The CFL is defined as

$CFL=\Delta t\left({max_{x,y}\lvert f_{x}(u)\rvert/\Delta x+max_{x,y}\lvert
f_{y}(u)\rvert/\Delta y}\right),$

and we adopt a 100$\times$100 grid.

######  Example 4.3.

(2D Burgers’ equation with continuous initial condition). We test 2D Burgers’
equation (4.6) with a continuous initial condition:

$u_{0}(x)=\left\\{\begin{aligned} (\sin(\pi x)\sin(\pi
y))^{2}&,&(x,y)\in(0,1)\times(0,1)\\\
0&,&\text{otherwise,}\end{aligned}\right.$ (4.7)

where $(x,y)\in[0,2]\times[0,2]$. The initial condition is shown in Figure 12
in both mesh and contour plots. The $CFL$ number is 7.6. The initial condition
evolves up to $T=3$. In Figure 13, we present both mesh and contour plots at
$T=1$, $2$, and $3$. The solution generates a comet-like shape. The sharp
discontinuity is formed at the head of the comet. The solution is observed to
be stable, and the shock is captured correctly under a very large time
stepping size.

Figure 12:  Initial condition of Exa.4.3. $N_{x}=N_{y}=100$.

Figure 13: Exa.4.3. $N_{x}=N_{y}=100$, $CFL=7.6$ .

######  Example 4.4.

(2D Riemann problem). Consider the 2D Burgers’ equation with the Riemann
Initial condition:

$u_{0}(x)=\left\\{\begin{aligned} 1&,&(x,y)\in(0,0.5]\times(0,0.5],\\\
2&,&(x,y)\in(-0.5,0]\times[0,0.5),\\\ 3&,&(x,y)\in[-0.5,0)\times[-0.5,0),\\\
4&,&(x,y)\in(0,0.5)\times(-0.5,0).\end{aligned}\right.$ (4.8)

The domain is $(x,y)\in[-0.5,0.5]\times[-0.5,0.5]$. The analytic solution of
this problem can be found in [11]. The initial values (1,2,3,4) are assigned
to each of the four quadrants, as shown in Figure 14. The $CFL$ number is
$8.6$ and final time $T=0.1$. The solution contains three shocks and one
rarefaction wave. One shock is formed at $\theta=0$. Two shocks are formed at
$\theta=\pi/2$ and $\pi$, they interact to form a new shock. The rarefaction
wave is formed at $\theta=3\pi/2$. The numerical scheme has the expected
performance and sharply captures the shocks and rarefaction waves under a
large time stepping size.

Figure 14: Initial condition of Exa.4.4. $N_{x}=N_{y}=100$.

Figure 15: Exa.4.4, $T=0.1$, $N_{x}=N_{y}=100$, $CFL=8.6$.

##  5 Concluding remarks

In this paper, we constructed a first order EL FV scheme for nonlinear
hyperbolic conservation laws. The main contribution was to introduce the merge
strategy in the influence region of an ETC to handle shocks, leading to a
scheme that is theoretically proved to be TVD and MPP. Moreover, the time step
size is much larger than the traditional Eulerian FV schemes. We also
theoretically demonstrated that if the size of the influence region was larger
than some threshold, larger influence region would not result in larger time
step sizes. The extension of the first-order EL FV scheme to high-order ones
can be done by applying high order spatial reconstruction with the minmod
limiter and the bound-preserving limiter, and by applying high order SSP RK
methods to temporal discretization in the space-time partitioned regions.
Computational aspects of such extensions will be explored in [3].

##  Reference

  * [1] B. Cockburn and C.-W. Shu, TVB Runge-Kutta local projection discontinuous Galerkin finite element method for conservation laws II: general framework, Mathematics of Computation, 52 (1989), 411-435.
  * [2] X. Cai, J.-M. Qiu and Y. Yang, An Eulerian-Lagrangian discontinuous Galerkin method for transport problems and its application to nonlinear dynamics, Journal of Computational Physics, 439 (2021), 110392.
  * [3] J. Chen, J. Nakao, J.-M. Qiu and Y. Yang, A new Eulerian-Lagrangian finite volume Runge-Kutta WENO method for nonlinear hyperbolic problems, in preparation.
  * [4] S. Gottlieb, D. Ketcheson and C-W. Shu, High order strong stability preserving time discretizations, Journal of Scientific Computing, 38 (2009), 251-289.
  * [5] A. Harten, High resolution schemes for hyperbolic conservation laws, Journal of Computational Physics, 49 (1983), 357-393.
  * [6] R. Healy and T. Russell, Solution of the advection-dispersion equation in two dimensions by a finite-volume Eulerian-Lagrangian localized adjoint method, Advances in Water Resources, 21 (1998), 11-26.
  * [7] C-S. Huang, T. Arbogast and J. Qiu An Eulerian–Lagrangian WENO finite volume scheme for advection problems, Journal of Computational Physics, 231 (2012), 4028-4052.
  * [8] L. Randall J, Finite volume methods for hyperbolic problems, Cambridge university press (2022).
  * [9] J. Nakao, J. Chen, and J.-M. Qiu, An Eulerian-Lagrangian Runge-Kutta finite volume (EL-RK-FV) method for solving convection and convection-diffusion equations, Journal of Computational Physics, 470 (2022), 111589.
  * [10] J.-M. Qiu, C.-W. Shu, Convergence of Godunov-type schemes for scalar conservation laws under large time steps, SIAM journal on numerical analysis, 46 (2008), 2211–2237.
  * [11] D.K. Yoon and W.J. Hwang, Two-dimensional Riemann Problem for Burgers’ equation, Bulletin of the Korean Mathematical Society, 45 (2008), 191-205.