On a moving grid numerical scheme for Hamilton-Jacobi equations

ON A MOVING GRID NUMERICAL SCHEME FOR HAMILTON-JACOBI EQUATIONS

BUM It ^HONG

1. Introduction

Analysis by the method of characteristics shows that if I and Uo are smooth and Uo has compact support, then the Hamilton-Jacobi equation

(H-J)

+ ^I(u x ) = 0, x E lR, t > 0, u(x,O) = uo(x), x E lR,

has a unique Cl solution u on some maximal time interval 0 :5 t < T for which limt...

u( x, t) exists uniformly; but this limiting function is not continuously differentiable. Thus u x becomes discontinuous at t = ^T. Crandall and Lions [2] showed both existence and uniqueness of the generalized solutions that satisfy so called "viscosity" condition.

They also showed that viscosity solutions of (H-J) are stable in Loo with respect to perturbation in the initial data, and consequently that the space of Lipschitz continuous functions forms a regularity space for (H-J). In one space dimension, Hong [3] has recently shown that if I is approximated in LOO(lR) to order (2 ⁿ )-3 by a Cl piecewise quadratic function In and if Uo is approximated in LOO by a continuous, piecewise quadratic polynomial Wo with 2

free knots, then the solution w(·, t) of

wt+ln(w x ) =0, xER, t>O, w(x,O) = wo(x), x E lR,

Received October 14, 1994.

1991 AMS Subject Classification: 70H20, 65M60.

Key words: Hamilton-Jacobi equations, Finite elements.

Supported by NON DIRECTED RESEARCH FUND, Korea Research Founda-

tion,1993.

is again continuous, piecewise quadratic for all time and has no more than C2

pieces for some C. As a result, u(·, t) can be approximated with an error not exceeding the error of approximation of Uo plus O((2

)-3).

In this paper, we construct a moving grid numerical scheme using the method of the characteristics that the continuous, piecewise quadratic solution w( x, t) of Hamilton-Jacobi equations in one space dimension may be approximated in LOO(JR.) to within O(N-

by a continuous, piecewise quadratic polynomial wo(x) with D(N) meshpoints.

To show this, we use the simple relationship between the equations of (H-J) and hyperbolic single conservation laws. This relationsh.1p is very simple: if ^w is the viscosity solution of (H-J), then v =

x is the entropy solution of scalar conservation laws

Vt

+ f( v)x = 0, x E JR., t > 0, v(x,O) = ^vo(x) = w~(x), x E lR.

Therefore, if one calculates shocks of single conservation laws accord- ing to the Rankine-Hugoniot jump condition and the entropy condi- tion, then one can calculate the viscosity solution w(x, t) by integrating v(x, t) with property that w( x, t) is continuous.

2. Stability of (H-J)

THEOREM 2.1. Suppose that f and 9 are Lipscmtz continuous and f(O) = ^g(O) = ^{0. If Uo and Wo are} bounded and Lipschitz continuous, and u and w are the viscosity solutions of

Ut

+ f( u x ) = 0, x E JR., t > 0, u(x,O}=uo(x), xEJR.,

and

Wt

+ g( ^w x ) = 0, x E JR., t > 0, . w(x,O) = wo(x), x E JR.,

then for any t > 0,

(H) lIu(·, t) - w(·, t)IILOO(ll) ::; lIuo - woIlLOO(ll) + tllf - gIlLOO(ll).

Proof See Hong [4].

3. A Construction of a Perturbed Equation

Suppose that f E W 3,OO(R.) is strictly convex and f(O) = 0. Then there is a Cl piecewise, quadratic approximation fN to f with knots at the point j fN for j = 0, 1, ... , N, that is defined by fN(j fN) =

f'(jfN), fN(O) = 0; fN is strictly convex. Moreover IIf - fNII Loo (lIi) ::;

Cllf(3)IILoo(lIi)N-

where C = (9 + ;)j"fel)3; ^{see [1] and [7].}

We suppose that a Lipschitz continuous function Uo having the sup- port in [0, 1] has no polynomial piece of degree ::; 1 and that the range of Uo is in [0,1]. We also assume that ua

^{is in BV(R.) for i = 0, 1 and}

that u~ is also in BV(R.) outside a finite set of points {diH=l where

u~ is discontinuous.

Now construct a continuous, piecewise quadratic approximation Wo to uo.

(1) choose Ti = ⁱ Jv for i = 0,1, ... ,N as initial meshpoints.

(2) If _u~(x) is discontinuous at di, then choose di- 2Jv3 ^and di + 2Jv3'

and add these two points to the set of initial meshpoints.

(3) Insert least number of meshpoints in the interval where u~( x) is smooth so that

(4) Construct a continuous, piecewise quadratic function woex) as follows. Let I i = [Ti, Ti+l]' Set woe ^Ti) = ^{uo( Ti)} and woe ^{Ti+I) =}

uo( Ti+l). Now we need one more information to determine an unknown coefficient for wo(x). Let Mi = ^sUPI; uHx) and mi = infI; u~(x). Then choose any number for w~ satisfying mi ::; minI; _W~( x) ::; maxI; _W~( x) ::; M

