Franc ¸ois Dubois
email: francois.dubois@math.univ-psud.fr.

Nonlinear Interpolation and Total Variation Diminishing Schemes

Keywords: nonlinear interpolation, finite differences, total variation AMS classification. Primary : 65M05, secondary : 65M10, 65M20

The Van Leer approach for the approximation of nonlinear scalar conservation laws is studied in one space dimension. The problem can be reduced to a nonlinear interpolation and we propose a convexity property for the interpolated values. We prove that under general hypotheses the method of lines in well posed in ℓ ∞ ∩ BV and we give precise sufficient conditions to establish that the total variation is diminishing. We observe that the second order accuracy can be maintained even at non sonic extrema. We establish also that both the TVD property and second order accuracy can be maintained after discretization in time with the second order accurate Heun scheme. Numerical illustration for the advection equation is presented.

Interpolation non linéaire et schémas à variation totale décroissante

Résumé

Nous étudions le schéma de Van Leer pour l'approximation de lois de conservation scalaires à une dimension d'espace. Nous proposons une propriété de convexité de l'interpolation non linéaire associée à cette méthode. Nous prouvons que sous des hypothèses générales, le schéma continu en temps conduit à un problème bien

Introduction

We consider the following scalar conservation law :

(1.1) ∂u ∂t + ∂ ∂x f (u) = 0 , x ∈ IR , t > 0 , u(x, t) ∈ IR where the flux function f is supposed to be a convex regular (C 2 class) real function. The initial condition takes the form (1.2) u(x, 0) = u 0 (x) ,

x ∈ IR and we assume that the initial datum u 0 satisfies :

(1.3) u 0 ∈ L ∞ (IR) ∩ BV(IR) .

• Even for smooth initial datum u 0 , a classical solution of the Cauchy problem (1.1).(1.2) does not exist in general (e.g. [START_REF] Smoller | Shock Waves and Reaction Diffusion Equations[END_REF]) and we consider in this paper weak solutions of the problem (1.1).(1.2), i.e. functions u ∈ L ∞ (IR × [0, +∞[) such that (1.4)

IR×IR + u ∂ϕ ∂t + f (u) ∂ϕ ∂x dx dt = 0 , ∀ϕ ∈ C 1 0 (IR×]0, +∞[) and (1.5) lim t -→ 0 || u(•, t) -u 0 (•) || L 1 (IR) = 0 .  •
The uniqueness of a weak solution satisfying (1.4).(1.5) is guaranteed if we consider [START_REF] Lax | Shock Waves and Entropy[END_REF]) only entropy solutions of the conservation law (1.1), i.e. weak solutions also satisfying (1.6)

IR×IR + η(u) ∂ϕ ∂t + ξ(u) ∂ϕ ∂x dx dt ≤ 0 , ∀ϕ ∈ C 1 0 (IR×]0, +∞[) , ϕ ≥ 0
where η : IR -→ IR is a strictly convex entropy and ξ : IR -→ IR is the associated entropy flux :

(1.7) [START_REF] Kruskov | First Order Quasilinear Equations with Several Space Variables[END_REF] proved that a weak solution of (1.1).(1.2) satisfying the inequalities (1.6) for all the choices of entropies (1.8) is necessarily unique. More recently, Di [START_REF] Perna | Convergence of Approximate Solutions to Conservation Laws[END_REF] proved that uniqueness is implied if the inequality (1.6) is valid for a single strictly convex entropy η.

ξ ′ (u) = η ′ (u) • f ′ (u) . With the particular choice (1.8) η c (u) = | u -c | , c ∈ IR ,

•

The approximation of (1.4)-(1.6) by finite volume numerical schemes is a very classical problem. In this paper, we first look at approximations that are discrete in space and continuous in time (method of lines). Let h > 0 be a real parameter and x j = j h be the associated mesh points. Following [START_REF] Godunov | A finite Difference Method for the Numerical Computation of Discontinuous Solutions of the Equations of Fluid Dynamics[END_REF], we search an approximation u j (t) which is constant in the interval I j ≡ j -1 2 h , j + 1 2 h :

(1.9) u j (t) ≈ 1 h

(j+ 1 2 ) h (j-1 2 ) h u(x, t) dx , j ∈ Z Z , t > 0 .
As was recognized by [START_REF] Lax | Systems of Conservation Laws[END_REF], we require u j (t) to satisfy a conservative numerical scheme :

(1.10)

du j dt + 1 h f j+ 1 2 -f j-1 2 = 0 , j ∈ Z Z , t > 0 .
• The system of ordinary differential equations (1.10) is now completely defined if we prescribe the initial conditions and the numerical flux f j+ 1 2 . Three point numerical schemes are parameterized by the numerical flux function Φ : (1.11) f j+ 1 2 = Φ(u j , u j+1 ) which is supposed to be Lipschitz continuous and consistent with the flux f : (1.12) Φ(u , u) ≡ f (u) , u ∈ IR . The numerical flux realizes some approximation of the Godunov flux (we refer to [START_REF] Harten | On Upstream Differencing and Godunov-type Schemes for Hyperbolic Conservation Laws[END_REF] for the details). Following [START_REF] Crandall | Monotone Difference Approximations for Scalar Conservation Laws[END_REF],

 the flux f of relation (1.11) is monotone if (u, v) -→ Φ(u, v) is a nondecreasing (respectively nonincreasing) function of u (resp. v). [START_REF] Kusnezov | On Monotone Difference Approximations for a First-order Quasi-linear Equation[END_REF] and [START_REF] Crandall | Monotone Difference Approximations for Scalar Conservation Laws[END_REF] have extended to monotone schemes the proof of convergence towards the entropy solution developed by [START_REF] Leroux | Convergence of the Godunov Scheme for First Order Quasilinear Equations[END_REF] for the Godunov scheme (when the equation (1.10) is also discretized in time). [START_REF] Sanders | On Convergence of Monotone Finite Difference Schemes With Variable Spatial Differencing[END_REF] proved that on irregular meshes, the solutions of the ODE (1.10) also converges to the entropy solution of (1.4)-(1.6) as h tends to zero. [START_REF] Osher | Riemann Solvers, the Entropy Condition, and Difference Approximations[END_REF] with the "E-schemes" extended the notion of monotone schemes to take into account non necessarily convex fluxes. The major default of three point monotone schemes is that they can have at best first order accuracy.

•

High resolution schemes (that are in general five point numerical schemes) have been proposed to overcome this lack of precision. On one hand, [START_REF] Harten | High Resolution Schemes for Hyperbolic Conservation Laws[END_REF] introduced the notion of total variation diminishing (TVD) schemes ; if the discrete total variation (1.13) TV(t)

≡ j∈Z Z | u j+1 (t) -u j (t) |
is a nonincreasing function of time, then the scheme (1.10) is said to be TVD. Monotone schemes are particular cases of TVD schemes and Harten gave sufficient conditions (generalized by [START_REF] Sanders | On Convergence of Monotone Finite Difference Schemes With Variable Spatial Differencing[END_REF] for the method of lines) to ensure that a numerical scheme is TVD. Unfortunately, three point TVD schemes are at most first order accurate and [START_REF] Harten | High Resolution Schemes for Hyperbolic Conservation Laws[END_REF] constructed second order numerical schemes by modifying the first order flux (1.11) into a five point scheme in a way analogous to the Flux Corrected Transport (FCT) of [START_REF] Boris | Flux Corrected Transport I. SHASTA, A Fluid Transport Algorithm That Works[END_REF].

• On the other hand, the "Multidimensional Upstream centered Scheme for Conservation Laws" (MUSCL) approach proposed by Van Leer [1979] (see also [START_REF] Colella | A Direct Eulerian MUSCL Scheme for Gas Dynamics[END_REF]) assumes that a piecewise linear interpolation is reconstructed from the mean values u j (t) :

(1.14) u h (x, t) = u j (t) + s j (t) (x -x j ) , x ∈ I j , j ∈ Z Z .

The slopes s j are chosen as nonlinear functions of the three mean values at the points j -1, j, j + 1 :

(1.15) s j = S(u j-1 , u j , u j+1 ) in such a way that the reconstruction (1.14) satisfies some monotonicity restrictions [START_REF] Van Leer | Towards the Ultimate Conservative Scheme IV. A New Approach to Numerical Convection[END_REF], see also [START_REF] Sweby | High Resolution Schemes Using Flux Limiters for Hyperbolic Conservation Laws[END_REF] for a unified vision of the flux limiters).

The function x -→ u h (x, t) is a priori discontinuous at the points x j+ 1 2 ; the two values u ± j+ 1 2 are defined on each side of x j+ 1 2 :

 (1.16)(a) u - j+ 1 2 = u j (t) + h 2 S(u j-1 , u j , u j+1 ) (1.16)(b) u + j+ 1 2 = u j+1 (t) - h 2 S(u j , u j+1 , u j+2 ) .
The flux function f j+ 1 2 is computed as in the Godunov scheme, but with the latter two values as arguments :

(1.17)

f j+ 1 2 = Φ u - j+ 1 2 , u + j+ 1 2 , t ≥ 0 , j ∈ Z Z .
The theoretical convergence properties of MUSCL schemes have been studied by [START_REF] Osher | Convergence of generalized MUSCL schemes[END_REF]. He gave sufficient conditions to establish that the scheme (1.10).(1.17) is TVD and proved under some restrictions the convergence to the entropy solution (using a discrete entropy inequality proposed in [START_REF] Osher | Riemann Solvers, the Entropy Condition, and Difference Approximations[END_REF]). Moreover second order accuracy is realized even at regular extrema which are not sonic points, i.e. values of u such that

(1.18) f ′ (u) = 0 .
This fact was recognized by [START_REF] Osher | High Resolution Schemes and the Entropy Condition[END_REF]. The MUSCL approach has been extended to higher orders by Collela-Woodward [1984] (PPM method) and by Harten et al [1987] with the so-called ENO schemes.

•

The main purpose of this paper is to show how to choose nonlinear interpolation formulae like (1.16) in order to get a TVD scheme. In the second part of this paper we propose some natural limitations on the interpolated values between two mesh points and we establish in the third part sufficient conditions that prove that the resulting scheme is TVD. In part IV, we demonstrate that the second order accuracy is obtained in all smooth parts of the flow. In part V we dicretize the method of lines in time and we precise conditions to maintain both the TVD property and second order accuracy in smooth regions. In the last part we present some numerical experiments for the advection equation with periodic boundary conditions.

Some Limitations for the Interface Values

We recall that a sequence of values u j is supposed to be given at the points x j of a regular mesh on the real axis. We notice a small difference with the finite volume method where the variables u j represent the mean values of some function in each interval I j . We interpolate those values at the points x j+ 1 2 by two different values u - j+ 1 2 and u + j+ 1 2 on each side of the interface x j+ 1 2 . By analogy with the MUSCL approach (1.16), we set

 (2.1) u - j+ 1 2 = L(u j-1 , u j , u j+1 ) (2.2) u + j+ 1 2 = R(u j , u j+1 , u j+2 ) .
The interpolation defined by (2.1).(2.2) is a priori nonlinear and in the following of this part we give some restrictions concerning the functions L(•, •, •) and R(•, •, •).

Property 2.1 Homogeneity

We suppose that the multiplication of all the arguments of (2.1).(2.2) by the same real number λ multiplies the interpolate values u -

j+ 1 2 , u + j+ 1 2
by the same argument, i.e. that the functions L and R are homogeneous of degree 1 :

(2.3) J(λu , λv , λw) = λ J(u, v, w) , J = L or R , λ ∈ IR .

Property 2.2 Translation invariance

We suppose that by addition of some constant λ to the three arguments of (2.1).(2.2), the resulting interpolate values are translated by the same value :

(2.4)

J(u + λ , v + λ , w + λ) = J(u, v, w) + λ , J = L or R , λ ∈ IR .

Property 2.3 Left-Right symmetry

