Supplement to On Wavewise Entropy Inequalities for High Resolution Schemes I: The Semidiscrete Case

Huanan Yang

5. OVERVIEW OF THE PROOF OF THEOREM 3.13 The goal of this supplement is to prove the third WEI criterion, Theorem 3.13. We argue by

contradiction: Assume that a certain self-similar scheme (1.2)-(1.4) satisfying Assumption 3.3 fails to converge. We need to show that there exists a sequence of numerical solutions {u^{k}} of the scheme that harbors an ATES. This highly nontrivial task is fulfilled in three steps, which extend from §6 to §8. First, in §6 we develop a new technique, the extremum tracking. We introduce the notions of extremum paths and approximate extremum paths of a numerical solution of the aforementioned scheme. It turns out that a sequence of approximate extremum paths associated with a sequence of numerical solutions in Ψ̂_{w_{−},w_{+},B} is necessarily a sequence of {ε_{k}}–paths, a building block of the ATES. Next, in §7, we analyze the asymptotic waves of the sequences of numerical solutions in a nonempty Ψ̂_{w_{−},w_{+},B}. Roughly speaking, a wave of a numerical solution is the generic structure of the numerical solution between two ( approximate ) extremum paths, and an asymptotic wave is a sequence of waves of a sequence of numerical solutions. Using similarity transforms and selecting subsequences, we show that there exists a sequence in Ψ̂_{w_{−},w_{+},B} such that in a compact domain, the transition regions and the boundaries of all sufficiently strong asymptotic waves converge to x = st, which is the path of the discontinuity of the limit W of Ψ̂_{w_{−},w_{+},B}. Hence, these asymptotic waves must be ATWs. We then split these ATWs into ATDs. Finally, in §8, using Theorem 3.2 and Lemma 3.10, we complete the proof of Theorem 3.13 by showing that if W is a traveling expansion shock, then one of the ATDs must be an ATES.

6. EXTREMUM TRACKING In this section we introduce and analyze the notions of extremum paths and approximate

extremum paths of a numerical solution u. Theses paths will serve as the boundaries of the transition regions of the waves of the numerical solution.

We begin with the following simple observation:

Lemma 6.1. If u is a uniformly bounded numerical solution of a scheme (1.2)-(1.4), then there are two positive constants C_{1} and C_{2} such that

|\frac{du_{j}(t)}{dt}| ≤ C_{1}/h and |\frac{du_{j}(t′′)}{dt} − \frac{du_{j}(t′)}{dt}| ≤ (C_{2}/h^{2})|t′′ − t′|. (6.1)

Proof. Suppose that |u| is bounded by the constant B, and that K is the Lipschitz coefficient of g: for any data {v_{j}}_{j=1}^{2p} and {v′_{j}}_{j=1}^{2p}, we have

|g(v_{1}, …, v_{2p}) − g(v′_{1}, …, v′_{2p})| ≤ K ∑_{j=1}^{2p} |v_{j} − v′_{j}|.

Then

|\frac{du_{j}(t)}{dt}| = |Δ_{−}g(u_{j−p+1}(t), …, u_{j+p}(t))/h| ≤ K ∑_{i=−p+1}^{p} |Δ_{−}u_{j+i}(t)|/h ≤ 4pKB/h = C_{1}/h,

and hence,

|\frac{du_{j}(t′′)}{dt} − \frac{du_{j}(t′)}{dt}| = |Δ_{−}(g(u_{j−p+1}(t′′), …, u_{j+p}(t′′)) − g(u_{j−p+1}(t′), …, u_{j+p}(t′)))/h|
≤ 2K ∑_{i=j−p}^{j+p} |u_{i}(t′′) − u_{i}(t′)|/h ≤ 2K ∑_{i=j−p}^{j+p} ∫_{t′}^{t′′}(|\frac{du_{i}(t)}{dt}|/h)dt
≤ 2K(2p + 1)|t′′ − t′|C_{1}/h^{2} = (C_{2}/h^{2})|t′′ − t′|.

This completes the proof. □

I. The extremum paths. The set X = {x_{j}}_{j=−∞}^{∞} is called the set of grid points and L = X × R_{+} the set of grid lines. The solution u is defined on L. A finite set of successive grid points {x_{p}, …, x_{q}} with q ≥ p is said to be the stencil of a spatial maximum, or simply an M-stencil of u at the time t, provided u_{p}(t) = ⋯ = u_{q}(t), u_{p−1}(t) < u_{p}(t), and u_{q+1}(t) < u_{q}(t). Notions of N-stencils for minima and E-stencils for general extrema are defined similarly.

Lemma 6.2. Suppose {x_{p}, …, x_{q}}, q ≥ p, is an M-stencil of u at the time t_{0}. Then there exists a δ > 0 such that, when |t − t_{0}| < δ, there exists at least one M-stencil {x_{p′}, …, x_{q′}} of u_{j}(t) at the time t that is a subset of {x_{p}, …, x_{q}}.

Proof. Since the numerical solution of a semidiscrete scheme is continuous in t, there exists a δ > 0 such that for each t with |t − t_{0}| < δ,

max{u_{p−1}(t), u_{q+1}(t)} < min{u_{p}(t), …, u_{q}(t)}.

Since {x_{p}, …, x_{q}} is a finite set, it contains a subset {x_{p′}, …, x_{q′}} with u_{p′}(t) = ⋯ = u_{q′}(t) = max{u_{p}(t), …, u_{q}(t)}, u_{p′−1}(t) < u_{p′}(t) and u_{q′+1}(t) < u_{q′}(t). □

Motivated by Lemma 6.2, we define a ridge of u as follows:

Definition 6.3. A nonempty subset of L denoted by M_{t_{1},t_{2}} is called a ridge of the numerical solution u from t_{1} to t_{2} if

(i) For all t ∈ [t_{1}, t_{2}] the set

P_{M}(t) =^{def} {x_{j} : (x_{j}, t) ∈ M_{t_{1},t_{2}}} = {x_{p(t)}, …, x_{q(t)}}

is not empty, and is an M-stencil of u at t.

(ii) M_{t_{1},t_{2}} satisfies the following “connectivity” condition: for each t on [t_{1}, t_{2}], there exists a neighborhood U(t) of t such that if t′ ∈ U(t) ∩ [t_{1}, t_{2}], then P_{M}(t′) ⊆ P_{M}(t).

The set P_{M}(t) is called the x-projection of M_{t_{1},t_{2}} at t. The value of u along the ridge is denoted by V_{M}(t): V_{M}(t) = u_{j}(t) for p(t) ≤ j ≤ q(t).

Hereafter , we use the notations M_{t_{1},t_{2}}, P_{M}(t) and V_{M}(t) exclusively for the above notions. If for all t ∈ [t_{1}, t_{2}] the M-stencil in (ii) is replaced by an N-stencil, then the set is called a trough of u from t_{1} to t_{2}, and is denoted by N_{t_{1},t_{2}}. The related notions P_{N}(t) and V_{N}(t) are defined similarly. Ridges and troughs are also called extremum paths. When we do not distinguish between ridges and troughs, we use E_{t_{1},t_{2}}, P_{E}(t) and V_{E}(t) for either type. We add superscripts on M, N, or E to indicate several paths in one solution, sequences of paths associated with a sequence of solutions, or both. We make the convention that E_{t_{1},t_{2}}^{1} < (≤)E_{t_{1},t_{2}}^{2} when max P_{E^{1}}(t) < (≤) max P_{E^{2}}(t) for all t ∈ [t_{1}, t_{2}]. Let t′′ > t′ ≥ 0. We say that a given E-stencil of u at t′′ can be traced back to t′ if it is the x-projection of a path E_{t_{1},t_{2}} at t′′.

Intuitively, if the scheme is nonoscillatory, no new extremum emerges for t > 0, and one should be able to trace any given E-stencil back to the initial time t = 0. This is indeed true (see Lemma 6.11) provided that the scheme satisfies the following TVD condition, also due to Tadmor [25].

Assumption 6.4 (Local Maximum Principle). If x_{i} belongs to an M(N)-stencil of u_{j}(t) at the time t, then

\frac{du_{i}(t)}{dt} ≤ (≥)0.

Clearly, a scheme satisfying Assumption 3.3 also satisfies Assumption 6.4.

The main result of this section is the Backward Traceability Lemma 6.11. A string of lemmas are needed in its proof: the Local Nonoscillatory Property Lemmas 6.5 and 6.6, the Monotonicity Property Lemmas 6.7 and 6.8, the Sweeping Over Property Lemma 6.9 and the Order Preserving Property Lemma 6.10. The proof of Lemma 6.10 also needs Lemma 6.5. Lemmas 6.7, 6.9, 6.10 and 6.11 will play active roles in §7 and §8 in the arguments of wave separations, concentrations and splitting, and in the eventual proof of Theorem 3.13.

We now establish the two local nonoscillatory properties.

Lemma 6.5 ( Local Nonoscillatory Property 1). With Assumption 6.3, if {x_{p}, …, x_{q}} is an M-stencil of u at some t_{0}, then there exists a δ > 0 such that at any t ∈ [t_{0}, t_{0} + δ), there is no N-stencil of u that is a subset of {x_{p}, …, x_{q}}.

Proof. Since u is continuous in t and {x_{p}, …, x_{q}} is an M-stencil of u at t_{0}, there exists a δ > 0 such that for t ∈ [t_{0}, t_{0} + δ),

max(u_{p−1}(t), u_{q+1}(t)) < min_{p≤j≤q} u_{j}(t).

If q ≤ p + 1, the lemma holds trivially. Otherwise, for any j with p < j < q, set

D_{j}(t) =^{def} min( max_{p≤l<j}(u_{l}(t) − u_{j}(t))_{+}, max_{j<r≤q}(u_{r}(t) − u_{j}(t))_{+})

and

D(t) =^{def} max_{p<j<q} D_{j}(t).

Here, (a)_{+} = a for a > 0, and (a)_{+} = 0 otherwise. Clearly, D(t) ≥ 0, and D(t) = 0 if and only if there is no N-stencil of u at t that is a subset of {x_{p}, …, x_{q}}.

The function D(t) is clearly continuous. Therefore, {t : D(t) > 0} ∩ [t_{0}, t_{0} + δ) is an open set which is a union of disjoint open intervals: ∪_{ν}I_{ν}. It suffices to show that D(t) is diminishing in I_{ν} for each ν. Fix an arbitrary t ∈ I_{ν}. There exist an i with p < i < q, an l with p ≤ l < i, and an r with i < r ≤ q such that D(t) = min(u_{l}(t) − u_{i}(t), u_{r}(t) − u_{i}(t)). Clearly, x_{l} and x_{r} each belongs to an M-stencil of u, and x_{i} belongs to an N-stencil of u at t. Hence, Assumption 6.4 implies

\frac{du_{l}(t)}{dt} ≤ 0, \frac{du_{r}(t)}{dt} ≤ 0, and \frac{du_{i}(t)}{dt} ≥ 0.

By Lemma 6.1, for any ε > 0, if t′ ∈ I_{ν} and 0 < t − t′ < h^{2}ε/2C_{2}, then

\frac{du_{l}(s)}{ds} ≤ \frac{ε}{2}, \frac{du_{r}(s)}{ds} ≤ \frac{ε}{2}, and \frac{du_{i}(s)}{ds} ≥ −\frac{ε}{2}

