Keywords: équation HJB, schéma non monotone, estimation d'erreur en norme L 1, schéma anti-diffusif, condition initiale discontinue

Convergence d'un schéma non monotone pour les équations HJB avec donnée initiale discontinue

. Dans ce papier, on prouve la convergence, en norme L 1 , à l'ordre 1, pour une condition initiale discontinue. Le caractère anti-diffusif du schéma est illustré par quelques exemples numériques.

Introduction

We consider the following first order Hamilton-Jacobi-Bellman equation:

ϑ t (t, x) + max α∈A (f (x, α) ϑ x (t, x)) = 0, t > 0, x ∈ R, (1a)
ϑ(0, x) = v 0 (x), x ∈ R, (1b)
with discontinuous initial data v 0 . In optimal control theory, the solution ϑ of equation [START_REF] Agbrall | High order numerical discretization for hamilton-jacobi equations on triangular meshes[END_REF] corresponds to the value function of the optimized problem [START_REF] Barles | Solutions de viscosité des équations de Hamilton-Jacobi[END_REF][START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF]. It is usual that this function, as well as the "final" cost v 0 , is discontinuous (for instance for target or Rendez-Vous problems).

In the continuous case (v 0 is continuous), there are several contributions dealing with numerical schemes for the discretization of HJB equations [START_REF] Crandall | Two approximations of solutions of Hamilton Jacobi equations[END_REF][START_REF] Falcone | Semi-lagrangian schemes for Hamilton-Jacobi equations, discrete representation formulae and godunov methods[END_REF][START_REF] Agbrall | High order numerical discretization for hamilton-jacobi equations on triangular meshes[END_REF][START_REF] Osher | High essentially nonoscillatory schemes for Hamilton-Jacobi equations[END_REF]. The work of Barles and Souganidis [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF] gives a general framework for the convergence of approximated solutions towards the viscosity solution, under generic monotonicity stability and consistency assumptions. In that case, an error bound in ∆x γ 2 is exhibited, ∆x being the mesh size, whenever the function v 0 is bounded γ-Hölder.

Nevertheless, when we deal with discontinuous intial data v 0 , classical monotone schemes are no more adapted. In fact, if we attempt to use these schemes, we observe an increasing numerical diffusion around discontinuities, and this is due to the fact that monotone schemes use at some level finite differences and/or interpolation technics.

In this paper, we analyse an explicit scheme for the numerical resolution of [START_REF] Agbrall | High order numerical discretization for hamilton-jacobi equations on triangular meshes[END_REF], closely related to the HJB-UltraBee scheme proposed in [START_REF] Bokanowski | Anti-diffusive schemes for linear advection and application to Hamilton-Jacobi-Bellman equations[END_REF]. We give a convergence proof, show anti-dissipative properties of the scheme, and give a L 1 -error estimate.

The UltraBee scheme has been developed to study compressible gas dynamics [START_REF] Després | Contact discontinuity capturing schemes for linear advection and compressible gas dynamics[END_REF], and more precisely to solve the transport equation. A generalization to HJB equations and many academic tests have been done to evaluate the behaviour of the scheme when dealing with discontinuities [START_REF] Bokanowski | Anti-diffusive schemes for linear advection and application to Hamilton-Jacobi-Bellman equations[END_REF]. Its comparison with the viability algorithm [5] [START_REF] Saint-Pierre | Approximation of viability kernel[END_REF] was encouraging to study more deeply convergence results.

Let us stress on that this scheme is explicit and non-monotonous (neither -monotone in the sense of R. Abgrall [START_REF] Agbrall | High order numerical discretization for hamilton-jacobi equations on triangular meshes[END_REF]). As far as we know, there are few non-monotone schemes that have been proved to converge for HJ equations. In [START_REF] Lions | Convergence of muscl and filtered schemes for scalar conservation laws and hamilton jacobi equations[END_REF], Lions and Souganidis show the convergence of a TVD second order scheme, but which is implicit.

For a large class of discontinuous initial data v 0 , and under some asumptions on the dynamics f (x, α) (see asumption (H3) in Section 2), we obtain a first-order error bound in L 1 norm, of the following form:

V (t n , .) -ϑ(t n , .) L 1 (R) ≤ C(L, t n , v 0 )∆x ∀t n ≥ 0, ( 2
)
where ϑ is the viscosity solution of (1), V is the numerical approximation and C(L, t n , v 0 ) is a positive contant wich depends only on t n , on L (Lipschitz constant of x → f (x, α), see Section 2.1), t n , and on the total variation of v 0 (see Definition 2.2). This is the first result of this kind to our knowledge, in the case of discontinuous viscosity solutions. Furthermore, in some particular cases, such as the eikonal equation (ϑ t +|ϑ x | = 0, corresponding to A := {±1} and f (x, α) = α), the constant C does not depend of t n . This shows a "non-diffusive" behavior of the scheme, as identified in [START_REF] Després | Contact discontinuity capturing schemes for linear advection and compressible gas dynamics[END_REF], for the advection case with constant sign velocity.

The paper is organized as follows: Sections 2 and 3 are devoted to the proof of (2) in the case of piece-wise constant initial data. In Section 4, we prove (2) for more general discontinuous initial data. In Section 5, we weaken some assumptions made before on the velocities and prove a similar estimate for a modified scheme. We conclude in Section 6 by some numerical illustrations, in particular showing the non-diffusive behavior of the proposed scheme. The appendix contains some useful technical results.

Preliminaries

Notations and preliminary results

We denote by v 0 : R → R a bounded lower semicontinuous (l.s.c.) function, A a compact set, and f : R × A → R a continuous function satisfying:

∃L ≥ 0, ∀α ∈ A, ∀x, y ∈ R, |f (y, α) -f (x, α)| ≤ L|y -x|. (3)
It is known that, under these assumptions, equation (1) admits a unique bounded l.s.c. bilateral viscosity solution [START_REF] Barles | Solutions de viscosité des équations de Hamilton-Jacobi[END_REF][START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF]. For convenience of the reader, we recall in the following definition the viscosity notion we use. Definition 2.1. A bounded l.s.c. function ϑ is a bilateral viscosity solution of (1) if, i) for any φ ∈ C 1 ((0, +∞) × R) and at any local minimum (t, x) ∈]0, +∞[×R of ϑφ, φ t (t, x) + max α∈A (f (x, α) φ x (t, x)) = 0.

ii) lim inf then equation ( 1) can be rewritten in the equivalent form:

ϑ t (t, x) + max(f m (x) ϑ x (t, x), f M (x) ϑ x (t, x)) = 0, t > 0, x ∈ R, (4a)
ϑ(0, x) = v 0 (x), x ∈ R. ( 4b
)
INRIA Notice that by [START_REF] Barles | Solutions de viscosité des équations de Hamilton-Jacobi[END_REF] and the definitions of f m and f M , we have f m (x) ≤ f M (x), ∀x ∈ R, and also (H1) f m and f M are L-Lipschitz continuous.

For simplicity of presentation, we first suppose the simplifying additional assumptions:

(H2) f m and f M are of constant sign, (H3) f m and f M are increasing functions of x.

These assumptions will be weakened in Section 5.

Remark 2.1. Assumptions (H1)-(H3) are satisfied for the particular case of the Eikonal equation: ϑ t +c|ϑ x | = 0, where c is a given constant and c ≥ 0

(taking f M (x) = -f m (x) = c).
We now define exact and approximated characteristics that will be very useful throughout the paper. Let x j := j ∆x be a uniform mesh with ∆x > 0 and j ∈ Z, and denote:

x j+ 1 2 := (j + 1 2
) ∆x, and I j :=]x j-1 2 , x j+ 1 2 [. As the dynamics f m and f M are lipschitz continuous, then for any x ∈ R we can define characteristics X M

x and X m x as the solutions of the Cauchy problems:

ẊM x (t) = f M (X M x (t)), X M x (0) = x, and Ẋm x (t) = f m (X m x (t)), X m x (0) = x. (5)
We also define approximated piece-wise constant velocity functions f S M and f S m , such that, ∀j ∈ Z:

f S M (x) = f M (x j ), ∀x ∈ I j , f S M (x j+ 1 2 ) = 0 if f M (x j ) f M (x j+1 ) ≤ 0, f M (x j ) otherwise, and
f S m (x) = f m (x j ), ∀x ∈ I j , f S m (x j+ 1 2 ) = 0 if f m (x j ) f m (x j+1 ) ≤ 0, f m (x j ) otherwise.
In general, the differential equation

χx (t) = f S M (χ x (t)), a.e. t ≥ 0, χ x (0) = x, (6)
may have more than one absolutely continuous solution. The non-uniqueness comes from the behavior on boundary points (x j+ 1 2 ) in the case when the velocity vanishes (or changes sign). Throughout this paper, we shall denote by X M,S x the function defined by: X M,S x solution of (6), and (7a)

if ∃t * ≥ 0 s.t. X M,S x (t * ) = x j+ 1 2 , f M (x j )f M (x j+1 ) ≤ 0 then X M,S x (t) = x j+ 1 2 ∀t ≥ t * . ( 7b
)
We have uniqueness of such solution (see appendix A). We construct X m,S

x in a similar way.

Lemma 2.1. Assume that (H1) holds. Let a, b be in R. The following assertions are satisfied:

(i) For every t ≥ 0, we have:

max |X M,S a (t) -X M a (t)|, |X m,S b (t) -X m b (t)| ≤ 1 2 Lt e Lt ∆x,
where L is the Lipschitz constant of f M and f m (see (H1)).

(ii) Let s ≤ t and assume that X m,S a

(θ) ≥ X M,S b (θ), for every θ ∈ [s, t]. Then |X m,S a (t) -X M,S b (t)| + ∆x ≤ e L(t-s) (|X m,S a (s) -X M,S b (s)| + ∆x).
On the other hand, if

X m a (θ) ≥ X M b (θ), for every θ ∈ [s, t], then |X m a (t) -X M b (t)| ≤ e L(t-s) (|X m a (s) -X M b (s)|).
(iii) Assume (H1) and (H3). If a > b, then the functions

t -→ X M,S a (t) -X m,S b (t) and t -→ X M a (t) -X m b (t) are increasing for t ≥ 0. (iv) Assume (H1) -(H3). If ∆x 2 < a -b, then the function t -→ X M,S a (t) -X m b (t) is increasing for t ≥ 0. (v) Assume (H1) -(H3). If X m,S b (θ) ≥ X m,S a (θ), for every θ ∈ [s, t]. Then we have |X m,S b (t) -X m,S a (t)| + ∆x ≤ e L(t-s) (|X m,S b (s) -X m,S a (s)| + ∆x). On the other hand, if X M,S a (θ) ≤ X M,S b (θ), for every θ ∈ [s, t], then |X M,S b (t) -X M,S a (t)| + ∆x ≤ e L(t-s) (|X M,S b (s) -X M,S a (s)| + ∆x).
Proof. (i) Let x ∈ R and j ∈ Z such that x ∈ I j . For y ∈ R, the following inequality holds

|f S M (x) -f M (y)| = |f M (x j ) -f M (x) + f M (x) -f M (y)| ≤ 1 2 L∆x + L|x -y|.
Therefore, for all t ≥ 0, we get:

|X M,S a (t) -X M a (t)| = | t 0 f S M (X M,S a (s)) -f M (X M a (s)) ds| ≤ 1 2 Lt∆x + L t 0 |X M,S a (s) -X M a (s)|ds.
Hence by using Gronwall's Lemma we obtain the desired estimate for

|X M,S a (t) -X M a (t)|. The bound for |X m,S b (t) -X m b (t)| is obtained in the same way. INRIA (ii) Let δ(θ) := X m,S a (θ) -X M,S b (θ) + ∆x. We have d dθ δ(θ) = f S m (X m,S a (θ)) -f S M (X M,S b (θ)) ≤ f S M (X m,S a (θ)) -f S M (X M,S b (θ)) ≤ L X m,S a (θ) -X M,S b (θ) + ∆x = L δ(θ).
The result follows by using a Gronwall estimate. The proof for the other estimate is similar.

(iii) Define δ(t) := X M,S a (t) -X m,S b
(t), and t * := inf{t > 0, δ(t) < 0}. As δ(0) > 0, then t * > 0. Then for all t ∈ [0, t * [, δ(t) ≥ 0 and we have:

d dt δ(t) = f S M (X M,S a (t)) -f S m (X m,S b (t)) ≥ f S m (X M,S a (t)) -f S m (X m,S b (t)),
which is positive, for t ∈ [0, t * [, by (H3). We deduce that δ is increasing on [0, t * [. Suppose that t * is finite, then we get by continuity of X M,S a and X m,S b that δ(t * ) ≥ δ(0) > 0. This contradiction shows that t * = +∞ and δ is increasing for all t ≥ 0. (The proof is similar for

t -→ X M a (t) -X m b (t).) (iv) Similar arguments as in (iii) (v) The proof is obtained as in (ii). 2
Lemma 2.2. Let v 0 be a bounded l.s.c. function on R, and assume that (H1) holds. Then, the unique viscosity solution of ( 4) is given by:

ϑ(t, x) = min y∈[X M x (-t),X m x (-t)] v 0 (y), ∀t > 0, x ∈ R. (8)
Proof. Notice that equation (4a) can be rewritten as follows

ϑ t (t, x) + max α∈[0,1] ((1 -α)f m (x) + αf M (x)) • ϑ x (t, x) = 0, t > 0, x ∈ R. (9)
The unique viscosity solution of equation ( 9) satisfying the initial condition (4b) (see [START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF]) is given by ϑ(t, x) = min

α∈L ∞ (R + ,[0,1]) v 0 (X α x (-t)) = min y∈[X M x (-t),X m x (-t)] v 0 (y),
where X α x is the solution of X α x (0) = x and Ẋα

x (t) = (1 -α(t))f m (X α x (t)) + α(t)f M (X α x (t)) for t ≥ 0 with α ∈ L ∞ (R + , [0, 1]). 2
We also consider the function ϑ S which is defined in an analogous way as in ( 8), but with the approximated characteristics X M,S x , X m,S

x instead of X M x and X m x :

ϑ S (t, x) := min y∈[X M,S x (-t),X m,S x (-t)] v 0 (y), ∀t > 0, x ∈ R. ( 10
)
This approximate function will play an important role throughout the paper.

Proposition 2.1. Under assumption (H1), we have 1 :

ϑ(t, .) -ϑ S (t, .) L 1 (R) ≤ Lte Lt T V (v 0 ) ∆x. ( 11
)
Proof. By using Lemma B.1 (taking

a 1 x = X M x (-t), b 1 x = X m x (-t), and a 2 x = X M,S x (-t), b 2 x = X m,S
x (-t)) (whose inverse functions are X M x (t), X m x (t), and X M,S x (t), X m,S x (t) respectively) together with Lemma 2.1 (i), we obtain the L 1 -norm estimate.

2 Using Lemma B.3, we also obtain Proposition 2.2. Under assumption (H1),

T V (ϑ S (t, .)) ≤ T V (v 0 ), ∀t ≥ 0.
For E ⊂ R a given set, we shall use in all the sequel the notation 1 E for the function defined by:

1 E (x) := 1 if x ∈ E, 0 otherwise.

The HJB-UltraBee scheme

Let ∆t > 0 be a constant time step, and t n := n∆t for n ≥ 0. We set the following notation for local "CFL" numbers:

ν m j := ∆t ∆x f m (x j ) and ν M j := ∆t ∆x f M (x j ),
and ν m = {ν m j , j ∈ Z}, ν M = {ν M j , j ∈ Z}. An adaptation of the UltraBee scheme has been proposed and numerically tested for the HJB equation [START_REF] Bokanowski | Anti-diffusive schemes for linear advection and application to Hamilton-Jacobi-Bellman equations[END_REF]5,[START_REF] Bokanowski | An adaptative antidissipative method for optimal control problems[END_REF]. Let us recall this formulation. We first introduce the notation for the average values of initial data:

V 0 j := 1 ∆x x j+ 1 2 x j-1 2 v 0 (x)dx, j ∈ Z. (12)
As we deal with an explicit scheme, we will assume in all the paper that the mesh size satisfies the CFL condition:

max x∈R max(|f m (x)|, |f M (x)|) ∆t ∆x ≤ 1. ( 13
)
1 Throughout this paper, we will use the following definition for the variation of a real-valued function w.

Definition 2.2. Let w be a real-valued function. the total variation of w is defined by: Initialization: We compute the initial averages V 0 = (V 0 j ) j∈Z as defined in [START_REF] Lions | Convergence of muscl and filtered schemes for scalar conservation laws and hamilton jacobi equations[END_REF]. Loop: For n ≥ 0, We compute V n+1 = (V n+1 j ) j∈Z by: Define "fluxes" V n j+ 1 2 (ν) for ν ∈ {ν m , ν M } as follows: If ν j ≥ 0 for every j ∈ Z, define:

T V (w) := sup 8
V n j+1/2 (ν) :=    min(max(V n j+1 , b + j (ν)), B + j (ν)) if ν j > 0 V n j+1 if ν j = 0 and V n j = V n j-1 V n j if ν j = 0 and V n j = V n j-1 , where b + j (ν) := max(V n j , V n j-1 ) + 1 νj (V n j -max(V n j , V n j-1 )), B + j (ν) := min(V n j , V n j-1 ) + 1 νj (V n j -min(V n j , V n j-1 )), (14)
If ν j ≤ 0 for every j ∈ Z, define:

V n j-1/2 (ν) :=    min(max(V n j-1 , b - j (ν)), B - j (ν)) if ν j < 0 V n j-1 if ν j = 0 and V n j = V n j+1 V n j if ν j = 0 and V n j = V n j+1 , where b - j (ν) := max(V n j , V n j+1 ) + 1 |νj | (V n j -max(V n j , V n j+1 )), B - j (ν) := min(V n j , V n j+1 ) + 1 |νj | (V n j -min(V n j , V n j+1 )). (15)
For ν ∈ {ν m , ν M }, let

V n+1 j (ν) := V n j -ν j V n j+ 1 2 (ν) -V n j-1 2 (ν) . Finally, set V n+1 j := min V n+1 j (ν m ), V n+1 j (ν M ) for every j ∈ Z.
In all the sequel, we shall use the notation:

S U B (V n ) := min V n+1 j (ν m ), V n+1 j (ν M ) j∈Z .
Under assumption (H2), we notice that the resulting scheme is well defined. We associate to the scheme values (V n j ) j , the l.s.c. step function V (t n , .) defined for every t n ≥ 0, x ∈ R by

V (t n , x) := V n j if x ∈]x j-1 2 , x j+ 1 2 [, min(V n j , V n j+1 ) if x = x j+ 1 2 . ( 16
)
RR n 0123456789

A first case where fronts do not meet

We consider here the case of an initial data of the form

v 0 (x) := 1 ]-∞,b[ (x) + 1 ]a,+∞[ (x), (17)
where a, b ∈ R ∪ {±∞} and a > b. Our aim in this section is to study in this simple case the relationship between the viscosity solution at time t n , ϑ(t n , .) and the values V n computed by the HJB-UB algorithm. We show, under the CFL condition, an L 1 -error estimate in ∆x stated in the following theorem:

Theorem 2.1. We assume that (H1) -(H3) and the CFL condition (13) are satisfied. Let v 0 be defined by (17), ∆x be such that a ≥ b + 3∆x, and ϑ be the viscosity solution of (4). Then

V (t n , .) -ϑ(t n , .) L 1 (R) ≤ (1 + Lt n e Ltn )T V (v 0 ) ∆x, ∀n ≥ 0. ( 18
)
Before dealing with the proof of Theorem 2.1, it will be useful to have the analytic expression of the viscosity solution ϑ (known in this case, since v 0 has a simple form): Remark 2.2. Assume assumption (H1) is satisfied, a > b, and v 0 as in (17). Then using Lemma 2.2 and by a direct calculation we obtain that the l.s.c. viscosity solution of ( 4) is given by :

ϑ(t, x) := 1 ]-∞,X m b (t)[ (x) + 1 ]X M a (t),+∞[ (x). ∀t ≥ 0, x ∈ R.
Also, the function ϑ S defined by [START_REF] Falcone | Semi-lagrangian schemes for Hamilton-Jacobi equations, discrete representation formulae and godunov methods[END_REF] satisfies:

ϑ S (t, x) = 1 ]-∞,X m,S b (t)[ (x) + 1 ]X M,S a (t),+∞[ (x), ∀t ≥ 0, x ∈ R.
In the following we denote by ϑ S,n the cell averages of ϑ S (t n , •), defined by ϑ S,n j

:= 1 ∆x Ij ϑ S (t n , x) dx for j ∈ Z, n ∈ N. (19)
Lemma 2.3. Assume that (H1) -(H3) hold, v 0 is defined by (17), and a ≥ b + 3∆x. Then the values V n j computed by algorithm 1 satisfy:

V n j = ϑ S,n j , ∀n ≥ 0, ∀j ∈ Z.
Proof. Case 1. We consider the case of v 0 (x) := 1 ]a,∞[ (x), and proceed by recursion on n ≥ 0 (the case v 0 (x) = 1 ]-∞,b[ (x) may be treated in a similar way). Let j ∈ Z be such that the discontinuity position

x n := X M,S a (t n ) lies in ]x j-1 2 , x j+ 1 2 ]. INRIA Then we have V n k = 0 for k < j, V n j ∈ [0, 1[, and V n k = 1 for k > j. By straightforward calculations, if ν M ≥ 0, we can verify that ϑ S,n+1 j-1 = V n+1 j-1 = 0, ϑ S,n+1 j = V n+1 j = max(0, V n j -ν M j ), ϑ S,n+1 j+1 = V n+1 j+1 = 1 - ν M j+1 ν M j max(0, ν M j -V n j ) if ν M j > 0 1 if ν M j = 0 and, if ν M ≤ 0, ϑ S,n+1 j-1 = V n+1 j-1 = |ν M j-1 | |ν M j | max(1, V n j + |ν M j |) -1 if ν M j < 0, 0 if ν M j = 0 ϑ S,n+1 j = V n+1 j = min(1, V n j + |ν M j |), ϑ S,n+1 j+1 = V n+1 j+1 = 1,
and in all cases, ϑ

S,n+1 k = V n+1 k = 0, ∀k ≤ j -2, and ϑ S,n+1 k = V n+1 k = 1, ∀k ≥ j + 2.
This means that the HJB-UltraBee scheme computes exactly V n+1 (ν M ) from V n for the advection with velocity f S M . In the same way we obtain that V n+1 (ν m ) computes exactly the average values from V n for the advection with velocity f S m . Hence we have, for every k ∈ Z,

V n+1 k (ν M ) = 1 ∆x I k 1 ]X M,S xn (∆t),∞[ (x)dx, (20)
V n+1 k (ν m ) = 1 ∆x I k 1 ]X m,S xn (∆t),∞[ (x)dx. ( 21
) Since X m,S xn (∆t) ≤ X M,S xn (∆t) we deduce that V n+1 k (ν M ) ≤ V n+1 k (ν m ),
and, for all k ∈ Z,

V n+1 k = V n+1 k (ν M ).
This concludes the proof of ϑ

S,n+1 = V n+1 . Case 2. Consider the case of v 0 (x) := 1 ]-∞,b[ (x) + 1 ]a,∞[ (x). As a -b ≥ 3∆x, by Lemma 2.1 (iii), we get X M,S a (t) ≥ 3∆x + X m,S b
(t) for t ≥ 0. This means that there are at least two successive cells with value

V n j = V n j+1 = 0 separating X m,S b (t n ) and X M,S a (t n ).
Then as in Case 1 we obtain for k ≥ j + 1 that (20) and ( 21) are also valid, and thus

for k ≥ j + 1, V n+1 k = V n+1 k (ν M ) = ϑ S,n+1 k (i.
e, an exact evolution following the discontinuity position X M,S a (t n+1 )). Also, in the same way as in Case 1, we obtain

for k ≤ j, V n+1 k = V n+1 k (ν m ) = ϑ S,n+1 k
RR n 0123456789 (i.e, an exact evolution following the discontinuity position X m,S b (t n+1 )). This concludes to

V n+1 k = ϑ S,n+1 k for all k ∈ Z. 2 Proof of Theorem 2.1: Since V n j = ϑ S,n
j , for all j ∈ Z and n ≥ 0, we obtain:

ϑ S (t n , .) -V (t n , .) L 1 (R) ≤ ∆x T V (ϑ S (t n , .)) = 2∆x = T V (v 0 ) ∆x. ( 22
)
Inequalities ( 22) and ( 11) lead to the desired result (18). 2

Remark 2.3. Lemma 2.3 shows the behaviour of the HJB-UltraBee scheme: when the two discontinuities are far from each other, the algorithm is able to recover, from the average values, their exact positions X M,S a (t) and X m,S b (t). Then the scheme makes these discontinuities evolve with the piece-wise constant velocities f S M and f S m . This is due to the fact that, as long as the discontinuities are separated by more than 3∆x from each other, the extrema of ϑ S can be identified by the scheme. This interpretation of the scheme extends some results of [START_REF] Lagoutiere | A non-dissipative entropic scheme for convex scalar equations via discontinuous cell reconstruction[END_REF] (for the advection case) to HJB equations. We will see in the next section that this exact computation of the averages of ϑ S is no more possible when two discontinuities lie in two successive cells, or in the same cell.

Case of piece-wise constant initial data

In this section we assume that there exists an increasing sequence of real values (y

i ) i=0,••• ,p+1 with y 0 = -∞, y p+1 = +∞, and (γ i ) i=0,••• ,p such that v 0 (x) =    i=0,...,p γ i 1 ]yi,yi+1[ (x) for x ∈ R\{y 1 , . . . , y p }, min(γ i-1 , γ i )
for x = y j and for i = 1, . . . , p.

With this definition, v 0 is a l.s.c. piece-wise constant function. We also assume that the mesh size ∆x satisfies:

∆x ≤ 1 3 min 1≤i≤p-1 (y i+1 -y i ). ( 24
)
We have derived in the previous section an error estimate when the discontinuities keep far enough from each other (more precisely, when they are separated by at least two entire cell intervals). In general, two discontinuities may become very close. Two critical cases may happen, see Figure 1.

In these cases, one time step of the UltraBee scheme given in algorithm 1 may not compute the average values exactly. In fact, it would do a false interpretation of the maximum value and of the discontinuity localization. The idea is to anticipate this critical situation. Hence when two discontinuities are too close, a truncation is done such that just one discontinuity remains in its right location (see Fig. 2). Here we modify the HJB-UltraBee scheme around maxima when one of the two critical cases of Fig. 1 Initialization: We compute the averages (V 0 j ) j∈Z by ( 12)

Loop: For n ≥ 0: A) Compute W := S U B (V n ) (HJB-UltraBee step). B) (Truncation step) For all indexes j such that    W j > max(W j-1 , W j+1 ), and W j = V n j or W j > W j-1 , W j+1 > W j+2 , and W j < V n j    and V n j -W j-2 < V n j -W j+2 , set V n+1 j-1 := W j-2 , V n+1 j := W j-2 ,
and

V n+1 j+1 := W j+2 + W j-2 -W j+2 V n j -W j+2 (W j+1 -W j+2 ),
For all indexes j such that

   W j > max(W j-1 , W j+1 ), and W j = V n j or W j-1 > W j-2 , W j > W j+1 , and W j < V n j    and V n j -W j-2 ≥ V n j -W j+2 , set V n+1 j+1 := W j+2 , V n+1 j := W j+2 ,
and

V n+1 j-1 := W j-2 + W j+2 -W j-2 V n j -W j-2 (W j-1 -W j-2 ).
Otherwise set V n+1 j := W j .

RR n 0123456789

x j x j x j+1
x j+1

(a) Initial data ϑ S (0, .) (b) Evolution by the scheme ϑ (t1, .), with averages V 1

Exact evolution at time t1, ϑ S (t1, .)

Exact evolution at time t1, ϑ S (t1, .) Hereafter the truncation step will be denoted by

V n+1 := T V n (W ).
Remark 3.1. The truncation step modifies values only near local strict maxima of (V n j ) j∈Z . The test

V n j -W j-2 < V n j -W j+2 (resp. V n j -W j-2 ≥ V n j -W j+2
) allows to check if the left jump is strictly smaller (resp. equal or greater) than the right jump near a local maxima, see Figure 2. In this case, the truncation corresponds to a recomputation of the average values such that the right (resp. left) discontinuity position is correctly coded. Hence the truncation allows to get rid of the left discontinuity and to keep the right one in its correct location. This truncation step aims to improve the treatment by the UltraBee scheme and to prevent the presence of two discontinuities in the same cell or in adjacent2 cells.

The main result of the section is the following. Theorem 3.1. Assume that (H1) -(H3) are satisfied. Let v 0 be a piece-wise constant function as in (23). We assume that the mesh size satisfies ( 13) and (24). Let ϑ be the viscosity solution of (4), and let V be defined by ( 16) and algorithm 2. We have

V (t n , .) -ϑ(t n , .) L 1 (R) ≤ (Lt n + 4)e Ltn T V (v 0 ) ∆x, ∀n ≥ 0.
Notice that the total variation of v 0 given by (23

) is T V (v 0 ) := i=1,...,p-1 |γ i+1 -γ i |.
Remark 3.2. We shall also see in the proof, for instance in the case of the eikonal equation, that ϑ S,n j = V n j as long as the discontinuities are far enough one from each other.

A first simple case when two fronts may meet

Let a, b be in R, with b ≥ a + 3∆x. Consider the following initial data:

v 0 (x) = 1 ]a,b[ (x), a.e. x ∈ R. ( 25
)
Remark 3.3. Thanks to [START_REF] Crandall | Two approximations of solutions of Hamilton Jacobi equations[END_REF], under assumption (H1), the unique l.s.c. viscosity solution of ( 4) is given by (for t ≥ 0, x ∈ R):

ϑ(t, x) := 1 ]X M a (t),X m b (t)[ (x), if X M a (t) < X m b (t), 0 otherwise. (26)
Also, by definition of ϑ S (see [START_REF] Falcone | Semi-lagrangian schemes for Hamilton-Jacobi equations, discrete representation formulae and godunov methods[END_REF]), for t ≥ 0 and x ∈ R we get

ϑ S (t, x) := 1 ]X M,S a (t),X m,S b (t)[ (x), if X M,S a (t) < X m,S b (t), 0 otherwise (27)
(the approximated characteristics X M,S a and X m,S b are defined as in [START_REF] Bokanowski | Anti-diffusive schemes for linear advection and application to Hamilton-Jacobi-Bellman equations[END_REF]).

As in (19) we denote by ϑ S,n the average cell values of ϑ S (t n , •).

Lemma 3.1. Assume that (H1) -(H3) are satisfied. Let v 0 be as in (25), and the mesh size satisfy [START_REF] Osher | High essentially nonoscillatory schemes for Hamilton-Jacobi equations[END_REF] and ∆x ≤ ba 3 . For every n ≥ 0, we have

V (t n , .) -ϑ S (t n , .) L 1 (R) ≤ 4∆x e Ltn . (28)
Proof. For n ∈ N, let j n and n be two integers such that X M,S a

(t n ) ∈]x jn-1 2 , x jn+ 1 2 ] and X m,S b (t n ) ∈]x n-1 2 , x n+ 1 2 ]
. Two cases may occur:

(i) n ≥ j n + 3 ∀n ≥ 0.
(ii) There exists a first index n ≥ 1 such that n < j n + 3. Assume (i). By the results of section 2.3 we know that the scheme computes the exact averages of ϑ S as long as the fronts are separated by at least two cells, that is, in the case for all k ≤ n, k ≥ j k + 3. In particular, no truncation step has occured in this case. We then have V n j = ϑ S,n j and can conclude as in (22) to

ϑ S (t n , .) -V (t n , .) L 1 (R) ≤ ∆x T V (ϑ S (t n , .)) = 2∆x = T V (v 0 ) ∆x. ( 29
)
Assume now (ii). For k < n, the estimate (29) holds (no truncation done yet). For k ≥ n, a truncation has occured at step n and thus V k = 0. For k ≥ n, we then have (using Lemma 2.1(ii))

||V (t k , .) -ϑ S (t k , .)|| L 1 = ||ϑ S (t k , .)|| L 1 = max 0, X m,S b (t k ) -X M,S a (t k ) ≤ e L(t k -tn) (X m,S b (t n ) -X M,S a (t n ) + ∆x) ≤ e Lt k 4∆x
. This gives the desired bound.

2

Proof of theorem 3.1 in the case v 0 is given by (25): It is now a simple consequence of (28) and of Proposition 2.1.

Proof of Theorem 3.1 in the general case

We notice that since v 0 is a step function, ϑ S (t, .) is also a step function. We need to define a truncation ϑ of ϑ S that will be connected to the scheme values.

For a given piece-wise constant l.s.c. function w (of the form ( 23)), we define the truncation function T runc(w) as follows. For x ∈ R, set

z x 1 := sup{z, z ≤ x, w(z) = w(x)} ∈ [-∞, ∞[, z x 2 := inf{z, z ≥ x, w(z) = w(x)} ∈ ] -∞, ∞]
(i.e. the closest left and right discontinuities of w to x). Let j 1 be such that z x 1 ∈ ]x j1- 1 2 , x j1 + 1 2 ] and j 2 be such that z x 2 ∈ [x j2-1 2 , x j2 + 1 2 [. Then set (see Fig. 2(b)):

T runc(w)(x) :=      max(w(z x 1 ), w(z x 2 )) if j 2 ∈ {j 1 + 1, j 1 + 2} and w(x) > max(w(z x 1 ), w(z x 2 )), w(x)
otherwise.

We now define the function ϑ by: ϑ (0, .) := v 0 , and ∀n ≥ 0, ϑ (t n+1 , .) = T runc(w n+1 ) where

w n+1 (x) := min y∈[X M,S x (-∆t),X m,S x (-∆t)] ϑ (t n , y). (30)
In the next result we derive an L 1 -error bound for ϑϑ S . We also prove that the cell averages of ϑ are exactly the values given by algorithm 2.

INRIA Lemma 3.2. Assume (H1)-(H3). (i) ∀n ≥ 0, ϑ S (t n , .) -ϑ (t n , .) L 1 (R) ≤ (4e Ltn -1)T V (v 0 ) ∆x. (ii) ∀j ∈ Z, ∀n ≥ 0, we have 1 ∆x Ij ϑ (t n , x) dx = V n j .
Proof. (i) First we notice that for t ≥ 0, ϑ (t, .) is a piece-wise constant l.s.c function (this can be proved, as for ϑ S , by using a recursion argument). At a given time t n , let (]α i , β i [) i=1,...,p be the local maxima intervals of ϑ S (t n , .

) (i.e. ϑ S (t n , x) ≡ const = µ i on ]α i , β i [ and µ i > max(ϑ S (t n , α i ), ϑ S (t n , β i ))).
Then we obtain (a) ϑ (t n , .) and ϑ S (t n , .) can only differ on the intervals

∪ i=1,...,p ]α i , β i [, (b) ∀i, if ϑ (t n , .) and ϑ S (t n , .) differ on ]α i , β i [, then ∀x ∈]α i , β i [, ϑ (t n , x) = max(ϑ S (t n , α i ), ϑ S (t n , β i )).
Indeed, by Lemma 2.1(iii), the length of the minima regions of ϑ S can only increase, so they will not deasappear and create new local extrema; Also by (H3) the fronts of an increasing region of ϑ S cannot get closer, as well as the fronts of a decreasing region of ϑ S . Now if ϑ S (t n , .) and ϑ (t n , .) differ on some interval ]α i , β i [, we have for x ∈]α i , β i [:

ϑ S (t n , .) -ϑ (t n , .) L 1 ([αi,βi]) = ϑ S (t n , x) -max(ϑ S (t n , α i ), ϑ S (t n , β i )) |β i -α i | ≤ T V (ϑ S (t n , .); ]α i , β i ]) |β i -α i |.
Also we know that a truncation has occured at some time t k < t n . At time t k , the discontinuity positions corresponding to α i and β i are located in α 0 i := X M,S αi (-(t nt k )) and β 0 i := X m,S βi (-(t nt k )) respectively. Since the truncation has occured, α 0 i and β 0 i are separated by less than two cell intervals, and |β 0 iα 0 i | ≤ 3∆x. By Lemma 2.1(ii), we thus have

