CONVERGENCE AND ERROR ESTIMATES OF RELAXATION SCHEMES FOR MULTIDIMENSIONAL CONSERVATION LAWS

M. A. Katsoulakis, G. Kossioris and Ch. Makridakis

Abstract. We study discrete and semidiscrete relaxation schemes for multidimensional scalar conservation laws. We show convergence of the relaxation schemes to the entropy solution of the conservation law and derive error estimates that exhibit the precise interaction between the relaxation time and the space/time discretization parameters of the schemes.

1. Introduction

In this paper we construct and analyze semidiscrete and fully discrete relaxation schemes for the approximation of the unique global weak solution of the scalar multidimensional conservation law,

(1.1)  \{ \begin{matrix}∂_{t}u + ∑_{i=1}^{N} ∂_{x_{i}}F_{i}(u) = 0, & x ∈ ℝ^{N}, t > 0, \\ u(x, 0) = u_{0}(x) ∈ L^{1}(ℝ^{N}) ∩ L^{∞}(ℝ^{N}) , \end{matrix}

satisfying the Kruzhkov entropy conditions [13],

(1.2)  ∂_{t}|u − k| + ∑_{i=1}^{N} ∂_{x_{i}}[ (F_{i}(u) − F_{i}(k))sign(u − k) ] ≤ 0 , in D′, for all k ∈ ℝ.

Our schemes are based on the relaxation approximation of (1.1) proposed recently by Katsoulakis and Tzavaras [11]:

(1.3)  \begin{aligned}∂_{t}w^{ε} + ∑_{i=1}^{N} Ã_{i}∂_{x_{i}}w^{ε} & = \frac{1}{ε} ∑_{i=1}^{N}(h_{i}(w^{ε}) − z_{i}^{ε}) \\ ∂_{t}z_{i}^{ε} − A_{i}∂_{x_{i}}z_{i}^{ε} & = \frac{1}{ε}(h_{i}(w^{ε}) − z_{i}^{ε}) ,  i = 1, ..., N. \end{aligned}

In (1.3), the quantities z_{i} are convected with velocities −A_{i}e_{i} (e_{i} are the unit coordinate vectors), while the quantity w is convected with velocity (Ã_{1}, …, Ã_{N}), where Ã_{i} = ω_{i}A_{i} > 0, A_{i} > 0. The functions h_{i}(w), i = 1, ⋯, N describing the interaction rates between w and Z = (z_{1}, ⋯ z_{N}), are smooth and strictly decreasing. Furthermore the system (1.3) is equipped with the conservation law,

(1.4)  ∂_{t}(w^{ε} − ∑_{i=1}^{N} z_{i}^{ε}) + ∑_{i=1}^{N} ∂_{x_{i}}A_{i}(ω_{i}w^{ε} + z_{i}^{ε}) = 0 .

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary: 35L65, 65M06. Secondary: 65M12, 82C40

It is shown in [11] that, as ε → 0, the local equilibrium, z_{i} = h_{i}(w), i = 1, …, N, is enforced and that the limiting dynamics of (1.3) is described by weak entropy solutions of

(1.5)  ∂_{t}(w − ∑_{i=1}^{N} h_{i}(w)) + ∑_{i=1}^{N} ∂_{x_{i}}A_{i}(ω_{i}w + h_{i}(w)) = 0 .

Conversely, for a given conservation law (1.1), one can find functions h_{i}, i = 1, …, N (h_{i} decreasing) and positive constants ω_{i} , A_{i} , i = 1, ⋯, N such that u^{ε} = w^{ε} − ∑_{i=1}^{N} h_{i}(w^{ε}) will converge as ε → 0 to the unique solution of (1.1-2), where (w^{ε}, Z^{ε}) solve (1.3).

The goal of this paper is the study of relaxation schemes induced by discretizing (1.3), yielding approximations to the solution of the multidimensional scalar conservation law (1.1), as ε → 0. We use this problem as a benchmark for understanding stability, convergence and error estimates for such schemes and in particular, the interrelation between the relaxation parameter ε and the space/time discretization parameters. Relaxation schemes to systems of conservation laws were first introduced by Jin and Xin [9], based on relaxation models similar (but not equivalent, except for N = 1) to (1.3). One of their principal advantages is their simplicity: due to the linear convection in the relaxation model, relaxation schemes are Riemann solver–free. In addition, semidiscrete relaxation schemes such as the ones studied in this paper turn out to be an important tool in the derivation of macroscopic conservation laws as a hydrodynamic limit of Interacting Particle Systems induced by a kinetic interpretation of (1.3), [12].

Convergence of the schemes. We consider upwind semidiscrete and fully discrete schemes for the discretization of (1.3), cf. Section 3. In the discrete case the stiff nonlinear term is discretized implicitly, [15], [9]. Let h and τ be the space and time discretization parameters and (W^{h,ε}, Z^{h,ε}), (W^{τ,h,ε}, Z^{τ,h,ε}) piecewise constant interpolations of the semidiscrete and fully discrete approximations of w in (1.3). We also set

U^{h,ε} = W^{h,ε} − ∑_{i=1}^{N} h_{i}(W^{h,ε}) , U^{τ,h,ε} = W^{τ,h,ε} − ∑_{i=1}^{N} h_{i}(W^{τ,h,ε}) .

Assuming that the grid in the fully discrete scheme satisfies an appropriate CFL condition, cf. Section 4b, we show that our schemes have the properties:

• they are L^{1}–contractive and Total Variation Diminishing (TVD).

• If the initial data u_{0}, (W_{0}^{h,ε}, Z_{0}^{h,ε}) are in BV (ℝ^{n}) and additionally the initial approximations satisfy ∑_{i=1}^{N} ||h_{i}(w_{0}^{h,ε}) − z_{0i}^{h,ε}||_{L^{1}} = O(ε), then for t > 0,

(1.5)  ||U^{h,ε}(t) − u(t, ·)||_{L^{1}(ℝ^{n})} ≤ ||U^{h,ε}(0) − u(0, ·)||_{L^{1}(ℝ^{n})} + O(\sqrt{ε + h}) .

In the fully discrete case and under the same assumptions on the initial data we have

(1.6)  ||U^{τ,h,ε}(t) − u(t, ·)||_{L^{1}(ℝ^{n})} ≤ ||U^{τ,h,ε}(0) − u(0, ·)||_{L^{1}(ℝ^{n})} + O(\sqrt{ε + τ + h}) .

These estimates yield the compactness and convergence properties of both schemes claimed earlier, under elementary hypotheses on the approximating initial data. In (1.5) and (1.6), the O–terms depend on the L^{∞}- norm and the total variation of the initial data and, on the terminal time T. It is important to note that our error estimate does not interrelate the parameters ε and h, τ in a restrictive way. Note also that the results obtained herein imply also the convergence, and the corresponding error estimate, for the first order schemes of [9] for N = 1. Similar error estimates, but of order O(ε^{1/3} + \sqrt{τ}), were obtained by Schroll, Tveito and Winther [20], for discrete approximations to a one dimensional relaxation model with nonlinear convection arising in chromatography; see also [21] for a similar result in two space dimensions. Stability and convergence properties of splitting schemes obtained by discretizing a 2 × 2 relaxation approximation of a one dimensional scalar conservation law, were studied in [1].

An approximation theorem. We begin, in Section 2, by considering an approximation theorem which is the discrete analogue of the main estimate in [3]. The method of doubling of variables introduced by Kruzhkov [13] and the ideas of Kuznetsov [14] to apply such a method to numerical approximations, have been extensively used by several authors to obtain error estimates for approximations to the entropy solution of (1.1), cf. e.g. [14], [19], [17]. This technique was further developed in the case of finite volume or finite element approximations [5], [22], [6], see also [7]. In this case, due to the lack of BV bounds for the discrete schemes even the convergence of the approximations is a rather technical task. Kuznetsov’s method along with DiPerna’s theory [8] are the main available tools to prove convergence in this case. Recently, Bouchut and Perthame [3], see also [2], proposed a compact form for deriving error estimates to conservation laws by revising the approach of [14], [13]. Their theorem can be applied directly without doubling the variables and thus avoiding much of the technical work, needed up to now, to obtain estimates for functions satisfying an approximate entropy inequality, cf. [3]. In section 2 we propose a variation of this result, which is what we call a discrete version of the main theorem in [3]; this is our Theorem 2.1. In the approximation estimate of Theorem 2.1 we explicitly include terms that typically arise in any numerical scheme approximating the scalar conservation law. This result is our main tool in obtaining the estimates (1.5), (1.6) for the semidiscrete and fully discrete relaxation approximations in section 5, cf. Theorems 5.1 and 5.2. The same estimate is also used by Katsaounis and Makridakis [10], to obtain converegence and error estimates to the entropy solution of (1.1), for a finite volume relaxation scheme based on the system (1.3).

The structure of the paper is as follows. We begin, in Section 2, by considering the approximation theorem mentioned above. In section 3 we present the discrete and semi-discrete relaxation schemes.

In section 4 we study the properties of the schemes, in particular we show that under structural conditions on the relaxation functions h_{i}, both schemes are L^{1} contractive with diminishing associated total variation (TVD) and satisfy an entropy condition. In section 5 we prove the convergence results and give the rate of convergence based on the theorem presented in section 2.

2. Error Bound for Approximating Schemes

In this section we establish an error estimate for approximating schemes for conservation laws, which is the discrete analogue of the theorem by Bouchut and Perthame [3]. In the following theorem, u_{h} stands for any function approximating the solution u of (1.1-2). Theorem 2.1. Let u_{h}, u ∈ L_{loc}^{∞}([0, ∞), L_{loc}^{1}(ℝ^{N})) be right continuous in t, with values in L_{loc}^{1}(ℝ^{N}). Assume that u is the entropy solution of a given conservation law, i.e., it satisfies (1.1) and (1.2). Let Ψ a nonegative test function Ψ ∈ C_{c}^{∞}([0, ∞) × ℝ^{N}) and assume that u_{h} satisfies,

(2.1)

− ∫∫_{(0,∞)×ℝ^{N}} (|u_{h} − k|∂_{t}Ψ + sign(u_{h} − k)[f(u) − f(k)] · ∇_{x}Ψ)dtdx
≤ ∫∫_{(0,∞)×ℝ^{N}} (α_{K}|Ψ| + α_{G}|∂_{t}Ψ| + ∑_{j} α_{H}^{j}|\frac{∂Ψ}{∂x_{j}} | + ∑_{1≤i, j≤N} α_{L}^{ij}|\frac{∂^{2}Ψ}{∂x_{i}∂x_{j}} |)dxdt

+ ∫∫_{(0,∞)×ℝ^{N}} (β_{G}B_{G}(∂_{t}Ψ) + ∑_{j} β_{H}^{j}B_{H}^{j}(\frac{∂Ψ}{∂x_{j}}) + ∑_{i,j} β_{L}^{ij}B_{L}^{ij}(\frac{∂^{2}Ψ}{∂x_{i}x_{j}}))dxdt

for all k ∈ ℝ,

where f = (F_{1}, …, F_{N}) and α_{G}, α_{H}^{j}, α_{K}, α_{L}^{ij}, β_{G}, β_{H}^{j}, β_{L}^{ij} are nonnegative k-independent functions in L_{loc}^{1}([0, ∞) × ℝ^{N}) and

(2.2)  α_{G}, β_{G} ∈ L_{loc}^{∞}([0, ∞), L_{loc}^{1}(ℝ^{N})) .

In addition, the operators B_{G}, B_{H}^{j}, B_{L}^{ij} : C^{∞}([0, ∞)×ℝ^{N}) → L_{loc}^{∞}([0, ∞)×ℝ^{N}) satisfy the properties: For Δ, δ > 0, let T_{h} = {K} be an element decomposition of supp g, g ∈ C^{∞}([0, ∞)×ℝ^{N}) into elements K, such that

(2.3)

diam(K_{t}) ≤ Δ , if either B_{H}^{j}, or B_{L}^{ij} is not zero, and
|K_{x}| ≤ δ , if the term B_{G} is not zero,

where K_{x} = {t : (t, x) ∈ K} and K_{t} = {x : (t, x) ∈ K}. We assume that for all (t, x) ∈ K, 1 ≤ i, j ≤ N,

(2.4)

|B_{G}(g)(t, x)| ≤ C sup_{t∈K_{x}} |g(t, x)|

|B_{H}^{j}(g)(t, x)| ≤ C sup_{x∈K_{t}} |g(t, x)|

|B_{L}^{ij}(g)(t, x)| ≤ C sup_{x∈K_{t}} |g(t, x)| ,

where C is a uniform constant independent of g and the element decomposition T_{h}. Then the following estimate holds: for any T ≥ 0, x_{0} ∈ ℝ^{N}, R > 0, Δ > 0, δ > 0, ν ≥ 0, denoting by M = Lip(f), B_{t} = B(x_{0}, R + M(T − t) + Δ + ν), we have:

(2.5)  \begin{matrix}∫_{|x−x_{0}|<R} |u_{h}(T, x) − u(T, x)|dx ≤ ∫_{B_{0}} |u_{h}(0, x) − u(0, x)|dx \\ + C(E^{t} + E^{x} + E^{G} + E^{H} + E^{K} + E^{L} + Ẽ_{G} + Ẽ_{H} + Ẽ_{L}) . \end{matrix}

Here

E^{t} = sup_{t=0,T ,0<s−t<δ} ∫_{B_{t}} |u(s, x) − u(t, x)|dx , E^{x} = sup_{t=0,T ,0<|x−y|<Δ} ∫_{B_{t}} |u(t, y) − u(t, x)|dx

E^{K} = ∫∫_{0≤t≤T x∈B_{t}} α_{K}(t, x)dxdt, E^{H} = \frac{1}{Δ} ∑_{j=1}^{N} ∫∫_{0≤t≤T x∈B_{t}} α_{H}^{j}(t, x)dxdt,

E^{L} = \frac{1}{Δ^{2}} ∑_{1≤i,j≤N} ∫∫_{0≤t≤T ,x∈B_{t}} α_{L}^{ij}(t, x)dxdt

E^{G} = (1 + \frac{T}{δ} + \frac{MT}{Δ + ν}) sup_{0≤t≤2T} ∫_{B_{t}} α_{G}(t, x)dx

and the Ẽ–terms are the same as the E–terms with α′s replaced by β′s.

The Lipschitz hypothesis on the function f can be removed if, for example, it is known that both u and u_{h} are uniformly bounded. Notice also that if the initial datum u_{0} in (1.1) is in BV (ℝ^{N}) then

E^{t} ≤ MδT V (u_{0}) , E^{x} ≤ ΔT V (u_{0}) ,

where T V (v) denotes the total variation of a function v ∈ BV (ℝ^{N}). The proof of Theorem 2.1 follows along the lines of the basic theorem in [3]. The novelty here is the explicit inclusion in (2.1) and the bound yielding (2.5), of the error β−terms that typically arise in any discrete or semidiscrete approximation of the scalar conservation law. The importance of such terms will become more clear in the sequel, when we apply Theorem 2.1 in the relaxation schemes.

Proof. For the sake of completeness we describe the basic steps of the proof, following [1], and then we estimate in detail the new β−terms.

1. Given two nonegative functions Φ, ζ ∈ C_{c}^{∞}((0, ∞) × ℝ^{n}) that will be specified later, we set

(2.6)  ϕ(t, x, s, y) = Φ(t, x)ζ(t − s, x − y) .

We now consider (2.1) for Ψ = ϕ(·, ·, s, y) with fixed (s, y) ∈ (0, ∞) × ℝ^{N} and k = u(s, y); similarly we also consider the entropy inequality (1.2) for the test function Ψ = ϕ(t, x, ·, ·), fixing (t, x) ∈ (0, ∞) × ℝ^{N} and picking k = u_{h}(t, x). We add the two relations, integrate with respect to all variables and using ∂_{t}ζ = −∂_{s}ζ, ∇_{x}ζ = −∇_{y}ζ, we obtain (2.7)

\begin{aligned}− ∫∫∫∫ & [|u_{h}(t, x) − u(s, y)|∂_{t}Φ(t, x) + sign(u_{h}(t, x) − u(s, y))[f(u_{h}(t, x)) − f(u(s, y))] · ∇_{x}Φ(t, x)] \\ & × ζ(t − s, x − y)dsdtdydx ≤ R^{α} + R^{β} , \end{aligned}

where

R^{α} = ∫∫∫∫ α_{K}(t, x)|ϕ(t, x, s, y)| + α_{G}(t, x)|∂_{t}ϕ(t, x, s, y)|

+ ∑_{j} α_{H}^{j}(t, x)|∂_{x_{j}}ϕ(t, x, s, y)|

+ ∑_{1≤i, j≤N} α_{L}^{ij}(t, x)|∂_{x_{i}x_{j}}^{2}ϕ(t, x, s, y)|dsdtdydx

and

R^{β} = ∫∫∫∫ β_{G}(t, x)B_{G}(∂_{t}ϕ(t, x, s, y))

+ ∑_{j} β_{H}^{j}(t, x)B_{H}^{j}(∂_{x_{j}}ϕ(t, x, s, y))

+ ∑_{1≤i, j≤N} β_{L}^{ij}(t, x)B_{L}^{ij}(∂_{x_{i}x_{j}}^{2}ϕ(t, x, s, y))dsdtdydx

=: R_{G}^{β} + ∑_{j} R_{H}^{β,j} + ∑_{1≤i, j≤N} R_{L}^{β,(i,j)} .

2. Now we select the functions Φ and ζ in (2.6). First, for any positive constants δ and Δ, we define ζ as follows:

ζ(t, x) = ζ^{t}(t)ζ^{x}(x), ζ^{t}, ζ^{x} ∈ C_{c}^{∞}, ≥ 0, ∫ ζ^{t}dt = ∫ ζ^{x}dx = 1

ζ^{t}(t) = \frac{1}{δ}ζ_{1}^{t}(\frac{t}{δ}), suppζ_{1}^{t} ⊂ (−1, 0),

ζ^{x}(x) = \frac{1}{Δ^{N}} ζ_{1}^{x}(\frac{x}{Δ}), suppζ_{1}^{x} ⊂ B(0, 1/4),

where ζ_{1}^{t}, ζ_{1}^{x} are given smooth functions independent of the partition, and of δ, Δ. The constants in the estimates of β terms, will depend also on

C_{t}^{(j)} = ||∂_{t}^{j}ζ_{1}^{t}||_{L^{∞}}, C_{x}^{(j)} = ||ζ_{1}^{x}||_{W^{j,∞}} .

For θ > 0, we define Y_{θ}(t) so that Y_{θ}(−∞) = 0 and Y′_{θ}(t) = \frac{1}{θ}Y′(\frac{t}{θ}), where Y′ ∈ C_{c}^{∞}, ≥ 0 and ∫ Y′ = 1. We intorduce yet another parameter ε > 0 and set χ(t) = Y_{ε}(t) − Y_{ε}(t − T) ∈ C_{c}^{∞}((0, T + ε)), ≥ 0. Finally we define ψ(t, x) = 1 − Y_{θ}(|x − x_{0}| − R − Δ/2 − M(T − t)) ≥ 0. We now set

Φ(t, x) = χ(t)ψ(t, x) .

Notice that Φ ∈ C^{∞} as long as Mε ≤ R + Δ/2. Inserting Φ in (2.7) and using the Lipschitz condition on f, we get, cf. [1],

− ∫∫∫∫ |u_{h}(t, x) − u(s, y)|χ′(t)ψ(t, x)ζ(t − s, x − y)dsdtdydx ≤ R^{α} + R^{β} .

Therefore

(2.8)  0 ≤ I + R^{t} + R^{x} + R^{α} + R^{β} ,

where

I = ∫∫∫∫ |u_{h}(t, x) − u(t, x)|χ′(t)ψ(t, x)ζ(t − s, x − y)dsdtdydx
R^{x} = ∫∫∫∫ |u_{h}(t, x) − u(t, y)|χ′(t)ψ(t, x)ζ(t − s, x − y)dsdtdydx
R^{t} = ∫∫∫∫ |u_{h}(t, y) − u(s, y)|χ′(t)ψ(t, x)ζ(t − s, x − y)dsdtdydx .

Furthermore notice that for θ fixed and ε small,

(2.9)  1_{B(x_{0},R+M(T −t)+Δ/2)} ≤ ψ(t, x) ≤ 1_{B(x_{0},R+M(T −t)+Δ/2+θ} .

We now intend to pass to the ε → 0 limit in (2.8), and with a suitable choice θ, obtain (2.5).

3. Using (2.9), the properties of ζ and the right continuity of v (see [3] for more details), we get,

lim sup_{ε→0} I ≤ ∫_{|x−x_{0}|<R+MT +Δ/2+θ} |u_{h}(0, x) − u(0, x)|dx − ∫_{|x−x_{0}|<R+Δ/2} |u_{h}(T, x) − u(T, x)|dx

lim sup_{ε→0} R^{t} ≤ 2E^{t}, lim sup_{ε→0} R^{x} ≤ 2E^{x} ,

provided we choose θ = Δ/4 + ν. We turn now to the terms R^{α} and R^{β}. First we have the following bounds for Φ,

(2.10)  \begin{matrix}|Φ(t, x)| ≤ C, |∇_{x}Φ(t, x)| ≤ \frac{C}{θ} , \\ |∂_{t}Φ(t, x)| ≤ |χ′(t)| + C \frac{M}{θ} , |∂_{x_{i}x_{j}}Φ| ≤ \frac{C}{θ^{2}} , \end{matrix}

and let

\begin{matrix}Ω = \{(t, x) : 0 ≤ t < T + ε, |x − x_{0}| < R + M(T − t) + Δ/2 + θ\} , \\ Ω_{t} = \{x : |x − x_{0}| < R + M(T − t) + Δ/2 + θ\} . \end{matrix}

Then (2.10) and the definition of ζ imply

R^{α} ≤ ∫∫_{Ω} [α_{K}(t, x) + C(\frac{1}{θ} + \frac{1}{Δ}) ∑_{j} α_{H}^{j}(t, x) + \frac{C}{δ} α_{G}(t, x)+

C(\frac{1}{Δ^{2}} + \frac{1}{θΔ} + \frac{1}{θ^{2}} ) ∑_{ij} α_{L}^{ij}(t, x)]dtdx + C(1 + M(T + ε)/θ) sup_{0<t<T +ε} ∫_{Ω_{t}} α_{G}(t, x)dx .

Keeping in mind that θ = Δ/4 + ν, we get

(2.11)  lim sup_{ε→0} R^{α} ≤ C(E^{K} + E^{G} + E^{H} + E^{L}) .

4. Finally we estimate the term R^{β}. Let T_{h} = {K} a decomposition of the support of Ψ, then T_{h,t} = {K_{t}} is a partition of the space domain.

To estimate the second term of R^{β} we note that (2.3) and suppΨ ⊂ Ω imply

R_{H}^{β,j} ≤C ∫∫ ∫ ∑_{K_{t}∈T_{h,t}} ∫_{K_{t}} β_{H}^{j}(t, x)( sup_{x} |(∂_{x_{j}}ζ(t − s, x − y)) Φ(t, x)|

+ sup_{x} |ζ(t − s, x − y) ∂_{x_{j}}Φ(t, x)|)dxdtdyds =: I_{H}^{1,j} + I_{H}^{2,j}.

Then, (2.9-10) yield

I_{H}^{1,j} ≤ C ∫∫ ∫ ∑_{K_{t}∈T_{h,t}} ∫_{K_{t}} 1_{Ω}(t, x)β_{H}^{j}(t, x) sup_{x} |∂_{x_{j}}ζ^{x}(x − y)| ζ^{t}(t − s)dxdtdyds .

Since supp∂_{j}ζ^{x} ⊂ B(0, Δ/4), then if |x − y| > Δ/4 we have ∂_{j}ζ^{x}(x − y) = 0. Therefore if K_{t,Δ} = {y ∈ ℝ^{N} : dist(y, K_{t}) ≤ Δ/4} then for x ∈ K_{t}, y ∈ (K_{t,Δ})^{C} we will have that ∂_{x_{j}}ζ^{x}(x − y) = 0, whence sup_{x∈K_{t},y∈(K_{t,Δ})^{C}} |∂_{x_{j}}ζ^{x}(x − y)| = 0. Hence,

∫ ∫_{K_{t}} ∫_{ℝ^{N}} 1_{Ω}(t, x)β_{H}^{j}(t, x) sup_{x} |∂_{x_{j}}ζ^{x}(x − y)| ζ^{t}(t − s)dydxds

≤ ∫_{K_{t}} 1_{Ω}(t, x)β_{H}^{j}(t, x) ∫_{K_{t,Δ}} C_{x}^{(1)} \frac{1}{Δ^{N+1}} dydx

≤ C C_{x}^{(1)} ∫_{K_{t}} 1_{Ω}(t, x)β_{H}^{j}(t, x)|K_{t,Δ}|\frac{1}{Δ^{N+1}} dydx.

Now

|K_{t,Δ}| ≤ C (diam(K_{t})^{N} + Δ^{N}),

therefore, by (2.3),

I_{H}^{1,j} ≤ C \frac{1}{Δ} ∫ ∑_{K_{t}∈T_{h,t}} \frac{diam (K_{t})}{Δ} ∫_{K_{t}} 1_{Ω}(t, x)β_{H}^{j}(t, x)dxdt

≤ C \frac{1}{Δ} ∫∫_{Ω} β_{H}^{j}dxdt.

Similarly using (2.3 − 4), (2.10) and the fact that supp|∂_{x_{j}}Φ| ⊂ Ω, we have,

I_{H}^{2,j} ≤ ∫∫ ∫ ∑_{K_{t}∈T_{h,t}} ∫_{K_{t}} 1_{Ω}(t, x)β_{H}^{j}(t, x)\frac{1}{θ} sup_{x} |ζ(t − s, x − y)|dxdtdyds

≤ C \frac{1}{θ} ∫ ∑_{K_{t}∈T_{h,t}} \frac{diam(K)}{Δ} ∫_{K_{t}} C_{x}^{(0)}1_{Ω}(t, x)β_{H}^{j}(t, x)dxdt

≤ \frac{C}{θ} ∫∫_{Ω} β_{H}^{j}dxdt.

For the terms with the time derivatives we first observe that for each fixed x, T_{h,x} = {K_{x}} defines a decomposition of the time domain. Therefore

∫∫ ∫∫ β_{G}|B_{G}(∂_{t}ϕ)|dxdtdyds

≤ C ∫∫ ∫_{ℝ^{N}} ∑_{K_{x}∈T_{h,x}} ∫_{K_{x}} 1_{Ω}(t, x)β_{G}(x, t)[ sup_{t} |Φ(t, x)∂_{t}ζ(t − s, x − y)|

+ sup_{t} |∂_{t}Φ(t, x)ζ(t − s, x − y)|]dxdtdyds =: I_{G}^{1} + I_{G}^{2}.

Now:

I_{G}^{1} ≤ ∫∫ ∫_{ℝ^{N}} ∑_{K_{x}∈T_{h,x}} ∫_{K_{x}} 1_{Ω}(t, x)β_{G}(x, t) sup_{t} |Φ(t, x)| sup_{t} |∂_{t}ζ(t − s, x − y)|dtdxdyds

≤ C ∫∫ ∫_{ℝ^{N}} ∑_{K_{x}∈T_{h,x}} ∫_{K_{x}} 1_{Ω}(t, x)β_{G}(x, t) sup_{t} |∂_{t}ζ^{t}(t − s)|ζ^{x}(x − y)dtdxdyds.

Denoting by K_{x}^{δ} = {t : t ∈ K_{x} + δ} we observe that since supp ∂_{t}ζ^{t} ⊂ (−δ, 0), if t ∈ K_{x}, s ∈ (K_{x}^{δ})^{C}, then ∂_{t}ζ^{t}(t − s) = 0. Therefore,

∫∫ ∫_{ℝ^{N}} ∫_{K_{x}} 1_{Ω}(t, x)β_{G}(t, x) sup_{t} |∂_{t}ζ^{t}(t − s)|ζ^{x}(x − y)dtdxdsdy

≤ C ∫_{ℝ^{N}} ∫_{K_{x}} 1_{Ω}(t, x)β_{G}(t, x) ∫_{K_{x}^{δ}} C_{t}^{(1)} \frac{1}{δ^{2}} dsdtdx

≤ \frac{C}{δ} ∫_{ℝ^{N}} ∫_{K_{x}} 1_{Ω}(t, x)β_{G}(t, x)C_{t}^{(1)} \frac{|K_{x}^{δ}|}{δ}dtdx

≤ \frac{C}{δ} ∫_{ℝ^{N}} ∫_{K_{x}} 1_{Ω}(t, x)(1 + \frac{|K_{x}|}{δ})β_{G}(t, x)dtdx.

Using (2.3) we obtain:

I_{G}^{1} ≤ \frac{C}{δ} ∫∫_{Ω} β_{G}(t, x)dtdx.

We now estimate I_{G}^{2} using the inequality |∂_{t}Φ(t, x)| ≤ |χ′(t)| + C \frac{M}{θ} (cf. (2.10) ):

I_{G}^{2} = ∫∫ ∫_{ℝ^{N}} ∑_{K_{x}∈T_{h,x}} ∫_{K_{x}} 1_{Ω}(t, x)β_{G}(t, x) sup_{t} |∂_{t}Φ(t, x)| sup_{t} ζ^{t}(t − s)ζ^{x}(x − y)dtdxdsdy

≤ ∫ ∫_{ℝ^{N}} ∑_{K_{x}∈T_{h,x}} ∫_{K_{x}} 1_{Ω}(t, x)β_{G}(t, x) sup_{t} |∂_{t}Φ(t, x)| sup_{t} ζ^{t}(t − s)dtdxds

≤ C ∫∫ 1_{Ω}(t, x)β_{G}(t, x)\frac{M}{θ} sup_{t} ζ^{t}(t − s)dtdsdx

+ ∫_{Ω_{x}} ∫ ∑_{K_{x}∈T_{h,x}} ∫_{K_{x}∩((0,ε)∪(T,T +ε))} 1_{Ω}(t, x)β_{G}(t, x)|χ′(t)| sup_{t} ζ^{t}(t − s)dtdsdx.

The first term is bounded as before by

C \frac{M}{θ} ∫∫_{Ω} β_{G}(t, x)dtdx ≤ C \frac{M}{θ} (T + ε) sup_{0<t<T +ε} ∫_{|x−x_{0}|<R+M(T −t)+Δ/2+θ} β_{G}(t, x)dx.

To estimate the second term recall also that χ(t) = Y_{ε}(t)−Y_{ε}(t−T) hence supp|χ′| ⊂ (0, ε)∪(T, T +ε) and |χ′| ≤ \frac{C}{ε} . Then using similar arguments as above, we bound this term by

C ∫_{ℝ^{N}} ∑_{K_{x}} ∫_{K_{x}∩((0,ε)∪(T,T +ε))}(1 + \frac{|K_{x}|}{δ})1_{Ω}(t, x)β_{G}(t, x)|χ′(t)|dtdx

≤ C ∫_{ℝ^{N}} ∑_{K_{x}} ∫_{K_{x}∩((0,ε)∪(T,T +ε))} 1_{Ω}(t, x)β_{G}(t, x)\frac{C}{ε} dtdx

≤ C sup_{T ≤t≤T +ε, 0≤t≤ε} ∫_{Ω_{t}} β_{G}(t, x)dx.

The above estimates yield the corresponding Ẽ terms by using that θ = Δ/4 + ν. Finally, we estimate R_{L}^{β,(i,j)} employing similar arguments as in the estimate of R_{H}^{β,j}, and the bound of the second derivatives of Φ in (2.10). We omit the details. □

Remark 2.1 The results of Theorem 2.1 hold if we replace assumptions (2.3-4) by

(2.3′)  diam(K) ≤ Δ , Δ = δ

and

(2.4′)  ∥B(g)∥_{L^{∞}(K)} ≤ C∥g∥_{L^{∞}(K)},

where B stands for any of B_{G}, B_{H}^{j} or B_{L}^{ij}. These assumptions are probably better suited in the case of space-time partitions.

3. Relaxation Approximations

In this section we present the schemes for the relaxation system that will be analysed in the sequel. First we discuss the relation between the conservation law (1.1) and the relaxation system (1.3) and in particular whether any given multidimensional, scalar conservation law can be realized as a zerorelaxation limit of solutions to (1.3). In view of the relation between (1.3) and (1.5), the question is rephrased whether (1.1) can be transformed to the form (1.5), with the functions h_{i}, describing the curve of local equilibria, being strictly decreasing. It turns out (see [11], Lemma 4.1) that it is possible to construct such functions h_{i} : ℝ → ℝ, with the properties \frac{dh_{i}}{dw} < 0, h_{i}(0) = 0 and lim_{w→±∞} h_{i}(w) = ∓∞, whenever ω_{i} , A_{i} > 0 , i = 1, ⋯, N are selected so that the fluxes F_{i}(u) satisfy the conditions

(3.1)  \begin{matrix}1 + ∑_{i} \frac{1}{A_{i}} \frac{dF_{i}}{du} & > 0 , \\ −1 + ω + c < \frac{1}{\frac{1}{1+ω} (1 + ∑_{i} \frac{1}{A_{i}} \frac{dF_{i}}{du} )} & \frac{1}{A_{i}} \frac{dF_{i}}{du} < ω_{i} , for u ∈ ℝ . \end{matrix}

Here ω = ∑_{i} ω_{i} and c a positive constant. Note that the second equation implies

∑_{i} \frac{1}{A_{i}} \frac{dF_{i}}{du} < ω ,

so (3.1) is a multi-dimensional analogue of the subcharacteristic condition (cf. Liu [16], Chen, Levermore, Liu [4]). In addition, the constructed functions h_{i} have the property

(3.2)  1 − ∑_{i} |\frac{dh_{i}}{dw} | > c , for w ∈ ℝ .

c being the constant of (3.1). This property is essential for the converegence of the relaxation schemes to the conservation law because it provides an estimate on the distance ∑_{i} ||h_{i}(w) − z_{i}||_{L^{1}} of the solution (w, Z) of (1.3) from the line of equilibria

(3.3)  {(w, Z) ∈ ℝ × ℝ^{N} : h_{i}(w) = z_{i}} .

Notice also that since we are dealing with bounded solutions of (1.1) and (1.3), properties (3.1) and (3.2) need not hold for all u, w ∈ ℝ but only for a bounded interval where the solutions lie. For now on we assume that we are given the functions h_{i} satisfying the above properties and for notational convenience we let

G_{i}(w, z_{i}) := h_{i}(w) − z_{i}.

3.a Semi-discrete relaxation schemes. For a space discretization parameter h > 0 and ε > 0, we consider approximations of the solution (w, Z) of the system (1.3), w_{q}(t) ≅ w(t, hq), z_{i,q} ≅ z_{i}(t, hq), q ∈ ℤ^{N}, defined by:

(3.4)  \begin{matrix}∂_{t}w_{q} + \frac{1}{h} ∑_{i} Ã_{i}(w_{q}(t) − w_{q−e_{i}}(t)) = \frac{1}{ε} ∑_{i} G_{i}(w_{q}(t), z_{i,q}(t)) \\ ∂_{t}z_{i,q} − \frac{1}{h}A_{i}(z_{i,q+e_{i}}(t) − z_{i,q}(t)) = \frac{1}{ε}G_{i}(w_{q}(t), z_{i,q}(t)) , i = 1, ⋯, N, \end{matrix}

with given initial approximations w_{q}(0), z_{i,q}(0). In addition, A_{i} > 0, Ã_{i} = A_{i}ω_{i} > 0, cf. §1, and e_{i} is the is the x_{i}-unit coordinate vector. This semi-discrete scheme was considered in [11], and in [12] an l^{1}(ℤ^{N})–contraction and a TVD property were shown. 3.b Discrete relaxation schemes. In addition, let τ > 0 be the time discretization parameter. Then the fully discrete relaxation scheme is defined by

(3.5)  \begin{matrix}w_{q}^{n+1} − w_{q}^{n} + \frac{τ}{h} ∑_{i} Ã_{i}(w_{q}^{n} − w_{q−e_{i}}^{n}) = \frac{τ}{ε} ∑_{i} G_{i}(w_{q}^{n+1}, z_{i,q}^{n+1}) \\ z_{i,q}^{n+1} − z_{i,q}^{n} − \frac{τ}{h}A_{i}(z_{i,q+e_{i}}^{n} − z_{i,q}^{n}) = \frac{τ}{ε} G_{i}(w_{q}^{n+1}, z_{i,q}^{n+1}), i = 1, ⋯, N. \end{matrix}

Here w_{q}^{n} ≅ w(hq, nτ) and z_{i,q}^{n} ≅ z_{i}(hq, nτ), and w_{q}^{0}, z_{i,q}^{0} are given approximations of the initial data. In the sequel we will use the notation (W, Z) to denote the set of values of the schemes (3.4), (3.5) on all grid points and typically supress the dependence on the parameters ε, h, τ, unless necessary.

4. Properties of the schemes

4.a Semi-discrete Scheme. The first proposition shows that the semi-discrete scheme is l^{1}-contractive and Total Variation Diminishing (TVD); the total variation of a function v : ℤ^{N} ↦ ℝ is defined as:

T V (v) = ∑_{i=1}^{N} T V^{i}(v) = ∑_{i=1}^{N} ∑_{q∈ℤ^{N}} h^{N−1}|v_{q+e_{i}} − v_{q}| .

Proposition 4.1. (L^{1}-contraction, TVD property) Let (W, Z), (W̄ , Z̄) be two solutions of (3.4), with corresponding initial data (W_{0}, Z_{0}), (W̄_{0}, Z̄_{0}) such that W_{0}, Z_{0}, W̄_{0}, Z̄_{0} ∈ l^{1}(ℤ^{N})∩l^{∞}(ℤ^{N}). Then, for all t > 0, ε > 0,

∑_{q∈ℤ^{N}} (|w_{q}(t) − w̄_{q}(t)| + ∑_{i} |z_{i,q}(t) − z̄_{i,q}(t)|)

≤ ∑_{q∈ℤ^{N}} (|w_{q}(0) − w̄_{q}(0)| + ∑_{i} |z_{i,q}(0) − z̄_{i,q}(0)|) .

Furthermore the semidiscrete scheme (3.4) is TVD:

∑_{q∈ℤ^{N}} (|w_{q+e_{k}}(t) − w_{q}(t)| + ∑_{i} |z_{i,q+e_{k}}(t) − z_{i,q}(t)|)

≤ ∑_{q∈ℤ^{N}} (|w_{q+e_{k}}(0) − w_{q}(0)| + ∑_{i} |z_{i,q+e_{k}}(0) − z_{i,q}(0)|) ,

for t > 0 and all directions e_{k}, k = 1, ..., N.

Proof. The essential ingredient of this proof is the monotonicity of G_{i}. To get an error estimate equation we first subtract the corresponding equations for (W, Z) and (\overline{W} , \overline{Z}). Then we multiply the equation for w_{q} − w̄_{q} by sign(w_{q}(t) − w̄_{q}(t)) and that for z_{i,q} − z̄_{i,q} by sign(z_{i,q}(t) − z̄_{i,q}(t)) and we add them up to obtain:

∂_{t}(|w_{q} − w̄_{q}| + ∑_{i} |z_{i,q} − z̄_{i,q}|) + \frac{1}{h} ∑_{i} A_{i}(ω_{i}|w_{q} − w̄_{q}| + |z_{i,q} − z̄_{i,q}|)

− \frac{1}{h} ∑_{i} A_{i}[ω_{i}sign(w_{q} − w̄_{q})(w_{q−e_{i}} − w̄_{q−e_{i}}) + sign(z_{i,q} − z̄_{i,q})(z_{i,q+e_{i}} − z̄_{i,q+e_{i}})]

= \frac{1}{ε} ∑_{i} [G_{i}(w_{q}(t), z_{i,q}(t)) − G_{i}(w̄_{q}(t), z̄_{i,q}(t))](sign(w_{q}(t) − w̄_{q}(t)) + sign(z_{i,q}(t) − z̄_{i,q}(t))) ≤ 0 .

The l^{1}-contraction property follows from the above inequality by summing over q, provided we show first that (W (t), Z(t)), (W̄ (t), Z̄(t)) ∈ l^{1} for any t > 0. For the details see [12]. The TVD estimate property follows by the translation invariance property of the scheme. □

We next prove a comparison principle which implies the discrete entropy inequality and an l^{∞} bound:

Proposition 4.2. Under the assumptions of Proposition 4.1 we have: For all t > 0, ε > 0,

(i)  ∂_{t}((w_{q} − w̄_{q})^{+} + ∑_{i}(z_{i,q} − z̄_{i,q})^{−}) + \frac{1}{h} ∑_{i} Ã_{i}[(w_{q} − w̄_{q})^{+} − (w_{q−e_{i}} − w̄_{q−e_{i}})^{+}]

− \frac{1}{h} ∑_{i} A_{i}[(z_{i,q+e_{i}} − z̄_{i,q+e_{i}})^{−} − (z_{i,q} − z̄_{i,q})^{−}] ≤ 0,

(ii) ∑_{q∈ℤ^{N}} [(w_{q}(t) − w̄_{q}(t))^{+} + ∑_{i}(z_{i,q}(t) − z̄_{i,q}(t))^{−}] ≤ ∑_{q∈ℤ^{N}} [(w_{q}^{0} − w̄_{q}^{0})^{+} + ∑_{i}(z_{i,q}^{0} − z̄_{i,q}^{0})^{−}] ,

(iii) If for some a < b we have, a ≤ w_{q}(0) ≤ b, h_{i}(b) ≤ z_{i,q}(0) ≤ h_{i}(a), i = 1, ⋯, N, q ∈ ℤ^{N}, then

a ≤ w_{q}(t) ≤ b, h_{i}(b) ≤ z_{i,q}(t) ≤ h_{i}(a), q ∈ ℤ^{N}, i = 1, ⋯, N,

i.e. the region R^{a,b} = [a, b] × ∏_{i=1}^{N}[h_{i}(b), h_{i}(a)] is positively invariant.

Proof. Let χ_{g>0} stand for the characteristic function of the set {s : g(s) > 0} where g is an arbitrary function and set η_{q} = (w_{q} − w̄_{q}) and ζ_{i,q} = z_{i,q} − z̄_{i,q}. Then multiplying the error equations for η_{q}, ζ_{i,q} by χ_{η_{q}>0}, −χ_{ζ_{i,q}<0} respectively and summing over i we get:

∂_{t}(η_{q}^{+} + ∑_{i} ζ_{i,q}^{−}) + \frac{1}{h} ∑_{i} Ã_{i}(η_{q} − η_{q−e_{i}})χ_{η_{q}>0} + \frac{1}{h} ∑_{i} A_{i}(ζ_{i,q+e_{i}} − ζ_{i,q})χ_{ζ_{i,q}<0}

= \frac{1}{ε} ∑_{i} [G_{i}(w_{q}, z_{i,q}) − G_{i}(w̄_{q}, z̄_{i,q})][χ_{η_{q}>0} − χ_{ζ_{i,q}<0}].

Observe now that the monotonicity properties of G imply

(4.2)  [G_{i}(w_{q}, z_{q,i}) − G_{i}(w̄_{q}, z̄_{i,q})](χ_{η_{q}>0} − χ_{ζ_{i,q}<0}) ≤ 0.

Also

(4.3)  (η_{q} − η_{q−e_{i}})χ_{η_{q}>0} ≥ η_{q}^{+} − η_{q−e_{i}}^{+} and (ζ_{i,q+e_{i}} − ζ_{i,q})χ_{ζ_{i,q}<0} ≥ −ζ_{i,q+e_{i}}^{−} + ζ_{i,q}^{−}.

Thererefore for each q ∈ ℤ^{N},

∂_{t}(η_{q}^{+} + ∑_{i} ζ_{i,q}^{−}) + \frac{1}{h} ∑_{i} Ã_{i}(η_{q}^{+} − η_{q−e_{i}}^{+}) − \frac{1}{h} ∑_{i} A_{i}(ζ_{i,q+e_{i}}^{−} − ζ_{i,q}^{−}) ≤ 0,

i.e., (i) holds. By summing over q ∈ ℤ^{N} (W (t), Z(t) are in l^{1}(ℤ^{N}) by proposition 4.1), we get (ii).

For (iii), we note that w̄_{q} = b, z̄_{i,q} = h_{i}(b), q ∈ ℤ^{N} is a solution of (3.4). Then (ii) implies w_{q}(t) − b ≤ 0, z_{i,q}(t) − h_{i}(b) ≥ 0 for all q ∈ ℤ^{N}, t > 0. A similar argument gives the lower bounds. □

Discrete Entropies. For any k ∈ ℝ consider the solution (W̄ , Z̄) of (4.1), where w̄_{q} = k, z̄_{i,q} = h_{i}(k), q ∈ ℤ^{N}. It is also clear that Proposition 4.2(i) is valid if we interchange positive with negative parts, thus after summation we get

∂_{t}(|w_{q} − k|+ ∑_{i} |z_{i,q} − h_{i}(k)|) + \frac{1}{h} ∑_{i} Ã_{i}(|w_{q} − k| − |w_{q−e_{i}} − k|)

− \frac{1}{h} ∑_{i} A_{i}(|z_{i,q+e_{i}} − h_{i}(k)| − |z_{i,q} − h_{i}(k)| ≤ 0, q ∈ ℤ^{N}, k ∈ ℝ. (4.4)

Finally we have the following proposition regarding the distance of a solution (W, Z) of (3.4) from the line of equilibria (3.3).

Proposition 4.3. In addition to the assumptions of Proposition 4.4, we assume that (3.2) holds. Let (W, Z) be a solution of (3.4) emanating from data with finite total variation and lying in an (invariant) region R^{a,b}. Then, the following estimate holds:

\frac{1}{ε} ∑_{q∈ℤ^{N}} h^{N} ∑_{i} |G_{i}(w_{q}(t), z_{i,q}(t))| ≤ K + \frac{e^{− \frac{c}{ε} t}}{ε} ∑_{q∈ℤ^{N}} h^{N} ∑_{i} G_{i}(w_{q}^{0}, z_{i,q}^{0}),

wherew c is the constant in (3.2) and K depends on R^{a,b} and the total variation of the initial data W_{0}, Z_{0}.

Proof. We observe

∂_{t}G_{i}(w_{q}(t), z_{i,q}(t)) =\frac{∂G_{i}}{∂w} [ − \frac{1}{h} ∑_{j} Ã_{j}(w_{q}(t) − w_{q−e_{j}}(t)) + \frac{1}{ε} ∑_{j} G_{j}(w_{q}(t), z_{j,q}(t))]

+ \frac{∂G_{i}}{∂z} [\frac{1}{h}A_{i}(z_{i,q+e_{i}}(t) − z_{i,q}(t)) + \frac{1}{ε}G_{i}(w_{q}, z_{i,q})]

Multiplying by signG_{i} and adding, we obtain

∂_{t} ∑_{i} |G_{i}|+\frac{1}{ε} ∑_{i}(−\frac{∂G_{i}}{∂z})|G_{i}| = \frac{1}{ε} ∑_{i} \frac{∂G_{i}}{∂w} signG_{i} ∑_{j} G_{j}

+ ∑_{i} signG_{i}(\frac{∂G_{i}}{∂w} [ − \frac{1}{h} ∑_{j} Ã_{i}(w_{q} − w_{q−e_{j}})] + \frac{∂G_{i}}{∂z} [\frac{1}{h}A_{i}(z_{i,q+e_{i}} − z_{i,q})])

Then, in view of the fact that W, Z are bounded (Proposition 4.2) and the TVD property of the scheme, we have upon summing with respect to q ∈ ℤ^{N},

\frac{d}{dt} ∑_{q∈ℤ^{N}} h^{N} ∑_{i} |G_{i}| + \frac{1}{ε} ∑_{q∈ℤ^{N}} h^{N} ∑_{i} ( − \frac{∂G_{i}}{∂z} − ∑_{j} |\frac{∂G_{j}}{∂w} |)|G_{i}|

≤ C ∑_{q∈ℤ^{N}} h^{N−1} ∑_{i}(|w_{q}^{0} − w_{q−e_{i}}^{0}| + |z_{i,q}^{0} − z_{i,q+e_{i}}^{0}|) ≤ K

We conclude the proof by integrating the above equality and using (3.2). □

4.b Discrete upwind scheme. In this section we present the properties of the discrete scheme (3.5). Proposition 4.4. (L^{1}-contraction, TVD property) Let (W, Z), (W̄ , Z̄) be two solutions of (3.5) with corresponding initial data (W_{0}, Z_{0}), (W̄_{0}, Z̄_{0}) such that W_{0}, Z_{0}, W̄_{0}, Z̄_{0} ∈ l^{1}(ℤ^{N}) ∩ l^{∞}(ℤ^{N}). If the CFL condition

(4.5)  τ_{h} = \frac{τ}{h} ≤ min_{i}\{1/NÃ_{i}, 1/A_{i}\}

is satisfied, then for all n ∈ ℕ, ε > 0,

∑_{q∈ℤ^{N}} (|w_{q}^{n} − w̄_{q}^{n}| + ∑_{i} |z_{i,q}^{n} − z̄_{i,q}^{n}|) ≤ ∑_{q∈ℤ^{N}} (|w_{q}^{0} − w̄_{q}^{0}| + ∑_{i} |z_{i,q}^{0} − z̄_{i,q}^{0}|) .

Furthermore the fully discrete scheme (3.5) is TVD:

∑_{q∈ℤ^{N}} (|w_{q+e_{k}}^{n} − w_{q}^{n}| + ∑_{i} |z_{i,q+e_{k}}^{n} − z_{i,q}^{n}|) ≤ ∑_{q∈ℤ^{N}} (|w_{q+e_{k}}^{0} − w_{q}^{0}| + ∑_{i} |z_{i,q+e_{k}}^{0} − z_{i,q}^{0}|) ,

for all n ∈ ℕ, ε > 0 and all directions e_{k}, k = 1, ..., N. Proof. Without loss of generality we may assume that the initial data vanish outside a ball B_{M} of radius M: due to the finite speed of propagation in (3.5), the solution (W_{n}, Z_{n}) at time t = nτ vanishes outside a ball B_{M+V nτ}, where V = max{A_{i}, Ã_{i} , i = 1, ⋯, N}. Therefore all the summations below are finite, and the statement of the Proposition will follow by eventually sending M → ∞.

Set U_{q}^{n} = w_{q}^{n} − w̄_{q}^{n}, V_{q}^{n} = z_{q}^{n} − z̄_{q}^{n}. Multiplying the error equations for U_{q}^{n} and V_{q}^{n} by signU_{q}^{n+1} and signV_{q}^{n+1} respectively, we obtain:

|U_{q}^{n+1}| + ∑_{i} Ã_{i}((τ_{h} − \frac{1}{NÃ_{i}})U_{q}^{n} − τ_{h}U_{q−e_{i}}^{n})signU_{q}^{n+1}

= \frac{τ}{ε} ∑_{i} [G_{i}(w_{q}^{n+1}, z_{i}^{n+1}) − G_{i}(w̄_{q}^{n+1}, z̄_{i,q}^{n+1})]signU_{q}^{n+1} ,

|V_{i,q}^{n+1}| + [(τ_{h}A_{i} − 1)V_{i,q}^{n} − τ_{h}A_{i}V_{i,q+e_{i}}^{n})]signV_{i,q}^{n+1}

= \frac{τ}{ε} [G_{i}(w_{q}^{n+1}, z_{i,q}^{n+1}) − G_{i}(w̄_{q}^{n+1}, z̄_{i,q}^{n+1})]signV_{i,q}^{n+1} ,

where τ_{h} = \frac{τ}{h}. We add the two relations and sum over q. Due to the monotonicity of G_{i} the right hand side of the resulting equality is nonpositive which yields:

(4.6)

∑_{q∈ℤ^{N}}(|U_{q}^{n+1}| + ∑_{i} |V_{i,q}^{n+1}|)

+ ∑_{i} ∑_{q∈ℤ^{N}} [(τ_{h}Ã_{i} − \frac{1}{N})U_{q}^{n}signU_{q}^{n+1} − τ_{h}Ã_{i}U_{q−e_{i}}^{n}signU_{q}^{n+1}]

+ ∑_{i} ∑_{q∈ℤ^{N}} [(τ_{h}A_{i} − 1)V_{i,q}^{n}signV_{i,q}^{n+1} − τ_{h}A_{i}V_{i,q+e_{i}}^{n}signV_{i,q}^{n+1}] ≤ 0 .

By selecting τ_{h} ≤ min_{i}{1/NÃ_{i}, 1/A_{i}} and using the inequalities

(τ_{h}Ã_{i} − \frac{1}{N})U_{q}^{n}signU_{q}^{n+1} ≥ (τ_{h}Ã_{i} − \frac{1}{N})|U_{q}^{n}|, (τ_{h}A_{i} − 1)V_{i,q}^{n}signV_{i,q}^{n+1} ≥ ((τ_{h}A_{i} − 1)|V_{i,q}^{n}|,

τ_{h}Ã_{i}U_{q−e_{i}}^{n}signU_{q}^{n+1} ≤ τ_{h}Ã_{i}|U_{q−e_{i}}^{n}|, τ_{h}A_{i}V_{i,q+e_{i}}^{n}signV_{i,q}^{n+1} ≤ τ_{h}A_{i}|V_{i,q+e_{i}}^{n}| ,

equation (4.6) yields

\begin{aligned}∑_{q∈ℤ^{N}}(|U_{q}^{n+1}|+ & ∑_{i} |V_{i,q}^{n+1}|) − ∑_{q∈ℤ^{N}}(|U_{q}^{m}| + ∑_{i} |V_{i,q}^{m}|) \\ & + ∑_{i} τ_{h}Ã_{i} ∑_{q∈ℤ^{N}}(|U_{q}^{m}| − |U_{q−e_{i}}^{m}|) + ∑_{i} τ_{h}A_{i} ∑_{q∈ℤ^{N}}(|V_{q}^{m}| − |V_{q+e_{i}}^{m}| ≤ 0 . \end{aligned}

The l^{1}-contraction follows as indicated at the beginning of the proof; the TVD property is a consequence of the l^{1}-contraction and the translation invariance of (3.5). □

As in the case of the semi-discrete scheme, (3.5) satisfies a monotonicity property and an entropy condition. The proof follows along the lines of that of Proposition 4.2.

Proposition 4.5. Under the assumptions of Proposition 4.4 the discrete scheme (3.5) satisfies:

∑_{q∈ℤ^{N}} ((w_{q}^{n+1} − w̄_{q}^{n+1})^{+} + ∑_{i}(z_{i,q}^{n+1} − z̄_{i,q}^{n+1})^{−}) ≤ ∑_{q∈ℤ^{N}} ((w_{q}^{n} − w̄_{q}^{n})^{+} + ∑_{i}(z_{i,q}^{n} − z̄_{i,q}^{n})^{−}) (i)

where the same inequality holds with positive and negative parts interchanged. (ii) (entropy condition). For any k ∈ ℝ,

|w_{q}^{n+1} − k| − |w_{q}^{n} − k| + ∑_{i} (|z_{i,q}^{n+1} − h_{i}(k)| − |z_{i,q}^{n} − h_{i}(k)|)

+ \frac{τ}{h} ∑_{i} Ã_{i}(|w_{q}^{n} − k| − |w_{q−e_{i}}^{n} − k|) − \frac{τ}{h} ∑_{i} A_{i}(|z_{i,q+e_{i}}^{n} − h_{i}(k)| − |z_{i,q}^{n} − h_{i}(k)|) ≤ 0

(iii) If for some a < b the initial approximations satisfy a ≤ w_{q}^{0} ≤ b, h_{i}(b) ≤ z_{i,q}^{0} ≤ h_{i}(a), i = 1, ⋯, N, q ∈ ℤ^{N} then

a ≤ w_{q}^{n} ≤ b, h_{i}(b) ≤ z_{i,q}^{n} ≤ h_{i}(a), q ∈ ℤ^{N}, n ∈ ℕ, i = 1, ⋯, N,

i.e. the region R^{a,b} = [a, b] × ∏_{i=1}^{n}[h_{i}(b), h_{i}(a)] is positively invariant. □

Finally we prove an analogous result to Proposition 4.3:

Proposition 4.6. In addition to the assumptions of Proposition 4.4, we assume that (3.2) holds. Let (W, Z) be a solution of (3.4) emanating from data with finite total variation and lying in an (invariant) region R^{a,b}. Then for all n ∈ ℕ, ε > 0,

∑_{q∈ℤ^{N}} h^{N} ∑_{i} |G_{i}(w_{q}^{n}, z_{i,q}^{n})| ≤ (1 + c\frac{τ}{ε})^{−n} ∑_{q∈ℤ^{N}} h^{N} ∑_{i} |G_{i}(w_{q}^{0}, z_{i,q}^{0})| + εK (i)

(ii) \frac{1}{τ} ∑_{q∈ℤ^{N}} h^{N}(|w_{q}^{n+1} − w_{q}^{n}| + ∑_{i} |z_{i,q}^{n+1} − z_{i,q}^{n}|) ≤ \frac{1}{ε}(1 + c\frac{τ}{ε})^{−n} ∑_{q∈ℤ^{n}} h^{N} ∑_{i} |G_{i}(w_{q}^{0}, z_{i,q}^{0})| + K

where c is the constant in (3.2) and K depends on R^{a,b} and the total variation of the initial data. Proof. We have

G_{i}(w_{q}^{n+1},z_{i,q}^{n+1}) − G_{i}(w_{q}^{n}, z_{i,q}^{n}) =

(w_{q}^{n+1} − w_{q}^{n}) ∫_{0}^{1} \frac{∂G_{i}}{∂w} (w_{q}^{n} + (w_{q}^{n+1} − w_{q}^{n})s, z_{i,q}^{n} + (z_{i,q}^{n+1} − z_{i,q}^{n})s)ds

+ (z_{i,q}^{n+1} − z_{i,q}^{n}) ∫_{0}^{1} \frac{∂G_{i}}{∂z} ((w_{q}^{n} + (w_{q}^{n+1} − w_{q}^{n})s, z_{i,q}^{n} + (z_{i,q}^{n+1} − z_{i,q}^{n})s)ds

= ( ∫_{0}^{1} \frac{∂G_{i}}{∂w} ds)[ − \frac{τ}{h} ∑_{j} Ã_{j}(w_{q}^{n} − w_{q−e_{j}}^{n}) + \frac{τ}{ε} ∑_{j} G_{j}(w_{q}^{n+1}, z_{j,q}^{n+1})]

+ ( ∫_{0}^{1} \frac{∂G_{i}}{∂z} ds)[\frac{τ}{h}A_{i}(z_{i,q+e_{i}}^{n} − z_{i,q}^{n}) + \frac{τ}{ε} G_{i}(w_{q}^{n+1}, z_{i,q}^{n+1})]

We multiply the above equality by sign G_{i}(w_{q}^{n+1}, z_{i,q}^{n+1}):

|G_{i}(w_{q}^{n+1}, z_{i,q}^{n+1})| − |G_{i}(w_{q}^{n}, z_{i,q}^{n})| − \frac{τ}{ε} ( ∫_{0}^{1} \frac{∂G_{i}}{∂z} ds)|G_{i}(w_{q}^{n+1}, z_{i,q}^{n+1})|

− \frac{τ}{ε} ( ∫_{0}^{1} |\frac{∂G_{j}}{∂w} |) ∑_{j} |G_{i}(w_{q}^{n+1}, z_{j,q}^{n+1})|

≤ C \frac{τ}{h} ∑_{j} |w_{q}^{n} − w_{q−e_{j}}^{n}| + c̃\frac{τ}{h}|z_{i,q}^{n} − z_{i,q+e_{i}}| ,

where C depends on R^{a,b}. We again multiply the above inequality by h^{N}, we sum over i, q and use (3.2) to obtain

(1 + c\frac{τ}{ε}) ∑_{q∈ℤ^{N}} h^{N} ∑_{i} |G_{i}(w_{q}^{n+1}, z_{i,q}^{n+1})| ≤ ∑_{q∈ℤ^{N}} h^{N} ∑_{i} |G_{i}(w_{q}^{n}, z_{i,q}^{n})|

+ Cτ ∑_{q∈ℤ^{N}} h^{N−1} ∑_{i} |w_{q}^{n} − w_{q−e_{i}}^{n}| + Cτ ∑_{q∈ℤ^{N}} h^{N−1} ∑_{i} |z_{i,q}^{n} − z_{i,q+e_{i}}|

where c is given in (3.3). We use the above inequality and the TVD property of the discrete scheme to get

(1 + c\frac{τ}{ε}) ∑_{q∈ℤ^{N}} h^{N} ∑_{i} |G_{i}(w_{q}^{n+1}, z_{i,q}^{n+1})| ≤ ∑_{q∈ℤ^{N}} h^{N} ∑_{i} |G_{i}(w_{q}^{n}, z_{i,q}^{n})| + τK

where K depends on R^{a,b} and the total variation of the initial data. By means of the last inequality we conclude

(1 + c\frac{τ}{ε})^{n} ∑_{q∈ℤ^{N}} h^{N} ∑_{i} |G_{i}(w_{q}^{n}, z_{i,q}^{n})| ≤ ∑_{q∈ℤ^{N}} h^{N} ∑_{i} |G_{i}(w_{q}^{0}, z_{i,q}^{0})| + τK ∑_{k=0}^{n−1}(1 + c\frac{τ}{ε})^{k}

which implies (i). We obtain inequality (ii) directly from (3.5),

\frac{1}{τ} |w_{q}^{n+1} − w_{q}^{n}| ≤ \frac{V}{h} ∑_{i} |w_{q} − w_{q−e_{i}}| + \frac{1}{ε} ∑_{i} |G_{i}(w_{q}^{n}, z_{i,q}^{n})| ,

the corresponding estimate for the z_{i,q}^{n} terms, (i) and the TVD property of the scheme. □

5. Convergence

We first consider the semi-discrete scheme defined by (3.4). Let Ω_{q} ⊂ ℝ^{N} the rectangular region with side length h and center at the q ∈ ℤ^{N} grid point and let (W^{h}, Z^{h}) the piecewise constant approximation function defined by

(5.1)  (W^{h,ε}(t, ·)|_{Ω_{q}}, Z^{h,ε}(t, ·)|_{Ω_{q}}) = (w_{q}(t), z_{1,q}(t), ⋯, z_{n,q}(t)) .

We consider initial data (W_{0}^{h,ε}, Z_{0}^{h,ε}) lying close to the line of equilibria, in the sense

(5.2)  ∑_{i} ||G_{i}(W_{0}^{h,ε}, Z_{i0}^{h,ε})||_{L^{1}} = O(ε) .

We then have the following theorem:

Theorem 5.1. Let (W^{h,ε}, Z^{h,ε}) be the piecewise constant functions (5.1) obtained by solutions of (3.4), with initial data (W_{0}^{h,ε}, Z_{0}^{h,ε}) ∈ BV (ℝ^{N}) ∩ L^{∞}(ℝ^{N}) and satisfying assumption (5.2). Let u be the entropy solution of (1.1) and U^{h,ε} = W^{h,ε} − ∑_{i} Z_{i}^{h,ε}. Then, for any fixed T > 0 and all t ≤ T,

(5.3)  ||U^{h,ε}(t, ·) − u(t, ·)||_{L^{1}} ≤ ||U^{h,ε}(0, ·) − u(0, ·)||_{L^{1}} + Ĉ\sqrt{ε + h} .

Here, Ĉ is a positive constant depending on the fluxes F^{i}, the L^{∞} norms and the total variation of (W_{0}^{h,ε}, Z_{0}^{h,ε}) and u_{0} = u(0, ·).

Proof. We first show that U^{h,ε} satisfies an approximate entropy condition similar to (2.1). For all k ∈ ℝ, define κ ∈ ℝ such that k = κ−∑_{i} h_{i}(κ) . Since the functions h_{i}, i = 1, ⋯, N are nonincreasing, we readily see that

|U^{h,ε} − k||_{Ω_{q}} = |w_{q} − κ| + ∑_{i} |h_{i}(w_{q}) − h_{i}(κ)| = |w_{q} − κ| + ∑_{i} |z_{i,q} − h_{i}(κ)| + J^{h,ε}(x, t) ,

where |J^{h,ε}(t, x)| ≤ ∑_{i} |G_{i}(W^{h,ε}(t, x), Z_{i}^{h,ε}(t, x))|. Similarly,

(F_{i}(U^{h,ε}) − F_{i}(k))sign(U^{h,ε} − k)|_{Ω_{q}} = [A_{i}ω_{i}(w_{q} − κ) + A_{i}(h_{i}(w_{q}) − h_{i}(κ))]sign(w_{q} − κ)

= A_{i}ω_{i}|w_{q} − κ| − A_{i}|h_{i}(w_{q}) − h_{i}(κ)|

= A_{i}ω_{i}|w_{q} − κ| − A_{i}|z_{i,q} − h_{i}(κ)| + H_{i}^{h,ε} ,

where ∑_{i} |H_{i}^{h,ε}(t, x)| ≤ V ∑_{i} |G_{i}(W^{h,ε}(t, x), Z_{i}^{h,ε}(t, x))|. If Ψ ∈ C_{c}^{∞}([0, ∞) × ℝ^{n}), Ψ ≥ 0, then

I(k, Ψ) = − ∫∫ (|U^{h,ε} − k|Ψ_{t} + ∑_{i}(F_{i}(U^{h,ε}) − F_{i}(k))sign(U^{h,ε} − k)Ψ_{x_{i}})dxdt

= − ∑_{q} ∫ dt((|w_{q} − κ| + ∑_{i} |z_{i,q} − h_{i}(κ)|) ∫_{Ω_{q}} Ψ_{t}dx) − ∫∫ J^{h,ε}Ψ_{t}dxdt

− ∑_{i} [ ∑_{q} ∫ dt(A_{i}ω_{i}|w_{q} − κ| − A_{i}|z_{i,q} − h_{i}(κ)|) ∫_{Ω_{q}} Ψ_{x_{i}}dx] − ∑_{i} ∫∫ H_{i}^{h,ε}(x, t)Ψ_{x_{i}}dxdt

= − ∑_{q} ∫ dt((|w_{q} − κ| + ∑_{i} |z_{i,q} − h_{i}(κ)|) ∫_{Ω_{q}} Ψ_{t}dx)

− ∑_{i} ∫ dtA_{i} ∑_{q} ((ω_{i}|w_{q} − κ| − |z_{i,q} − h_{i}(κ)|)\frac{1}{h} ∫_{Ω_{q}}(Ψ|_{x_{i}=h(q+ \frac{1}{2} e_{i})} − Ψ|_{x_{i}=h(q− \frac{1}{2} e_{i})})dx)

− ∑_{i} ∫∫ H_{i}^{h,ε}(x, t)Ψ_{x_{i}}dxdt − ∫∫ J^{h,ε}Ψ_{t}dxdt

= − ∑_{q} ∫_{ℝ} dt((|w_{q} − κ| + ∑_{i} |z_{i,q} − h_{i}(κ)|) ∫_{Ω_{q}} Ψ_{t}dx)

+ ∑_{i} ∫ dt(A_{i}ω_{i} ∑_{q}(|w_{q} − κ| − |w_{q−e_{i}} − κ|)\frac{1}{h} ∫_{Ω_{q}} Ψ|_{x_{i}=h(q− \frac{1}{2} e_{i})}dx)

− ∑_{i} ∫ dt(A_{i} ∑_{q}(|z_{i,q+e_{i}} − κ| − |z_{i,q} − κ|)\frac{1}{h} ∫_{Ω_{q}} Ψ|_{x_{i}=h(q+ \frac{1}{2} e_{i})}dx)

− ∑_{i} ∫∫ H_{i}^{h,ε}Ψ_{x_{i}}dxdt − ∫∫ J^{h,ε}Ψ_{t}dxdt

Using the discrete entropy inequality we obtain

I(κ, Ψ) ≤ ∑_{i} A_{i}ω_{i} ∫ dt( ∑_{q}(|w_{q} − κ| − |w_{q−e_{i}} − κ|)\frac{1}{h} ∫_{Ω_{q}}(Ψ|_{x_{i}=h(q− \frac{1}{2} e_{i})} − Ψ)dx)

− ∑_{i} A_{i} ∫ dt( ∑_{q}(|z_{i,q+e_{i}} − κ| − |z_{i,q} − κ|)\frac{1}{h} ∫_{Ω_{q}}(Ψ|_{x_{i}=h(q+ \frac{1}{2} e_{i})} − Ψ)dx)

− ∑_{i} ∫∫ H_{i}^{h,ε}(x, t)Ψ_{x_{i}}dxdt − ∫∫ J^{h,ε}Ψ_{t}dxdt .

The first term on the right hand-side of the inequality is bounded by

∑_{i} A_{i}ω_{i} ∫ dt( ∑_{q}(|w_{q} − w_{q−e_{i}}|)\frac{1}{h} ∫_{Ω_{q}} |Ψ|_{x_{i}=h(q− \frac{1}{2} e_{i})} − Ψ|dx),

and the second term by

∑_{i} A_{i} ∫ dt( ∑_{q}(|z_{i,q+e_{i}} − z_{i,q}|)\frac{1}{h} ∫_{Ω_{q}} |Ψ|_{x_{i}=h(q+ \frac{1}{2} e_{i})} − Ψ|dx).

To apply Theorem 2.1 note that the partition of [0, ∞) × ℝ^{n} consisting by [0, ∞) × Ω_{q}, q ∈ ℤ^{N} defines a partition of supp Ψ, T_{h} = {K^{q}}, simply by taking K^{q} = ( [0, ∞) × Ω_{q}) ∩ supp Ψ. Then we define for V = max_{i}{A_{i}, A_{i}ω_{i}},

B_{H}^{i}(∂_{x_{i}}Ψ)|_{K^{q}} = \frac{V}{h} (|Ψ|_{x_{i}=h(q− \frac{1}{2} e_{i})} − Ψ| + |Ψ|_{x_{i}=h(q+ \frac{1}{2} e_{i})} − Ψ|),

and

β_{H}^{i}(t, x)|_{K^{q}} = |w_{q} − w_{q−e_{i}}| + |z_{i,q+e_{i}} − z_{i,q}| .

Then B_{H}^{i}, satisfies (2.4). The TVD property of the semidiscrete approximation implies

∑_{i} ∫∫ β_{H}^{i}dtdx ≤ T hT V (W_{0}^{h,ε}, Z_{0}^{h,ε})

where T V (W_{0}^{h,ε}, Z_{0}^{h,ε}) = T V (W_{0}^{h,ε})+T V (Z_{0}^{h,ε}) and T V (Z_{0}^{h,ε}) = ∑_{i} ∑_{q} h^{N−1}|z_{i,q+e_{i}}^{0}−z_{i,q}^{0}|, T V (W_{0}^{h,ε}) = ∑_{i} ∑_{q} h^{N−1}|w_{q+e_{i}}^{0}−w_{q}^{0}|. Since all the hypotheses of Theorem 2.1 are satisfied, sending δ → 0, R → ∞, delivers

||U^{h,ε}(·, T) − u(·, T)||_{L^{1}(ℝ^{N})} ≤ ||U^{h,ε}(·, T) − u(·, T)||_{L^{1}(ℝ^{N})} + C[ΔT V (u_{0})

+ \frac{T h}{Δ}T V (W_{0}^{h,ε}, Z_{0}^{h,ε}) + (1 + \frac{(M + 1)T}{Δ} ) sup_{0≤t≤2T} ∫_{ℝ^{N}} ∑_{i} |G_{i}(W^{h,ε}(x, t), Z_{i}^{h,ε}(x, t)|dxdt

+ \frac{1}{Δ} ∑_{i} ∫∫_{0≤t≤T, x∈ℝ^{N}} |G_{i}(W^{h,ε}(x, t), Z_{i}^{h,ε}(x, t)|dxdt] .

Setting I^{h,ε} = sup_{[0,2T]} ∑_{i} ||G_{i}(W^{h,ε}(·, t), Z_{i}^{h,ε}(·, t)||_{L^{1}}, we get

||U^{h,ε}(·, T) − u(·, T)||_{L^{1}} ≤||U^{h,ε}(·, 0) − u(·, 0)||_{L^{1}}

+ C[ΔT V (u_{0}) + \frac{T h}{Δ}T V (W_{0}^{h,ε}, Z_{0}^{h,ε}) + I^{h,ε} + \frac{(M + 2)T I^{h,ε}}{Δ} ].

By considering the minimum of the right-hand side of (4.6) over Δ we get

||U^{h,ε}(·, T) − u(·, T)|| ≤||U^{h,ε}(·, 0) − u(·, 0)||_{L^{1}(ℝ^{N})}
+ C[I^{h,ε} + T^{1/2}\sqrt{T V (W_{0}^{h,ε}, Z_{0}^{h,ε})T V (u_{0})h + (M + 2)T V (u_{0})I^{h,ε}} ],

In view of the above inequality and Proposition 4.3 we conclude the proof of the theorem. □

Remark. 5.1 The previous analysis applies directly to the semidiscrete upwind relaxation scheme introduced in [9] for the scalar one dimensional conservation law, based on the relaxation approximation,

(5.4)  \{ \begin{matrix}u_{t} + v_{x} = 0 , & (t, x) ∈ (0, ∞) × ℝ \\ v_{t} + c^{2}u_{x} = −\frac{1}{ε}[v − f(u)] , & (t, x) ∈ (0, ∞) × ℝ . \end{matrix}

As the relaxation parameter ε → 0, the local equilibrium v = f(u) is enforced, yielding the scalar equation [18],

u_{t} + f(u)_{x} = 0 , (t, x) ∈ (0, ∞) × ℝ ,

provided the following subcharacteristic condition holds:

−c < f′(u) < c .

The approximating scheme for (5.4), introduced in [9] is

\begin{matrix}\frac{∂}{∂t}u_{j} + \frac{1}{2γ} [v_{j+1} − v_{j−1}] − \frac{1}{2γ} c[u_{j+1} − 2u_{j} + u_{j−1}] = 0, \\ \frac{∂}{∂t}v_{j} + \frac{1}{2γ} c^{2}[u_{j+1} − u_{j−1}] − \frac{1}{2γ} c[v_{j+1} − 2v_{j} + v_{j−1}] = −\frac{1}{ϵ}[v_{j} − f(u_{j})] . \end{matrix}

Rewriting the semidiscrete system in Riemann invariants,

w_{j} = v_{j} + cu_{j}, z_{j} = v_{j} − cu_{j} ,

we have

\begin{matrix}\frac{∂}{∂t}w_{j} + \frac{c}{γ} [w_{j} − w_{j−1}] = \frac{1}{ϵ}G(w_{j}, z_{j}) \\ \frac{∂}{∂t}z_{j} − \frac{c}{γ} [z_{j+1} − z_{j}] = \frac{1}{ϵ}G(w_{j}, z_{j}) , \end{matrix}

where G(w, z) = f(\frac{w−z}{2c}) − \frac{w+z}{2} . If the subcharacteristic condition is met, then G is separately nonincreasing in both variables and the previous results hold for this case also.

We next obtain a convergence rate for the fully discrete scheme (3.5). We first define the piecewise constant approximation function given by

(5.5)  (W^{τ,h,ε}(·, ·)|_{Ω_{q}×[nτ,(n+1)τ)}, Z^{τ,h,ε}(·, ·)|_{Ω_{q}×[nτ,(n+1)τ)}) = (w_{q}^{n}, z_{1,q}^{n}, ⋯, z_{N,q}^{n}).

Since the proof follows the lines of Theorem 5.1 we only consider the extra terms that appear in (3.5) due to the time discretization.

Theorem 5.2. Let (W^{τ,h,ε}, Z^{τ,h,ε}) be the piecewise constant functions (5.5) obtained by solutions of (3.5), with initial data (W_{0}^{h,ε}, Z_{0}^{h,ε}) ∈ BV (ℝ^{N}) ∩ L^{∞}(ℝ^{N}) and satisfying assumption (5.2). Let u be the entropy solution of (1.1) and U^{τ,h,ε} = W^{τ,h,ε} − ∑_{i} Z_{i}^{τ,h,ε}. Then, if the CFL condition (4.5) is satisfied, then for any fixed T > 0 and all t ≤ T, ε > 0,

(5.6)  ||U^{τ,h,ε}(t, ·) − u(t, ·)||_{L^{1}} ≤ ||U^{τ,h,ε}(0, ·) − u(0, ·)||_{L^{1}} + C̃\sqrt{ε + τ + h} ,

Here, C̃ is a positive constant depending on the fluxes F^{i}, the L^{∞} norms and the total variation of (W_{0}^{h,ε}, Z_{0}^{h,ε}) and u_{0} = u(0, ·). Proof. We only consider in the sequel the contribution of the time derivative in (2.1). We have,

− ∫∫ |U^{τ,h,ε} − k|Ψ_{t}dtdx =

= − ∑_{q} ∑_{n} (|w_{q}^{n} − κ| + ∑_{i} |z_{i,q}^{n} − h_{i}(k)|) ∫_{Ω_{q}} ∫_{I_{n}} Ψ_{t}dtdx − ∫∫ J^{τ,h,ε}Ψ_{t}dtdx

= − ∑_{q} ∑_{n} (|w_{q}^{n} − κ| + ∑_{i} |z_{i,q}^{n} − h_{i}(k)|) ∫_{Ω_{q}}[Ψ((n + 1)τ, ·) − Ψ(nτ, ·)]dx

− ∫∫ J^{τ,h,ε}Ψ_{t}dtdx

= ∑_{q} ∑_{n} ((|w_{q}^{n+1} − κ| − |w_{q}^{n} − κ|)+

+ ∑_{i} (|z_{i,q}^{n+1} − h_{i}(k)| − |z_{i,q}^{n} − h_{i}(k)|)) ∫_{Ω_{q}} Ψ((n + 1)τ, ·)dx − ∫∫ J^{τ,h,ε}Ψ_{t}dtdx

= ∑_{q} ∑_{n} ((|w_{q}^{n+1} − κ| − |w_{q}^{n} − κ|)+

+ ∑_{i} (|z_{i,q}^{n+1} − h_{i}(k)| − |z_{i,q}^{n} − h_{i}(k)|))\frac{1}{τ} ∫_{Ω_{q}} ∫_{I_{n}} Ψ(t, x)dtdx

+ ∑_{q} ∑_{n} ((|w_{q}^{n+1} − κ| − |w_{q}^{n} − κ|)+

+ ∑_{i}(|z_{i,q}^{n+1} − h_{i}(k)| − |z_{i,q}^{n} − h_{i}(k)|))\frac{1}{τ} ∫_{Ω_{q}} ∫_{I_{n}} (Ψ(t, x)|_{t=(n+1)τ} − Ψ(t, x))dtdx

− ∫∫ J^{τ,h,ε}Ψ_{t}dtdx,

where I_{n} = [nτ, (n + 1)τ) and |J^{τ,h,ε}(t, x)| ≤ ∑_{i} |G_{i}(W^{τ,h,ε}(t, x), Z_{i}^{τ,h,ε}(t, x))|. That is, the time discretization will contribute the extra term

∑_{q} ∑_{n} [\frac{1}{τ} |w_{q}^{n+1} − w_{q}^{n}| + \frac{1}{τ} ∑_{i} |z_{i,q}^{n+1} − z_{i,q}^{n}|] ∫_{Ω_{q}} ∫_{nτ}^{(n+1)τ} |Ψ(t, x)|_{t=(n+1)τ} − Ψ(t, x)|dtdx

to the bound of the discrete entropy I(k, Ψ). Following the notation of Theorem 2.1, for K^{n,q} = (I_{n} × Ω_{q}) ∩ supp Ψ, define the function

B_{G}(∂_{t}Ψ)|_{K^{n,q}} = \frac{1}{τ} |Ψ(t, x)|_{t=(n+1)τ} − Ψ(t, x)|,

and

β_{G}(t, x)|_{K^{n,q}} = |w_{q}^{n+1} − w_{q}^{n}| + ∑_{i} |z_{i,q}^{n+1} − z_{i,q}^{n}|.

It is clear that B_{G}(∂_{t}Ψ) satisfies (2.4). By Proposition 4.6(ii), we have that β_{G} satisfies (2.2) and

sup_{0≤t≤2T} ∫ β_{G} dx ≤ τ[\frac{1}{ε}(1 + c\frac{τ}{ε})^{−n} ∑_{q∈ℤ^{n}} h^{N} ∑_{i} |G_{i}(w_{q}^{0}, z_{i,q}^{0})| + K] ≤ τK̂ ,

where K̂ is a positive constant depending on the L^{∞} norm and the total variation of the data, as well

as the assumption (5.2).

The spatial terms (that give rise to the β_{H}^{j} terms in Theorem 2.1) are handled as in Theorem 5.1.

Following the lines of the proof of Theorem 5.1 we conclude by minimizing over Δ the quantity (we

take δ = Δ)

\frac{C}{Δ}[T hT V (W_{0}^{h,ε}, Z_{0}^{h,ε}) + (M + 2)T I^{τ,h,ε} + K̂(M + 1)T τ] + C(M + 1)ΔT V (u_{0}) + CI^{τ,h,ε} + τK̂ ,

where I^{τ,h,ε} is the corresponding quantity to I^{h,ε} in the proof of Theorem 5.1. □

Acknowledgments. The authors would like to thank A. Tzavaras for his interest in this work and

many valuable discussions. The reaserch of M. Katsoulakis is partially supported by NSF grant No.

DMS-9500717. The research of G. Kossioris and Ch. Makridakis is partially supported by European

Union TMR grant No. FMRXCT960033.

References

[1] D. Aregba-Driollet and R. Natalini, Convergence of relaxation schemes for conservation laws, (1996), (preprint).

[2] Bouchut, C. Bourdarias and B. Perthame, A MUSCL method satisfying all the numerical entropy inequalities, Math. Comp. 65 (1996), 1439-1461.

[3] Bouchut and B. Perthame, Kruzhkov’s estimates for scalar conservation laws revisited, Univ. of Orleans no. 96-02, (1996), (preprint).

[4] G.-Q. Chen, C. D. Levermore and T.-P. Liu, Hyperbolic conservation laws with stiff relaxation terms and entropy, Comm. Pure Appl. Math. 47 (1994), 789-830.

[5] B. Cockburn, F. Coquel and P. LeFloch, An error estimate for finite volume methods for conservation laws, Math. Comp. 64 (1994), 77-103.

[6] B. Cockburn and P.-A. Gremaud, Error estimates for finite element methods for scalar conservation laws, SIAM J. Numer. Anal. 33 (1996), 522-554.

[7] B. Cockburn and P.-A. Gremaud, A priori error estimates for numerical methods for scalar scalar conservation laws. Part I: The general approach, Math Comp 65 (1996), 533-573.

[8] R.J. DiPerna, Measure-valued solutions to conservation laws, Arch. Rational Mech. Anal. 88 (1985), 223-270.

[9] S. Jin and Z. Xin, The relaxing schemes for systems of conservation laws in arbitrary space dimensions, Comm. Pure Appl. Math. 48 (1995), 235-277.

[10] T. Katsaounis and Ch. Makridakis, Finite volume relaxation schemes for conservation laws, (in preparation).

[11] M.A. Katsoulakis and A.E. Tzavaras, Contractive relaxation systems and the scalar multidimensional conservation law, Comm. P.D.E 22 (1997), 195-233.

[12] M.A. Katsoulakis and A.E. Tzavaras, I. Contractive relaxation systems and interacting particles for scalar conservation laws, C. R. Acad. Sci. Paris I 323 (1996), 865-870. II. Interacting particle systems with relaxation to a scalar conservation law, (in preparation).

[13] S.N. Kruzhkov, First order quasilinear equations with several independent variables, Math. USSR Sbornik 10 (1970), 217-243.

[14] N.N. Kuznetzov, 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-119.

[15] R. J. LeVeque and H. C. Yee, A study of numerical methods for hyperbolic conservation laws with stiff terms, J. Comp. Phys. 86 (1990), 187-210.

[16] T.-P. Liu, Hyperbolic conservation laws with relaxation, Comm. Math. Phys. 108 (1987), 153-175.

[17] B. J. Lucier, A moving mesh numerical method for hyperbolic conservation laws, Math. Comp. 40 (1983), 91-106.

[18] R. Natalini, Convergence to equilibrium for the relaxation approximations of conservation laws, Comm. Pure Appl. Math. 8 (1996), 795-823.

[19] R. Sanders, On convergence of monotone finite difference schemes with variable spatial differencing, Math. Comp. 40 (1983), 91-106.

[20] H. J. Schroll, A. Tveito and R. Winther, An L^{1} error bound for a semi-implicit difference scheme applied to a stiff system of conservation laws, SIAM J. Num. Analysis, (to appear).

[21] W. Shen, A. Tveito and R. Winther, A system of conservation laws including a stiff term; the 2D case, BIT 36 (1996), 786-813.

[22] J.-P. Vila, Convergence and error estimates in finite volume schemes for general multidimensional scalar conservation laws, Math. Mod. Numer. Anal. 28 (1994), 267-295.

M. A. Katsoulakis Department of Mathematics and Statistics, University of Massachusetts, Amherst, MA 01003. markos@math.umass.edu

G. Kossioris and Ch. Makridakis Department of Mathematics, University of Crete, Heraklion, 71409 Greece and Institute for Applied and Computational Mathematics, FORTH, Heraklion, 71 110 Greece. kosioris@math.uch.gr makr@math.uch.gr