for all s ∈ [t′, t]. It follows that

u_{l}(t′) ≥ u_{l}(t) − \frac{ε}{2}(t − t′),
u_{r}(t′) ≥ u_{r}(t) − \frac{ε}{2}(t − t′),
u_{i}(t′) ≤ u_{i}(t) + \frac{ε}{2}(t − t′).

Hence,

D(t′) ≥ D_{i}(t′) ≥ min(u_{l}(t′) − u_{i}(t′), u_{r}(t′) − u_{i}(t′))
≥ min(u_{l}(t) − u_{i}(t), u_{r}(t) − u_{i}(t)) − ε(t − t′)
= D(t) − ε(t − t′).

This implies D(s′′) − D(s′) ≥ −ε(s′ − s′′), for any s′, s′′ ∈ I_{ν} with s′ > s′′. The arbitrariness of ε then yields D(s′′) − D(s′) ≥ 0. □

Lemma 6.6 (Local Nonoscillatory Property 2). With Assumption 6.4, if

u_{p−1}(t_{0}) > u_{p}(t_{0}) ≥ ⋯ ≥ u_{q}(t_{0}) > u_{q+1}(t_{0}),

then there exists a δ > 0 such that for t ∈ [t_{0}, t_{0} + δ)

u_{p−1}(t) > u_{p}(t) ≥ ⋯ ≥ u_{q}(t) > u_{q+1}(t). (6.2)

Proof. Since the numerical solution is continuous in t, there exists a δ > 0 such that

u_{p−1}(t) > max_{p≤i≤q} u_{i}(t) ≥ min_{p≤i≤q} u_{i}(t) > u_{q+1}(t)

for t ∈ [t_{0}, t_{0} + δ). Define

D(t) = max_{p≤l<q}( max_{l<r≤q}(u_{r}(t) − u_{l}(t))_{+}).

Clearly, D(t) ≥ 0, and D(t) = 0 if and only if (6.2) holds. It therefore suffices to show that D(t) diminishes in t ∈ [t_{0}, t_{0} + δ). We omit the rest of the proof, which is similar to that for Lemma 6.5. □

Lemma 6.7 (First Monotonicity Property). With Assumption 6.4, if M_{t_{1},t_{2}} is a ridge, then the corresponding V_{M}(t) is a decreasing function on [t_{1}, t_{2}].

Proof. Fix an arbitrary ε > 0. Let t_{1} ≤ t′ < t′′ ≤ t_{2}. By the “connectivity condition,” for any t ∈ [t′, t′′], there is a δ(t) ∈ (0, h^{2}ε/C_{2}) such that the interval O_{t} = (t − δ(t), t + δ(t)) satisfies

O_{t} ⊆ (t′, t′′) if t ∈ (t′, t′′), (6.3)

P_{M}(s) ⊆ P_{M}(t) for s ∈ O_{t}. (6.4)

By Assumption 6.4 and Lemma 6.1 we also have

\frac{du_{j}(s)}{ds} ≤ ε for s ∈ O_{t} and x_{j} ∈ P_{M}(t). (6.5)

Since

⋃_{t∈[t′,t′′]}(t − \frac{1}{2}δ(t), t + \frac{1}{2}δ(t)) ⊃ [t′, t′′],

there exists a finite partition of [t′, t′′]: t′ = τ_{0} < τ_{1} < ⋯ < τ_{n} = t′′ such that

⋃_{ν=0}^{n}(τ_{ν} − \frac{1}{2}δ(τ_{ν}), τ_{ν} + \frac{1}{2}δ(τ_{ν})) ⊃ [t′, t′′].

Notice that the condition (6.3) implies that the inclusion of (τ_{0} − \frac{1}{2}δ(τ_{0}), τ_{0} + \frac{1}{2}δ(τ_{0})) and (τ_{n} − \frac{1}{2}δ(τ_{n}), τ_{n} + \frac{1}{2}δ(τ_{n})) is necessary to form the covering. Obviously, we may assume that

\frac{δ(τ_{ν}) + δ(τ_{ν+1})}{2} > τ_{ν+1} − τ_{ν} for each ν = 0, 1, …, n − 1.

Hence, either δ(τ_{ν+1}) > τ_{ν+1} − τ_{ν} or δ(τ_{ν}) > τ_{ν+1} − τ_{ν}. In both cases, (6.4) and (6.5) imply

V_{M}(τ_{ν+1}) − V_{M}(τ_{ν}) ≤ ε(τ_{ν+1} − τ_{ν}),

which yields

V_{M}(t′′) − V_{M}(t′) ≤ ε(t′′ − t′).

It follows that

V_{M}(t′′) ≤ V_{M}(t′)

since ε is arbitrary. □

Lemma 6.8 (Second Monotonicity Property). With Assumption 6.4, if M_{t_{1},t_{2}} is a ridge of u with

P_{M}(t) = {x_{p(t)}, …, x_{q(t)}} for each t ∈ [t_{1}, t_{2}],

then

R(t) = inf_{q(t)<j<∞} u_{j}(t)

is an increasing function on [t_{1}, t_{2}].

Proof. For any ε > 0, let t_{1} ≤ t′ < t′′ ≤ t_{2}, t′′ − t′ < \frac{h^{2}ε}{2C_{2}} . Suppose \{j_{ν}\}_{ν=1}^{∞} satisfy j_{ν} > q(t′′) and

lim_{ν→∞} u_{j_{ν}}(t′′) = R(t′′).

Then Assumption 6.4 and the continuity of the numerical flux imply

lim_{ν→∞} inf \frac{du_{j_{ν}}(t′′)}{dt} ≥ 0,

which, by Lemma 6.1, implies

lim_{ν→∞} inf \frac{du_{j_{ν}}(t)}{dt} ≥ −\frac{ε}{2}

uniformly for t ∈ [t′, t′′]. Therefore,

R(t′) = inf_{q(t′)<j<∞} u_{j}(t′) ≤ lim_{ν→∞} inf u_{j_{ν}}(t′)
≤ lim_{ν→∞} u_{j_{ν}}(t′′) + ε(t′′ − t′)
= R(t′′) + ε(t′′ − t′).

Now, for any s′, s′′ ∈ [t_{1}, t_{2}] with s′ < s′′, we partition [s′, s′′] into a finite number of disjoint subintervals of lengths bounded by h^{2}ε/2C_{2}, we apply the above inequality to each of the subintervals, and we sum the results up. This yields R(s′) ≤ R(s′′) + ε(s′′ − s′). Therefore, R(s′) ≤ R(s′′) since ε is arbitrary. □

The following lemma implies that along its route of propagation, an extremum path of u sweeps over all the grid points in between.

Lemma 6.9 (Sweeping Over Property). With the Assumption 6.4, if M_{t_{1},t_{2}} is a ridge of u such that x_{p} = min[P_{M}(t_{1}) ⋃ P_{M}(t_{2})], (6.6)

and x_{q} = max[P_{M}(t_{1}) ⋃ P_{M}(t_{2})], (6.7) then

⋃_{t_{1}≤t≤t_{2}} P_{M}(t) ⊇ {x_{j} : p ≤ j ≤ q}. (6.8)

Proof. Assume j is an integer between p and q such that

x_{j} ∉ ⋃_{t_{1}≤t≤t_{2}} P_{M}(t).

Then (6.6) and (6.7) imply that both

Q_{l} = {t ∈ [t_{1}, t_{2}] : max P_{M}(t) < x_{j}}

and

Q_{r} = {t ∈ [t_{1}, t_{2}] : min P_{M}(t) > x_{j}}

are not empty. Clearly, Q_{l} ⋃ Q_{r} = [t_{1}, t_{2}] and Q_{l} ⋂ Q_{r} = ∅. These contradict the connectivity of the interval [t_{1}, t_{2}] since both Q_{l} and Q_{r} are open in [t_{1}, t_{2}] by the “connectivity” of M_{t_{1},t_{2}}. Therefore, (6.8) holds. □

The next lemma implies that the forward extremum path of u starting from an E-stencil at any time t_{0} is unique.

Lemma 6.10 (Order Preserving Property). Let E_{t_{1},t_{2}}^{(1)} and E_{t_{1},t_{2}}^{(2)} with t_{1} < t_{2} be two extremum paths of u. If

max P_{E^{(1)}}(t_{2}) < min P_{E^{(2)}}(t_{2}),

then E_{t_{1},t_{2}}^{(1)} < E_{t_{1},t_{2}}^{(2)}.

Proof. By the “connectivity condition,” the set {t ∈ [t_{1}, t_{2}] : max P_{E^{(1)}}(t) < min P_{E^{(2)}}(t)} is a nonempty open subset of [t_{1}, t_{2}]. If this subset is not [t_{1}, t_{2}] itself, then there is a t′ ∈ [t_{1}, t_{2}] such that max P_{E^{(1)}}(t) < min P_{E^{(2)}}(t) holds for all t ∈ (t′, t_{2}], and either P_{E^{(1)}}(t′) = P_{E^{(2)}}(t′) or max P_{E^{(2)}}(t′) < min P_{E^{(1)}}(t′). The former case contradicts Lemma 6.5, and the latter contradicts the “connectivity condition.” □

We are ready to present and prove our main result of this section.

Lemma 6.11 (Backward Traceability Property). With the Assumption 6.4, any M-stencil {x_{p}, …, x_{q}} at any T > 0 can be traced back to t = 0.

Proof. Let T be the set of t for which there exists an M_{t,T} with P_{M}(T) = {x_{p}, x_{p+1}, …, x_{q}}. We prove the lemma by showing that T is nonempty and is both open and closed in [0, T].

“Open”: Let t′ ∈ T . Then there exists an M_{t′,T} such that P_{M}(T) = {x_{p}, x_{p+1}, …, x_{q}}. As we have seen repeatedly, there exists a δ_{1} > 0 such that for t ∈ [t′ − δ_{1}, t′)

max(u_{p(t′)−1}(t), u_{q(t′)+1}(t)) < min_{p(t′)≤j≤q(t′)} u_{j}(t). (6.9)

Let N(t) be the number of the M-stencils {x_{p_{i}(t)}, …, x_{q_{i}(t)}} ⊂ P_{M}(t′) at the time t, i = 1, …, N(t). The function N(t) is defined on [t′ − δ_{1}, t′). The range of N(t) is a finite set of integers {n_{ν}}_{ν=1}^{m}. Let n_{1} > n_{2} > ⋯ > n_{m}. We claim that there exists a δ ∈ (0, δ_{1}] such that N(t) ≡ n_{m} for t ∈ [t′ − δ, t′). Indeed, the claim is trivially true for m = 1. In the case m > 1, consider the set {t ∈ [t′ − δ_{1}, t′) : N(t) > n_{m}}. Lemma 6.2 implies that this set is open in [t′ − δ_{1}, t′). If the claim were false, there would be a nonempty open interval (s_{1}, s_{2}) ⊂ [t′ − δ_{1}, t′) such that N(s_{1}) = n_{m} and N(t) > n_{m} for t ∈ (s_{1}, s_{2}). This would contradict Lemmas 6.5 and 6.6. Hence, the claim is true.