|β i -α i | ≤ e L(tn-t k ) (|β 0 i -α 0 i | + ∆x) -∆x ≤ (4e Ltn -1)∆x.
Summing these bounds for all local maxima intervals [α i , β i ] we obtain ϑ S (t n , .)-ϑ (t n , .) L 1 (R) ≤ (4e Ltn -1)∆xT V (ϑ S (t n , .)). Then we conclude the proof of (i) using Proposition. 2.2.

(ii) Now, we prove recursively that for all n ≥ 0:

(P n ) V n j = 1 ∆x Ij ϑ (t n , x)dx, ∀j ∈ Z and (Q n )
Any two successive discontinuity positions in ϑ (t n , .) are separated by at least two cell intervals

((Q n ) amounts to have ϑ (t n , .) = i µ n i 1 ]yi,yi+1[ a.e. , with y i ∈]x j i 1 -1 2 , x j i 1 + 1 2 ], y i+1 ∈ [x j i 2 -1 2 , x j i 2 + 1 2 [ and j i 2 ≥ j i 1 + 3.
) For n = 0, ϑ (0, .) = v 0 = ϑ(0, .) and (P 0 ) follows, also (Q 0 ) is true by the definition of v 0 and of the mesh step ∆x. Now let us suppose (P n ) and (Q n ). Let W := S U B (V n ), and define w n+1 as in (30). Since V n codes the average values of ϑ (t n , .) where the discontinuity positions are separated by at least two cells, the Ultra-Bee scheme computes the correct averages for one time-step evolution, and we will have

W j = 1 ∆x Ij w n+1 (x)dx
(this uses the same arguments as in the proof of Lemma 2.3).

As long as the discontinuity positions in w n+1 are separated by at least two entire cells, ϑ (t n+1 , .) = T runc(w n+1 ) = w n+1 , and we have (Q n+1 ). Also V n+1 j values in step B) of algorithm 2 are unchanged. Hence V n+1 j = W j which proves (P n+1 ). Because of assumption (H3), the only case the discontinuity positions of w n+1 may be separated by less than two entire cells is around the local maxima. (Recall that by (H3), discontinuity positions in a monotonous part of ϑ (t n , .) can only get far from each other. This is also true for discontinuity positions around a local minimum, by Lemma 2.1(iii)). Now let us assume that ϑ (t n+1 , x) := T runc(w n+1 )(x) = w n+1 (x) for some x ∈ R. This means that x is surrounded by two discontinuities of w n+1 , denoted z x 1 and z x 2 , which are separated by one cell (critical case 1), or which lie in two successive cells (critical case 2), see Fig. 1. Let us consider for instance that we have a critical case 2 (critical case 1 being similar). We may also assume that V n j -W j-2 < V n j -W j+2 as illustrated in Fig. 2. In this case we see that the average values in cells I j-1 and I j can be set to W j-2 (hence the redefinition V n+1 j-1 = V n+1 j := W j-2 in algorithm 2). Then the remaining discontinuity position x ∈ I j+1 can be computed by two different ways: first, by