We suppose that by exchange of the two extreme arguments of (2.1) (i.e. we reverse left and right) the left interpolation at x j+ 1 2 is transformed into the right interpolation at x j-1 2 (Figure 2.1) :

(2.5) R(w, v, u) = L(u, v, w) . w u u v j-1 j j+1 j-1 j j+1 R (u,v,w) = L (w,v,u) Figure 2.1. Left-right symmetry.  Proposition 2.1
If the properties 2.1 to 2.3 are assumed, there exists some limiter function ψ :

IR -→ IR such that (2.6) L(u, v, w) = v + 1 2 ψ w -v v -u (v -u) (2.7) R(u, v, w) = v - 1 2 ψ v -u w -v (w -v) .
Proof of Proposition 2.1

We have simply

L(u, v, w) = v + L(u -v, 0, w -v) = v + (v -u) L -1, 0, w -v v -u and R(u, v, w) = L(w, v, u) = v + 1 2 ψ u -v v -w (v -w) .

Property 2.4 Monotonicity

We suppose that the interpolated values u -

j+ 1 2 and u + j+ 1 2 belong to the interval [min(u j , u j+1 ) , max(u j , u j+1 )], i.e. (2.8) min(v, w) ≤ L(u, v, w) ≤ max(v, w) (2.9) min(u, v) ≤ R(u, v, w) ≤ max(u, v) .
We remark that the inequalities (2.9) are a simple consequence of (2.5) and (2.8).

Proposition 2.2

If the properties 2.1 to 2.4 are valid, the limiter ψ satisfies the condition

(2.10) 0 ≤ ψ(λ) λ ≤ 2 , λ ∈ IR
and if the properties 2.1 to 2.3 are supposed, the inequalities (2.10) imply the property 2.4.

Proof of Proposition 2.2

It is a straightforward consequence of (2.6), written under the form :

(2.11) L(u, v, w) = v + 1 2 ψ w -v v -u w -v v -u (w -v) .

•

We introduce now an original notion concerning the nonlinear interpolation at the interfaces, first proposed in [START_REF] Dubois | Interpolation non linéaire et schémas à variation totale décroissante, internal report[END_REF].

 Property 2.5 Convexity

We suppose that for each integer j, the sequence of the interpolate values (2.12)

u j-1 , u + j-1 2 , u j , u - j+ 1 2 , u j+1 ,
is the restriction to the nodes (2.13) x j-1 , x j-1 2 , x j , x j+ 1 2 , x j+1 , of some convex or concave function, depending on the concavity of the sequence (2.14)

u j-1 , u j , , u j+1 .
More precisely, if the inequality (2.15)

u j -u j-1 ≤ u j+1 -u j
holds (convexity of the sequence (2.14)), we suppose that the discrete increments of (2.12) realizes a nondecreasing sequence :

(2.16)

u + j-1 2 -u j-1 ≤ u j -u + j-1 2 ≤ u - j+ 1 2 -u j ≤ u j+1 -u - j+ 1 2
and if we change "≤" into "≥" in the relations (2.15) then we must do it also in (2.16) (concavity of the sequence (2.16)), see Figure 2.2. Example 2.1.

j-1 j-1/2 j j+1/2 j+1
The classical Lagrange interpolation by a polynomial of degree 2 inside the cell ]x j-1 2 , x j+ 1 2 [ corresponds to the limiter function ψ(λ) = 1+3 λ 4 . It satisfies the properties of homogeneity, translation invariance, convexity but not monotonicity (see [START_REF] Van Leer | Towards the Ultimate Conservative Scheme I. The Quest of Monotonicity[END_REF]).

 Property 2.3

If the properties 2.1 to 2.3 hold then the property 2.5 is equivalent to the following inequalities concerning the limiter function :

(2.17)

1 ≤ λ ψ 1 λ ≤ ψ(λ) ≤ λ , λ ≥ 1 (2.18) λ ≤ ψ(λ) ≤ λ ψ 1 λ , λ ≤ 0 .

Proof of Proposition 2.3

We first suppose that the property 2.5 is valid. We set

(2.19) w = v + λ (v -u) .
Then the inequality (2.15) is satisfied if and only if

(2.20) (λ -1) (v -u) ≥ 0 .
Then the inequalities (2.16) take the form (2.21)

     1 - 1 2 λ ψ(λ) (v -u) ≤ - 1 2 λ ψ(λ) (v -u) ≤ . . . . . . ≤ 1 2 ψ(λ) (v -u) ≤ λ -ψ(λ) (v -u) .
If we suppose that (v -u) ≥ 0, we obtain easily (2.17). If we reverse the inequality (2.20), we have also to reverse (2.21), thus (2.17

). If 0 ≤ λ ≤ 1 the change of variable µ = 1 λ gives 1 ≥ 1 µ ψ(µ) ≥ ψ 1 µ ≥ 1 µ , λ = 1 µ , 0 < λ < 1
which is exactly (2.17). When λ ≤ 0, the inequality (2.21) remains valid but under the hypothesis v -u < 0. Then we have

(2.22) 1 ≥ λ ψ 1 λ ≥ ψ(λ) ≥ λ , λ ≤ 0
which establishes (2.18).

•

We suppose now that the inequalities (2.17).(2.18) hold. We claim that (2.22) is valid because if we change λ into 1 λ in the inequality (2.18) we get

1 λ ≤ ψ 1 λ ≤ 1 λ ψ(λ) , λ ≤ 0
which establishes the two first inequalities of (2.22). The end of the proof can be obtained without difficulty.

We summarize the last two properties (relations (2.10), (2.17), (2.18)) into the following one :

 Proposition 2.4
If we suppose that the properties 2.1 to 2.5 are valid, the limiter ψ defined in (2.6) satisfies (2.7)) :

(2.23) 1 ≤ λ ψ 1 λ ≤ ψ(λ) ≤ λ λ ≥ 1 (2.24) λ ≤ ψ(λ) ≤ 2 λ 0 ≤ λ ≤ 1 (2.25) λ ≤ ψ(λ) ≤ 0 λ ≤ 0 .
(2.26)(a)

u - j-1 2 = u j + 1 2 ψ(λ j ) (u j -u j-1 ) (2.26)(b) u + j-1 2 = u j - 1 2 λ j ψ 1 λ j (u j -u j-1 ) with λ j = u j+1 -u j u j -u j-1
and following e.g. [START_REF] Sweby | High Resolution Schemes Using Flux Limiters for Hyperbolic Conservation Laws[END_REF] we can introduce the inverse r j of the ratio λ j :

(2.27) r j = u j -u j-1 u j+1 -u j and rewrite the limiter ψ in terms of the variable r, by defining (2.28) ϕ(r) ≡ r ψ 1 r .

We emphasize that there is a priori no reason to suppose ϕ ≡ ψ. The two first equalities of (2.26) take the form

(2.29)(a) u - j+ 1 2 = u j + 1 2 ϕ(r j ) (u j+1 -u j ) (2.29)(b) u + j-1 2 = u j - 1 2 ϕ 1 r j (u j -u j-1 ) .
Moreover, the inequalities derived in Proposition 2.4 can be translated in terms of the limiter ϕ defined in (2.28).

Proposition 2.5

Let ϕ be defined by (2.28). The limiter ψ satisfies the inequalities (2.23)-(2.25) if and only if the function ϕ verifies :

(2.30) max (0, r)

≤ ϕ(r) ≤ 1 , -∞ < r ≤ 1 (2.31) 1 ≤ ϕ(r) ≤ min (r, 2) , r ≥ 2 (2.32) ϕ(r) ≤ r ϕ 1 r , r ≥ 1 .
Proof of Proposition 2.5 • We first suppose r ≤ 0. Thus the inequality (2.25) joined with (2.28) shows that we have 0 ≤ ϕ(r) ≤ 1 and (2.30) is established in this case. If r ≥ 0, the convexity property reduces to (2.17) and the monotonicity property corresponds to (2.10). By changing λ into 1 r , we get

(2.33) r ≤ r ϕ 1 r ≤ ϕ(r) ≤ 1 , 0 ≤ r ≤ 1
which achieves the proof of (2.30).

• If r ≥ 0, we get from (2.33) :

(2.34) 1 ≤ ϕ(r) ≤ r , 0 ≤ r ≥ 1 and also (2.32). On the other hand condition (2.10) can be rewritten by changing λ into 1 r ; we deduce :

ϕ(r) ≡ r ψ 1 r ≤ 2 , r ≥ 1 .
The latter inequality, joined with (2.34) proves that (2.31) holds. The other side of the equivalence is established by similar arguments.

Example 2.2.

Let ψ be defined by the relations

(2.35)(a) ψ(λ) = 0 , λ ≤ 0 (2.35)(b) ψ(λ) = 2 λ , 0 ≤ λ ≤ 1 3 (2.35)(c) ψ(λ) = 1 2 + 1 2 λ , 1 3 ≤ λ ≤ 3 (2.35)(d) ψ(λ) = 2 , λ ≥ 3 .
This corresponds to the original MUSCL extrapolation [START_REF] Van Leer | Towards the Ultimate Conservative Scheme IV. A New Approach to Numerical Convection[END_REF]) and the κ limiters af [START_REF] Anderson | Comparison of Finite Volume Flux Vector Splittings for the Euler Equations[END_REF] (see also [START_REF] Chakravarthy | Application of a New Class of High Accuracy TVD Schemes to the Navier Stokes Equations[END_REF]) correspond to the choice

(2.36)(a) ψ κ (λ) = 0 , λ ≤ 0 (2.36)(b) ψ κ (λ) = 1 2 (1-κ) min 1 , 3 -κ 1 -κ λ + (1+κ) min λ , 3 -κ 1 -κ if λ ≥ 0 .
All of those limiters (-1 ≤ κ ≤ 1) satisfy ϕ ≡ ψ (see (2.28)) and the inequalities (2.23).(2.25) ; we remark that in the latter relations, we do not impose the values of ψ corresponding to negative arguments to be null. This last condition is necessary if we interpolate u by a linear function inside the interval I j and suppose moreover the condition of monotonicity. We remark also that the so-called Van Albada limiter [1982], defined by (2.37)

ψ(λ) = λ (1 + λ) (1 + λ) 2 ≡ λ ψ 1 λ , λ ∈ IR satisfies neither (2.23).(2.25) [for λ ≤ -1] nor (2.30).(2.32) [for -1 ≤ λ ≤ 0]. Proposition 2.6
The limiter L(u, v, w) satisfying the properties 2.1 to 2.3 is Lipschitz continuous, i.e.

(2.38)

∃ C > 0 , ∀ u, v, w, u ′ , v ′ , w ′ ∈ IR, | L(u, v, w) -L(u ′ , v ′ , w ′ ) | ≤ C | u -u ′ | + | v -v ′ | + | w -w ′ |
if and only if the limiter functions ψ (defined at (2.6)) and ϕ (defined at (2.28)) satisfy a similar property :

(2.39)(a)

∃ K > 0 , ∀ λ, λ ′ ∈ IR, | ψ(λ ′ ) -ψ(λ) | ≤ K | λ ′ -λ | (2.39)(b) ∃ K > 0 , ∀ r, r ′ ∈ IR, | ϕ(r ′ ) -ϕ(r) | ≤ K | r ′ -r | .
Proof of Proposition 2.6 • We suppose first that (2.38) holds. We take u = -1, v = 0, w = λ and analogous relations for the "prime" variables. Then we have (according to (2.6)) :

1 2 ψ(λ ′ ) -ψ(λ) = L(-1, 0, λ ′ -1) -L(-1, 0, λ -1) .
Similarly, we have :

1 2 ϕ(r ′ ) -ϕ(r) = L(-r ′ , 0, 1) -L(-r, 0, 1)
which establishes (2.39).

• We suppose that (2.39) is realized. For a set of given real numbers u, v, w (respectively u ′ , v ′ , w ′ ) , we define λ, r (resp. λ ′ , r ′ ) by the formulae