Now for any fixed t ∈ [t′ − δ, t′), let {P^{(i)}(t)}_{i=1}^{n_{m}} be the collection of M-stencils in order of increasing space coordinates. Fix any i between 1 and n_{m}. Then for any t ∈ (t′ − δ, t′), define M_{t,T} by letting M_{t′,T} ⊂ M_{t,T} and P_{M}(s) = P^{(i)}(s) for s ∈ [t, t′). To see that the M_{t,T} thus defined is a ridge of u, it suffices to verify the “connectivity condition”. Indeed, since N(t) ≡ n_{m} for t ∈ [t′ − δ, t′), Lemma 6.2 implies that for any fixed t ∈ (t′ − δ, t′), there exists a δ_{2} > 0 such that P^{(i)}(s) ⊆ P^{(i)}(t) for any i between 1 and n_{m}, provided that |s − t| < δ_{2}. This shows that T is open in [0, T].

“Closed”: Suppose that {τ_{μ}}_{μ=0}^{∞} is a decreasing sequence of real numbers such that τ_{0} = T and τ_{μ} → t′ ∈ [0, T) as μ → ∞. Suppose also that there exists a sequence of ridges {M_{τ_{μ},T}^{μ} } such that P_{M^{μ}}(T) = {x_{p}, x_{p+1}, …, x_{q}} and P_{M^{μ}}(t) = {x_{p^{μ}(t)}, …, x_{q^{μ}(t)}} when μ = 1, 2, 3, … and τ_{μ} ≤ t ≤ T.

We claim that x_{p^{μ}(t)} and x_{q^{μ}(t)} are uniformly bounded. Let us first show that there exists a number X_{max} such that for all μ, x_{q^{μ}(t)} < X_{max} when τ_{μ} ≤ t ≤ T.

Noticing that P_{M^{μ}}(T) is independent of μ, we set a =^{def} V_{M^{μ}}(T) and σ =^{def} [V_{M^{μ}}(T)−R_{M^{μ}}(T)]/3, where R_{M^{μ}}(t) = inf_{j≥q^{μ}(t)} u_{j}(t). By Lemmas 6.7 and 6.8, for all t ∈ [τ_{μ}, T],

V_{M^{μ}}(t) ≥ a and R_{M^{μ}}(t) ≤ a − 3σ. (6.10)

Suppose that l is a positive integer such that Δt =^{def} (T − t′)/l < σh/C_{1}, where C_{1} is the positive constant in Lemma 6.1. We show that for each k = 0, …, l − 1, there is a constant X_{max}^{k} such that for all t ∈ [T − (k + 1)Δt, T − kΔt] and t ≥ τ_{μ}, we have x_{q^{μ}(t)} < X_{max}^{k}. We apply induction to k. By (6.10), there is an integer j_{0} > q such that u_{j_{0}}(T) < a − 2σ. Hence, by Lemma 6.1, for all t ∈ [T − Δt, T] there holds u_{j_{0}}(t) < a − σ. Therefore, for all t ∈ [T − Δt, T] we have q^{μ}(t) < j_{0} by the First Monotonicity Property Lemma 6.7, the Sweeping Over Property Lemma 6.9, and the first inequality in (6.10). Hence, X_{max}^{0} =^{def} x_{j_{0}} has the desired property. Similarly, if X_{max}^{k−1} has the desired property, then there is a j_{k} > max_{μ} q^{μ}(T −kΔt) such that for all t ∈ [T −(k+1)Δt, T −kΔt] one has u_{j_{k}}(t) < a − σ. Therefore, X_{max}^{k} = x_{j_{k}} has the desired property. Now X_{max} = max_{k=0,...,l−1} X_{max}^{k} is an upper bound of x_{q^{μ}(t)}. Similarly, there exists a number X_{min} that is a lower bound of x_{p^{μ}(t)}. This proves the claim.

We show that there is a sequence of ridges {M_{τ_{μ},T} }_{μ=1}^{∞} such that P_{M}(T) = {x_{p}, x_{p+1}, …, x_{q}} and M_{τ_{μ_{1}},T} ⊂ M_{τ_{μ_{2}},T} if μ_{1} < μ_{2}. (6.11)

Because of (6.11), it is not necessary to use superscripts to distinguish different ridges in this sequence.

To see this, let us assume that {P_{i}^{μ}}_{i=1}^{m_{μ}} is the collection of M-stencils of u at τ_{μ} between X_{min} and X_{max}. Since x_{p^{μ}(t)} and x_{q^{μ}(t)} are uniformly bounded, m_{μ} is a bounded sequence. Inductively, we select an M-stencil P^{μ} = P_{i_{μ}}^{μ} at τ_{μ} for each natural number μ as follows: We are able to select a P^{1} = P_{i_{1}}^{1} such that it is the x-projections at τ_{1} of an infinite subsequence (SQ)_{1} of {M_{τ_{μ},T}^{μ} }_{μ=1}^{∞} because m_{1} is bounded. In general, if (SQ)_{μ} and P^{μ} have been selected, we are able to select a P^{μ+1} = P_{i_{μ+1}}^{μ+1} such that it is the x-projections at τ_{μ+1} of an infinite subsequence (SQ)_{μ+1} of (SQ)_{μ} because {m_{μ}}_{μ=1}^{∞} is a bounded sequence. Thus, P^{μ} is selected for every natural number μ. Now we define M_{τ_{μ},T} to be the unique ridge of u such that P_{M}(τ_{μ}) = P^{μ} ( uniqueness is guaranteed by Lemma 6.10 ). The relation (6.11) follows from the uniqueness.

Suppose that P_{M}(t) = {x_{p(t)}, …, x_{q(t)}} and that

p̃ = lim_{μ→∞} inf p(τ_{μ}), and q̃ = lim_{μ→∞} sup q(τ_{μ}).

We have p̃ ≤ q̃. Since p(τ_{μ}) and q(τ_{μ}) are uniformly bounded, q(τ_{μ}) ≤ q̃ and p(τ_{μ}) ≥ p̃ for sufficiently large μ. Moreover, Lemmas 5.6 and 5.9 and the continuity of u in t imply that

u_{p}(t′) = ⋯ = u_{q}(t′) = lim_{μ→∞} V (τ_{μ}).

Let p̂ and q̂ be the integers such that p̂ ≤ p̃ ≤ q̃ ≤ q̂ with

u_{p}(t′) = ⋯ = u_{q}(t′),

and

u_{_{p}−1}(t′) ≠ u_{p}(t′), u_{_{q}+1}(t′) ≠ u_{q}(t′).

To see that such a q̂ does exist, recall that we have indeed shown the existence of an x_{j_{l−1}} = X_{max}^{l−1} > q̃ such that u_{j_{l−1}}(t′) < a − σ. Similarly, p̂ exists. The collection {x_{p}, …, x_{q}} is an M-stencil of u at t′, because otherwise, by Lemmas 6.5 and 6.6, {x_{_{p}−1}, …, x_{_{q}+1}} would not contain any M-stencil at t = τ_{μ} for sufficiently large μ and the existence of the aforementioned M_{τ_{μ},T} would be violated. Set P_{M}(t′) = {x_{p}, …, x_{q}}. Then M_{t′,T} is well defined. This shows that T is closed in [0, T]. □

The extremum paths of u are closely related to the spatial variation of u.

As usual, the total spatial variation of a numerical solution u at t is defined by

T V_{u}(t) = ∑_{j=−∞}^{∞} |u_{j}(t) − u_{j−1}(t)|.

Under Assumption 6.4, if T V_{u}(0) is bounded, then T V_{u}(t) ≤ T V_{u}(0) and both

V^{L} = lim_{j→−∞} u_{j}(t) and V^{R} = lim_{j→∞} u_{j}(t)

exist and are independent of t. If the x-projections {P_{E^{m}}(t)}_{m=m′}^{m′′} of a collection of extremum paths, E_{0,t}^{m′} < ⋯ < E_{0,t}^{m′′}, are all the m′′ − m′ + 1 distinct E-stencils of u at t with max P_{E^{−1}}(t) < 0 ≤ max P_{E^{0}}(t), then clearly

T V_{u}(t) = |V^{L} − V_{E^{m′}} (t)| + ∑_{m=m′+1}^{m′′} |V_{E^{m}}(t) − V_{E^{m−1}}(t)| + |V^{R} − V_{E^{m′′}} (t)|. (6.12)

In the case m′ and/or m′′ is infinity, the above formula still holds if the corresponding bound(s) of the summations is (are) replaced by −∞ and/or ∞ , and if |V^{L} − V_{M^{m′}} (t)| and/or |V_{R} − V_{E^{m′′}} (t)| vanish(es) accordingly.

Suppose 0 ≤ t < t′. One sees easily from the formula (6.12) that the variation decay

DT V_{u}(t, t′) =^{def} T V_{u}(t) − T V_{u}(t′)

is twice the sum of the decreases (increases) of the values of u along all ridges (troughs), including the ones that vanish, when t increases from t′ to t. This observation motivates the following simple yet useful result.

Lemma 6.12. Suppose the numerical solution u of a scheme (1.2)–(1.4) satisfies Assumption 6.4. Suppose also that E_{t,t′}^{1} ≤ E_{t,t′}^{2} are two extremum paths of u such that either P_{E^{1}}(t′) and P_{E^{2}}(t′) are identical or they are two successive E-stencils of u at t′. Let

(6.13) u^{M} = max_{min P_{E^{1}}(t′)≤x≤max P_{E^{2}}(t′)} u(x, t′) and u^{N} = min_{min P_{E^{1}}(t′)≤x≤max P_{E^{2}}(t′)} u(x, t′).

(i) If min P_{E^{1}}(t) ≤ x_{j} ≤ max P_{E^{2}}(t), then

u^{N} − DT V_{u}(t, t′)/2 ≤ u_{j}(t) ≤ u^{M} + DT V_{u}(t, t′)/2.

(ii) If min P_{E^{1}}(t) ≤ x_{p} < x_{q} ≤ max P_{E^{2}}(t), and u_{q}(t) − u_{p}(t) has the opposite sign of V_{E^{2}}(t) − V_{E^{1}}(t), then

|u_{q}(t) − u_{p}(t)| ≤ DT V_{u}(t, t′)/2.

Proof. Without loss of generality, assume that E_{t,t′}^{1} and E_{t,t′}^{2} are a trough and a ridge, respectively. It follows that u^{M} = V_{E^{2}}(t′) and u^{N} = V_{E^{1}}(t′). Hence, using Lemma 6.7, we have

DT V_{u}(t, t′) ≥ 2[(V_{E^{2}}(t) − V_{E^{2}}(t′)) + (V_{E^{1}}(t′) − V_{E^{1}}(t)) + (u_{j}(t) − V_{E^{2}}(t))]
≥ 2(u_{j}(t) − V_{E^{2}}(t′)) = 2(u_{j}(t) − u^{M}).

This proves the second part of the desired inequality in (i). The first part can be similarly shown. Next,