x -x j+ 1 2 ∆x = W j+1 -W j+2 V n j -W j+2
, and second, if V n+1 j+1 codes the correct average value on I j+1 after truncation,

x -x j+ 1 2 ∆x = V n+1 j+1 -W j+2 W j-2 -W j+2
(recall that the scheme values should code the average of an exact piece-wise function). Thus we obtain the desired definition of V n+1 j in terms of the (W k ) as in algorithm 2 B), which proves (P n+1 ).

On the other hand, after the truncation step, there are no more critical cases in ϑ (t n+1 , .) and thus we have (Q n+1 ).

2

INRIA

Proof of theorem 3.1 in the general piece-wise constant case: Combining Proposition 2.1 and Lemma 3.2(i) we obtain

ϑ(t n , .) -ϑ (t n , .) L 1 (R) ≤ ϑ(t n , .) -ϑ S (t n , .) L 1 (R) + ϑ S (t n , .) -ϑ (t n , .) L 1 (R) ≤ (Lt n + 4)e Ltn -1)T V (v 0 ) ∆x. (31)
Then, using Lemma 3.2(ii), we obtain

ϑ (t n , .) -V (t n , .) L 1 (R) ≤ T V (ϑ (t n , .))∆x. ( 32
)
By construction of ϑ (and using Lemma B.3), we also have T V (ϑ (t, .)) ≤ T V (ϑ S (t, .)) ≤ T V (v 0 ). Together with (31), (32) we obtain the desired bound of Theorem 3.1. 2

Case of a general discontinuous initial data

In this section we generalize Theorem 3.1 (where we supposed that v 0 was a piece-wise constant function) to more general discontinuous initial data v 0 . We assume that v 0 : R → R is a l.s.c. function, with T V (v 0 ) < ∞, and that v 0 has a finite number of extrema. More precisely we consider the following assumption :

(H4)       
There exist A 1 , . . . , A q+1 and B 1 , . . . , B q real numbers with

A 1 = -∞ ≤ B 1 < A 2 < • • • < B q ≤ A q+1 = +∞, (with possibly B 1 = -∞ or B q = +∞), such that v 0 on each [A i , B i [, v 0 on each ]B i , A i+1 ], and v 0 (B i ) = min(v 0 (B - i ), v 0 (B + i )).
In particular A i are local minima of v 0 , and B i are local maxima of v 0 .

We also consider ∆x small enough such that the minima and maxima of v 0 are separated at least by 3∆x:

∆x < 1 3 min i=1,...,q min (B i -A i , A i+1 -B i ) . ( 33
)
Let a regular grid with mesh size ∆x, and let ∆t > 0.