w = v + λ(v -u) ; v = u + r(w -v) (resp. w ′ = v ′ + λ ′ (v ′ -u ′ ) ; v ′ = u ′ + r ′ (w ′ -v ′ )
) and we decompose the left hand side of (2.38) as follows :

(2.40)

L(u ′ , v ′ , w ′ ) -L(u, v, w) = v ′ -v + + 1 2 ϕ(r ′ ) -ϕ(r) (w ′ -w) + 1 2 ϕ(r) (w ′ -w) -(v ′ -v) If r ′ = ∞ (resp. r = ∞) then w ′ = v ′ (resp. w = v)
| r ′ -r | | w ′ -v ′ | ≤ | u ′ -u | + (1+ | r |) | v ′ -v | + | r | | w ′ -w |
joined to (2.39) establishes the property (2.38) under the restriction

(2.42) | r | ≤ 1 .
The same conclusion holds if we reverse the roles of r and r ′ .

Inequality (2.38) is established if we suppose (2.43) | λ | ≤ 1 and | λ ′ | ≤ 1 .
We have in this case

(2.44)

L(u ′ , v ′ , w ′ ) -L(u, v, w) = v ′ -v + + 1 2 ψ(λ) (v ′ -v + u ′ -u) + 1 2 ψ(λ ′ ) -ψ(λ) (v ′ -u ′ )
and according to (2.10) and (2.39) it is sufficient to remark that we have

| λ ′ -λ | | v ′ -v | ≤ (1+ | λ |) | v ′ -v | + | λ | | u ′ -u | + | w ′ -w | to obtain finally : | L(u ′ , v ′ , w ′ ) -L(u, v, w) | ≤ 1 + K 2 (| u ′ -u | + 2 | v ′ -v | + | w ′ -w |)
which ends the proof.

Remark 2.2. The total variation of the "reconstructed sequence"

(2.45)

u ≡ • • • , u j-1 , u - j-1 2 , u + j-1 2 , u j , u - j+ 1 2 , u + j+ 1 2 , u j+1 , • • • (j ∈ Z Z) is naturally defined by (2.46) TV( u) ≡ j∈Z Z | u j -u + j-1 2 | + | u - j+ 1 2 -u j | + j∈Z Z | u + j+ 1 2 -u - j+ 1 2 | .
The properties 2.1 to 2.5 do not imply that the total variation of the reconstructed sequence is smaller than TV(u) (c.f. (1.23)). For example, in the particular case of the following simple sequence (2.47)(a)

u j = -3 h , j ≤ -1 (2.47)(b) u 0 = 0 , u 1 = h (2.47)(c) u j = 4 h , j ≥ 2
the reconstructed sequence associated with the MUSCL scheme (2.35) admits a total variation given by (2.48)

TV( u) = TV(u) + 2 h . (see Figure 2.4) 4 h h -3 h Figure 2.4.
The total variation of the reconstructed sequence (2.38) with the MUSCL scheme (squares) is greater than the TV of the initial sequence (points).

3.

Decrease of the Total Variation In this section, we suppose that the interpolated values at the interfaces (j + 1

2 ) h are given by the relations (2.27).(2.29) and are submitted to the restrictions described in the Part II (properties 2.1 to 2.5). We study the following differential system

(3.1) du j dt + 1 h f j+ 1 2 -f j-1 2 = 0 , j ∈ Z Z , t > 0
with the flux at the interface (j + 1 2 ) h given by a monotone flux function Φ :

(3.2) f j+ 1 2 = Φ(u - j+ 1 2 , u + j+ 1 2 ) , j ∈ Z Z .
We suppose that the initial datum

(3.3) u j (0) = u 0 j , j ∈ Z Z satisfies (3.4) u 0 ∈ ℓ ∞ (Z Z) ∩ BV(Z Z) , id est (3.5)(a) sup j∈Z Z | u 0 j | < ∞ (3.5)(b) j∈Z Z | u j+1 -u 0 j | < ∞ .
Then the method of lines is well defined, at least locally in time.

Proposition 3.1 The semi-discrete numerical scheme defined by the differential system (3.1).(3.2) and (2.27).(2.29) associated with the initial condition (3.3).(3.4) has a unique solution u j (t), j ∈ Z Z, t ∈ [0, T ], for some T > 0, if the flux function Φ is Lipschitz continuous on the compact sets of IR :

(3.7) ∀ M > 0, ∃ C > 0 , ∀ u, v, u ′ , v ′ ∈ IR, | u |≤ M, | v |≤ M, | u ′ |≤ M, | v ′ |≤ M =⇒ | Φ(u ′ , v ′ ) -Φ(u, v) | ≤ C | u -u ′ | + | v -v ′ | .
Proof of Proposition 3.1 • From the classical Cauchy-Lipschitz theorem it is sufficient to prove that the difference of the flux

(3.8) F j (u) = - 1 h f j+ 1 2 -f j-1 2 , j ∈ Z Z , u ∈ ℓ ∞ (Z Z) is a Lipshitz continuous ℓ ∞ (Z Z) -→ ℓ ∞ (Z Z) function. According to (3.5), we suppose that | u j |≤ M.
Then the same property is realized for the intermediate states u ± j+ 1 2 according to the property 2.4 (monotonicity). We have :

 | F j (u) | ≤ 1 h | Φ(u - j+ 1 2 , u + j+ 1 2 ) -Φ(u - j+ 1 2 , u j ) | + | Φ(u - j+ 1 2 , u j ) -Φ(u j , u j ) | + | Φ(u j , u j ) -Φ(u j , u + j-1 2 ) | + | Φ(u j , u + j-1 2 ) -Φ(u - j-1 2 , u + j-1 2 ) | ≤ C h | u + j+ 1 2 -u j | + | u - j+ 1 2 -u j | + | u + j-1 2 -u j | + | u - j-1 2 -u j | ≤ C h | 1 - 1 2 ϕ 1 r j+1 | | u j+1 -u j | + 1 2 ϕ 1 r j | u j+1 -u j | + + 1 2 ϕ(r j ) | u j -u j-1 | + | 1 - 1 2 ϕ 1 r j-1 | | u j -u j-1 | ≤ 16 C h M that establishes that F is a function ℓ ∞ (Z Z) -→ ℓ ∞ (Z Z). • We prove that F is Lipschitz continuous on the bounded sets of ℓ ∞ (Z Z). Let (u j ) j∈Z Z , (v j ) j∈Z Z be two bounded sequences in ℓ ∞ (Z Z) : (3.9) | u j | ≤ M , | v j | ≤ M , ∀ j ∈ Z Z .
According to the monotonicity property (2.8), the interpolated values u ±

j+ 1 2 , v ± j+ 1 2
, satisfy the same property. From the inequality (3.7) and the proposition 2.6 we deduce | Φ(u -

j+ 1 2 , u + j+ 1 2 ) -Φ(v - j+ 1 2 , v + j+ 1 2 ) | ≤ | u - j+ 1 2 -v - j+ 1 2 | + | u + j+ 1 2 -v + j+ 1 2 | ≤ K C | u j-1 -v j-1 | + 2 | u j -v j | + 2 | u j+1 -v j+1 | + | u j+1 -v j+1 | ≤ 6 K C sup ℓ∈Z Z | u ℓ -v ℓ | .
Then we have the estimate

(3.10) | F j (u) -F j (v) | ≤ 12 K C h sup ℓ∈Z Z | u ℓ -v ℓ |
and the proposition is established.

Remark 3.1.

From the Proposition 3.1, we know that the function [0, T ] ∋ t -→ (u j (t)) j∈Z Z which belongs to ℓ ∞ (Z Z) is derivable ; in particular, the sequence (u j (t)) j∈Z Z is bounded uniformly in space and time :

(3.11) ∃ M > 0 , ∀ t ∈ [0, T ] , ∀ j ∈ Z Z , | u j (t) | ≤ M .

•

We focus now on the total variation of (u j (t)) (c.f. (1.13)). We suppose moreover the following restrictions: Property 3.1. We fix a real α such that 1 ≤ α ≤ 2. We suppose that the limiter ϕ related to the interpolated values u ± j+ 1 2 according to (2.29) satisfies the following inequalities :

(3.12) ϕ(r) ≤ (α -2) r , r ≤ 0 (3.13) ϕ(r) ≤ α , r > 0 . Remark 3.2.
If ϕ satisfies the conditions (2.30).(2.32), (3.12).(3.13) for the particular value α = 2 and the complementary restriction :

(3.14) ϕ(r) ≤ 2 r , 0 ≤ r ≤ 1 ,
then the restrictions that we obtain for ϕ correspond exactly to the "second order TVD region" derived previously by [START_REF] Sweby | High Resolution Schemes Using Flux Limiters for Hyperbolic Conservation Laws[END_REF]. For the other values of α, (1 ≤ α < 2) the estimates (3.12).(3.13) are new. We can transcribe the Property 3.1 and the inequality (3.14) in terms of the ψ-limiter (c.f. (2.26)) :

(3.15)(a) ψ(λ) ≥ α -2 , λ ≤ 0 (3.15)(b) ψ(λ) ≤ α λ , 0 ≤ λ ≤ 1 (3.15)(c) ψ(λ) ≤ 2 , λ ≥ 1 .
Theorem 3.1. Decrease of the total variation Let (u j (t)) (j ∈ Z Z, t ∈ [0, T ]) be defined by the method of lines (the hypotheses are the ones given at Proposition 3.1). We suppose also that the limiter function ϕ that defines the interpolated values at mid-points according to (2.29), satisfies (2.30).(2.32) and Property 3.1 (relations (3.12).(3.13)). Moreover the flux function Φ of relation (3.2) is supposed to be monotone

(3.16) Φ u (u, v) ≥ 0 , Φ v (u, v) ≤ 0
and absolutely continuous relatively to each variable :

Φ(u, v) = Φ(u 0 , v) + u u 0 Φ u (ξ, v) dξ , Φ(u, v) = Φ(u , v 0 ) + v v 0 Φ v (u, ξ) dξ .
Then, the total variation TV(t) of (u j (t)) defined in (1.13) is a decreasing function of time :

(3.17) Proof of Theorem 3.1.

TV(t + θ) ≤ TV(t) 0 ≤ t ≤ t + θ ≤ T .  y = 2 r y = r 2 α r 0 1 ϕ (r) 1 y = (α -2) r

•

We fix some notations :

(3.18)

ϕ j ≡ ϕ(r j ) , ϕ j ≡ ϕ 1 r j , j ∈ Z Z (3.19) ∆ j+ 1 2 ≡ u j+1 -u j , j ∈ Z Z .
Then (2.29) admits the following form :

(3.20)(a) u - j+ 1 2 = u j + 1 2 ϕ j ∆ j+ 1 2 (3.20)(b) u + j+ 1 2 = u j+1 - 1 2 ϕ j+1 ∆ j+ 1 2 . We also denote by α j-1 2 (respectively β j+ 1 2 ) the mean value of Φ u (respectively Φ v ) over the domain [ u - j-1 2 , u - j+ 1 2 ]× {u + j-1 2 } (resp. {u - j+ 1 2 } ×[ u + j-1 2 , u + j+ 1 2 ]) : (3.21) Φ(u - j+ 1 2 , u + j-1 2 ) -Φ(u - j-1 2 , u + j-1 2 ) ≡ α j-1 2 (u - j+ 1 2 -u - j-1 2 ) (3.22) Φ(u - j+ 1 2 , u + j+ 1 2 ) -Φ(u - j+ 1 2 , u + j-1 2 ) ≡ β j+ 1 2 (u + j+ 1 2 -u + j-1 2 ) .
According to the monotonicity (3.16) of the flux Φ, we have :

(3.23) α j+ 1 2 ≥ 0 , β j+ 1 2 ≤ 0 , j ∈ Z Z .
• When we derive formally the total variation (1.13) with respect to time, we have d dt