DT V_{u}(t, t′) ≥ ∑_{j=min P_{E^{1}}(t)}^{max P_{E^{2}}(t)−1} |u_{j+1}(t) − u_{j}(t)| − ∑_{j=min P_{E^{1}}(t′)}^{max P_{E^{2}}(t′)−1} |u_{j+1}(t′) − u_{j}(t′)|
= ∑_{j=min P_{E^{1}}(t)}^{max P_{E^{2}}(t)−1} |u_{j+1}(t) − u_{j}(t)| − (V_{E^{2}}(t′) − V_{E^{1}}(t′))
≥ ∑_{j=min P_{E^{1}}(t)}^{max P_{E^{2}}(t)−1} |u_{j+1}(t) − u_{j}(t)| − (V_{E^{2}}(t) − V_{E^{1}}(t))
≥ |V_{E^{2}}(t) − u_{q}(t)| + |u_{q}(t) − u_{p}(t)| + |u_{p}(t) − V_{E^{1}}(t)| − (V_{E^{2}}(t) − V_{E^{1}}(t))
≥ V_{E^{2}}(t) − u_{q}(t) + u_{p}(t) − u_{q}(t) + u_{p}(t) − V_{E^{1}}(t) − (V_{E^{2}}(t) − V_{E^{1}}(t))
= 2(u_{p}(t) − u_{q}(t)).

This proves (ii). □

II. The approximate extremum paths. Given a path E_{t_{1},t_{2}}, we would like, ideally, to have a function x_{E}(t): [t_{1}, t_{2}] → R that satisfies the following conditions:

(1) There is a finite partition of [t_{1}, t_{2}]

t_{1} = τ_{0} < τ_{1} < ⋯ < τ_{n} = t_{2}

such that x_{E}(t) is a constant on each subinterval (τ_{ν−1}, τ_{ν}) for 1 ≤ ν ≤ n.

(2) x_{E}(t) ∈ P_{E}(t) for t ∈ [t_{1}, t_{2}].

It is not clear if such a function x_{E}(t) exists. However, we do know that there exist piecewise constant functions of t that represent E_{t_{1},t_{2}} sufficiently well. Without loss of generality, we discuss spatial maxima only.

Lemma 6.13. For each ridge M_{t_{1},t_{2}} of a numerical solution u generated by a scheme (1.2)- (1.4) satisfying Assumption 6.4, and for any ε > 0, there exists a piecewise constant function x_{M}^{ε}(t) : [t_{1}, t_{2}] → R and a finite partition of [t_{1}, t_{2}] : t_{1} = τ_{0} < τ_{1} < ⋯ < τ_{n} = t_{2} such that x_{M}(t) ≡ c_{ν} and c_{ν} ∈ P_{M}(τ_{ν−1}) ⋂ P_{M}(τ_{ν}) (6.14)

on each subinterval (τ_{ν−1}, τ_{ν}) for 1 ≤ ν ≤ n. Furthermore, at any t ∈ [t_{1}, t_{2}], for any x_{i} between ( and including ) x_{M}^{ε}(t) and P_{M}(t), we have

|V_{M}(t) − u_{i}(t)| < ε. (6.15)

Finally, for V_{M}^{ε}(t) =^{def} u(x_{M}^{ε}(t), t),

T V_{t_{1}≤t≤t_{2}}(V_{M}^{ε}(t)) < V_{M}(t_{1}) − V_{M}(t_{2}) + ε/2. (6.16)

Proof. We repeat the construction of the finite covering in the proof of Lemma 6.7 with the following modifications: First we replace [t′, t′′] by [t_{1}, t_{2}]. Second, for each t ∈ [t_{1}, t_{2}] we choose the positive δ(t) so small that in addition to (6.3) and (6.4), the following inequalities also hold for s ∈ O_{t} and x_{j} ∈ P_{M}(t):

|u_{j}(s) − u_{j}(t)| < \frac{ε}{2} (6.17)

and

\frac{du_{j}(s)}{ds} < \frac{ε}{4(t_{2} − t_{1})}, (6.18)

where (6.18) can be achieved because of Assumption 6.4 and Lemma 6.1.

With the finite covering, for each ν = 1, …, n, if δ(τ_{ν}) > τ_{ν} − τ_{ν−1}, we choose c_{ν} to be any number in P_{M}(τ_{ν−1}), otherwise we choose c_{ν} to be any number in P_{M}(τ_{ν}). Set

x_{M}^{ε}(t) ≡ c_{ν} for τ_{ν−1} < t < τ_{ν}. (6.19)

Now (6.14) follows from the “connectivity” condition of M_{t_{1},t_{2}}, and (6.15) from (6.17). To show that (6.16) holds, notice that

I = T V_{t_{1}≤t≤t_{2}}(V_{M}^{ε}(t)) = ∑_{ν=1}^{n} ∫_{τ_{ν−1}}^{τ_{ν}} |\frac{dV_{M}^{ε}(t)}{dt}|dt.

Suppose x_{j_{ν}} = c_{ν}; then

I = ∑_{ν=1}^{n} ∫_{τ_{ν−1}}^{τ_{ν}} |\frac{du_{j_{ν}}(t)}{dt}|dt = ∑_{ν=1}^{n} ∫_{τ_{ν−1}}^{τ_{ν}} (−\frac{du_{j_{ν}}(t)}{dt} + 2(\frac{du_{j_{ν}}(t)}{dt})_{+}) dt
≤ V_{M}(t_{1}) − V_{M}(t_{2}) + \frac{2ε}{4(t_{2} − t_{1})} ∑_{ν=1}^{n} ∫_{τ_{ν−1}}^{τ_{ν}} dt = V_{M}(t_{1}) − V_{M}(t_{2}) + ε/2.

This completes the proof of the lemma. □

We call the function x_{M}^{ε}(t) an ε-ridge to M_{t_{1},t_{2}}. Similarly, we have the notion ε-troughs. Both ε-ridges and ε-troughs are called ε-E paths.

We have the following result concerning the notions of ε-E paths of this section, the ε-paths in the sense of Definition 3.5, and the sets Ψ̂_{w_{−},w_{+},B} introduced in §3. Recall that {ε_{k}} is a sequence of positive numbers such that ε_{k} → 0 as k → ∞.

Lemma 6.14. Suppose that all the sequences of a set Ψ̂_{w_{−},w_{+},B} consist of numerical solutions generated by the same scheme (1.2)-(1.4) satisfying Assumption 6.4, and that {u^{k}} ∈ Ψ̂_{w_{−},w_{+},B}. Let k by a positive integer. If x_{E}^{ε_{k}}(t) is an ε_{k}-E path of u^{k}, then it is also an ε_{k}-path of the first type with respect to u^{k}.

Proof. The conditions (i) and (ii) in Definition 3.5 are the same as the relation (6.14) in Lemma 6.13 where ε-E paths are defined. The relation (6.15) verifies the condition (iii) in Definition 3.5.

Finally, suppose x_{E}^{ε_{k}}(t) is an approximate path to the exact one E_{0,1}^{k}. By Lemma 6.12, the condition (iii) in the definition of Ψ̂_{w_{−},w_{+},B} implies that |V_{E^{k}}(0) − V_{E^{k}}(1)| < ε_{k}/2. Combining this inequality and (6.16), one verifies the condition (iv) in Definition 3.5. □

We end this section by extending Lemma 6.12 to ε-E paths.

Lemma 6.15. Suppose that, in addition to the conditions and the notations of Lemma 6.12, x_{I(t)} and x_{J(t)} are ε-E paths to E_{t,t′}^{1} and E_{t,t′}^{2} respectively, such that x_{I(t′)} ∈ P_{E^{1}}(t′) and x_{J(t′)} ∈ P_{E^{2}}(t′).

(i) If x_{I(t)} ≤ x_{j} ≤ x_{J(t)}, then

u^{N} − DT V_{u}(t, t′)/2 − ε ≤ u_{j}(t) ≤ u^{M} + DT V_{u}(t, t′)/2 + ε.

(ii) If x_{I(t)} ≤ x_{p} < x_{q} ≤ x_{J(t)}, and u_{q}(t) − u_{p}(t) has the opposite sign of V_{E^{2}}(t) − V_{E^{1}}(t), then

|u_{q}(t) − u_{p}(t)| ≤ DT V_{u}(t, t′)/2 + 2ε.

Proof. The inequalities follow from Lemma 6.12 and the relation (6.17) immediately. □ Remark. Lemmas 6.12 and 6.15 also hold when u(x, t′) is monotone between −∞ and

max P_{E^{2}}(t′), or when u(x, t′) is monotone between min P_{E^{1}}(t) and ∞. In the former case, min P_{E^{1}}(t) is replaced by −∞ and V_{E^{1}}(t) is replaced by V^{L}; in the latter case, max P_{E^{2}}(t) is replaced by ∞ and V_{E^{2}}(t) is replaced by V_{R}. The proof is similar to that in the standard case and is omitted.

7. WAVE SEPARATIION, CONCENTRATIONS AND SPLITTINGS By Theorem 3.2, to prove Theorem 3.13, it suffices to show that if Ψ̂_{w_{−},w_{+},B} ≠ ∅, and if its

limit W is a traveling expansion shock, then it contains a sequence that harbors an ATES. In order to extract the ATES, we screen the sequence of Ψ̂_{w_{−},w_{+},B} with the waves in the following domains:

Ω =^{def} {(x, t) : |x − st| ≤ 1, 0 ≤ t ≤ 1},

Ω_{δ}^{c} =^{def} {(x, t) : |x − st| < δ, 0 ≤ t ≤ 1},

Ω_{δ}^{−} =^{def} {(x, t) : −1 ≤ x − st ≤ −δ, 0 ≤ t ≤ 1},

Ω_{δ}^{+} =^{def} {(x, t) : δ ≤ x − st ≤ 1, 0 ≤ t ≤ 1},

where x = st is the path of the discontinuity of W, and δ is an arbitrary constant in (0, 1). We first collect a few facts concerning similarity transforms and the set Ψ̂_{w_{−},w_{+},B}. We require that the mapping T_{x′,t′}^{γ} preserve the indices of the schemes. Namely, if u = T_{x′,t′}^{γ}ũ,

then u_{j}(t) = ũ_{j}(t′ + γt), i.e., ũ_{j}(t) = u_{j}((t − t′)/γ).

Lemma 7.1. Suppose that {x̃^{k}(t), ỹ^{k}(t)}_{k=1}^{∞} is an ATW of {ũ^{k}}_{k=1}^{∞} ∈ Ψ̂_{w_{−},w_{+},B}, with the limit path x = αt + β and the two states L and R. Let γ be a constant in (0, 1), t′ and x′ be two constants such that 0 ≤ t′ ≤ 1 − γ and that x′ = st′. For each k, let z̃^{k}(t) be an ε_{k}-E path with respect to ũ^{k} from t′ to t^{k} where t′ + γ ≤ t^{k} ≤ 1. Suppose also that x̃^{k}(t) < z̃^{k}(t) < ỹ^{k}(t) when t′ ≤ t ≤ t^{k}. We then have:

(i) T_{x′,t′}^{γ}Ψ̂_{w_{−},w_{+},B} ⊂ Ψ̂_{w_{−},w_{+},B}.

(ii) {x^{k}(t), y^{k}(t)}_{k=1}^{∞} is an ATW of {u^{k}}_{k=1}^{∞} with the limit path x = αt + β′ and the two states L and R. Here, u^{k} = T_{x′,t′}^{γ}ũ^{k}, x^{k}(t) = [x̃^{k}(t′ + γt) − x′]/γ, y^{k}(t) = [ỹ^{k}(t′ + γt) − x′]/γ, and β′ = (αt′ + β − x′)/γ.

(iii) If lim_{k→∞} ũ^{k}(z̃^{k}(t^{k}), t^{k}) = C̃ exists, and C̃ ≠ L, then {x̃^{k}(t), z̃^{k}(t)}_{k=1}^{∞} is also an ATW of {u^{k}}_{k=1}^{∞} with the limit path x = αt+β′ and the two states L and C̃, where z^{k}(t) = [z̃^{k}(t′+γt)−x′]/γ.