(5) Insert new meshpoints Ti satisfying w~( Ti) = -k ^{for all j} =

O, ... ,N.

From these two approximations fN and Wo, we have the following properties.

LEMMA 3.1. Iw~(x)IBV(lIi)::;3Iu~(x)IBV(lIi)'

Proof· Consider one interval Ii = h, Ti+l]' Let _~i = ^{IIil, Mi =}

sup I; u~, and mi = infI; u~' Let Si be the slope of _w~ on h, ^Ti+l].

Then since Iw&IBV(I.) = ISil~i ::; Mi - mi ::; lu&IBV(I.),

L Iw~IBV(I;) ^::; L lu~IBV(I;)

::; lu~(x)IBV(J!l.).

We now measure the jump Iw&(rt) - w&(ri-)I. Since

Iw&(rt) - w~(ri-)I ::; (Mi - mi) + (Mi+l - miH) ::; lu~IBV(I;) + lu~IBv(I.+d'

~i Iw&(rt)-w&(ri-)I ::; ~i(lu&IBV(I;)+lu&IBV(I.+d) ::; 2Iu&(x)IBV(J!l.).

Hence Iw&(x)IBV(J!l.) ::; 3Iu&(x)IBV(ll).

LEMMA 3.2. Suppose that s is a piecewise linear interpolation to I

at 0 = ^to < t 1 < ... < ^tN-l < ^tN = ^{1, and the ti's are chosen so that}

rt;+l 1

(ti+l - ti) It; 1f"ldx ::; N2

f'IBV([O,1j) for all i,

then III - slloo ::; 41-21f'IBV([O,1j).

Proof. See [3].

LEMMA 3.3. H u&(x) has k number of discontinuities, then there are at most (6Iu&IBV(J!l.) + ^6)N + ^6k -1 meshpoints.

Proof. Step (1) and step (2) give at most 2k+N +1 meshpoints. By de Boor [1], step (3) gives at most N new meshpoints. We now count the number of meshpoints ri inserted by step (5). If call it "pi and order them, then each interval ['lj1i, 'lj1i+l] mayor may not contain previously inserted meshpoints: If ['lj1i, 'lj1i+l] does not contain any old meshpoint generated by (1), (2) and (3), then "pi and 'lj1iH are two adjacient points constructed by (5). Therefore Iw&('lj1i) - w&( 'lj1i+l)1 = it

-k

or -k _I;/ ⁼ 1- for some j. So the total number of meshpoints in this case is no more than 2Iw&IBV(J!l.)N ::; 6Iu&IBV(J!l.)N. If ['lj1i, "piH] does contain any old meshpoint, then, since the number of old meshpoints is 2k + 2N + 1, at most (2k + 2N -1) number of the interval ["pi, _~iH]

may contain old meshpoints. So the total number of meshpoints of

this kind is no more than 2(2k + ^{2N -1) = 4k} + ^{4N -} 2. Therefore

step (5) adds no more than (6Iu&IBV(m) + ^4)N + ^{4k -} 2 number of new

meshpoints. So we complete the proof.

THEOREM 3.4.

Proof. Let B be the union of I i ⁼ h, Ti+l] containing a point at which u~ is discontinuous. Let A = [0,1] - B. Then

lI u o - woIlLOO(li) _~ sup luo - wol + sup luo - wol

B A

= maxsup IUO(Ti) - WO(Ti) + r: (u~(s) ^- w~(s» ^dsl

B I. lr.

+ mIX s~p ^luo( Td - Wo( Ti) + f.

(u~( ^{s) -} w~( ^{s» dsl}

~ ^{maxsup {} lu~(s) ^- w~(s)l ^ds

B

11.

+ m;xs~p ITHl - Tilllu~(s) - w~(s )11

^(1;)

I

~ m;xs~p ~3 \u~IBv(1.)

+ ~ lIu~ ^- w~IILoo(A)

1 I

I 1 ( 1 1""1 )

~ ^N3 Uo BV(li) + ^{N 4N2} Uo - Wo BV(lPl-{d;})

= ~3 (Iu~IBV(lPl) ⁺ ~lu~IBV(li-{d.}».

Here the first part-of the third inequality is because the area of the set of points that are greater than u~ but less than w~ plus those points that are less than u~ but greater than w~ is obviously less than or equal to ITi+l - Til = _~ times lu~IBv(I.) because w~ is in between sUPI, u~ and infI. u~, and the second part of the fourth inequality is valid because of (3) in the construction of wo(x).

4. A Moving Grid Numerical Scheme for Perturbed Equa-

tion

(3)

Let vo(x) = wti(x). Then vo(x) is discontinuous piecewise linear having support in [0,1].

By the method of characteristics, we calculate the solution of the perturbed single conservation laws

Vt + ^fN(V)x = 0, x ER, t > 0, v(x,O)=vo(x), xER.

Lax: [6] showed the general theory of hyperbolic conservation laws. IT v is continuous on h(t), Ti+l(t)), then v is linear on [Ti(t), Ti+l(t)] since fN is quadratic. So it is enough to find the nodal values using the Rankine-Hugoniot jump condition and the entropy condition. That is to determine the evolution of shocks. Let vHt) = limx...Ti(t)- vex, t) and v~(t) = limx... ^Ti(t)+ vex, t). Since fN is strictly convex and

is continuous, the following two inequalities (the entrdpy condition) . trivially hold. Let v(x,t) be discontinuous at Ti(t). Then

(1) fN(V;~t)) ^- f~(v~(t)) > fN(TJ) - f~(v~(t)) ^{for TJ E} [v~(t), ^v;(t)]

v:Ct)-v~(t) - TJ-v~(t)

if _v~(t) > v~(t), or

(2) fN(V;~t)) ^- f~(v~(i)) > fN(TJ) - f!,!(v;(t)) for TJ E [v;(t),v~(t)]

vj(t) - v~(t) - TJ - vi(t)

if vHt) < v~(t). Therefore no meshpoints are generated during the evolution of v because f

is strictly convex and

is continuous. The meshpoint moves along the characterics and the solution v is constant along the trajectory Ti = Ti(t) which propagates with speed, due to Rankine-Hugoniot jump condition,

dTi {f1v(V;(t)), if vt(t) = v~(t),

dt = fN(V{(t»-fN(V;(t» if vi(t)

vi(t)

.

, I -;-

So if v is continuous on [Ti(t) , Ti+l(t)], ¥f is constant and dv£;t) dvi (t)

~ =0 because (4)

dvj(t) {O, ^{if vt(t) = v~(t),}

~- = vt(t)-v;-l(t) (fN(Vt (t))-f~(v~(t)) _ i' ^{(vi(t))) otherwise,}

Ti(t)-Ti_l(t)

N I '

(6) and (5) .

dv~(t) {O, ^{if vHt) =} v~(t),

---a:;:- = V:+l(t)-V~(t) (/

' (vi(t)) _ fN(vt(t»-f-:v(v~(t))) otherwise.

T;+l(t)-r;(t) N

(4) d (5) di tl fr dV(T;(t),t) _ av(r;(t),t) + av(r;(t),t) dr;(t)

an are rec y om dt - at ar;(t) dt'

To determine where the shocks occur, we solve the above equations between shock interaction times. Therefore it is equivalent to find the trajectory of meshpoint Ti. We use the fact that the conservation of mass holds near the discontinuity to find the shock trajectory as follows. Let, to the right of the shock, (respectively, to the left of the shock) f'N(v) = arv 2 + 2brv + er and let v have the initial slope Sr' Ulv( v) = a,v

+ ^{2b ,v} + ^Cl and let v have the initial slope S,.) Suppose that Ti is the initial shock point.

We use the fact that mass is conserved near the discontinuity to find the shock trajectory. Let the triangle ABC having the vertices A(x, t), B(XI,O) and C(X r, 0), where Xl < Ti < Xr. Let the characteristic line from B to A (recpectively, from C to A) be

X = Xl + tllv(VI(XI)) where VI = b

+ b

x,

(x = Xr + tf'N(vr(x r)) where VI ⁼ b ₂₀ + b

X respectively.) where VI and

are polynomial pieces to the left and right hand sides of Ti respectively.

Suppose that the shock curve joining the point (Ti' 0) and A(x, t) is inside the triangle ABC, then V must solve the equation weakly on the triangle ABC;

(7)

0= [ [Vt + fN(V)x] dxdt

JllABC

=t( - flv(VI(XI)) + flv'( VI(XI))VI(XI))

+ tU'N(vr(x r)) - 1'N'(vr(xr))vr(xr)) _ [T; vI(x)dx _ rr ^vr(x)dx.

JXI Jr;

The second equality simplly follows if one uses the divergence theorem.

One can plug in the formulas for flv, I'N, Xl, Xr, VI and vr. Then one can

get rid of

and

from the system (6) and (7) through a process called

"elimination". We just use built-in eliminate commands in Macsyma or Maple. Finally

and t satisfy the following polynomial equation.

° ^{=(2blla12t +} 1)(2b2la22t + 1)

(2bub2la22tx2 - 2bllb21a12tx2 - b21 x 2 + bll x 2 - 4allbllb2la22t2x + 4a21bllb2la12t2x + 4blOb2la22tx - 4b20blla12tx + 2a2lb21tx - 2allblltx - 2b2o x + 2blO x

+ 8a20bub21 a12a22t3 - 8al0 b

b2la12a22t3 + 2a~1 b

b2l a22t3 - 2a~1 bllb2la12t3 - 4b~ob2la12a22t2 + 4b~oblla12a22t2 - 4blOallb2la22t2 + 4a2ob2la22t2 - alOb21a22t2

+ 4b20a2lblla12t2 + 4a2oblla12t2 - 4aIQblla12t2 - a~l b21t 2

+ a~lbllt2 + 2b~oa22t - 2b~Oa12t + ^2b2oa21t

- 2blOallt + 1a2ot - 2alOt).

Let the last factor be P(x, t) = 0. Then P has total degree three, and quadratic in x. So we can write

where Pi(t) has the degree i in t, and x(t) can be calculated by the quadratic formula. The behavior is rather complicated. Newton claimed to classify all cubic curves, and he drew many useful diagrams.

This is contained in hiscolIected mathematical works published by Cambridge UDiversity Press.. To find which branch. we go on, we. sta,rt with the fact that we normalized the shock curve to begin at the point (0,0), so that tells you the sign of the discriminant. We also need to know which branch (plus or minus) to choose. However it is sufficient to see which branch goes through (0,0) again according to Newton's mathematical works.

Once all Ti(t) have been found, we compute the viscosity solution w(x,t) of

(P) Wt + fN( w z ) = 0, x E lR, t > 0,

w(x,O) = wo(x), xE lR,

as follows; We know that w(x, t) and vex, t) have the same compact support; see [5]. Totheleftsideof'To(t), w(x,t) = Obecausev(x,t) = ^0.

Because w(x, t) = _J~(t) v(s, t) ds and w(x, t) is continuous at all 'Ti(t), the constant of each quadratic piece of w(x, t) can obtained successively from 'To (t).

THEOREM 4.1. Let f E Wa,OO(R) be strictly convex. Let a Lipscb.itz continuous function Uo have the support in [0,1] having the range in [0,1]. Suppose that u~i) is in BV(R) for i = ^{0,1 with} u~ ^E BV(R) outside a :finite set of points {dil~=l where u~ is discontinuous. As- sume that u(x,t) is the viscosity solution of (H-J). lithe approximate solution w( x, t) of (P) obtained by above numerical scheme, then

lIu(" t) - w(·, t)1I Loo (li) ~ ~a [lu~IBV(li) ⁺ ~lu~IBV(li-{d;})

+ Ctllf(a)IIL~(lII)]

where C = ^{(9 +} _~)fi(!Da.

Proof. It directly follows from Theorem 2.1, Lemma 3.3 and Theo- rem 3.4.

This shows that this scheme achieves O(N-a) approximation w be- cause Wo has O(N) meshpoints.

ACKNOWLEDGEMENT. The author would like to thank the refree for his/her excellent comments and suggestions.

References

1. C. de Boor, Good approximation by splines with variable knots, Spline Func- tions and Approximation Theory, edited by A. Meir and A. Sharma, ISNM, Birkhauser-Verlag, Basel, 21 (1973), 57-72.

2. M. G. Crandall and P. L. Lions, Viscosity solutions of Hamilton-Jacobi equa- tions, Tran. Amer. Math. Soc., 277 (1989), 1-42.

3. B. I. Hong, On regularity and approximation for Hamilton-Jacobi equations, J.

Korean Math. Soc., 30 (1993), 93-104.

4. B. I. Hong, Regularity for Hamilton-Jacobi equations via approximation, Bull.

Austral Math. Soc. 51 (1995), 195-213.

5. S. N. KruZkhov, First order quasilinear equations with several indepedent vari- ables, Math. USSR Sbornik, 10 (1970), 217-243.

6. P. D. Lax, Hyperbolic Systems of Conservation Laws and Mathematical Theory of Shock Waves, Regional Conference Series in Applied Mathematics, Philadel- phia, 1973.

7. Yu. N. Subbotin and N. 1. Chernykh, Order of the best spline approximationof some classes of functions, Matem. Zametki, 23 (1970), 31-42.

Department of Mathematics

Kyung Hee University, Yongin

Kyunggi 449-701, Korea