TV(t) = j∈Z Z sgn (u j+1 -u j ) d dt (u j+1 -u j ) .
Then we consider the following sequence

(3.24) p j+ 1 2 = -sgn (u j+1 -u j ) d dt (u j+1 -u j ) , j ∈ Z Z .
From the equalities (3.1), (3.2), (3.20).(3.22), we have the elementary calculus :

-h

du j dt = -Φ(u - j+ 1 2 , u + j+ 1 2 ) + Φ(u - j-1 2 , u + j-1 2 ) = -Φ(u - j+ 1 2 , u + j+ 1 2 ) + Φ(u - j+ 1 2 , u + j-1 2 ) -Φ(u - j+ 1 2 , u + j-1 2 ) + Φ(u - j-1 2 , u + j-1 2 ) = -β j+ 1 2 (u + j+ 1 2 -u + j-1 2 ) -α j-1 2 (u - j+ 1 2 -u - j-1 2 ) = -β j+ 1 2 u j+1 - 1 2 ϕ j+1 ∆ j+ 1 2 -u j - 1 2 ϕ j ∆ j-1 2 -α j-1 2 u j + 1 2 ϕ j ∆ j+ 1 2 -u j-1 + 1 2 ϕ j-1 ∆ j-1 2 = -β j+ 1 2 1 - 1 2 ϕ j+1 + 1 2 ϕ j r j ∆ j+ 1 2 -α j-1 2 1 + 1 2 ϕ j r j - 1 2 ϕ j+1 ∆ j-1 2 .
Then

p j+ 1 2 = - | ∆ j+ 1 2 | ∆ j+ 1 2 d dt u j+1 -u j = | ∆ j+ 1 2 | ∆ j+ 1 2 1 h β j+ 3 2 1 - 1 2 ϕ j+2 + 1 2 ϕ j+1 r j+1 ∆ j+ 3 2 + α j+ 1 2 1 + 1 2 ϕ j+1 r j+1 - 1 2 ϕ j ∆ j+ 1 2 -β j+ 1 2 1 - 1 2 ϕ j+1 + 1 2 ϕ j r j ∆ j+ 1 2 -α j-1 2 1 + 1 2 ϕ j r j - 1 2 ϕ j+1 ∆ j-1 2 . and (3.25)                p j+ 1 2 = | ∆ j+ 1 2 | h β j+ 3 2 r j+1 1 - 1 2 ϕ j+2 + 1 2 ϕ j+1 r j+1 + + α j+ 1 2 1 + 1 2 ϕ j+1 r j+1 - 1 2 ϕ j -β j+ 1 2 1 - 1 2 ϕ j+1 + 1 2 ϕ j r j -α j-1 2 r j 1 + 1 2 ϕ j r j - 1 2 ϕ j+1 .
We integrate (3.25) relatively to time (0 ≤ t ≤ τ ≤ t + θ ≤ T ), we sum the result for j = k, k + 1, . . . , ℓ and we factorize α j+ 1 2 and β j+ 1 2 (Abel transformation). We obtain :

(3.26)                                                            h ℓ j=k | ∆ j+ 1 2 (t) | -| ∆ j+ 1 2 (t + θ) | = = ℓ j=k t+θ t | ∆ j+ 1 2 (τ ) | α j+ 1 2 1 - r j | r j | 1 + 1 2 ϕ j+1 r j+1 - 1 2 ϕ j dτ + t+θ t | ∆ ℓ+ 1 2 (τ ) | α ℓ+ 1 2 1 + 1 2 ϕ ℓ+1 r ℓ+1 - 1 2 ϕ ℓ dτ - t+θ t | ∆ k-1 2 (τ ) | α k-1 2 r k | r k | 1 + 1 2 ϕ k r k - 1 2 ϕ k-1 dτ + ℓ j=k+1 t+θ t | ∆ j+ 1 2 (τ ) | β j+ 1 2 r j | r j | -1 1 - 1 2 ϕ j+1 + 1 2 ϕ j r j dτ + t+θ t | ∆ ℓ+ 3 2 (τ ) | β ℓ+ 3 2 r ℓ+1 | r ℓ+1 | 1 - 1 2 ϕ ℓ+2 + 1 2 ϕ ℓ+1 r ℓ+1 dτ - t+θ t | ∆ k+ 1 2 (τ ) | β k+ 3 2 1 - 1 2 ϕ k+1 + 1 2 ϕ k r k dτ .
The first, second, fourth and sixth terms of the right hand side of (3.26) are positive, due to (3.23) and the following inequalities :

(3.27) 1 + 1 2 ϕ j+1 r j+1 - 1 2 ϕ j ≥ 0 , j ∈ Z Z (3.28) 1 - 1 2 ϕ j+1 + 1 2 ϕ j r j ≥ 0 , j ∈ Z Z .

•

We establish (3.27). We distinguish two cases, according to the sign of r j+1 . If r j+1 ≥ 0, we have, due to (3.13) and (2.30).(2.31) :

1 2 ϕ j ≤ 1 2 α ≤ 1 ≤ 1 + 1 2 ϕ j+1 r j+1
which proves (3.27) in this case. On the other hand, if r j+1 < 0, we have, due to (3.12) :

1 2 ϕ j - 1 2 ϕ j+1 r j+1 ≤ 1 2 α - 1 2 (α -2) = 1
and (3.27) is established. Inequality (3.28) is equivalent , according to (3.18), to :

1 - 1 2 ϕ(λ j+1 ) + 1 2 1 λ j ϕ 1 λ j , λ j = 1 r j 
which corresponds exactly to (3.27).

•

The third and fifth terms of the right hand side of (3.26) are bounded by

(3.29) γ = 2 M (2 + K) θ
according to (3.11), (3.7), (2.30), (2.31), (2.39) and the constant γ is independent of k and ℓ. When k tends to -∞ and ℓ to +∞, the previous inequalities give the following estimate :

(3.30) TV(t) -TV(t + θ) ≥ -4 M (2 + K) θ .
By taking t = 0 and θ ≤ T, this inequality proves that TV(θ) is well defined for all θ ≤ T. Moreover, the third and fifth terms of the right hand side of (3.26) tend to zero from the previous considerations and the Lebesgue dominated convergence Theorem. Taking k -→ -∞ and ℓ -→ +∞ in (3.26), we finally deduce : TV(t) -TV(t + θ) ≥ 0 , θ ≥ 0 which is exactly (3.17).

Remark 3.3.

Since the work of [START_REF] Harten | High Resolution Schemes for Hyperbolic Conservation Laws[END_REF], the TVD property is derived from an incremental form of the scheme (3.1) Moreover, the inequalities (3.27).(3.28) have been previously considered among others by [START_REF] Sweby | High Resolution Schemes Using Flux Limiters for Hyperbolic Conservation Laws[END_REF], Chakravarthy-Osher [1983] and [START_REF] Spekreijse | Multigrid Solution of Monotone Second-Order Discretizations of Hyperbolic Conservation Laws[END_REF]. Here these inequalities are obtained essentially as a consequence of other considerations concerning the limiter, and not as necessary conditions to assume the TVD property. In particular, the limiter function ϕ(r) is not necessarily null for the negative values of the argument r as it is usually supposed (see Figure 3.1). To be complete, the sufficient conditions proposed by [START_REF] Spekreijse | Multigrid Solution of Monotone Second-Order Discretizations of Hyperbolic Conservation Laws[END_REF] (see also [START_REF] Cahouet | Uniformly Second Order Convergent Schemes for Hyperbolic Conservation Laws including Leonard's Approach[END_REF]) allow possible non-null values for ϕ(r) when r < 0 but their conditions are not a priori compatible with the hypothesis of monotonicity.

We turn now to an important result of this paper.

Theorem 3.2. ℓ ∞ stability. Let u j (t) be the solution of the differential system (3.1).(3.3); we assume that all the hypotheses of the Theorem 3.1 are satisfied. Then we have (3.31) inf

ℓ∈Z Z u 0 ℓ ≤ u j (t) ≤ sup ℓ∈Z Z u 0 ℓ , j ∈ Z Z , 0 ≤ t ≤ T .  Remark 3.4.
An immediate corollary of the Theorem 3.2 is the fact that the solution u j (t) is (for each h fixed) defined globally in time, i.e. the time T ≥ 0 introduced at the Proposition 3.1 can be taken equal to +∞.

•

The proof of Theorem 3.2 contains essentially the ideas given previously by [START_REF] Sanders | On Convergence of Monotone Finite Difference Schemes With Variable Spatial Differencing[END_REF] and [START_REF] Osher | Convergence of generalized MUSCL schemes[END_REF]. The new difficulty here is to work with an infinite set of indices j (Osher supposed the periodicity in space). So we first prove the following property : Proposition 3.2. For each time t, 0 ≤ t ≤ T, the sequence (u j (t)) j∈Z Z defined by (3.1).(3.3) has a limit M (t) (respectively m(t)) for j -→ +∞ (respectively j -→ -∞) and we have (3.32)

M (t) ≡ M (0) , m(t) ≡ m(0) , 0 ≤ t ≤ T .
Proof of Proposition 3.2.

•

The existence of M (t) and m(t) is a direct consequence of the convergence of the series that defines the total variation for each time t (c.f. Theorem 3.1).

•

We now consider the mean value of u j (t) :

v N (t) = 1 N N j=1 u j (t) , N ≥ 1 , 0 ≤ t ≤ T .
The function v N is derivable and we have

(3.33) dv N dt + 1 N f N + 1 2 -f 1 2 .
From the Remark 3.1 and the continuity of the flux relatively to {u j (t)} (see the proof of the proposition 3.1), there exists some constant κ such that

(3.34) | dv N dt | ≤ κ N .
Then dv N dt tends uniformly to zero as N tends to +∞. Moreover from the Cesaro convergence Theorem, v N tends to M (t) as N -→ ∞. We deduce from these two facts that M (t) is derivable, and

(3.35) dM dt = 0 .
The first equality of (3.32) is established. The proof is analogous for m(t).

Proof of Theorem 3.2.

• It is sufficient to prove (3.31) for t small enough to establish the property. For t ∈ [0, T ], we define

µ(t) = inf j∈Z Z u j (t) .
Then -→ µ(t) is continuous and we distinguish two cases :

(i) µ < m.
Then for some j 0 (t), we have

(3.36) µ(t) = u j 0 (t) .
With the notations introduced in the proof of Theorem 3.1, we have :

(3.37)      h du j dt = -β j+ 1 2 (u j+1 -u j ) 1 - 1 2 ϕ j+1 + 1 2 ϕ j r j + α j-1 2 (u j-1 -u j ) 1 + 1 2 ϕ j r j - 1 2 ϕ j-1
and (3.37) is non-negative for j = j 0 . Consequently for t ′ ≥ t and t ′ -t sufficiently small, we have which establishes the contradiction. The proof concerning the maximum bound is analogous.

(3.38) µ(t ′ ) ≥ µ(t) , ∀ t ′ ≥ t , t ′ -t small enough. (ii) µ ≥ m. If the alternative (i) is realized at t = 0,

Convergence, Order of Accuracy

In this section the parameter h > 0 tends to zero. Two questions are naturally related to this problem : 1) What is the order of the truncation error of the scheme (3.1)(3.2), (2.27).(2.29) as h tends to zero ? 2) Does the function u h (x, t) defined by (4.1)

u h (x, t) = u h j (t) , j -1 2 h ≤ x ≤ j + 1 2 h
 (where the superscript h recalls the dependence towards h of the solution u j (t) of the method of lines) converge to the unique entropy solution of (1.1).(1.2) ? The following property answers the first point.

Proposition 4.1.

We suppose that the entropy solution u(x, t) of (1.1).(1.2) is regular around some point (x 0 , t 0 ). Let v h j (t) be defined by (4.2)