Proof. Notice that x^{k}(t), y^{k}(t) and z^{k}(t) are the S_{x′,t′}^{γ} image of x̃^{k}(t), ỹ^{k}(t) and z̃^{k}(t), respectively, and the line x = αt + β′ is the S_{x′,t′}^{γ} image of the line x = αt + β. Since a scaling and a displacement of the independent variables are the only effects of the mapping T_{x′,t′}^{γ} on the the numerical solutions, (i) and (ii) are trivially true. To verify (iii), it suffices to notice that by Lemma 6.14, z^{k}(t) is an ε_{k}-path of the first type, which together with lim_{k→∞} ũ^{k}(z̃^{k}(t^{k}), t^{k}) = C̃ imply u^{k}(z^{k}(t), t) → C̃ uniformly for 0 ≤ t ≤ 1. □

We now state the first main result of this section.

Lemma 7.2 (Wave Separation and Concentration). If Ψ̂_{w_{−},w_{+},B} ≠ ∅, then it contains a sequence {u^{k}} such that

|u^{k}(x, t) − W (x, t)| < ε_{k} for (x, t) ∈ Ω_{ε_{k}}^{−} ⋃ Ω_{ε_{k}}^{+}.

See the Appendix for a quite involved proof of the lemma.

Letting Ψ_{w_{−},w_{+},B} be the subset of Ψ̂_{w_{−},w_{+},B} that consists of all the sequences satisfying the conclusion of Lemma 7.2, we can restate the lemma as: If Ψ̂_{w_{−},w_{+},B} ≠ ∅, then Ψ_{w_{−},w_{+},B} ≠ ∅.

It makes sense to call Lemma 7.2 wave separation and concentration because if {x^{k}(t), y^{k}(t)} is a ATW of {u^{k}} ∈ Ψ_{w_{−},w_{+},B} with the limit path x = αt + β, then it is either separated from x = st in the sense that |αt + β − st| ≥ 1 for 0 ≤ t ≤ 1, or it is concentrated on x = st in the sense that αt + β = st for 0 ≤ t ≤ 1.

Next, we use Lemma 6.11 to split the concentrated ATWs backwardly into ATDs and other insignificant waves. Assumption 6.4 is adequate for most arguments. However, we do need Assumption 3.3 to establish the essential monotonicity property of the waves.

Here is the second main result of this section.

Lemma 7.3. Suppose that the numerical scheme satisfies Assumption 3.3. Then for any ρ > 0, if Ψ_{w_{−},w_{+},B} is not empty, it contains a sequence {u^{k}(x, t)} that has Ñ(ρ) ATWs

{x_{I_{i}^{k}(t)}^{k}, x_{J_{i}^{k}(t)}^{k}}_{k=1}^{∞}, i = 1, …, Ñ(ρ)

with a common limit path x = st, where Ñ(ρ) = O(1/ρ). Moreover:

(i) For i = 1, …, Ñ(ρ), if L̃_{i} and R̃_{i} are the two states of the ith ATW, then

L̃_{i}, R̃_{i} ∈ {w : f(w) = f[w; w_{−}, w_{+}]}.

(ii) If st − 1 ≤ x_{j}^{k} < x_{j+1}^{k} ≤ x_{I_{1}^{k}(t)}^{k} or x_{J_{_{N}(ρ)}^{k}(t)}^{k} ≤ x_{j}^{k} < x_{j+1}^{k} ≤ st + 1, and 0 ≤ t ≤ 1, then

|u_{j+1}^{k}(t) − u_{j}^{k}(t)| ≤ ρ + 2ε_{k}.

(iii) If J_{i−1}^{k}(t) ≤ j < j + 1 ≤ I_{i}^{k}(t), and 0 ≤ t ≤ 1, then |u_{j+1}^{k}(t) − u_{j}^{k}(t)| ≤ ρ + ε_{k}.

Furthermore, all the Ñ(ρ) ATWs are ATDs.

Proof. During the proof we may repeatedly select subsequences and construct new sequences of Ψ_{w_{−},w_{+},B}. To avoid complicated notation, the sequences will be denoted by {u^{k}} unless otherwise specified.

We start at t = 1. For each k, a complete region of monotonicity (CRM) of u^{k} at t = 1, denoted by M̃^{k}, is a set of consecutive grid points M̃^{k} = {x_{p^{k}}^{k}, …, x_{q^{k}}^{k}} such that

(1) M̃^{k} ⊂ [s − 1, s + 1].

(2) u_{j}^{k}(1) is monotone with respect to j when p^{k} ≤ j ≤ q^{k}.

(3) If either x_{p^{k}−1}^{k} or x_{q^{k}+1}^{k} is added to M̃^{k}, (1) or (2) no longer holds.

Set L̃^{k} = u_{p^{k}}^{k}(1), R̃^{k} = u_{q^{k}}^{k}(1) and G^{k} = R̃^{k} − L̃^{k}. We use subscripts to distinguish several CRMs and related notions. Fix an arbitrary constant ρ > 0. We assume that ε_{k} < ρ/16 by ignoring terms with small k, and we only consider those CRMs with |G^{k}| > ρ − ε_{k}. Since the total spatial variation is uniformly bounded by B, the total number Ñ^{k} of these CRMs is uniformly bounded in k. Therefore, by using a subsequence of {u^{k}}, if necessary, we assume that the number Ñ^{k} ≡ Ñ = Ñ(ρ) is independent of k. We arrange the Ñ CRMs in order of ascending space coordinates: M̃_{i}^{k}, i = 1, …, Ñ. By using a subsequence again, if necessary, we assume that

L̃_{i} =^{def} lim_{k→∞} L̃_{i}^{k} and R̃_{i} =^{def} lim_{k→∞} R̃_{i}^{k}

(7.1)

exist. Clearly, |R̃_{i} − L̃_{i}| ≥ ρ. By further screening the sequences of the numerical solutions, we construct an ATD from t = 0 to t = 1 for each sequence {M̃_{i}^{k}}_{k=1}^{∞} of CRMs. Hence, we need a sequence of pairs of ε_{k}-paths for each of them. Usually, ε_{k}-E paths play this role. However, we sometimes have to use the following ε_{k}-paths of the second type for the leftmost or the rightmost ATD. Suppose P^{k}(t) and Q^{k}(t) are the two integer-valued functions satisfying

x_{P^{k}(t)}^{k} < st − 2ε_{k} ≤ x_{P^{k}(t)+1}^{k} < x_{Q^{k}(t)−1}^{k} ≤ st + 2ε_{k} < x_{Q^{k}(t)}^{k}.

By using a subsequence, if necessary, we assume that ph_{k} < ε_{k}, where p is the size of the stencil of the scheme (see §1). It is easy to check that x_{P^{k}(t)}^{k} and x_{Q^{k}(t)}^{k} are ε_{k}-paths of the second type.

Now we are ready to define two ε_{k}-paths x_{I_{i}^{k}(t)}^{k} and x_{J_{i}^{k}(t)}^{k} for each M̃_{i}^{k}. If

|u_{j}^{k}(1) − w_{−}| < 2ε_{k} for s − 1 ≤ x_{j}^{k} ≤ x_{p_{1}^{k}}^{k}, (7.2)

we let x_{I_{1}^{k}(t)}^{k} = x_{P^{k}(t)}^{k}; if

|u_{j}^{k}(1) − w_{+}| < 2ε_{k} for s + 1 ≥ x_{j}^{k} ≥ x_{qk ; _{N}}^{k}, (7.3)

we let x_{Jk ; _{N}(t)}^{k} = x_{Q^{k}(t)}^{k}. In all the other cases, x_{p_{i}^{k}}^{k} and x_{q_{i}^{k}}^{k} belong to some E-stencils of u^{k} at t = 1, and using Lemma 6.10 and Lemma 6.14, we can trace them back by extremum paths E_{0,1}^{k,i,L} and E_{0,1}^{k,i,R}, respectively, or by their corresponding ε_{k}-E paths x_{I_{i}^{k}(t)}^{k} and x_{J_{i}^{k}(t)}^{k}, respectively.

Using these paths, we define

Ω_{i}^{(k)} =^{def} {(x, t) : x_{I_{i}^{k}(t)−1/2}^{k} ≤ x ≤ x_{J_{i}^{k}(t)−1/2}^{k}, 0 ≤ t ≤ 1},

Ω^{(k)} =^{def} ⋃_{i=1}^{_{N}(ρ)} Ω_{i}^{(k)}.

(7.4)

By Lemma 6.14, for every i between 1 and Ñ, {x_{I_{i}^{k}(t)}^{k}, x_{J_{i}^{k}(t)}^{k}} is a pair of ε_{k}-paths in the sense of Definitions 3.5 and 3.6. It is straightforward to verify that they satisfy the properties (i), (ii) and (iii) in Definition 3.8. Hence, they are ATWs with a common limit path x = st. Moreover, if J_{i−1}^{k}(t) ≤ j < j + 1 ≤ I_{i}^{k}, and |u_{j+1}^{k}(t) − u_{j}^{k}(t)| > ρ + ε_{k}, then (x_{j}^{k}, t) and (x_{j+1}^{k}, t) are between two extremum paths such that their x-projections at t = 1 either are identical, or are the two E-stencils of a CRM with a jump bounded by ρ − ε_{k} because the CRM does not belong to the collection of Ñ CRMs. This violates Lemma 6.12, and hence |u_{j+1}^{k}(t) − u_{j}^{k}(t)| ≤ ρ + ε_{k} when J_{i−1}^{k}(t) ≤ j < j + 1 ≤ I_{i}^{k}. This is Property (iii) in Lemma 7.3. Property (ii) can be shown similarly. It remains to show that there is a sequence in Ψ_{w_{−},w_{+},B} such that not only the preceding properties hold, but also all the Ñ(ρ) ATWs are essentially monotone, i.e., they are ATDs. We achieve this goal in the following three steps.

Step 1. We show that for any t ∈ [0, 1], and for sufficiently large k, if the integers p and q satisfy I_{i}^{k}(t) ≤ p < q ≤ J_{i}^{k}(t) where the positive integer i ≤ Ñ(ρ), and if u_{q}^{k}(t) − u_{p}^{k}(t) and R̃_{i} − L̃_{i} have opposite signs, then |u_{q}^{k}(t) − u_{p}^{k}(t)| < 6ε_{k}.

By Lemma 6.15, the only nontrivial cases are the ones when at least one of x_{I_{i}^{k}(t)}^{k} and x_{J_{i}^{k}(t)}^{k} is an ε_{k}-path of the second type. Hence, we focus on the case that i = 1, that x_{I_{1}^{k}(t)}^{k} is an ε_{k}-path of the second type, and that x_{J_{1}^{k}(t)}^{k} is an ε_{k}-E path. All other cases can be dealt with similarly.