We denote by v P 0 the l.s.c. function associated to v 0 as follows. We set U j :=]x 3j-1 2 , x 3j+ 5 2 [, for all j ∈ Z,

• If U j ∩ {(A k ) k=2,...,q , (B k ) k=1,...,q } = ∅, set v P 0 (x) := 1 3∆x Uj v 0 (y)dy, ∀x ∈ U j . (34a) • otherwise if A k ∈ U j (resp. B k ∈ U j ) set v P 0 (x) := v 0 (A k )(resp. v 0 (B k )) ∀x ∈ U j . (34b)
• Extend v P 0 by lower semi-continuity :

v P 0 (x 3j-1 2 ) = min v P 0 (x + 3j-1 2 ), v P 0 (x - 3j-1 2 ) . ( 34c
)
RR n 0123456789

We have

v(t, .) -u(t, .) L 1 (R) ≤ e Lt v 0 -u 0 L 1 (R) ∀t ≥ 0. ( 37
)
Proof of Theorem 4.1. By construction of v P 0 , and under assumption (H4), the function v P 0 is increasing on intervals where v 0 is increasing, and decreasing on intervals where v 0 is decreasing, and the local minima of v P 0 are the same as the ones of v 0 . Hence we can apply Proposition 4.1 to compare ϑ and ϑ P and obtain together with Lemma 4.1:

ϑ(t, •) -ϑ P (t, •) L 1 (R) ≤ e Lt (3∆xT V (v 0 )), ∀t ≥ 0. ( 38
)
Now by Theorem 3.1 we also have

V (t n , .) -ϑ P (t n , .) L 1 (R) ≤ (Lt n + 4)e Ltn T V (v P 0 )∆x, ∀n ≥ 0.
Furthermore, it is easy to see that T V (v P 0 ) ≤ T V (v 0 ). Together with (38) this concludes the proof of Theorem 4.1.

2

We now conclude the section with the proof of Proposition 4.1.

Proof of Proposition 4.1:

Step 1. We first study the case when u 0 is a monotonous increasing function. In this case v 0 is also increasing. u(t, x) = u 0 (X M x (-t)) and v(t, x) = v 0 (X M x (-t)). Hence, using the change of variable y = X M x (t), we get

u(t, .) -v(t, .) L 1 (R) = R |u(t, y) -v(t, y)|dy = R |u(t, X M x (t)) -v(t, X M x (t))|| dy dx (t)|dx.
Here, as f M is Lipschitz then, by the Rademacher theorem, it is almost everywhere differentiable and we get: dy dx (t) = exp t 0 f M (X M x (s))ds . In particular, | dy dx (t)| ≤ e Lt for all t ≥ 0, and we obtain the bound

u(t, .) -v(t, .) L 1 (R) ≤ e Lt u 0 -v 0 L 1 (R) .
The proof is similar when u 0 is a decreasing function.

Step 2. Now we study the case when u 0 has essentially only one local maximum located in B 1 . More precisely, we suppose that u 0 on (-∞, B 1 ) and u 0 on (B 1 , ∞). The representation Lemma C.2 allows to write u 0 as:

u 0 = min(u 01 , u 02 ), with u 01
and u 02

where u 01 and u 02 are defined as in Lemma C.2. Then the viscosity solution is given by:

u(t, x) = min u 01 (X M x (-t)), u 02 (X m x (-t)) , t ≥ 0, x ∈ R.
By assumption (ii), v 0 also satisfies v 0 on (-∞, B 1 ) and v 0 on (B 1 , ∞). We can also write v 0 = min(v 01 , v 02 ) where v 01 and v 02 are also defined as in Lemma C.2, and we have

v(t, x) = min v 01 (X M x (-t)), v 02 (X m x (-t)) t ≥ 0, x ∈ R. (39)
Next, we define b as a meeting point for the following two curves at a given time t:

x → v 01 (X M x (-t)) and x → v 02 (X m x (-t)). Then

u(t, .) -v(t, .) L 1 (R) = b -∞ |u(t, x) -v(t, x)|dx + +∞ b |u(t, x) -v(t, x)|dx. We notice that for x ≤ b, u(t, x) = u 01 (X M x (-t)) and v(t, x) = v 01 (X M x (-t)). We thus get b -∞ |u(t, x) -v(t, x)| dx = b -∞ |u 01 (X M x (-t)) -v 01 (X M x (-t))| dx = X M b (-t) -∞ |u 01 (x) -v 01 (x)| exp t 0 f M (X M x (s))ds dx ≤ e LT u 01 -v 01 L 1 (-∞,X M b (-t)) , (40)
In the same way:

(b,+∞) |u(t, x) -v(t, x)| dx ≤ e LT ||u 02 -v 02 || L 1 (X m b (-t),+∞) (41)
Since

f M ≥ f m , then X M b (-t) ≤ X m b (-t).
Hence combining ( 40) and ( 41) we obtain (37). Notice that for Step 1 and Step 2 there is no need of assumption (iii).

Step 3. We turn now to the proof in the general case (u 0 as in (H4)). Using assumptions (23)-( 24) we can decompose u 0 into monotonous parts: there exist an integer q ≥ 1 and real numbers A 1 , . . . , A q+1 , B 1 , . . . , B q as in (H4) (with possibly B 1 = -∞ or B q = +∞), and such that u 0 on each [A i , B i [ and on each ]B i , A i+1 ]. We first consider the time interval [0, τ 1 [ such that the number of local maxima q of u keeps constant. 3 We note that around a local minima A i , the solutions u and v will stay constant in the following sense: if we set

I t i := [X m Ai (t), X M Ai (t)] for t ∈ [0, τ 1 ], we have u(t, x) = u 0 (A i ) and v(t, x) = u 0 (A i ), ∀x ∈ I t i .
Hence, in order to bound ||u(t, .)v(t, .)|| L 1 (R) , we have to estimate the difference on the remaining intervals

J t i := [X M Ai (t), X m Ai+1 (t)]: u(t, .) -v(t, .) L 1 (R) = q i=1 u(t, .) -v(t, .) L 1 (J t i ) , (ν) . Set V n+1,1 := min V n+1 (ν m ), V n+1 (ν M ) . B) Truncation: Set V n+1,2 := T V n (V n+1,1
) as in algorithm 2.

C) Prediction:

Set W := V n+1,2 . (decreasing critical cases) Let J -:=    j ∈ Z, W j-1 > W j > W j+1 > W j+2 and V n j < W j or W j-2 > W j-1 > W j > W j+1 > W j+2 and V n j = W j   
and J -, * := J -\ {j ∈ J -, s.t. j + 2 ∈ J -}.

For j ∈ J -, * , set

V n+1 j-1 := W j-2 , V n+1 j := W j-2
, and

V n+1 j+1 := W j+2 + W j+1 -W j+2 V n j -W j+2 (W j-2 -W j+2 ). ( 44
)
(increasing critical cases)

Let J + :=    j ∈ Z, W j+1 > W j > W j-1 > W j-2 and V n j < W j or W j+2 > W j+1 > W j > W j-1 > W j-2 and V n j = W j    and J +, * := J + \{j ∈ J + , s.t. j -2 ∈ J + }.
For j ∈ J +, * , set

V n+1 j+1 := W j+2 , V n+1 j := W j+2 ,
and

V n+1 j-1 := W j-2 + W j-1 -W j-2 V n j -W j-2 (W j+2 -W j-2 ). ( 45
)
INRIA otherwise set V n+1 j = W j (i.e. for j such that {j -1, j, j + 1} ∩ (J -, * ∪ J +, * ) = ∅).

Then we have the following general error estimate:

Theorem 5.1. We suppose (H1). Let v 0 be an l.s.c. function satisfying (H4) and such that T V (v 0 ) < ∞ (in particular v 0 has a finite number of extrema).

Let ∆x > 0 and ∆t > 0 satisfy the CFL condition ( 13) and (33). Let V n j be defined by algorithm 3, V as in ( 16), and ϑ be the viscosity solution of ( 4). (i) If v 0 is piece-wise constant as in (23), with p discontinuities, and if

(H5a) ∃ε > 0, ∀x ∈ R, f m (x) + ε ≤ f M (x) and ∆x < ε 2L , or (H5b) ∀x ∈ R, f m (x) ≤ 0, f M (x) ≥ 0, then V (t n , •) -ϑ(t n , •) L 1 (R) ≤ (Lt n + 4p)e Ltn T V (v 0 )∆x, ∀n ≥ 0. ( 46
) (ii) If (H5c) f m = f M and is an increasing function, then V (t n , •) -ϑ(t n , •) L 1 (R) ≤ (1 + Lt n e Ltn )T V (v 0 )∆x, ∀n ≥ 0. ( 47
)
Remark 5.1. Assumption (H5b) is satisfied by the eikonal equation ϑ t +c(x)|ϑ x | = 0, where c is a L-lipschitz positive function.

Remark 5.2. As in [START_REF] Bokanowski | Anti-diffusive schemes for linear advection and application to Hamilton-Jacobi-Bellman equations[END_REF], when f M (resp. f m ) changes sign, it is important to use two fluxes

V n,L j+ 1 2 and V n,R j+ 1 2
, which may be different on the cell's interface containig the zero of f M (resp.

f m ). The choice made for these fluxes insure the stability, consistency and TVD 4 properties, see [7, Remark 2.1].

Remark 5.3. When assumptions (H1) -(H3) hold, the discontinuities around a minimum could only get far from each other. However, if we assume only (H1), the discontinuities may become closer. A truncation in this feature would produce an error which is not always controlled by the mesh size ∆x. Hence we assume one of the (H5) assumptions in order to avoid this truncation. Indeed, with (H5) two discontinuities around a local minimum cannot become closer than 2∆x (see Lemma 5.3).

Remark 5.4. When removing assumption (H3), two successive discontinuities in a monotone zone of v 0 can become very close. This motivates the prediction step: if the discontinuities are too close, we keep only one of them as shown in Figure 3. The algorithm then codes correctly the exact localization of the remaining discontinuity. This prediction step is handled only in the two critical cases explicited in figure 4, i.e. when the discontinuities are separated by less than two entire cells.

, Evolution of fronts ϑ S (t n+1 , .)

ϑ S (t n+1 , .)

Initial front positions

Prediction ϑ (t n+1 , .)

Preliminaries

We first prove in the following Lemma that the scheme computes the exact average values of ϑ S in some elementary cases, where truncation and prediction steps are not used.

Lemma 5.1. We assume (H1) and ( 13). Let a, b, α, β be real numbers, with β ≥ 0.