v h j (t) = u(j h , t) , j ∈ Z Z , h > 0 , t ≥ 0 .
The residual of the semi-discrete scheme (3.1)(3.2), (2.27).(2.29), i.e. the quantity obtained when we apply the scheme (3.1) to the exact "nodal" values v h j (t) :

(4.3) ρ h j (t) ≡ dv h j dt - 1 h Φ v - j+ 1 2 , v + j+ 1 2 -Φ v - j-1 2 , v + j-1 2
is second order accurate in space : (4.4) (4.6)

ρ h j (t) = O(h 2 ) , h -→ 0 , ∃ j 0 , x 0 = j 0 h if the
r j = v h j -v h j-1 v h j+1 -v h j ≡ ∆ j-1 2 ∆ j+ 1 2 (4.7)(a) v - j+ 1 2 (t) = v h j + 1 2 ϕ(r j ) ∆ j+ 1 2 ≡ v j + 1 2 ϕ j ∆ j+ 1 2 (4.7)(b) v + j-1 2 (t) = v h j - 1 2 ϕ 1 r j ∆ j-1 2 ≡ v j - 1 2 ϕ j ∆ j-1 2 .
We develop ρ h j (t) around (x 0 , t 0 ) assuming that x 0 is a mesh point (see (4.4)) : (4.8)

x 0 = j h for some j ∈ Z Z . Two cases can occur, according to the nullity of the gradient ∂u ∂x (x 0 , t 0 ) .

• u ′ j ≡ ∂u ∂x (x 0 , t 0 ) = 0 . We develop the numerical flux (4.9)

f j+ 1 2 = Φ v j + 1 2 ϕ j ∆ j+ 1 2 , v j + 1 - 1 2 ϕ j+1 ∆ j+ 1 2 
by the Taylor formula, with the notations

α j = ∂Φ ∂u (u = v j , v = v j ) , β j = ∂Φ ∂v (u = v j , v = v j ) , f j = Φ(v j , v j ) .
We get (4.10)

f j+ 1 2 = f j + α j ϕ j ∆ j+ 1 2 + β j 1 - 1 2 ϕ j+1 ∆ j+ 1 2 + O ∆ 2 j+ 1 2
We must now specify the behavior of the ϕ's as h tends to zero. We have on one hand (4.11)

r j = 1 - 1 2 h u ′′ j u ′ j + O(h 2 ) 1 + 1 2 h u ′′ j u ′ j + O(h 2 ) = 1 -h u ′′ j u ′ j + O(h 2 ) with u ′′ j =
∂ 2 u ∂x 2 (x 0 , t 0 ) and on the other hand (4.12) 1

r j = 1 + h u ′′ j u ′ j + O(h 2 ) .
When we substitute these developments into (4.10), with the hypotheses (c.f. (4.5))

(4.13)(a) ϕ(1 + ξ) = 1 + ξ ϕ ′ + + O(ξ 2 ) , ξ -→ 0 , ξ > 0 (4.13)(b) ϕ(1 -ξ) = 1 -ξ ϕ ′ -+ O(ξ 2 ) , ξ -→ 0 , ξ > 0 .
We obtain (assuming

u ′′ j u ′ j > 0 ; the other case is analogous) : (4.14)      f j+ 1 2 = f j + 1 2 h u ′ j (α j + β j ) + 1 2 h 2 u ′′ j (-α j ϕ ′ --β j ϕ ′ + ) + + h 2 4 u ′′ j (α j + β j ) + h 2 8 (u ′ j ) 2 f ′′ j + O(h 3 )
where f ′′ j is defined by the formula :

(4.15) f ′′ j = (Φ uu + Φ uv + Φ vu + Φ uu )(v j , v j ) = d 2 f du 2 (v j )
. Similarly, we easily obtain (4.16)

r j-1 ≡ v h j-1 -v h j-2 v h j -v h j-1 = 1 -h u ′′ j u ′ j + O(h 2 ) (4.17)(a) ϕ j-1 = 1 -h u ′′ j u ′ j ϕ ′ -+ O(h 2 ) (4.17)(b) ϕ j = 1 + h u ′′ j u ′ j ϕ ′ + + O(h 2 ) .
We insert the latter expressions in the following expression of the numerical flux at (j -1 2 ) h :

(4.18) f j-1 2 = Φ v j + 1 2 ϕ j-1 -1 ∆ j-1 2 , v j - 1 2 ϕ j ∆ j-1 2
and we obtain finally: the other case is analogous) :

(4.19)      f j-1 2 = f j - 1 2 h u ′ j (α j + β j ) - 1 2 h 2 u ′′ j (α j ϕ ′ -+ β j ϕ ′ + ) + + h 2 4 u ′′ j (α j + β j ) + h 2 8 (u ′ j ) 2 f ′′ j + O(h 3
) . We subtract (4.19) from (4.14) and we also notice that

(4.20) (α j + β j ) u ′ j = f ′ (v j (t)) u ′ j = - d dt u j (t) .
Finally we get (4.21) ρ h j (t) = O(h 2 ) as desired.

•

We consider now the case of an extremum : u ′ j ≡ ∂u ∂x (x 0 , t 0 ) = 0. Then ∂u ∂t (x 0 , t 0 ) = 0 due to the conservation law (1.1). We focus on the development of the ratio r j of the slopes :

(4.22) r j = -1 2 u ′′ j + O(h) 1 2 u ′′ j + O(h) = -1 + O(h) .
In a similar manner, we have:

(4.23) 1 r j+1 = 3 2 u ′′ j + O(h) 1 2 u ′′ j + O(h) = 3 + O(h) .
Then the flux at the interface (j + 1 2 ) admits the following form :

(4.24)

f j+ 1 2 = f j + 1 2 h 2 u ′′ j 1 2 α j ϕ(-1) + β j 1 - 1 2 ϕ(3) + O(h 3 ) .
The expressions r j-1 and 1 r j are computed according to (4.23) and (4.22) respectively. Then the numerical flux at (j -1

2 ) h can be developed as (4.25)

f j-1 2 = f j - 1 2 h 2 u ′′ j 1 - 1 2 ϕ(3) α j - 1 2 ϕ(-1) β j + O(h 3 )
and we finally get in this case :

ρ h j (t) = - 1 h (f j+ 1 2 -f j-1 2 )  that is (4.26) ρ h j (t) = - 1 2 h u ′′ j ϕ(-1) + ϕ(3) 2 -1 (α j -β j ) + O(h 2 )
and the proposition is established.

Remark 3.1.

In a previous paper, Osher [START_REF] Osher | High Resolution Schemes and the Entropy Condition[END_REF] claimed that if a semi-discrete scheme which takes the form (4.27)

du j dt = 1 h C j+ 1 2 ∆ j+ 1 2 -D j-1 2 ∆ j-1 2 , j ∈ Z Z with (4.28) C j+ 1 2 ≥ 0 , D j+ 1 2 ≥ 0 , j ∈ Z Z
is necessarily first order near a non sonic critical point ( ∂u ∂x = 0, f ′ (u) = 0). The numerical semi-discrete scheme (3.1)(3.2), (2.27).(2,29) studied herein admits the form (4.27)(4.28). More precisely, we have, according to (3.20).(3.22) :

(4.29)(a) C j+ 1 2 = -β j+ 1 2 1 - 1 2 ϕ j+1 + 1 2 ϕ j r j (4.29)(b) D j+ 1 2 = α j+ 1 2 1 + 1 2 ϕ j+1 r j+1 - 1 2 ϕ j .
Near a critical point, the expressions (3.27) and (3.28) vanish with h and according to (4.5), the factors ∆ j± 1 2 are O(h 2 ). Moreover the coefficients β j+ 1 2 and α j-1 2 are bounded. The second order is clear. In fact the consistency property assumed in the previous reference (formula (2.11)) is not relevant for a critical point while the term ∂u ∂x in (2.10) is null. The result can also be stated intuitively : near a regular extremum, the curve looks like a parabola and its interpolation by a constant is second order accurate in that case.

Our condition (4.5)(b) which is the key for this second-order accuracy has been independently proposed by [START_REF] Wu | MmB -A New Class of Accurate High Resolution Schemes for Conservation Laws in Two Dimensions[END_REF].

•

We study now the convergence of the sequence u h (x, t) defined in (4.1) to the entropy solution of (1.1)(1.2).We have not proved that the scheme studied previously converges to the entropy solution ; therefore we give known results concerning the convergence of u h (x, t). First we have the following property : Proposition 4.2. The sequence of functions u h (•, •) defined for (x, t) ∈ IR×]0, +∞[ from the line values u j (t) according to the relation (4.1) are bounded in each compact set in L ∞ ∩ BV(IR × 0, +∞[) where the space BV is defined according to [START_REF] Volpert | The spaces BV and quasilinear equations[END_REF]. This bound is independent of h > 0.

Proof of Proposition 4.2. In Part 3, we have proved the BV property relatively to the space variable x (Theorem 3.1) and the L ∞ stability (Theorem 3.2). It is now sufficient to prove the BV stability for the time variable. Let T and ∆t > 0 be two fixed times. We have :

T 0 dt +∞ -∞ dx | u h (x, t + ∆t) -u h (x, t) | ≤ ≤ T 0 dt j∈Z Z ∆t 0 dθ | ∂u j ∂t (t + θ) | ≤ h j∈Z Z T 4C h ∆t 0 dθ | u j+1 -u j | + | u j -u j-1 | (t + θ)
where the constant C has been introduced in (3.7). Therefore the BV property in time follows from the BV stability in space (Theorem 3.1).

• From Proposition 4.2 and the compactness of the injection L ∞ ∩ BV -→ L ∞ (see [START_REF] Volpert | The spaces BV and quasilinear equations[END_REF]) we deduce that a subsequence of uh converges to a weak solution of (1.1)(1.2) but not necessarily to the entropy solution. To prove that a subsequence of uh converges to the entropy solution it is sufficient to establish a discrete entropy inequality [START_REF] Harten | quad On Finite Difference Approximations and Entropy Conditions For Shocks[END_REF]). Recently, [START_REF] Osher | Riemann Solvers, the Entropy Condition, and Difference Approximations[END_REF] has proposed a sufficient discrete entropy condition to establish the discrete entropy inequality : (4.30)

u j+1 u j η ′ (w) f j+ 1 2 -f (w) dw ≤ 0 , j ∈ Z Z .
When f j+ 1 2 is computed according to the MUSCL method (e.g. the relations (3.2), (2.27)-(2.29)), [START_REF] Osher | Convergence of generalized MUSCL schemes[END_REF] proved that when the flux function Φ in (3.2) is monotone (which has been always assumed in this paper), the sequence u h converges almost everywhere to the unique entropy solution of (1.1) (1.2) if the limiter function ϕ(•) satisfies the monotonicity property 2.4 and the following severe restrictions : the function ϕ(•) is null for negative arguments and the function ϕ(•) satisfies the following property :

(4.31)    0 ≤ ϕ j ≤ 2 max 0 , min u j -u j+ 1 2 u j -u j+1 , u j-1 2 -u j u j -u j+1 if u j > u j+1 , for each j ∈ Z Z



with the following definition for the mean value at (j + 1 2 ) h :

(4.32) f u j+ 1 2 = 1 u j -u j+1 u j u j+1 f (w)dw .
The condition (4.31) couples the interpolation at the interface values and the (physical) flux function f. This result is at our knowledge the best one concerning the convergence of the sequence u h towards the entropy solution of the conservation law if one uses the MUSCL approach. For other studies concerning this problem we refer also to [START_REF] Osher | On the Convergence of Difference Approximations to Scalar Conservation Laws[END_REF] and [START_REF] Vila | High Order Scheme and Entropy Condition for Nonlinear Hyperbolic Systems of Conservation Laws[END_REF].

Time Discretization

We focus now on the discretization in time of the semi-discrete scheme (3.1).

(3.2) (associated with (2.27).(2.29)). We assume that this semi-discrete scheme is Total Variation Diminishing, i.e. that the sufficient conditions (2.30)-(2.32) and (3.12).(3.13) are satisfied. We consider the following three schemes in time (∆t = t n+1 -t n is the time step and we denote by λ the ratio ∆t ∆x ) : First Order Scheme

(5.1) 1 ∆t (u n+1 j -u n j ) + 1 ∆x Φ u n, - j+ 1 2 , u n, + j+ 1 2 -Φ u n, - j-1 2 , u n, + j-1 2 = 0 .
Modified Euler Scheme (Heun scheme)

(5.2)(a) 1 ∆t ( u n+1 j -u n j ) + 1 ∆x Φ u n, - j+ 1 2 , u n, + j+ 1 2 -Φ u n, - j-1 2 , u n, + j-1 2 = 0 (5.2)(b) 1 ∆t (u n+1 j -u n j ) + 1 ∆x f n j+ 1 2 + f n+1 j+ 1 2 -(f n j-1 2 + f n+1 j-1 2 = 0
with the fluxes given by the relations

(5.3) f n j+ 1 2 = Φ u n, - j+ 1 2 , u n, + j+ 1 2 , f n+1 j+ 1 2 = Φ u n+1, - j+ 1 2 , u n+1, + j+ 1 2 .
Predictor-Corrector Scheme

(5.4)(a)) 2 ∆t u n+ 1 2 j -u n j + 1 ∆x f n j+ 1 2 -f n j-1 2 = 0 (5.4)(b)) 1 ∆t (u n+1 j -u n j ) + 1 ∆x f n+ 1 2 j+ 1 2 -f n+ 1 2 j-1 2 = 0 .
As in the previous cases we have the same type of notations :