Without loss of generality, assume that R̃_{i} > L̃_{i}. We argue by contradiction. Hence, we assume that u_{p}^{k}(t) − u_{q}^{k}(t) ≥ 6ε_{k}. Then either u_{p}^{k}(t) ≥ w_{−} + 3ε_{k}, or u_{p}^{k}(t) < w_{−} − 3ε_{k}. Consider the case u_{p}^{k}(t) ≥ w_{−} + 3ε_{k}. Let E_{0,1}^{k,A} and E_{0,1}^{k,B} be two extremum paths with max P_{E^{k,A}}(t) < x_{p}^{k}, and max P_{E^{k,B}}(t) ≥ x_{p}^{k} such that the two E-stencils P_{E^{k,A}}(1) and P_{E^{k,B}}(1) are either identical or successive. Lemma 6.12 implies that either E_{0,1}^{k,A} is a ridge with V_{E^{k,A}}(1) > w_{−}+2ε_{k}, or E_{0,1}^{k,B} is. The former implies that either P_{E^{k,A}}(1) = P_{E^{k,1,R}}(1), which by Lemma 6.12 leads to u_{p}^{k}(t)−u_{q}^{k}(t) < 2ε_{k}, a contradiction to the assumption, or E_{0,1}^{k,A} ∩ Ω = ∅, which implies that if (x′, t) ∈ E_{0,1}^{k,A} and (x′′, t) ∈ Ω_{ε_{k}}^{−}, then x′ < x′′ < x_{p}^{k}, u^{k}(x′, t) − u^{k}(x′′, t) > ε_{k}, and u_{p}^{k}(t) − u^{k}(x′′, t) > 2ε_{k}. The last three inequalities violate Lemma 6.12. The latter implies that P_{E^{k,B}}(1) = P_{E^{k,1,R}}(1), and that both E_{0,1}^{k,B} and E_{0,1}^{k,1,R} are ridges. Hence, Lemma 6.12 implies that u_{p}^{k}(t) − u_{q}^{k}(t) < 2ε_{k}, which leads to a contradiction as mentioned earlier. Similarly, the case u_{p}^{k}(t) < w_{−}−3ε_{k} also leads to contradictions. We let the readers check the details.

Step 2. It is in this step that Assumption 3.3 is needed. First, let us fix an i between 1 and Ñ(ρ), and consider the sequence of pairs {x_{P^{k}(t)}^{k}, x_{I_{i}^{k}(t)}^{k}}. Clearly, it is an ATW with the limit path x = st if w_{−} ≠ L̃_{i}. Since the scheme satisfies Assumption 3.3, and since s(w_{+} − w_{−}) = f(w_{+}) − f(w_{−}), an application of Corollary 3.11 to the ATW yields that L̃_{i} ∈ {w : f(w) = f[w; w_{−}, w_{+}]} if w_{−} ≠ L̃_{i}. However, since w_{−} ∈ {w : f(w) = f[w; w_{−}, w_{+}]}, we have that L̃_{i} ∈ {w : f(w) = f[w; w_{−}, w_{+}]} always holds. Similarly, R̃_{i} ∈ {w : f(w) = f[w; w_{−}, w_{+}]}. Consider {û^{k}} = T_{s/2,1/2}^{1/2}{u^{k}}. By Lemma 7.1 and the convention made at the beginning of this section, we have

(a) {û^{k}} ∈ Ψ̃_{w_{−},w_{+},B}.

(b) For each i = 1, …, Ñ(ρ), the sequence of pairs

{x̂_{Î_{i}^{k}(t)}, x̂_{Ĵ_{i}^{k}(t)}} = {x̂_{I_{i}^{k}((1+t)/2)}, x̂_{J_{i}^{k}((1+t)/2)}} = {2x_{I_{i}^{k}((1+t)/2)} − s, 2x_{J_{i}^{k}((1+t)/2)} − s} (7.5)

is an ATW of {û^{k}} with the limit path x = st and the two states L̃_{i} and R̃_{i}.

Because the effects of the mapping T_{1/2,s/2}^{1/2} are no more than a scaling and a displacement, the following properties also hold:

(c) If |û^{k}(x, t) − W (x, t)| ≥ ε_{k}, then (x, t) ∈ Ω_{2ε_{k}}^{c}.

(d) All the properties (i)–(iii) in Lemma 7.3, with the ATWs replaced by their S_{s/2,1/2}^{1/2} images.

(e) The values of {û^{k}} satisfy the result of the step 1, i.e., |û_{q}^{k}(t) − û_{p}^{k}(t)| < 6ε_{k} when Î_{i}^{k}(t) ≤ p < q ≤ Ĵ_{i}^{k}(t) and (û_{q}^{k}(t) − û_{p}^{k}(t))(R̃_{i} − L̃_{i}) < 0.

We now prove one more property of {û^{k}}:

(f) Let {j^{k}} be a sequence of integers, and {t̂^{k}} be a sequence of real numbers in [0, 1]. Suppose that x̂_{Î_{i}^{k}(t̂^{k})}^{k} ≤ x̂_{j^{k}}^{k} < x̂_{j^{k}+1}^{k} ≤ x̂_{Ĵ_{i}^{k}(t̂^{k})}^{k} and that u_{j^{k}+1}^{k}(t̂^{k}) − u_{j^{k}}^{k}(t̂^{k}) and R̃_{i}^{k} − L̃_{i}^{k} have opposite signs. If lim_{k→∞} u_{j^{k}}^{k}(t̂^{k}) = A, then A ∈ {w : f(w) = f[w; w_{−}, w_{+}]}.

In fact, by letting t^{k} = (1 + t̂^{k}), noticing that {u^{k}|_{t≥1/2}} = (T_{s/2,1/2}^{1/2})^{−1}{û^{k}}, and using (7.5), we get

{t^{k}} ⊂ [1/2, 1], x_{I_{i}^{k}(t^{k})}^{k} ≤ x_{j^{k}}^{k} < x_{j^{k}+1}^{k} ≤ x_{J_{i}^{k}(t^{k})}^{k}, and (u_{j^{k}+1}^{k}(t^{k}) − u_{j^{k}}^{k}(t^{k}))(R̃_{i} − L̃_{i}) < 0.

Assume that A does not belong to {w : f(w) = f[w; w_{−}, w_{+}]}. Then by the result of step 1, for sufficiently large k, there is an E-stencil of u^{k} at t^{k} which can be traced back by an extremum path E_{0,t^{k}}^{k} or by an ε_{k}-E path z̃^{k}(t), such that the following properties hold:

z̃^{k}(t^{k}) ∈ P_{E^{k}}(t^{k}), |u^{k}(z̃^{k}(t^{k}), t^{k}) − u_{j^{k}}^{k}(t^{k})| < 6ε_{k}, and x_{I^{k}(t)}^{k} < z̃^{k}(t) < x_{J^{k}(t)}^{k}.

Denoting x_{I^{k}(t)}^{k} and x_{J^{k}(t)}^{k} by x̃^{k}(t) and ỹ^{k}(t), respectively, and applying Lemma 7.1, one sees that if x^{k}(t) = 2x̃^{k}(t/2) and z^{k}(t) = 2z̃^{k}(t/2), then the pair {x^{k}(t), z^{k}(t)} is an ATW of T_{0,0}^{1/2}{u^{k}} ∈ Ψ_{w_{−},w_{+},B} with the limit path x = st and the two states L̃_{i} and A. Hence, by Corollary 3.11, A ∈ {w : f(w) = f[w; w_{−}, w_{+}]}. This contradiction proves the property (f).

Step 3. Now we construct the desired sequence, still denoted by {u^{k}}, in Ψ_{w_{−},w_{+},B} as follows. By (f), given any η > 0, there is a K(η) such that if t ∈ [0, 1], and i = 1, …, Ñ(ρ), and if j is

an integer such that I_{i}^{k}(t) ≤ j < j + 1 ≤ J_{i}^{k}(t) and that (û_{j+1}^{k}(t) − û_{j}^{k}(t))(R̃_{i} − L̃_{i}) < 0, then

û_{j}^{k}(t), û_{j+1}^{k}(t) ∈ N_{η} ({w : f(w) = f[w; w_{−}, w_{+}]})

provided k > K(η). Let {ε_{m_{k}}} be a subsequence of {ε_{k}} such that ε_{m} < 6ε_{k} when m ≥ m_{k}. Let n_{k} = max(K_{ε_{k}}, m_{k}). Finally, define u^{k} = û^{n_{k}}. From the properties (a) to (f), it is evident that the sequence {u^{k}} has all the properties stated in Lemma 7.3. □

8. PROOF OF THEOREM 3.13 Again we argue by contradiction. Assume that a self-similar scheme of the form (1.2)-(1.4) that

satisfies Assumption 3.3 fails to converge. By Theorem 3.2 there are two distinct numbers w_{−} and w_{+} and a positive constant B such that the set Ψ̂_{w_{−},w_{+},B} is not empty, and such that its limit W is a traveling expansion shock. Therefore, by definition, there exists a convex entropy function U(w) with its corresponding flux F (w) such that

Φ = ∫_{w_{−}}^{w_{+}} U′′(w)(f[w; w_{−}, w_{+}] − f(w))dw ∫_{x=st} ϕ(x, t)dt > 0,

where ϕ(x, t) is a nonnegative smooth test function with compact support in the interior of Ω such that ∫_{x=st} ϕ(x, t)dt > 0. Hence the set Ψ_{w_{−},w_{+},B} is also not empty and contains a sequence {u^{k}(x, t)} that satisfies Lemma 7.3. We keep all the notation from Lemma 7.3 and assume that {Ω_{i}^{(k)}}_{k=1}^{∞}, i = 1, …, Ñ(ρ) and Ω^{(k)} are defined by (7.4). Our goal is to show that at least one of the ATDs is an ATES. We consider

Φ^{k} = ∫_{0}^{1} ∑_{j} h_{k}(\frac{d}{dt}U(u_{j}^{k}(t)) + D_{+}G_{j− \frac{1}{2}}^{k} (t))ϕ_{j+ \frac{1}{2}} (t)dt, (8.1)

where ϕ_{j+ \frac{1}{2}} (t) = ϕ(x_{j+ \frac{1}{2}}^{k} , t). Integrating by parts and passing to the limit, one shows easily that Φ^{k} approaches Φ. We split Φ^{k} into two parts:

Φ^{k} = Φ_{1}^{k} + Φ_{2}^{k},

where Φ_{2}^{k} denotes the summation over Ω^{(k)}, and Φ_{1}^{k} denotes the summation that is not included in Φ_{2}^{k}. We have

|Φ_{1}^{k}| ≤ U′′_{max}ϕ_{max} ∫_{0}^{1} ∑_{(x_{j}^{k}(t),t)∈Ω\Ω^{(k)}} |∫_{u_{j}^{k}(t)}^{u_{j+1}^{k}(t)}(g_{j+ \frac{1}{2}}^{k} (t) − f(w))dw| dt.

By Corollary 3.4, if either

|Δ_{+}u_{j}^{k}(t)| + |Δ_{+}u_{j+1}^{k}(t)| < 2(ρ + 2ε_{k}) or |Δ_{+}u_{j−1}^{k}(t)| + |Δ_{+}u_{j}^{k}(t)| < 2(ρ + ε_{k}), (8.2)

then |g_{j+ \frac{1}{2}}^{k} (t) − f(w)| < Cρ when w is between u_{j}^{k}(t) and u_{j+1}^{k}(t). If neither inequality in (8.2) holds, then there is an i between 1 and Ñ(ρ) − 1 such that j = J_{i}^{k}(t) = I_{i+1}^{k}(t) − 1. Hence,