Let v 0 (x) := α + β1 ]a,+∞[ (x) (resp. v 0 (x) := α + β1 ]-∞,b[ (x)). (i) We have ϑ S (t, x) := α + β1 ]X M,S a (t),+∞[ (x) (resp. ϑ S (t, x) := α + β1 ]-∞,X m,S b (t)[ (x)), INRIA case 1 case 2 Figure 4: Critical cases of prediction (ii) ∀n ≥ 0, ∀j ∈ Z : V n j = 1 ∆x Ij ϑ S (t n , x)dx (48)
Proof. Part (i) is obtained by direct verifications using [START_REF] Falcone | Semi-lagrangian schemes for Hamilton-Jacobi equations, discrete representation formulae and godunov methods[END_REF]. For (ii), we shall treat the case of v 0 (x) = 1 ]a,+∞[ (x) (the other cases beeing similar). We proceed as in Lemma 2.3. We prove the statement by recursion. Let us denote by x n := X M,S (t n ) the discontinuity position at time t n . Note that it suffices to prove that

V n+1 j (ν M ) = 1 ∆x Ij 1 ]X M,S xn (∆t),+∞[ (x)dx ∀j ∈ Z. (49)
Indeed we have in the same way:

V n+1 j (ν m ) = 1 ∆x Ij 1 ]X m,S xn (∆t),+∞[ (x)dx ∀j ∈ Z.
And this will prove that V n+1 j = V n+1 j (ν M ) as desired. In the case when for all j ∈ Z, ν M j ≥ 0, (or if for all j ∈ Z, ν M j ≤ 0), the result comes from Lemma 2.3. It remains to treat the case when (ν M j ) changes signs. We denote ν := ν M for simplicity. Assume that x n ∈]x j-1 2 , x j+ 1 2 ] (i.e., V n k = 0 for k < j, V n j ∈ [0, 1[, and V n k = 1 for k > j). We furthermore assume that x n = x j+ 1 2 (the case of x n = x j+ 1 2 can be treated in a similar way). In particular we have V n j-1 = V n j-2 and V j+1 = V j+2 . Let us show that the values (V n+1 k (ν)) k=j-1,j,j+1 are correctly computed by the modified UltraBee scheme. We first state the following Lemma:

Lemma 5.2. (i) V n,L/R j+ 1 2 ∈ [min(V n j , V n j+1 ), max(V n j , V n j+1 )] (Consistency). (ii) (Stability) V n j = V n j-1 and ν j ≥ 0 ⇒ V n+1 j = V n j . (iii) (Stability) V n j = V n j+1 and ν j ≤ 0 ⇒ V n+1 j = V n j .
Proof of Lemma 5.2 Assertion (i) can be obtained as in [START_REF] Bokanowski | Anti-diffusive schemes for linear advection and application to Hamilton-Jacobi-Bellman equations[END_REF].

(ii) If ν j = 0, is immediate. If ν j > 0, we notice that V n,L j+ 1 2 = V n j because b + j = B + j = V n j . On the other hand, if ν j-1 > 0, then V n,R j+ 1 2 = V n,L j-1 2 = V n j (using V n j-1 = V n j and the consistency property). If otherwise ν j-1 ≤ 0, then V n,R j+ 1 2 ∈ {V n j , V n j-1 (see definition), hence V n,R j+ 1 2 = V n j .
(iii) the proof of this assertion is similar to (ii).

2 We come back to the proof of Lemma 5.1. In the case ν j = 0, we have V n+1 j (ν) = V n j , which is the correct value (the characteristics does not evolve in I j ). If ν j+1 > 0, we already know from Section 2 that V n+1 j+1 (ν) is correctly computed (we are in a subcase of ν j ≥ 0, ν j+1 ≥ 0). The case when ν j+1 < 0 is similar. We can use the same arguments to see that V n+1 j-1 (ν) is also correctly computed. Now we assume that ν j > 0 (the case when ν j < 0 can be treated in a similar way), and study the different remaining cases.

1) Case ν j-1 > 0. We can also suppose that ν j+1 ≤ 0 (otherwise, (ν k ) k=j-1,j,j+1 ≥ 0 and this has already been treated).

We first have V n+1 j-1 = V n j-1 (using Lemma 5.2(i)), the correct expected value.

Also V n+1 j = V n j -ν j (V n,L j+ 1 2 -V n,R j-1 2
), where V n,L j+ 1 2 is computed as in Algorithm 1 (Section 2) for positive velocities, and where

V n,R j-1 2 = V n,L j-1 2 = V n j-1 .
Hence the computation of V n+1 j is as in the case of positive velocities, and gives the correct expected value. Finaly,

V n+1 j+1 = V n j+1 using Lemma (iii). 2) Case ν j-1 < 0. First, V n+1 j-1 = V n j-1 -ν j-1 (V n,L j-1 2 -V n,R j- 3 2
), where

V n,L j-1 2 = V n j-1 (by definition in Algorithm 3), V n,R j-3 2 ∈ [V n j-1 ; V n j-2 ] = {V n j-1 } (by consistency), hence V n+1 j-1 = V n j-1 . Then, V n+1 j = V n j -ν j (V n,L j+ 1 2 -V n,R j-1 2
) where V n,L j+ 1 2 has the flux definition with ν j > 0, and V n,R j-1 2 takes the value V n j-1 (since V n j = V n j+1 using the fact that x n = x j-1 2 ). Hence in the interval I j , the estimate of the fluxes are the same as in the case of positive velocities, and are thus correct (exact evolution of the average values locating the discontinuity position in I j or I j+1 . Finaly, we have only to check the value of V n+1 j+1 in the case ν j+1 < 0. In this case, V n,R j+ 1 2 = V n j+1 (by Lemma 5.2(ii)), and V n,L j+ 3 2 = V n j+1 (by Lemma 5.2(i)), hence V n+1 j+1 = V n j+1 . 3) Case ν j-1 = 0. We first obtain V n+1 j-1 = V n j-1 . Then V n+1 j and V n+1 j+1 are computed as in the case ν j-1 < 0 (proof is left to the reader). This concludes the proof of Lemma 5.1 2 Remark 5.5. Indeed we have proved a more precise result: if at some time t n we have that ϑ S (t n , .) is a step-wise constant fonction with all successive discontinuities separated by at least two entire intervals, and if (48) holds for j ∈ Z, then also we have

V n+1 j = 1 ∆x Ij ϑ S (t n+1 , x)dx ∀j ∈ Z.

INRIA

Remark 5.6. Several estimates of Section 2 can be extended here. In particuar, under assumption (H1) only, the estimates of Lemma 2.1(i),(ii) and (v) also hold (in particular for changing sign velocities). Proof is left to the reader.

Lemma 5.3. We assume (H1) and one of the (H5) assumptions. Let a, b ∈ R be such that ba ≥ 2∆x. Then for all t ≥ 0, X M,S b (t) -X m,S a (t) ≥ 2∆x.

Proof. If we assume (H5b) or (H5c) it is easy to see that d dt (X M,S b (t) -X m,S a (t)) ≥ 0, for a.e. t ≥ 0, hence the result. Now assume (H5a). Suppose there exists θ ≥ 0 such that X M,S b (θ)-X m,S a (θ) < 2∆x. By continuity there exists τ ≥ 0 such that X M,S b (τ )-X m,S a (τ ) = 2∆x and

X M,S b (t) -X m,S a (t) < 2∆x, for t in a neighborhood V(τ + ) of τ + .
Case 1. We first suppose that X m,S a (τ ) ∈ I j-1 for some j ∈ Z (i.e., X m,S a (τ ) belongs to the interior of a mesh interval) and thus also X M,S b (τ ) ∈ I j+1 . In particular δ : t → X M,S b (t) -X m,S a (t) is differentiable at t = τ and necessarily we have δ(τ ) ≤ 0. Hence f m (x j-1 ) ≥ f M (x j+1 ). Then

f M (x j-1 ) -2L∆x ≤ f M (x j+1 ) ≤ f m (x j-1 ) ≤ f M (x j-1 ) -ε,
and we get 2L∆x ≥ ε which contradicts (H5a). Thus this case cannot occur.

Case 2. Now we suppose that X m,S a (τ ) = x j-1 2 for some j ∈ Z (and thus X (θ) ∈ I j+1 for θ ∈ V(τ + ), then using (H5a) we get

f M (x j+1 ) ≤ f m (x j ) ≤ f M (x j ) -ε.
Since we also have f M (x j+1 ) ≥ f M (x j ) -L∆x, we obtain

f M (x j ) -L∆x ≤ f M (x j ) -ε ≤ f M (x j ) -2L∆x
which leads to 2L ≤ L, a contradiction. Otherwise, if the two characteristics move in the same direction, we obtain a contradiction in the same way as in Case 1. 2

Proof of Theorem 5.1

We first define a prediction operator as follows. Let w be a real piece-wise constant and l.s.c. function. For x ∈ R, set

z x 1 := sup{z, z ≤ x, w(z) = w(x)} ∈ [-∞, ∞[, z x 2 := inf{z, z ≥ x, w(z) = w(x)} ∈ ] -∞, ∞]
i.e. the closest left and right discontinuities of w to a given x. Let j and k be such that

z x 1 ∈]x j-1 2 , x j+ 1 2 ] and z x 2 ∈ [x k-1 2 , x k+ 1 2 [.
Now to prove (ii), notice that under assumption (H5c), equation (4a) is reduced to an advection equation. In particular, as f M is increasing then the discontinuities never meet: we do not need any truncation or prediction step in the scheme. The proof of Theorem 5.1(ii) is similar to the proof of Theorem 2.1.

2 In order to prove Lemma 5.4, we first establish the following.

Lemma 5.5. Assume that v 0 satisfies assumption (H4) (with (A i ) i=2,...,q local minima). (i) for all interval I ⊂ R,

ϑ S on I ⇒ ϑ on I, ϑ S on I ⇒ ϑ on I, (ii) If X M,S Ai (t n ) is a local minima of ϑ S (t n , .
) (i = 2, . . . , q), then it is also a local minima of ϑ (t n , .), and we have ϑ (t n , y) = ϑ S (t n , y) (= ϑ S (t n , X M,S Ai (t n ))) for all y ∈ [X m,S Ai (t n ), X M,S Ai (t n )]. Proof. By Lemma 5.3, two discontinuities positions a i and b i limiting a given minimum A i in v 0 , initially separated by at least 3∆x, stay at more than 3∆x in ϑ S (t n , .) and thus stay separated at least by two cell intervals. In particular they cannot meet with our assumption.

Also since the operators P red and T runc do not modify the monotonicity and keep the minima values, we obtain that ϑ (t n , .) will keep the monotonicity regions of ϑ S (t n , .) (as well as the minima regions of ϑ S (t n , .)). This proves both (i) and (ii).

2

Remark 5.8. Note that a minima zone of ϑ S (t n , .) can disappear. This happens only in the case the neighboring left or right maxima zones disappear. By the previous Lemma ϑ (t n , .) will have a similar property.

Proof of Lemma 5.4(i). Let J i := [X M,S Ai (t n ), X m,S Ai+1 (t n )]. To show (52), by using Lemma 5.5(ii), it is sufficient to obtain the following bound

ϑ S (t n , .) -ϑ (t n , .) L 1 (Ji) ≤ p(4e Ltn -1)T V (v 0 , [A i , A i+1 ]) ∆x (54)
(the result will then follow by summation on i). It means that we need to show (52) in the particular case when v 0 on [A 1 , B 1 ] and v 0 on [B 1 , A 2 ]. We can assume A 1 = -∞ and A 2 = ∞ to simplify.

Let ϑ ,0 (t n , .) := ϑ S (t n , .). We define recursively the function ϑ ,k for k ≥ 0 as follows. Let t n k be the first time where a prediction should be performed in the function ϑ ,k-1 (t n k , .) (i.e., two successive discontinuities in a decreasing or in an increasing region of ϑ ,k-1 (t n k , .) are separated by less than two entire cell intervals). Then set

ϑ ,k (t, .) := ϑ ,k-1 (t, .) for t < t n k , ϑ ,k (t n k , .) := P red(ϑ ,k-1 (t - n k , .)), ϑ ,k (t, x) := min y∈[X M,S x (t-tn k ),X m,S x (t-tn k )] ϑ ,k (t n k , y) for t ≥ t n k and x ∈ R.
for x ∈ (-2, 2) and with periodic boundary conditions. Notice that we can take f M = 1 and f m = -1. The CFL condition is ∆t ∆x ≤ 1 (here we have choosen the CFL number to be ∆t ∆x = 0.9). The initial condition is defined as follows:

ϑ(0, x) =                2 if x ∈] -1.6, -1[, 1.7 if x ∈ [-1, 0.1[, 0.2 if x ∈ [0.1, 0.6], 1.2 if x ∈]0.6, 1.2[, 0.7 if x ∈ [1.2, 1.6[, 0
otherwise.

In Figure 5, we show the exact solution (black line) and the numerical values of algorithm 2 (cross) at different times.

We follow the evolution of two local maxima until they disappear, in particular in the last two time steps: just before they disappear (c) and then just after (d). Notice that the scheme computes exactly the mean value of the solution far from critical situations. In fact the dynamics f m and f M are constant here, and the approximated characteristics X M,S x and X m,S x coincide with X M

x and X m x respectively. This leads to an exact computation of the average values of ϑ ≡ ϑ S by the scheme (except when discontinuities are too close)

Example 2: piece-wise continuous initial data. The initial condition is given by

ϑ(0, x) = -x 2 + 1.5 if x ∈ [-1, 1], 0 otherwise.
The results are shown in Figure 6.

Example 3: two local maxima.

Here we consider a piece-wise continuous initial data with two local maxima :

ϑ(0, x) = x 2 + 0.7 if x ∈ [-1, 1], 0 otherwise.
The results are shown in Figure 7.

Remark 6.1. In pratice, numerical tests show that when the initialization of the algorithm is done with a projection with mesh size ∆x (instead of 3∆x), the error gets smaller (up to 10 times smaller).

Example 4: We consider the eikonal equation ( 56) on (-1, 1) but now with an initial condition composed of two discontinuities, as follows: We see in Table 1 that the error is bounded by 2∆x.

ϑ(0, x) = 1 if x ∈] -0.7, 0.9[, 0 otherwise.

Example 5: Eikonal equation with varying velocity

In this example we deal with algorithm 3 in order to illustrate the prediction step. We consider the following Eikonal equation:

B TV bounds

Lemma B.1. Let v 0 be an l.s.c. function such that T V (v 0 ) < ∞. For j = 1, 2, let x → a j x and x → b j x be non-decreasing, one-to-one functions from R onto R. We assume that (i) x → a j

x and x → b j x are non-decreasing, one-to-one functions from R onto R (for j = 1, 2). (ii) a j

x ≤ b j x for j = 1, 2 and x ∈ R. (iii) there exists δ ≥ 0, such that,

∀x ∈ R, max(|(a 2 ) -1 (x) -(a 1 ) -1 (x)|, |(b 2 ) -1 (x) -(b 1 ) -1 (x)|) ≤ δ.
(where (a j ) -1 and (b j ) -1 denotes the reciprocical functions of a j and b j resp.). Let also

v j (x) := min y∈[a j x ,b j x ]
v 0 (y).

Then

||v 1 -v 2 || L 1 (R) ≤ 2δ T V (v 0 ). ( 58
)
Proof. We first assume that a 2 x = a 1 x , ∀x. Then we notice that: Proof. Let ṽ0 be defined by ṽ0 (x) := lim y→x,y<x v 0 (y) for every x ∈ R (i.e, ṽ0 (x) = v 0 (x -). Then ṽ0 is left-continuous, and there exists a positive measure μ such that T V (ṽ 0 , ]-∞, x[) = μ(] -∞, x[) for every x ∈ R. (This can be deduced for instance from [START_REF] Rudin | Real and complex analysis[END_REF]). We have also μ({x}) = |v 0 (x -)v 0 (x + )|, for every x ∈ R. Also, since T V (v 0 ) < ∞, v 0 admits at most a countable set of discontinuity points denoted (a n ) n≥0 . Let

|v 2 (x) -v 1 (x)| ≤ T V (v 0 ; [b 1 x ; b 2 x ]) (59)
q n := |v 0 (a - n ) -v 0 (a n )| + |v 0 (a n ) -v 0 (a + n )| -|v 0 (a - n ) -v 0 (a + n )|
(q n ≥ 0) and

µ := μ + n∈N q n δ x=an
where δ x=an is the dirac measure centered in a n . Then for x / ∈ {a n , n ∈ N}, we have µ(] -∞, x[) = μ(] -∞, x[) + an<x q n = T V (v 0 , ] -∞, x[). Passing to the limit x → ∞ we obtain µ(R) = T V (v 0 ).

2 We know come back to the proof of Lemma B.1 In particular we obtain from (59)

|v 2 (x) -v 1 (x)| ≤ µ([b 1
x ; b 2 x [), a.e. x ∈ R.

Then we have, using the Fubini Theorem : v 0 (y).

We have T V (w) ≤ T V (v 0 ).

INRIA

  t→0 + y→x ϑ(t, y) = v 0 (x), ∀x ∈ R. If we set for all x ∈ R f m (x) := min α∈A f (x, α) and f M (x) := max α∈A f (x, α),

  j+1 )w(y j )|; k ∈ N * , and (y j ) 1≤j≤k+1 increasing sequence 9

Figure 1 :

 1 Figure 1: Critical cases of truncation

Figure 2 :

 2 Figure 2: Truncation step for critical case 2

Figure 3 :

 3 Figure 3: Prediction step

  If the two characteristics X m,S a (θ) and X M,S b (θ) move such that X m,S a (θ) ∈ I j and X M,S b

3 Figure 5 :- 2 Figure 6 :

 3526 Figure 5: (Example 1) Piece-wise constant function, #cells=70.

ϑ

  t (t, x) + |x| • |ϑ x (t, x)| = 0, x ∈ (-1, 1), with periodic boundary conditions. Here we take f M (x) = |x| and f m (x) = -|x|. The initial condition is given byϑ(0, x) = x ∈] -0.8, -0.5], 1 if x ∈ [-0.5, 0.6], 0.7 if x ∈ [0.6, 0.7[, 0.2 if x ∈ [0.7, 0.8[, 0 otherwise.Since f m and f M are not constant, ϑ and ϑ S will differ. Results are shown in Figure8. In Fig.8(a), two critical cases of prediction appear simultaneously in the decreasing zone.The algorithm handles only a prediction for the right discontinuity (Fig.8(b)). In Fig.8(c), a prediction step is again needed, and so on.

Figure 8 :

 8 Figure 8: (Example 5) Prediction steps in Algorithm 3, # cells=40

  where [α; β] denotes the interval [min(α, β), max(α, β)]. (To prove (59), assume for instance the case b1 x ≤ b 2 x . Consider z 1 ∈ [a 1 x , b 1 x ] such that v 1 (x) = v 0 (z 1 ) and z 2 ∈ [a 1 x , b 2 x ] such that v 2 (x) = v 0 (z 2 ). If the minimum for v 2 can be reached in [a 1 x , b 1 x ] then v 1 (x) = v 2 (x). Otherwise we have z 2 ∈ [b 1 x , b 2 x ] and v 2 (x) = v 0 (z 2 ) < v 0 (z 1 ) = v 1 (x). Hence |v 2 (x)v 1 (x)| = v 0 (z 1 )v 0 (z 2 ) = v 0 (z 1 )v 0 (b 1 x ) + v 0 (b 1 x )v 0 (z 2 ) ≤ v 0 (b 1 x )v 0 (z 2 ) ≤ T V (v 0 ; [b 1 x , b 2 x ]).The case when b 2 x ≤ b 1 x is similar.) Now we establish the following.Lemma B.2.There exists a positive real measure µ such that µ(R) = T V (v 0 ) and T V (v 0 ; ]-∞, β[) = y∈]-∞,β[ dµ(y), for a.e β ∈ R.

R |v 2 1 x ;b 2 xy∈R x∈R 1 y∈[b 1 x ;b 2 x 2 Lemma B. 3 .

 21211223 (x)v 1 (x)|dx ≤ x∈R y∈R 1 y∈[b [ dµ(y) dx = [ dx) dµ(y) = y∈R |(b 2 ) -1 (y) -(b 1 ) -1 (y)|dµ(y) ≤ y∈R δ dµ(y) ≤ δ T V (v 0 ).Now in the general case when a 2 x = a 1 x , we have|v 2 (x)v 1 (x)| ≤ T V (v 0 ; [a 1 x ; a 2 x ]) + T V (v 0 ; [b 1 x ; b 2 x ])(60)(the proof is analogous to (59)). Then both parts of the R.H.S. of (60) can be handled as before and we deduce (58). Let v 0 be an l.s.c. function with T V (v 0 ) < ∞. We assume that for all x ∈ R, a x ≤ b x , and x → a x , x → b x are non-decreasing functions, and consider w(x) := min y∈[ax,bx]

Table 1 :

 1 (Example 4) Evolution of the error with the mesh size ∆x, CF L = 0.9

	12, t = 0.25	(c) error=0.09, t = 0.45

RR n 0123456789

We mean by adjacent here the neighboring cells from the left and from the right INRIA

For instance we consider τ 1 > 0 to be the first time such that min i=1,...,q X m a i+1 (t) -X M b i (t) vanishes, with a i := inf{x, u 0 (y) = u 0 (A i ) ∀x ≤ y ≤ A i } and b i := sup{x, u 0 (y) = u 0 (A i ) ∀A i ≤ y ≤ x}.INRIA

Then the scheme values are initialized as usual but starting from v P 0 , i.e.

This initialization ensures that the initial step function v P 0 will satisfy (23)-( 24), and that the coded discontinuities are separated by at least 3∆x. The aim of step (34) is also to keep the correct (local) extremal value of v 0 . This is motivated by the fact that the exact minima and maxima values should propagate. It allows to obtain better long-time approximations.

The general convergence result is the following.

Theorem 4.1. We assume (H1)-(H3), and consider a l.s.c. function v 0 satisfying (H4), and such and T V (v 0 ) < ∞. We also assume that mesh steps ∆x and ∆t satisfy the CFL condition ( 13) and (33). Let ϑ be the unique viscosity solution of (4a)-(4b). We consider (V 0 j ) defined by ( 34)-( 35) and (V n ) n≥1 given by algorithm 2. Let V be defined by ( 16). Then V (t n , .)ϑ(t n , .) L 1 (R) ≤ (Lt n + 7)e Ltn T V (v 0 ) ∆x, ∀n ≥ 0.

Remark 4.1. We can treat a discontinuous initial data of the form v 0 := 1 R\{0} . In this case we have

. We shall need preliminary estimates Lemma 4.1. We have

Proof. The result is immediate by the definition of v P 0 . 2

Now let ϑ P be the l.s.c. viscosity solution of (4a) with initial data v P 0 , i.e., ϑ P (0, x) := v P 0 (x), ∀x ∈ R.

The following estimate is essential in the analysis (the proof is postponed to the end of the section). Proposition 4.1. We assume (H1). Let u 0 and v 0 be two l.s.c. functions, such that v 0u 0 ∈ L 1 (R). We suppose furthermore that (i) u 0 satisfies assumption (H4) (with (A i ) i=2,...,q local minima); (ii) for all interval I ⊂ R,

Let u and v be defined by

u 0 (y), and v(t, x) := min

v 0 (y).

INRIA

(the J t i are disjoint as long as t < τ 1 ). Notice that ϑ(t, .) and ϑ P (t, .) admit only one maximum on J t i . Then as in Step 2 we can show that:

) . Summing the previous bounds we obtain for t ∈ [0, τ 1 ]:

Now we consider the case when the number of maxima q may lower, and proceed recursively on q. We obtain on a time interval [τ 1 , τ 2 [, where the number of maxima is constant and equal to q -1, the similar bound:

Then with (42) we obtain for all t ≤ τ 2 the desired bound, and so on. This concludes the proof of Proposition 4.1.

2

Case of changing sign velocities

We explain in this section how to get a general error estimate using mainly assumption (H1). Instead of assumptions (H2) and (H3) we shall use less restrictive assumptions that will be detailled in Theorem 5.1 below. Let v 0 : R → R be a l.s.c. function such that T V (v 0 ) < ∞.

We consider a regular grid (x j ) as in Section 2, and define f S M and f S m as in Section 2.1. The following algorithm introduces two modifications to algorithm 2: left and right fluxes (denoted by V n,L and V n,R ), for computing the UltraBee estimates, and a prediction step. We will explain later on the relevance of these modifications.

Algorithm 3

Initialization: We compute the initial averages (V 0 j ) as in (34)-(35). Loop: For n ≥ 0, we compute V n+1 from V n in three steps:

A) Evolution by a modified HJB-UltraBee scheme:

(where b + j , b - j , B + j and B - j are defined by ( 14)-( 15)). If ν j ≥ 0 and

Let us denote w(x -) := lim y→x, y<x w(y) and w(x + ) := lim y→x, y>x w(y). Then set

otherwise.

(

Remark 5.7. The above definition means that we set P red(w)(x) = w((z x 1 ) -) in the case x belongs to a decreasing zone of w (for instance), surrounded by two discontinuities of w that are separated at most by one cell, but also such that the next right discontinuity z z x 2 2 is at least separated by two cells from the right discontinuity z x 2 (see Fig. 3). Then we define ϑ (t n , .) for all n ≥ 0 by : ϑ (0, .) := v P 0 , ∀n ≥ 0, ϑ (t n+1 , .) = P red(T runc(w n+1 )) where w n+1 is as in (30).

We also define ϑ S as in [START_REF] Falcone | Semi-lagrangian schemes for Hamilton-Jacobi equations, discrete representation formulae and godunov methods[END_REF] but starting from v P 0 , i.e.:

Now, we focus on the proof of Theorem 5.1 (i) (in particular we have v P 0 ≡ v 0 here). We follow the proofs of Theorem 3.1 and 4.1. For a given piece-wise constant initial data v 0 (with discontinuities separated by at least 3∆x), it remains to prove that the following still holds -in a similar way as in Lemma 3.2.

Lemma 5.4. Under the assumptions of Theorem 5.1(i), we have (i)

Proof of Theorem 5.1. The proof of (i) follows by using (52) and previous estimates :

INRIA

This means that ϑ ,1 (t n , .) is the function where only the first occuring prediction in ϑ ,0 = ϑ S is taken into account, ϑ ,2 (t n , .) is the function where only the first prediction in ϑ ,1 is taken into account, etc. We obtain for k = 1, . . . , p,

)|| L 1 = 0, and if t n ≥ t n k , we obtain the bound (55) by using similar arguments as in the proof of Lemma 3.2(i). Also we note that ϑ ,p (t n , .) ≡ ϑ (t n , .), because there are at most p prediction steps that can be done in ϑ (t n , .). Summing these bounds for k = 1, . . . , p and by a triangular inequality this proves (54).

2

Proof of Lemma 5.4(ii). The proof is obtained by a recursion argument on n ≥ 0. Lemma 5.1 shows that an isolated discontinuity of ϑ S (t n , .), as long as it keeps separated from other discontinuity positions by at least two cell intervals, has its evolution correctly coded by algorithm 3 for one time step. Also Lemma 5.3 implies that two discontinuities positions a i and b i limiting a given minimum A i in v 0 (and evolving as X m,S ai (t) and X M,S bi (t)) stay at more than 3∆x, and thus are separated at least by two cell intervals. Hence the problem of having discontinuity positions in ϑ S no more separated by two cell intervals can only come from maxima regions or monotonous regions of ϑ S .

Then as in Lemma 3.2(ii) we can show that the cell averages of T runc(w n+1 ) are well coded by the scheme values V n+1,2 j after Step A) and Step B). Finally it remains to prove that the prediction step C) corresponds to the application of prediction operator P red on the function T runc(w n+1 ). The proof is very similar to the proof of Lemma 3.2(ii) for the truncation step (i.e. a discontinuity position vanishes and the remaining discontinuity leads to a recomputation of average values). 2

Numerical tests

In this section, we apply algorithm 2 and 3 to some examples. These tests show the numerical relevance of the method especially for the truncation step. The L 1 -error is computed by the formula:

error

where (V n j ) are the numerical values and ϑ is the exact viscosity solution (4). Example 1: piece-wise constant initial data. We consider the following Eikonal equation:

INRIA

A Definition of the approximated characteristics

We prove existence and uniqueness of the absolutely continuous solution X M,S a (t) of the differential equation:

We define recursively the caracteristic as follows. Assume that a ∈]x j0 -1 2 , x j0+ 1 2 ] for some index j 0 . We consider the case f M (x j0 ) ≥ 0 (the case f M (x j0 ) < 0 beeing similar). We define τ 0 := 0,

and for k ≥ 1,

, if f M (x j0 +k ) > 0 (i.e., ∆x fM (x j 0 +k ) is the time needed for a caracteristic to cross the interval I j0+k ). Otherwise, if there exists a first index k * such that f M (x j0 +k * ) ≤ 0, then we define τ k * +1 := +∞ and stop the iterations. Note that since f M is Lipschitz, we have either lim k→∞ τ k = +∞ (in this case set k * = +∞), or there exists

(where χ(τ 0 ) = a and χ(τ k ) = x j0 +k-1 2 for k ≥ 1), and if t ≥ τ k * , we set

Then χ(t) is a solution of (57).

In order to show the unicity of the solution of (57), we first notice that the first time t * when two solutions may differ must be such that χ(t * ) be on an interface: ∃j ∈ Z, χ(t * ) = x j+ 1 2 . In the case f M (x j )f M (x j+1 ) ≤ 0, by definition we have χ(t) = x j+ 1 2 for all t ≥ t * , and unicity. Otherwise, in the case f M (x j )f M (x j+1 ) > 0, we have necessarily f M (x j ) > 0 (we assume here that f M (x j0 ) > 0). Then the only solution for t > t * in a neighborhood of t * , is given by

This shows unicity.

INRIA

Proof. Let x 0 < x 1 , • • • < x p be real numbers. We want to estimate δ := j=1,...,p |w(x j )w(x j-1 )| For all j, we define y j as the smallest real number of [a xj , b xj ] such that w(x j ) := min [ax j ,bx j ] v 0 (y) = v 0 (y j ). Let us prove that (y j ) is a non-decreasing sequence. It suffices to check that x 0 ≤ x 1 ⇒ y 0 ≤ y 1 . a) In the case b x0 ≤ a x1 , we obtain y 0 ≤ y 1 trivially. b) Otherwise, if min [ax 0 ,bx 0 ] v 0 = min [ax 0 ,ax 1 ] v 0 , then y 0 ∈ [a x0 , a x1 ] and thus y 0 ≤ y 1 . c) Otherwise, we have min

Hence we have proved that y 0 ≤ y 1 in all cases.

Then, by definition of T V (v 0 ),

Taking the supremum over all non-decreasing sequences (x j ), we obtain the desired result. 2

Lemma B.4. Let v 0 be a real valued function such that T V (v 0 ) < ∞, then

Proof. : The number of discontinuity points of v 0 is of zero measure as

Then we can write

(we recall that x j = j∆x here). To invert the sum and the integral, we have used that a.e x ∈ R, v 0 is continuous at the points (x + x j ) j∈Z . 2

C Representation Lemma

In this section we denote by ϑ * the upper semi continuous (u.s.c.) envelope of a real valued function ϑ. We also denote ϑ(B -) := lim We start with an elementary result related to the minimum of two viscosity solutions.

Lemma C.1. Let v 0 , v 01 and v 02 : R → R be l.s.c. functions. Let ϑ, ϑ 1 and ϑ 2 be the l.s.c solutions of (4a) with initial data v 0 , v 01 and v 02 respectively. If v 0 = min(v 01 , v 02 ) then for all t ≥ 0, x ∈ R, ϑ(t, x) = min(ϑ 1 (t, x), ϑ 2 (t, x)).

Proof. Let w = min(ϑ 1 , ϑ 2 ). It is easy to check that the function w is l.s.c, and satisfies the initial condition w(0, x) = v 0 (x) in the sense of Definition 2.1 ii). Let φ be C 1 -regular and (t, x) ∈ R + × R a minimum of wφ with w(t, x) = ϑ 1 (t, x) (the case w(t, x) = ϑ 2 (t, x) being similar). Then ϑ 1φ has also a minimum at (t, x). Since ϑ 1 is a viscosity solution, we obtain that φ satisfies (4a). Hence w is a l.s.c. viscosity solution of (4a). By uniqueness of ϑ, we obtain w = ϑ. 2

Notice that the same arguments would not work for the maximum of two viscosity solutions instead of the minimum.

We now give a representation formula for a viscosity solution in a particular case.

Lemma C.2. Let v 0 : R → R be a l.s.c function. We assume that there exists B 1 such that v 0 for x < B 1 , and v 0 for x > B 1 , and v 0 (B 1 ) = min(v 0 (B - 1 ), v 0 (B + 1 )). We define the functions: Let ϑ 1 (respectively ϑ 2 ) be the l.s.c. viscosity solution of (4a) with initial condition v 01 (respectively v 02 ). Then v 0 = min(v 01 , v 02 ) and ϑ(t, x) := min(ϑ 1 (t, x), ϑ 2 (t, x)), t ≥ 0, x ∈ R is the l.s.c. viscosity solution of (4a)-(4b). In particular, we have ϑ(t, x) = min v 01 (X M

x (-t)), v 02 (X m x (-t)) .

Proof. : It is easy to check that v 0 = min(v 01 , v 02 ). Then we apply Lemma C.1 to obtain ϑ = min(ϑ 1 , ϑ 2 ). Let I t x := [X M x (-t), X m x (-t)]. We also have ϑ 1 (t, x) = inf y∈I t x v 01 (y) = v 01 (X M

x (-t)) as v 01 is an increasing function, and similarily ϑ 2 (t, x) = v 02 (X m x (-t)) as v 02 is decreasing.