(5.5)

f n j+ 1 2 = Φ u n, - j+ 1 2 , u n, + j+ 1 2 , f n+ 1 2 j+ 1 2 = Φ u n+ 1 2 , - j+ 1 2 , u n+ 1 2 , + j+ 1 2 .
In the following, we study the TVD property of the scheme (5.1).( 5.4) under some ad hoc restrictions.

We define two versions of the modified predictor-corrector scheme by the incremental relations (5.16)(a) u

n+ 1 2 j = u j + 1 2 C k j+ 1 2 ∆ j+ 1 2 -D k j-1 2 ∆ j-1 2 (5.16)(b) u n+1 j = u j + 1 2 C k j+ 1 2 ∆ n+ 1 2 j+ 1 2 -D k j-1 2 ∆ n+ 1 2 j-1 2 .
If k is equal to n (respectively n + 1 2 ) in relation (5.16) the predictor-corrector scheme is explicit in time for the two steps (respectively implicit for the predictor step and explicit for the corrector). Notice that in equation (5.16) the index k is the same in both steps (5.16)(a) and (5.15)(b) whereas in the original predictorcorrector scheme (5.4) (5.5) k is equal to n for the predictor and k is equal to n + 1 2 in the corrector. We have the following property :

Proposition 5.4
The predictor-corrector schemes defined in Definition 5.1 are TVD under the hypotheses of Proposition 5.1.

Proof of Proposition 5.4 •

We first develop ∆

n+ 1 2 j+ 1 2
and we drop the exponent n for all the variables defined at time n∆t and the exponent k of (5.16) associated with the coefficients C and D :

∆ n+ 1 2 j+ 1 2 ≡ u n+ 1 2 j+1 -u n+ 1 2 j (5.17) ∆ n+ 1 2 j+ 1 2 = 1- 1 2 C j+ 1 2 +D j+ 1 2 ∆ j+ 1 2 + 1 2 C j+ 3 2 ∆ j+ 3 2 + 1 2 D j-1 2 ∆ j-1 2 .
• We substitute (5.17) in equation (5.16)(b). We obtain in this manner :

u n+1 j = u j + 1 2 C j+ 1 2 C j+ 3 2 ∆ j+ 3 2 + + C j+ 1 2 1 - 1 2 (C j+ 1 2 + D j+ 1 2 ) - 1 2 D j-1 2 C j+ 1 2 ∆ j+ 1 2 -D j-1 2 1 - 1 2 (C j-1 2 + D j-1 2 ) - 1 2 D j-1 2 C j+ 1 2 ∆ j-1 2 - 1 2 D j-1 2 D j-3 2 ∆ j-3 2 .
This representation is of the type proposed in (5.13). The inequalities (5.14) take the form :

(5.18)(a)

C j+ 1 2 C j-1 2 ≥ 0 (5.18)(b) C j+ 1 2 1 - 1 2 (C j+ 1 2 + D j+ 1 2 ) - 1 2 D j-1 2 + C j-1 2 C j+ 1 2 ≥ 0  (5.18)(c)      (C j+ 1 2 + D j+ 1 2 ) 1 - 1 2 (C j+ 1 2 + D j+ 1 2 ) - 1 2 C j+ 1 2 D j-1 2 + C j+ 3 2 D j+ 1 2 ≤ 1 (5.18)(d) (C j+ 1 2 +D j+ 1 2 ) 1- 1 2 (C j+ 1 2 +D j+ 1 2 ) - 1 2 D j-1 2 (C j+ 1 2 +D j+ 1 2 ) ≥ 0 (5.18)(e) D j+ 1 2 D j-1 2 ≥ 0 .
From the inequalities (5.11) the inequalities (5.18) (a) and (e) hold clearly. On the other hand, we have :

left hand side of (5.18)(b) ≥ C j+ 1 2 1 - 1 2 - 1 2
C j+ 1 2 = 0 and (5.18)(b) is established. The inequality (5.18)(d) holds by the same argument. Finally, the left hand side of (5.18)(c) is dominated by (C j+ 1 2 + D j+ 1 2 ) and this last inequality is established according to (5.11)(c).

Remark 5.1

As mentioned previously, we have not proved that under the natural form (5.4).(5.5) the predictor-corrector scheme is TVD. In fact, the inequalities of the type (5.18) contain in that case a mixing of the Cs and Ds with time steps n and n + 1 2 . The simple algebra derived in the last proposition is not possible anymore. We also remark that Definition 5.1 proposes a scheme under its incremental form. Therefore this scheme is not a priori conservative. These two remarks illustrate the difficulty in maintaining both the conservative form of the numerical scheme and the TVD property for a predictor-corrector scheme constructed from the first order scheme (5.1).

•

In the last part of this section we study the order of accuracy of the predictorcorrector scheme (5.4).(5.5) and the modified Euler scheme (5.2).( 5.3) in the sense of the truncation error near a regular local extremum of the solution (t, x) -→ u(t, x) of the conservation law (1.1). We recall that in Proposition 4.1 we have proved that the truncation error (4.4) for the method of lines is second order accurate in space if the limiter function ϕ satisfies the condition

(5.19) ϕ(-1) + ϕ(3) = 2 .
We first make the following two hypotheses concerning the numerical flux function Φ of relation (3.2) and the limiter function ϕ(-1) for the interface interpolations.

Property 5.2

We suppose that the monotone flux function Φ ≡ Φ(u, v) satisfies the condition :

(5.20

)(a) df (w) > 0 =⇒ ∂Φ ∂v (w, w) = 0 (5.20)(b) df (w) < 0 =⇒ ∂Φ ∂u (w, w) = 0 .
• We note that the monotone flux functions proposed by [START_REF] Godunov | A finite Difference Method for the Numerical Computation of Discontinuous Solutions of the Equations of Fluid Dynamics[END_REF] and [START_REF] Engquist | Stable and Entropy Condition Satisfying Approximations for Transonic Flow Calculations[END_REF] satisfy the hypothesis 5.1 whereas the numerical flux associated with the [START_REF] Lax | Systems of Conservation Laws[END_REF] scheme :

(5.21) Φ µ (u, v) = 1 2 f (u) + µ u + 1 2 f (v) -µ v
(where µ is chosen such that df (w) ≤ -µ in the domain of variation of w) does not.

Property 5.3

The limiter function r -→ ϕ(r) satisfies the identity

(5.22) (1 -σ) ϕ 1 + σ -1 + σ + (1 + σ) ϕ 3 + σ 1 + σ ≡ 2 , ∀ σ ∈ [0, δ]
for some parameter δ > 0 and the discrete relations