|Φ_{1}^{k}| ≤ U′′_{max}ϕ_{max} ∫_{0}^{1} Cρ ∑_{j=−∞}^{∞} |Δ_{+}u_{j}^{k}(t)|
+ U′′_{max}ϕ_{max} ∫_{0}^{1} ∑_{i=1}^{_{N}(ρ)−1} |∫_{u_{J^{k}_{i}(t)}^{k}(t)}^{u_{J^{k}_{i}(t)+1}^{k}(t)}(g_{J_{i}^{k}(t)+1/2}^{k}(t) − f(u_{J_{i}^{k}(t)}^{k}(t)))dw| dt

+ U′′_{max}ϕ_{max} ∫_{0}^{1} ∑_{i=1}^{_{N}(ρ)−1} |∫_{u_{J^{k}_{i}(t)}^{k}(t)}^{u_{J^{k}_{i}(t)+1}^{k}(t)}(f(u_{J_{i}^{k}(t)}^{k}(t)) − f(w))dw| dt.

The first and the third terms on the right are bounded by CU′′_{max}ϕ_{max}Bρ. By Lemma 3.7, the second term is bounded by

U′′_{max}ϕ_{max}(ρ + ε_{k}) ∑_{i=1}^{_{N}(ρ)−1} ∫_{0}^{1} |g_{J_{i}^{k}(t)+1/2}^{k}(t) − f(u_{J_{i}^{k}(t)}^{k}(t))| dt ≤ CU′′_{max}ϕ_{max}Bε_{k} → 0

as k → ∞, because Ñ(ρ)(ρ + ε_{k}) ≤ CB. Hence, there is a constant C̃ independent of ρ and k such that |Φ_{1}^{k}| < C̃ρ for sufficiently large k.

On the other hand, Lemma 3.10 implies that

Φ_{2}^{k} → Φ_{2} = _{N} ; ∑ ; i=1[F (R̃_{i}) − F (L̃_{i}) − s(U(R̃_{i}) − U(L̃_{i}))] ∫_{x=st} ϕ(x, t)dt.

Hence, we have Φ_{2} ≥ Φ − C̃ρ. (8.3)

It follows for sufficiently small ρ that Φ_{2} > 0 and hence there exists a positive integer i ≤ Ñ(ρ) such that F (R̃_{i}) − F (L̃_{i}) − s(U(R̃_{i}) − U(L̃_{i})) > 0. (8.4)

Therefore, {u^{k}} harbors an ATES. □

Appendix. The purpose of this appendix is to prove Lemma 7.2. Consider a semidiscrete scheme that satisfies a local maximum principle in the sense of Assumption 6.4. We begin with the following

Lemma A.1 (L^{∞}(L_{loc}^{1}) Convergence). For any sequence {u_{k}} ∈ Ψ̂_{w_{−},w_{+},B} with the limit W (x, t), and for any fixed α > 0,

∫_{st−α}^{st+α} |u^{k}(x, t) − W (x, t)|dx → 0 as k → ∞ (A.1)

uniformly for t ∈ [t_{a}, t_{b}]. Here, W (x, t) is the limit of Ψ̂_{w_{−},w_{+},B}, and [t_{a}, t_{b}] is a fixed interval.

Proof. In this proof, C stands for a generic constant. We assume the contrary, namely, that there exists a positive constant η, a sequence of integers {k_{j}}_{j=1}^{∞} with k_{j+1} > k_{j}, and a sequence {t_{j}}_{j=1}^{∞} in [t_{a}, t_{b}] such that

∫_{st_{j}−α}^{st_{j}+α} |u^{k_{j}}(x, t_{j}) − W (x, t_{j})|dx > η. (A.2)

However, since T V_{u^{k}}(t) < B, and since the numerical flux is Lipschitz continuous,

∥ u^{k_{j}}(t_{1}) − u^{k_{j}}(t_{2}) ∥_{L^{1}} = ∑_{i=−∞}^{∞} |u_{i}^{k_{j}}(t_{2}) − u_{i}^{k_{j}}(t_{1})|h_{k_{j}}
= ∑_{i=−∞}^{∞} | ∫_{t_{1}}^{t_{2}} h_{k_{j}} \frac{du_{i}^{k_{j}}(t)}{dt}dt|
= ∑_{i=−∞}^{∞} | ∫_{t_{1}}^{t_{2}}(g_{i+1/2}^{k_{j}}(t) − g_{i−1/2}^{k_{j}}(t))dt|
≤ C|t_{1} − t_{2}|

for any t_{1} and t_{2}. Because W has the same property, the triangle inequality implies that δu^{k_{j}} =^{def} u^{k_{j}} − W satisfies

∥ δu^{k_{j}}(t_{1}) − δu^{k_{j}}(t_{2}) ∥_{L_{1}}≤ C|t_{1} − t_{2}|.

Therefore,

\begin{matrix}| ∫_{st_{2}−α}^{st_{2}+α} |δu^{k_{j}}(t_{2})|dx − ∫_{st_{1}−α}^{st_{1}+α} |δu^{k_{j}}(t_{1})|dx| \\ ≤∥ δu^{k_{j}}(t_{1}) − δu^{k_{j}}(t_{2}) ∥_{L_{1}} +C|t_{1} − t_{2}| \\ ≤ C|t_{2} − t_{1}|. \end{matrix} (A.3)

The relations (A.2) and (A.3) imply that

∫_{t_{a}−η/C}^{t_{b}+η/C} dt ∫_{st−α}^{st+α} |δu^{k_{j}}(x, t)|dx ≥ \frac{η^{2}}{C} .

This contradicts the L_{loc}^{1} convergence of u^{k}. □

Assume that the set Ψ̂_{w_{−},w_{+},B} is not empty. Our proof of Lemma 7.2 consists of 2 steps.

Step 1. We first construct a finite collection of paths that attract the set

{(x, t) ∈ Ω_{δ}^{−} : u^{k}(x, t)− > w_{−} + ρ}.

For any k with ε_{k} < ρ/16, set α_{k} = w_{−} + ρ/2 + ε_{k} and β_{k} = w_{−} + ρ − ε_{k}. We divide the set of all subscripts j with u_{j}^{k}(1) > β_{k} into disjoint subsets:

{j : u_{j}^{k}(1) > β_{k}} = _{m_{k}} ; ⋃ ; m=1 Π_{m}^{k}

such that:

(a) If m̃_{k} ≥ 2, then max Π_{m}^{k} < min Π_{m+1}^{k} when m = 1, 2, …, m̃_{k} − 1.

(b) If m̃_{k} ≥ 2, then for each m = 1, 2, …, m̃_{k} − 1, there is a integer j between Π_{m}^{k} and Π_{m+1}^{k} for which u_{j}^{k}(1) < α_{k}.

(c) For each m = 1, 2, …, m̃_{k}, u_{j}^{k}(1) ≥ α_{k} if min Π_{m}^{k} ≤ j ≤ max Π_{m}^{k}.

We call the set x_{Π_{m}^{k}}^{k} a ρ-peak of u^{k}. The following properties follow immediately:

1. Since T V_{u^{k}}(t) < B (see §3), the numbers m̃_{k} are bounded independent of k:

m̃_{k} < \frac{B}{ρ − 4ε_{k}} + 1 < \frac{4B}{3ρ} + 1.

2. For each m between 1 and m̃_{k}, fix one ridge M_{0,1}^{k,m}, if any, such that its x-projection P_{M^{k,m}}(1) at t = 1 is a subset of x_{Π_{m}^{k}}^{k} and call it the marked ridge m. It may happen that the marked ridge 1 or marked ridge m̃_{k} does not exist. In such a case, Π_{1}^{k} or Π_{m^{k}}^{k} must be an infinite set of consecutive integers, and u_{j}^{k}(1) must be monotone in j for j ∈ Π_{1}^{k} or for j ∈ Πk ; _{m_{k}}, i.e., u_{j}^{k}(1) is greater than β_{k} and is increasing in j for sufficiently large j, or u_{j}^{k}(1) is greater than β_{k} and is decreasing for sufficiently small j.

The following lemma confirms that the union of these marked ridges attract the set {(x, t) ∈ Ω_{δ}^{−} : u^{k}(x, t) > w_{−} + ρ}.

Lemma A.2. For any constants δ and ε with 0 < ε < δ/2, there exists a K > 0 such that for k > K, if (y, t_{0}) ∈ Ω_{δ}^{−} and u^{k}(y, t_{0}) > w_{−} + ρ, (A.4)

then there exists an m between 1 and m̃_{k} such that the marked ridge m exists, and such that |y − x_{j}^{k}| < ε for any x_{j}^{k} ∈ P_{M^{k,m}}(t_{0}).

Proof. According to the L^{∞}(L_{loc}^{1}) Convergence Lemma A.1 ( with α = 1), for ε ∈ (0, δ/2) there exists a real number K such that for k > K, there exist x′ and x′′ with y − ε < x′ < y < x′′ < y + ε such that u^{k}(x′, t_{0}) < w_{−} + ρ/2 and u^{k}(x′′, t_{0}) < w_{−} + ρ/2. (A.5)

Assume that E_{0,1}^{k,L} and E_{0,1}^{k,R} are two extremum paths of u^{k} between t = 0 and t = 1 such that max P_{E^{k,L}}(t_{0}) < y ≤ max P_{E^{k,R}}(t_{0}) and such that max P_{E^{k,L}}(1) and P_{E^{k,R}}(1) are either identical or successive E-stencils of u^{k} at t = 1. Without loss of generality, assume that E_{0,1}^{k,L} = N_{0,1}^{k,L} is a trough and E_{0,1}^{k,R} = M_{0,1}^{k,R} is a ridge. Noticing (A.4) and the second inequality of (A.5), and applying Lemma 6.12, we see that max P_{M^{k,R}}(t_{0}) < x′′ and that V_{M^{k,R}}(1) > β_{k}. Therefore, P_{M^{k,R}}(1) ⊂ x_{Π^{k,m}}^{k} for some integer m between 1 and m̃_{k}. Hence, the marked ridge m, M_{0,1}^{k,m}, exists. The marked ridge m and M_{0,1}^{k,R} may or may not be the same ridge. Nevertheless, since both P_{M^{k,R}}(1) and P_{M^{k,m}}(1) belong to x_{Π^{k,m}}^{k}, Lemma 6.12 and the inequalities in (A.5) yield the desired relation P_{M^{k,m}}(t_{0}) ∈ (x′, x′′).

In the case there are not two extremum paths E_{0,1}^{k,L} and E_{0,1}^{k,R} with the aforementioned properties, the conclusion of the lemma still holds (see the Remark at the end of §6). □

Step 2. By finding a special sequence {u^{k}} in Ψ̂_{w_{−},w_{+},B}, we will separate and concentrate the sequence of the sets {{(x, t) ∈ Ω : u^{k}(x, t) > w_{−} + ρ, x ≤ st}}_{k=1}^{∞}. We use the same notation {u^{k}} for all the sequences involved unless otherwise specified. Since for fixed ρ, the sequence {m̃_{k}} is uniformly bounded, we assume, by using a subsequence, if necessary, that m̃_{k} ≡ m̃ for all k. With this sequence and for each k and m = 1, …, m̃, define successively

z^{k,m}(t) =^{def} min P_{M^{k,m}}(t) − st,

Z^{k,m} =^{def} inf_{t∈[0,1]} z^{k,m}(t),

Z^{m} =^{def} lim_{k→∞} inf Z^{k,m}.