(5.23) k + 1 2 ϕ k -1 2 k + 1 2 -k - 1 2 ϕ k -3 2 k -1 2 = 1 , k = -2, -1, 0, +1, +2 .
Proposition 5.5. Accuracy of the predictor-corrector scheme If on one hand the flux function Φ is regular (i.e. absolutely continuous relatively to each variable, monotone (relations (3.17)) and satisfies the property 5.2, and if on the other hand the limiter function ϕ satisfies the monotonicity property 2.4, the property 5.3, and is derivable at the particular value r = 1, then the predictor-corrector scheme (5.4).(5.5) admits a truncation error

(5.24) ρ(h, u) ≡ 1 ∆t u(x j , t n+1 ) -u(x j , t n ) + 1 ∆x f n+ 1 2 j+ 1 2 (u) -f n+ 1 2 j-1 2 (u)
of second order accuracy : ρ(h, u) = O(h 2 ) if the following CFL restriction is satisfied :

(5.25) ∆t ∆x sup

w | df (w) | ≤ δ .
Proof of Proposition 5.5. Three cases are distinguished by the fact that the first derivative of u is null or not. We use the same notations as in Proposition 4.1.

• u x ≡ ∂u ∂x (x j , t n ) = 0 . We have (5.26) r j+k ≡ v n j+k -v n j+k-1 v n j+k+1 -v n j+k = 1 - u xx u x h + O(h 2 ) , j, k integers.
When we introduce this relation into (4.7) we have :

(5.27)

     v n, ± j+k+ 1 2 = v j + k + 1 2 h u x + 1 2 k 2 + k + 1 2 -ϕ ′ (1) h 2 u xx - 1 2 ∆t f x - 1 2 ∆t h k + 1 2 f xx + O(h 3 ) and
(5.28) v

n+ 1 2 j+k = v j + kh u x 1 2 k 2 h 2 u xx - 1 2 ∆t f x - 1 2 ∆t kh f xx + O(h 3 ) .
So that the ratio r n+ 1 2 j+k at t = (n + 1 2 )∆t also satisfies the relation (5.26) (!), i.e. :

(5.29) r

n+ 1 2 j+k ≡ v n+ 1 2 j+k -v n+ 1 2 j+k-1 v n+ 1 2 j+k+1 -v n+ 1 2 j+k = 1 - u xx u x h + O(h 2 ) .
We insert again this relation into (4.7). We deduce (5.30)

     v n, ± j+k+ 1 2 = v j + k + 1 2 h u x + 1 2 k 2 + k + 1 2 -ϕ ′ (1) h 2 u xx - 1 2 ∆t f x - 1 2 ∆t h k + 1 2 f xx + O(h 3 )
and the numerical flux can finally be developed at the point (j + k + 1 2 )h as f

n+ 1 2 j+k+ 1 2 = f v n, ± j+k+ 1 2 + O(h 3 ) (5.31)            f n+ 1 2 j+k+ 1 2 = f j + k + 1 2 h f x - 1 2 ∆t f ′ f x + k + 1 2 2 h 2 f xx - 1 2 ∆t k + 1 2 h 2 f ′ f xx + f ′ f x u x h 2 f xx + 1 8 ∆t 2 f ′ f ′′ u x f x + f ′ f xx + f ′′ (f x ) 2 + O(h 3 ) .
Then the finite difference of fluxes at the point x j is given by :

(5.32)

f n+ 1 2 j+ 1 2 -f n+ 1 2 j-1 2 = f x h - 1 2 ∆t h f ′ f xx + f ′′ u x f x + O(h 3 ) .
Finally the truncation error is evaluated by

(5.33) ρ(h, u) = u t + 1 2 ∆t u tt + f x - 1 2 ∆t f ′ f xx + f ′ u x f x + O(h 2 )
and the result is in this particular case a direct consequence of elementary algebra from the partial differential equation (1.1).

• u x = 0 , u xx = 0 . We observe first that v n+1 j is defined by the intermediate values v n+1/2 j for k = -2, -1, 0, +1, +2 because the interpolation (4.7) is a three-point scheme. Moreover these nodal values at t = (n + 1 2 )∆t are defined from the given values v n j+k ≡ u(x j+k , t n ) for k = -3, -2, -1, 0, +1, +2, +3. We have :

(5.34)

r n j+k = k -1 2 k + 1 2 + O(h) (5.35)(a) v n, - j+k+ 1 2 = v j + 1 2 h 2 u xx k 2 + k + 1 2 ϕ k -1 2 k + 1 2 + O(h 3 ) (5.35)(b) v n, + j+k+ 1 2 = v j + 1 2 h 2 u xx (k + 1) 2 -k + 1 2 ϕ k + 3 2 k + 1 2 + O(h 3 ) . Therefore the flux difference δf n j+k ≡ f n j+k+ 1 2 -f n j+k-1 2
are evaluated by the developments (5.36)

f n j+k = k h 2 f ′ u xx + O(h 3 ) , k = -2, -1, 0, +1, +2
because the coefficients of the partial derivatives of the flux function Φ in Taylor formula are null according to the property 5.3 (relations (5.23)). The values at the intermediate time admit the development

(5.37) v n+ 1 2 j+k = v j + 1 2 k 2 h 2 u xx - 1 2 ∆t k h 2 f ′ u xx + O(h 3 )
and we have

(5.38) r

n+ 1 2 j+k = -1 + 2k -λ f ′ 1 + 2k -λ f ′ + O(h 3 ) , k = -1, 0, +1 .
Using the Taylor formula again, we finally get :

(5.39)

                       f n+ 1 2 j+ 1 2 -f n+ 1 2 j-1 2 = ∂Φ ∂u (v j , v j ) -1 + 1 2 (1 -λf ′ ) ϕ 1 + λf ′ -1 + λf ′ + + 1 2 (1 + λf ′ ) ϕ 3 + λf ′ 1 + λf ′ + + ∂Φ ∂v (v j , v j ) 1 - 1 2 (1 -λf ′ ) ϕ 3 -λf ′ 1 -λf ′ + + 1 2 (-1 -λf ′ ) ϕ -1 + λf ′ 1 + λf ′ + O(h 3 ) .
To fix the ideas, we suppose f ′ > 0. Then ∂Φ ∂v is null according to Property 5.2 of the numerical flux function. Moreover, the coefficient in front of ∂Φ ∂u is also null thanks to Property 5.3 (relation (5.22)) if we have λ f ′ ≤ δ which is exactly the CFL condition (5.25). The proof is analogous when f ′ < 0. The sonic case f ′ = 0 is very simple because the brackets of (5.39) are both null according to (5.19) (which can be seen as a particular case of both (5.22) and (5.23) with σ = 0  following we will denote this new limiter function (5.41) by "Lagrange limiter". We note also that the idea of using Lagrange interpolation for the construction of limiter functions was at our knowledge first proposed by [START_REF] Leonard | A Stable and Accurate Convective Modelling Procedure Based on Quadratic Upstream Interpolation[END_REF] with the so-called Quick limiter. For a modification of this limiter that does not satisfy the monotonicity condition for negative values of the argument r, we refer to [START_REF] Cahouet | Uniformly Second Order Convergent Schemes for Hyperbolic Conservation Laws including Leonard's Approach[END_REF].

     ρ(h, u) ≡ 1 ∆t u(x j , t n+1 ) -u(x j , t n ) + + 1 2 ∆x f n j+ 1 2 (u) + f n+1 j+ 1 2 (u) -f n j-1 2 (u) -f n+1 j-1 2 (u)
of the modified Euler scheme (5.2).(5.3) is of second order accuracy if the following more restrictive CFL condition is satisfied :

(5.43) ∆t ∆x sup

w | f ′ (w) | ≤ 1 2 δ .
Proof of Proposition 5.6

As in Proposition 5.5 we divide the proof in three steps, following the value of u x and u xx .

• u x (x j , t n ) = 0. We develop the numerical flux at time t n and x = (k + j + 1 2 ) h as in Proposition 5.5 :

(5.44)

     f n k+j+ 1 2 = f j + k + 1 2 h u x f ′ + 1 2 k + 1 2 2 h 2 (u x ) 2 f ′′ + + 1 2 h 2 u xx k 2 + k + 1 2 -ϕ ′ (1) f ′ + O(h 3 ) .
On one hand, we have

(5.45) δf n j = h f x + O(h 3 ) and on the other hand :

(5.46)

u n+1 j+k = u j + (k h u x -∆t f x ) + 1 2 h k 2 h u xx -2k ∆t f xx + O(h 3 ) .
Therefore the ratio of gradients after the "tilda" step (5.2)(a) is given by (5.26) or (5.29). The extrapolated values at the interface (j + k + 1 2 ) are again evaluated according to (5.30) except that ∆t must be replaced by 2 ∆t. In an analogous way, the tilda flux defined in (5.3) admits a development (5.31) with ∆t. replaced by 2 ∆t. We deduce :

(5.47)

δf j = h f x -∆t h f ′ f xx + f ′′ u x f x + O(h 3 ) .
The truncation error admits exactly the form (5.33) and the property is proved in this case.

• u x (x j , t n ) = 0 , u xx (x j , t n ) = 0. The difference of fluxes around the point (j + k)h is given according to relation (5.36) due to Property 5.3. We have :

(5.48)

r j+k ≡ v n+1 j+k -v n+1 j+k-1 v n+1 j+k+1 -v n+1 j+k = -1 + 2 k -2 λ f ′ 1 + 2 k -2 λ f ′ + O(h)
according to (5.43) and (5.22). Therefore the development of the flux difference at point j h and at time (n + 1)∆t is simply developed :

(5.49) δf

,+1 j ≡ f n+1 j+ 1 2 -f n+1 j-1 2 = f ′ f xx + O(h 3 )
and the truncation error admits finally the form (5.33).

Numerical Tests with the Advection Equation

In this section we present numerical comparisons of the schemes studied in Part 5 for a simple model problem. We show that the truncation errors studied at propositions 5.5 and 5.6 are numerically second order accurate for the Lagrange limiter (5.41) especially at a nonsonic extremum. We study also the effect of the restrictive CFL condition (5.43) on the accuracy of the two step Heun scheme.

Moreover we compare the accuracy measured in the discrete ℓ 1 , ℓ 2 , ℓ ∞ , norms and in terms of the truncation error (see also Harten et al [1987]).

We focus on the one-dimensional linear advection equation (6.1)

∂u ∂t + a ∂u ∂x = 0 , 0 ≤ x ≤ 1 , t ≥ 0 , a = 1
with periodic boundary conditions :

(6.2) u(0) = u(1) .

We look at the advection of a regular profile with a (local) extremum at x = 1 2 without annulation of the third derivative at this point (which is the case with a sinus-type profile) giving unexpected superconvergence for the truncation error at x = 1 2 :

(6.3) du 0 dx 1 2 = 0 , d 3 u 0 dx 3 1 2 = 0 .
We define our profile u 0 as a C 2 class periodic function on the interval [0, 1] according to the conditions (6.4)(a)

u 0 (x) = 1 -x - 1 2 2 + x - 1 2 3 , 1 4 ≤ x ≤ 3 4 (6.4)(b) u 0 (0) = du 0 dx (0) = d 2 u 0 dx 2 (0) = u 0 (1) = du 0 dx (1) = d 2 u 0 dx 2
(1) = 0 (6.4)(c) u 0 polynomial of degree 5 in 0, 1 4 and in 3 4 , 1 .

The uniqueness of u 0 defined by (6.4) is clear due to the use of the classical finite element interpolation in the intervals [0, 1 4 ] and [ 3 4 , 1].

•

We study the Cauchy problem (6.1)(6.2) associated with the initial condition (6.5) u(0, x) = u 0 (x) , 0 ≤ x ≤ 1 during one period, i.e. for time t in [0, 1]. At time t = 1, the exact solution of (6.1).(6.2).(6.5) is equal to the initial condition u 0 and the error is therefore easy to evaluate. We discretize the equation (6.1) on meshes with cell diameters ∆x ≡ h that are constant on each mesh and chosen as powers of 1 2 : (6.6) 4, 5, 6, 7, 8, 9, 10 , and the computational nodes x j (the cell centers in the finite volume approach) are located at (6.7)

h = 2 -k k = 3,
x j = (j -1) h , j = 1, . . . , N (h) = 1 h .

We have tested three types of temporal schemes : the so-called "five points TVD scheme", the predictor-corrector scheme, and the Heun scheme (second order (iv) Min-mod limiter [START_REF] Harten | High Resolution Schemes for Hyperbolic Conservation Laws[END_REF]) [START_REF] Roe | Some Contributions to the Modelling of Discontinuous Flows[END_REF]) (6.17)(a)

(6.16)    ϕ minmod (r) ≡ 0 if r < 0 , ϕ minmod (r) = r if 0 ≤ r ≤ 1 , ϕ minmod (r) ≡ 1 if r ≥ 1 (v) Superbee limiter
ϕ superB (r) ≡ 0 if r < 0 , ϕ superB (r) = 2 r if 0 ≤ r ≤ 1 2 , (6.17)(b) ϕ superB (r) ≡ 1 if 1 2 ≤ r ≤ 1 , (6.17)(c) ϕ superB (r) = r if 1 ≤ r ≤ 2 , ϕ superB (r) ≡ 2 if r ≥ 2 .
(vi) The Lagrange limiter proposed in Part 5 (relations (5.41)).

(vii) Min Mod absolute value limiter, that we define according to (6.18)

ϕ MMA (r) = ϕ minmod | r | .
(viii) The UNO2 interpolation, which is a five point interpolation that is defined according to

(6.19) minmod(a, b) ≡ a ϕ minmod b a (6.20) ∂ 2 u j+1/2 = minmod u j-1 -2 u j + u j+1 , u j -2 u j+1 + u j+2 (6.21) u - j+1/2 = u j + 1 2 minmod u j -u j-1 + 1 2 ∂ 2 u j-1/2 , u j+1 -u j - 1 2 ∂ 2 u j+1/2 .
We note that this UNO2 scheme has a stencil of a priori 7 points for the one step temporal scheme (6.9) (only 5 points in the interpolations (i)-(vii)) and 13 points for the temporal schemes (6.10).(6.11) (compared to 9 with the other schemes described herein).

Known results established in [START_REF] Sweby | High Resolution Schemes Using Flux Limiters for Hyperbolic Conservation Laws[END_REF] are precised by the following proposition :

Proposition 6.1

The discretization of the scalar advection equation (6.1) joined with the five point scheme (6.9).(6.12) and some limiter function ϕ admits a truncation error

(6.22) ρ(h, u) ≡            1 ∆t u(x j , t n+1 ) -u(x j , t n ) + + 1 h a ∆t ∆x 2 u(x j , t n ) -u(x j-1 , t n+1 ) - 1 h a ∆t ∆x 1 - a ∆t ∆x v - j+1/2 (u, t n ) -v - j-1/2 (u, t n )  (where v - j+1/2 (u, t n
) is a notation for interpolation (6.12) applied with the values of the solution interpolated at the grid points x j+1/2 ) which is second order accurate (6.23) ρ(h, u) = O(h 2 ) at a local extremum of the function u : (6.24) ∂u ∂x x = x j , t = t n = 0 , ∀ h if the following condition (proposed in Part 4) holds : (6.25) ϕ(-1) + ϕ(3) = 2 .

Proof of Proposition 6.1 • From the relations (5.35)(a) we have :

(6.26) v - j+1/2 -v - j-1/2 = 1 2 h 2 ∂ 2 u ∂x 2 1 - 1 2 ϕ(-1) - 1 2 ϕ(3) + O(h 3 )
and ρ(h, u) admits the development

(6.27) ρ(h, u) =      ∂u ∂t + 1 2 ∆t ∂ 2 u ∂t 2 - 1 2 σ 2 h ∂ 2 u ∂x 2 + + 1 2 h σ (1 -σ) ∂ 2 u ∂x 2 1 - 1 2 ϕ(-1) - 1 2 ϕ(3) + O(h 3 ) .
Thus estimate (6.23) is a consequence of (6.25),(6.8) and (6.1).

We can compare on figure 6.1 several profiles obtained for different meshes at time t = 1 with the Heun scheme. In order to quantify the errors, we set Advection of a regular profile. Solutions obtained with the Lagrange limiter and the 5 points uno2 scheme.

(6.28) || u h (t = 1) -u(t = 1) || ℓ 1 = h N (h) j=1 | u j, h (t = 1) -u 0 (x j ) | (6.29) || u h (t = 1) -u(t = 1) || ℓ 2 = h N (h) j=1 | u j, h (t = 1) -u 0 (x j ) | 2 1/2 (6.30) || u h (t = 1) -u(t = 1) || ℓ ∞ = max j=1, ..., N (h) | u j, h (t = 1) -u 0 (x j ) | .  0

•

We present four numerical experiments associated respectively to the following choice concerning the temporal scheme : exp 1 Five points TVD scheme (6.9) CFL : σ = 1 2 exp 2 Predictor-corrector scheme (6.10) CFL : σ = 1 2 exp 3 Heun scheme (6.11) CFL : σ = 1 2 exp 4 Heun scheme (6.11) CFL : σ = 1 4 . For each of these numerical experiments we have advected the initial profile defined in (6.4) during one period with seven different meshes defined in (6.6) and the eight different fluxes (i) to (viii). We present on figures 6.2 to 6.5 the ℓ 1 , ℓ 2 , ℓ ∞ errors defined in (6.28)-(6.30) as functions of log 2 (1/h) and the truncation error (defined respectively in (6.22), (5.24) and (5.42)) at the particular point x = 1 2 where the maximum occurs (it is always a mesh point). All the residuals are proposed in terms of their base 2 logarithm. Therefore if some residual r(h) is "at the order α" : (6.31) r(h) = C h α 1 + o(h) the slope of the curve log 2 [r(h)] as a function of log 2 (1/h) is simply equal to -α and is directly readable on the figures. We notice first that the truncation errors at the extremum (x = 1 2 ) have exactly the behavior predicted in (6.23), (5.25) and (5.43); with σ = 1 2 the order of the truncation error at the extremum is only 1 with the Heun scheme (Fig. 6.4.d) therefore it is of order 2 with the same numerical scheme and σ = 1 4 (Fig. 6.5.d). The five point scheme (Fig. 6.2) show that the MUSCL limiter and the UNO2 scheme are really second order accurate in the L ∞ norm (Fig. 6.2.c). When we use a two step scheme and a Courant number σ = 1 2 (Fig. 6.3 and 6.4) the Lagrange limiter is "better than second order accurate" (order 2.2 in the L ∞ norm) and the other limiters are second order accurate but "only" in the norms L1 and L2. With the Heun scheme and a severe CFL restriction (Fig. 6.5) the results of the Lagrange limiter are degraded despite the fact that the truncation error remains everywhere second order accurate !



Franc ¸ois Dubois

Conclusion

In this contribution, we have proposed a concept of convexity preserving property for the approximation of scalar conservation laws with the Van Leer's numerical method. New restrictions have been derived for the construction of the associated limiter functions. We have proved that the method of lines is well posed for u 0 in ℓ 1 ∩ BV and new conditions on the limiter have been given to prove the TVD property of the associated solution. We have proved that second order accuracy (in the sense of the truncation error) can be maintained, even at a nonsonic extremum ; this last property and Total Variation Diminishing are compatible with a discretization in time with a two-level Runge-Kutta scheme under new restrictions on the limiter function that have been detailed. An example of such a limiter (the so-called Lagrange limiter) has been proposed and implemented in the case of the advection equation. Theoretical results on orders of convergence have been confirmed numerically. This concept of convexity preserving interpolation could be extended in two directions : the treatment of multidimensional scalar problems and the approximation of systems of conservation laws.

8.

Figure 2 . 2 .

 22 Figure 2.2. Convexity of the interpolated value at the intermediate points.

FigureFigure 2 . 3 .

 23 Figure 2.3 represents the constraints associated with (2.23).(2.25) ( except the second inequality of (2.23) !).

Figure 3 . 1 .

 31 Figure 3.1. Admissible regions for the limiter ϕ. The dark shaded region corresponds to the conditions (3.12).(3.14) and the clear shaded set completes it to describe (2.30) (2.31).

  the property (3.38) corresponds exactly to the desired result. Otherwise, we have (38) is in default, we consider θ such that µ(θ) < m and τ defined by (3.40) τ = sup {t, t ≤ θ , µ(t) ≥ m } . We have 0 ≤ τ < θ and µ(τ ) = m by continuity. According to (3.38), µ is non-decreasing inside the interval [τ, θ]. So that (3.41) µ(θ) ≥ µ(τ )

  limiter function ϕ of the relation (2the v j ′ s according to the relations (2.27).(2.29), i.e.

Figure 5

 5 Figure 5.1. The Lagrange limiter (defined by the relations (5.41)).

Figure

  Figure 6.1.Advection of a regular profile. Solutions obtained with the Lagrange limiter and the 5 points uno2 scheme.

Figure 6 . 2 .Figure 6 Figure 6 Figure 6

 62666 Figure 6.2. Advection of a regular profile. Errors for the flux corrected transport type temporal scheme with Courant number = 0.5.

Property 5.1 We suppose that the limiter function ϕ defined in (2.9) satisfies the following inequality :

(5.6) ∃ M > 0 , ∀ r > 0 , ϕ(r) r ≤ M .

From the Figure 3.1, we have clearly M ≥ 1.

Proposition 5.1

The first order scheme (5.1) joined with (2.27).(2.29) is TVD under the hypotheses (2.30).(2.32), (3.12).(3.13) and (5.6) for the limiter function if the following Courant-Friedrichs-Lewy condition holds :

(5.7)

with the partial gradients of the fluxes α j+ 1 2 and β j+ 1 2 defined by the formulae (3.21).(3.22).

Proof of Proposition 5.1 •

The incremental form of the scheme (5.1) has the expression

(5.8)

(we drop the index n when there is no ambiguity). Therefore it is under the form considered by [START_REF] Harten | High Resolution Schemes for Hyperbolic Conservation Laws[END_REF] :

(5.9)

Harten's conditions must be satisfied :

(5.11)(a)

The inequalities (5.11)(a)(b) are a direct consequence of the Theorem 3.1. On the other hand, we have :

(5.12)(a)

1 + 1 2



Nonlinear Interpolation and Total Variation Diminishing Schemes

(5.12)(b) 1 -1 2 ϕ j+1 + 1 2 ϕ j r j ≤ 1 + M 2 and the inequality (5.11)(c) is a direct consequence of the CFL condition (5.7).

Proposition 5.2 [START_REF] Shu | Efficient Implementation of Essentially Non-Oscillatory Shock-Capturing Schemes[END_REF]) The modified Euler scheme (5.2).( 5.3) is total variation diminishing under the same hypotheses as in Proposition 5.1 and the same CFL restriction (5.7).

•

The predictor-corrector scheme is more complicated to study. We begin with the following lemma :

We consider a numerical scheme given by the following incremental form : (5.13)

This scheme is TVD if the following inequalities hold for each integer j :

e j+ 1 2 ≥ 0 . This proposition generalizes the one proposed by [START_REF] Harten | High Resolution Schemes for Hyperbolic Conservation Laws[END_REF] and used previously in this paper. The proof is straightforward. We omit it.

•

We now analyze the TVD property for the predictor-corrector scheme (5.4). (5.5). This scheme does not belong to the general class considered by [START_REF] Shu | Efficient Implementation of Essentially Non-Oscillatory Shock-Capturing Schemes[END_REF]. In fact, we have not proved that under the form (5.4).(5.5) the predictorcorrector scheme is total variation diminishing but no conter-examples have been found. Nevertheless we modify the scheme (5.4).(5.5) in the following way : Definition 5.1 For k equal to n and n + 1 2 let C j+ 1 2 and D j-1 2 be defined by the relations

k = 0 respectively). The truncation error (5.24) is again evaluated according to relation (5.33) and the property is established in this second case.