Obviously, Z^{m} increases with m. By using a subsequence again, if necessary, we assume that

Z^{m} = lim_{k→∞} Z^{k,m}.

Let \overline{m} be the integer, if any, such that 1 ≤ \overline{m} ≤ m̃ for which Z\overline{m} < 0 and Z^{\overline{m}+1} ≥ 0.

Without loss of generality, assume that 1 ≤ \overline{m} < m̃. By using a subsequence, if necessary, we assume that there is a sequence \{t^{k}\} ⊂ [0, 1], with t^{k} → \overline{t}, such that z^{k,\overline{m}}(t^{k}) → Z\overline{m} as k tends to infinity.

Lemma A.3. There exists a constant γ > 0, independent of k, such that for sufficiently large k, the part M_{\overline{t}−γ,\overline{t}+γ}^{k,\overline{m}} of the marked ridge m which is of course not affected by using subsequences, is entirely to the left of the line x = st + \frac{3}{4}Z\overline{m}.

Proof. The idea is as follows. When k becomes large, P_{M^{k,\overline{m}}}(t^{k}) keeps a distance to the left of the line x = st + \frac{3}{4}Z\overline{m}. Since s is finite, and since the ridge sweeps over all the intermediate points as it moves (Lemma 6.9), it takes some time for them to meet. Until then, the path stays to the left of the line.

Let σ = |Z\overline{m}|/16, and γ_{0} = 2σ/|s|. We have

x^{R} =^{def} s\overline{t} + Z\overline{m} + 2σ < st + \frac{3}{4}Z\overline{m},

if |t − \overline{t}| < γ_{0}. However, by Lemma A.1,

lim_{k→∞} max P_{M^{k,\overline{m}}}(t^{k}) = s\overline{t} + Z\overline{m},

which implies that, for sufficiently large k,

x^{L} =^{def} s\overline{t} + Z\overline{m} + σ > max P_{M^{k,\overline{m}}}(t^{k}). (A.6)

Hence, by the Sweeping Over Lemma 6.9, if at a certain time t̂, max P_{M^{k,\overline{m}}}(t̂) ≥ x^{R}, then for any x ∈ [x^{L}, x^{R}], there is a time t(x) between t^{k} and t̂ such that

u^{k}(x, t(x)) = V_{M^{k,\overline{m}}}(t(x)) > w_{−} + ρ − ε_{k} ≥ w_{−} + \frac{15}{16}ρ.

Therefore,

∫ t̂ ; t^{k}|\frac{∂u^{k}(x, t)}{∂t}|dt ≥ (w_{−} + \frac{15}{16}ρ − u^{k}(x, t̂))_{+}, (A.7)

where (a)_{+} = \frac{a+|a|}{2}, and without loss of generality, we have assumed that t̂> t^{k}. On the one hand,

S_{k} =^{def} ∫_{−∞}^{∞} dx ∫ t̂ ; t^{k}|\frac{∂u^{k}(x, t)}{∂t}|dt
(A.8)  = ∫ t̂ ; t^{k}( ∑_{j=∞}^{∞} |g_{j+ \frac{1}{2}}^{k} (t) − g_{j− \frac{1}{2}}^{k} (t)|)dt
≤ cB|t^{k} − t̂|

for some constant c. Now, (A.7) and Lemma A.1 imply that

\begin{aligned}S_{k} & > ∫_{x^{L}}^{x^{R}}(w_{−} + \frac{15}{16}ρ − u^{k}(x, t̂))_{+}dx \\ & → \frac{15}{16}ρ(x^{R} − x^{L}) = \frac{15}{16}σρ \end{aligned}

as k → ∞, and hence, for sufficiently large k,

S_{k} > \frac{σρ}{2}. (A.9)

Combining (A.8) and (A.9), we get

|t̂− t^{k}| > \frac{σρ}{2cB} .

Now if we choose γ = min(\frac{σρ}{4cB} , \frac{γ_{0}}{2} ), then there exists a real number K such that, when k > K, (A.6), (A.9) and |t^{k} − \overline{t}| < γ hold. We then have

|t^{k} − t| < 2γ = min(\frac{σρ}{2cB} , γ_{0}),

and hence, max P_{M^{k,\overline{m}}}(t) < x^{R} < st + 3Z\overline{m}/4 when k > K and |t − \overline{t}| < γ. □

According to Lemmas A.2 and A.3, for any δ′ ∈ (0, |Z\overline{m}|/4) and ε ∈ (0, |Z\overline{m}|/4)), there exists a K̃ such that if

st + Z\overline{m}/2 ≤ x ≤ st − δ′ and |t − \overline{t}| < γ, then

u^{k}(x, t) < w_{−} + ρ for k > K̃. (A.10)

Let τ = min(|Z\overline{m}|/2, γ, 1). For each k, define ũ^{k} by

ũ^{k} =^{def} T_{s(\overline{t}−τ),\overline{t}−τ}^{τ} u^{k} if \overline{t} − τ ≥ 0

and

ũ^{k} = T_{s\overline{t},\overline{t}}^{τ}u^{k} if \overline{t} − τ < 0.

Then, Lemma 7.1 implies that {ũ^{k}} ∈ Ψ̂_{w_{−},w_{+},B}. By (A.10), ũ^{k}(x, t) < w_{−} + ρ when k > K̃ and (x, t) ∈ Ω_{δ}^{−}, where δ = δ′/τ. Moreover, since δ′ is arbitrary, δ is also arbitrary. Denoting the new sequence by {u^{k}} again, we therefore have shown that for any positive constants δ and ρ, there is a sequence {u^{k}} ∈ Ψ̂_{w_{−},w_{+},B}, and there exists K_{δ,ρ} > 0, such that when k > K_{δ,ρ} and (x, t) ∈ Ω_{δ}^{−}, one has u_{k}(x, t) ≤ w_{−} + ρ. Ignoring the terms with k ≤ K_{δ,ρ}, we have shown that for any positive constants δ and ρ, there is a sequence {u^{k}} ∈ Ψ̂_{w_{−},w_{+},B} such that u_{k}(x, t) ≤ w_{−} + ρ when (x, t) ∈ Ω_{δ}^{−}. We can enhance the above result by similarly separating or concentrating the sets {(x, t) ∈ Ω_{δ}^{−} : u^{k}(x, t) < w_{−} −ρ}, {(x, t) ∈ Ω_{δ}^{+} : u^{k}(x, t) > w_{+} +ρ} and {(x, t) ∈ Ω_{δ}^{+} : u^{k}(x, t) < w_{+} − ρ}. Summarizing these results, we conclude that, for any pair (δ, ρ) of positive constants, there is a sequence {u_{δ,ρ}^{k}} ∈ Ψ̂_{w_{−},w_{+},B} such that, if |u_{δ,ρ}^{k}(x, t) − W (x, t)| > ρ, then (x, t) ∈ Ω_{δ}^{c}. Since both δ and ρ are arbitrary, Lemma 7.2 follows from a diagonal process.

References

[1] F. Bouchut, C. Bourdarias and B. Perthame, Un exemple de méthode MUSCL satisfaisant toutes les inégalités d’entropie numériques, C.R. Acad. Sci. Paris, Série I, 317 (1993), 619-624

[2] G. Chen and J. Liu, Convergence of second-order schemes for isentropic gas dynamics, Math. Comp. 61 (1993) 607-629

[3] B. Cockburn, F. Coquel and F. LeFloch, An error estimate for finite volume methods for multidimensional conservation laws, Math. Comp., to appear.

[4] B. Cockburn and P. Gremaud, An error estimate for finite element methods for scalar conservation laws, SIAM J. Numer. Anal., to appear.

[5] F. Coquel and F. LeFloch, Convergence of finite difference schemes for conservation laws in several space dimensions: the corrected antidiffusive flux approach, Math. Comp. 57 (1991), 169-210.

[6] M. Crandall and A. Majda, Monotone difference approximations for scalar conservation laws, Math. of Comp. 34 (1980), 1-21.

[7] R. J. DiPerna, Convergence of approximate solutions to conservation laws, Arch. Rational Mech. Anal. 82 (1983), 27-70.

[8] S. K. Godunov, A finite difference method for the numerical computation of discontinuous solutions of the equations of fluid dynamics, Mat. Sb. 47 (1959), 271-306

[9] J. Goodman and R. Leveque, On the accuracy of stable schemes for 2D scalar conservation laws, Math. of Comp. 45, (1985), 15-21

[10] A. Harten, J. M. Hyman and P. D. Lax, On finite-difference approximations and entropy conditions for shocks, Comm. Pure and Appl. Math. 29 (1976), 297-322

[11] G. Jennings, Discrete shocks, Comm. Pure Appl. Math. 27 (1974), 25-37.

[12] C. Johnson, A. Szepessy and P. Hansbo, On the convergence of shock capturing streamline diffusion finite element methods for hyperbolic conservation laws, Math. Comp. 54 (1990), 107-129.

[13] S. N. Kruzkov, irst order quasilinear equations in several independent variables, Math. USSR Sb. 47 (1970), 217-243 [14] N. N. Kuznetsov, Accuracy of some approximate methods for computing the weak solutions of

a first-order quasi-linear equation, USSR Comp. Math. and Math. Phys. 16 (1976), 105–109.

[15] P. Lions and P. Souganidis, Convergence of MUSCL type methods for scalar conservation laws, C. R. Acad. Sci. Paris. 311, Série I (1990), 259-264.

[16] H. Nessyahu and E. Tadmor, Non-oscillatory central differencing for hyperbolic conservation laws, J. Comput. Phys. 87 (1990), 408-463

[17] S. Osher, Riemann solvers, the entropy condition and difference approximations, SIAM J. Numer. Anal. 21 (1984), 217-235

[18] S. Osher, On convergence of generalized MUSCL schemes, SIAM J. Numer. Anal. 22 (1985), 947-961

[19] S. Osher and S. Chakravarthy, High resolution schemes and entropy condition, SIAM J. Numer. Anal. 21 (1984), 955-984

[20] S. Osher and E. Tadmor, On the convergence of difference schemes to scalar conservation laws, Math. Comp. 50 (1988), 19-51

[21] R. Sanders, On convergence of monotone finite difference schemes for variable spatial differencing, Math. Comp. 40 (1983), 19–36.

[22] C.-W. Shu, Numerical solutions on conservation laws, PhD thesis (1986)

[23] G. Jiang and C.-W. Shu, On cell entropy inequality for discontinuous Galerkin methods, Math. Comp. to appear

[24] P. K. Sweby, High resolution schemes using flux limiters for hyperbolic conservation laws, SIAM J. Numer. Anal. 21 (1984), 995-1011

[25] E. Tadmor, Convenient total variation diminishing conditions for nonlinear difference schemes, SIAM J. Numer. Anal. 25 (1988), 1002-1014

[26] A. Vol’pert, The space BV and quasi-linear equations, Math. USSR Sb 73 (1967), 255-302 [27] P. Woodward and P. Colella, The piecewise-parabolic method (PPM) for gas-dynamical simu-

lations, J. Comput. Phys. 54 (1984), 115-173

[28] H. Yang, An artificial compression method for ENO schemes: the slope modification method, J. Comput. Phys. 89 No. 1 (1990) 125-160 [29] H. Yang, Nonlinear wave analysis and convergence of MUSCL schemes, IMA preprint Series

697, 1990