• u x = 0 , u xx = 0. We have clearly v n, ±

It is straightforward to develop the truncation error (5.24) and to verify the property. This ends the proof.

Remark 5.2 If the limiter function satisfies Property 5.3 and is affine, it takes necessarily the form (5.40) ϕ(r) = 1 + a (r -1) . This kind of function is not compatible with the monotony-convexity conditions (2.30)-(2.32) and the sufficient TVD conditions (3.12).(3.13) if (5.40) holds for all the real values of the argument r. Therefore the actually known limiters (e.g. minmod, superbee (see [START_REF] Roe | Some Contributions to the Modelling of Discontinuous Flows[END_REF]), MUSCL (see [START_REF] Van Leer | Towards the Ultimate Conservative Scheme IV. A New Approach to Numerical Convection[END_REF]), etc. ) do not satisfy both (5.22).(5.23). Nevertheless , the function defined as follows (5.41)(a) ϕ(r) = 0 , r ≤ -3 3]. Then (5.23) is satisfied. Moreover (5.22) holds for δ = 1 2 and Property (5.1) is also satisfied with M = 5 2 . This limiter satisfies also the TVD conditions (3.12).(3.13) of Property 3.1 with α = 3 2 and the properties 2.4 and 2.5 of monotonocity and convexity. Finally we observe that the interpolate value

(according to the notation proposed in (2.1)) corresponds to the Lagrange polynomial interpolation of degree 2 if and only if ϕ satisfies (5.40) with a = 1 4 . In the Runge-Kutta). All these schemes are parameterized by the interpolation u - j-1/2

(at the left side of the interface x j-1/2 ) from the cell center values (6.7) in the spirit described in Part 2 of this paper and detailed in the following. The temporal schemes are associated with the Courant number (6.8) σ = a ∆t h .

To be precise we give the formulae for this temporal integration.

• Five points TVD scheme (see e. g. [START_REF] Sweby | High Resolution Schemes Using Flux Limiters for Hyperbolic Conservation Laws[END_REF]) :

(6.9)

.

• Predictor-Corrector Scheme (see also (5.4).(5.5) ) :

(6.10)(a)

.

• Heun scheme (see also (5.2).(5.3)) (6.11)(a)

. The interpolation at point x j+1/2 is chosen according to a three point interpolation as in the previous sections :

(6.12)

or with the UNO2 interpolation proposed by Harten-Osher [1987]. Concerning the limiter functions we have restricted ourselves to the following ones : (i) First-order upwind scheme (6.13) ϕ upwind (r) ≡ 0 (ii) Lax Wendroff type scheme (6.14) ϕ LW (r) ≡ 1 .

We remark that (6.14) joined with (6.12) defines the [START_REF] Lax | Systems of Conservation Laws[END_REF] scheme only when it is associated with the temporal scheme (6.9). The two other cases justify the "type" restriction in our denomination.

(iii) Van Leer's MUSCL limiter [1977] (6.15)(a) ϕ MUSCL (r) ≡ 0 if r < 0 , ϕ MUSCL (r) = 2 r if 0 ≤ r ≤ 1 3 (6.15)(b) ϕ MUSCL (r) = 1 2 (1+r) if 1 3 ≤ r ≤ 3 , ϕ MUSCL (r) = 2 if r ≥ 3 .