This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
{x) < v(x) in a TL-neighborhood O of x0 and p(x,Dcp)<9 0. By (16), A is also a neighborhood of JB£,„(xn,0) = {x £ fi : ) < 6 < 1 $(x) € 2(x) for any x G O and therefore a contradiction. Q R + is a continuous mapping we will say that Wi, W2,... W^ are the wells of ip if it holds that 0 \\v\\j 0 for x £ fl. Let us consider the one-step discretization of (4): (xo,to) < 1- We have to show that the following inequality l( 0 0 -2nae 0, - > 0 ', 0 assertion (8) follows from (21) by taking the limits for a < /? | 0. This concludes the proof of Lemma (4.1). • Remark 4.1 A subsolution can be constructed in a similar way, namely ,d(x,t) w ... p) - ee A 0 0 in the domain of interest, but this is of use in several practical applications including seismology Sy or computations of lenses. Therefore, the eikonal equation rewrites: dXl 0 ; (ii) / 3 2 > 0. 0 and all u £ U. Note that this assumption can be relaxed by imposing a suitable boundary condition on the inflowing part of fi, see 6 , Section 1. Furthermore, our setup is easily extended to min-max problems. A standard dynamic programming argument (see e.g. l) shows that for each T > 0 and each t £ [0,T — r] the solution v is uniquely determined by
xeO,
in viscosity sense for some 9 < 1. Then there exists ip £ W 1 '°°(fi) such that tp(x0) = v(x0), ip{x) < v(x) with a strict inequality out of BL(x0,0) and p(x,Dip) <9'
xeO,
in viscosity sense for some 9' < 1. The previous lemma says that any test function can be perturbed in such a way to be a strict subtangent out of the set of points having 0 L-distance from the point xo where we test the equation (in the standard theory of viscosity solution this is simply achieved by adding |x — xo| 2 to the test function). Proposition 3.1 Assume (14) and let vn : fi —• E be a locally uniformly bounded sequence of singular supersolutions of (12). Then v(x) = liminf, vn(x) := inf{liminf vn(xn) n—»+oo
: xn ->• x}.
n
is a singular supersolution of (3). Proof. Assumption (14) implies that 9nr{x) < r„(x)
for any x e H,
9nPn(x,P) < p(x,p)
for any (x,p) e 0. x RN.
^ '
and consequently 9nL(x,y) < Ln(x, y) for any x,y £ H. (16) Assume by contradiction that v is not a singular supersolution, therefore there is a function
xeO
in viscosity sense, for some 9 < 1. In light of Lemma 3.1, we assume that there is T£ -neighborhood A of x 0 such that (v - (p){x) > (v - 4>)(x0) p(x, D(p) < 9
for any x £ A \
BL(xo,0),
for any x € A
in viscosity sense, for some 9 £ (0,1). Therefore there exists a sequence x„ of minimizers of vn —
53
Ln(xn, x) = 0} for n sufficiently large and so, for such n,
:= sup{\.imsupHn(xn,pn)
n—y+oo
: (x„,p„) -> (x,p)}
n
(17) for any (x,p) 6 ft x RN. Coupling conditions (14) and (17) we obtain stability of singular solutions as we will see in some specific examples in the next section. 4
Approximation of the value function
This section is devoted to the study of two types of approximation of equation (3), vanishing viscosity and discretization. In general, a direct approximation of equation (3), for example obtained by discretization or vanishing viscosity, does not work since the approximating equations do not satisfy condition (14). Therefore as a preliminary step we regularize equation (3) obtaining a new problem with an empty singular set. Then we devise an approximation of the regular problem. We will show that if the two approximation steps, regularization and either discretization or vanishing viscosity, are related in an appropriate way, we get convergence to the singular solution of the limit problem. We start by introducing a regularization of equation (3). For e > 0, we consider the equation sup{-6(x, a)Du(x) - fe(x,a)}
= 0,
i£(l
(18)
where fs(x,a) = max{/(x,a),e}. Since fe(x,a) > e > 0, equation (18) coupled with the Dirichlet boundary condition (4) admits a unique viscosity solution vs. This solution is given by the value function of the control problem with dynamics (1) and cost functional
Mx,q) = f Jo
fMt),q(t))dt + g(Z(T)).
54
Proposition 4.1 Let vE be the sequence of viscosity solutions of (18)-(4)Then lim vAx) = v(x) uniformly in Q., where v is the singular solution of (3)-(4). Proof. Set Zs{x) = {p G RN : He{x,p) < 0}, where Hs(x,p) = sup {-b(x,a)p-
f£{x,a)}
.
(19)
Then Z(x) C Ze(x) for any x e Cl and, from Proposition 3.1, v(x) lim inf,v s (x) is a singular supersolution of (3).
=
Since also condition (17) is satisfied we have that v(x) = lim sup* ve(x) is e->-0
a viscosity subsolution of (3). Since (see Theorem 6.2 in 6 ) it is easy to see that v(x) < g(x) < u(x) for x € dtt, Theorem 3.1 imphes that v(x) < v,(x) in ft. On the other side, by definition, v(x) > v_(x) in 11 and therefore v(x) = v{x) = v(x) (20) where v is the singular solution of (3)-(4). To conclude, observe that equality (20) implies the uniform convergence of ve to v (see 1 , 3 ) . D Now we describe a semidiscrete approximation scheme for equation (18). Following 2 , this scheme is obtained by discretization of the control problem associated with equation (18). For simplicity we assume that fi is convex. ^From now on, e > 0 is fixed. Let h > 0 be sufficiently small and consider a discrete time control problem with dynamics f z„+i = xn + hb(xn, an) \ xQ = x £
n € N fi,
. . '
l
where qh — {an}n& € A^ and A% is the space of sequences in qh C A for which v(x,qh) := inf{n € N : xn $ Cl} is finite. Define a discrete cost functional on the trajectories of (21) by
n=0
(we assume the convention that X]n=o previous discrete time control problem
=
0). Then the value function of the
vhe(x) = inf Jhe(x,qh).
(22)
55
is a solution of ' vht{x) = m{aSA{vhe(x
+ hb(x,a)) + hf€(x,a)}
x 6 ft vo
N
vhe(x)=g(x)
xe&"\n.
(23)
It is rather standard to show that the value function Vht is the unique bounded solution of (23). Moreover there exists a constant C independent of h and e such that
lh«l|oo
(24)
Let uif be a modulus of continuity for f(x, a) in ft. Theorem 4.1 Let v^t be a sequence of solutions of (23) and assume that h = h(e) is such that
?M->0
ase^0+.
(25)
Then v(x) — lim VhAx) e—1-0
uniformly in ft where v is the singular solution of (3)-(4). Proof. We will only prove that v_(x) = lim inf, u/,e (x) is a singular supersolution e—>0
of (3). It is more or less standard (see for example 2 , 4 ) to show that v(x) = lim sup* Vh£(x) is a subsolution. Hence applying an argument similar to that of Proposition 4.1 we conclude the proof. Assume by contradiction that there exists <j> 6 Wrl,°°(ft) such that such that (j>(xo) = n(xo), (x) < v.{x) in a TI-neighborhood O of x0 for which p(x,D4>)<e
x£0
(26)
in the viscosity sense. Observe first (see 6 ) that (26) is equivalent to p(x,p)<9<\
xeO, p<Ed
(27)
where d<j>{x) is the Clarke generalized gradient of <j> at x (see 8 ) . By Lemma 3.1, we may assume that (j>(x) < v_{x) out of BL(XO,0). Therefore there exists a sequence xe such that L{XQ,XS) -> 0 for which 4>{x£) = Vhe{xe) + &e, Hx) < Vhe(x) + 5t for x G O with 5S -¥ Ofor e ->• 0.
56
Since v^e is a solution of (23) we get / vh((xe+hb(xe,a))-vhe(xe) \ 0 = supaeA < f,(xe,a)^ < ( (j)(xt+hb(xe,a))-(j>(xe) \ h <j)(xt + \b(xc,ae)) -4>{xe) fe(x(1a€ h for some a e S A. By the mean value theorem for the generalized gradient (see 8 ) , there exists p e e d<j>(xe+r}hb(x(,a()), for some 77 € (0,1), such that <^(x£+/i6(a;e,a£))— 4>(xe) = hb(xe,a€)pt. Therefore 0 < -b(xt,a()p(
-
fs(x£,at)+uf(hMb)
where xt = x( + T)hb(xt, ae) and M& is a constant such that \b(x, a)\ < M\> for any (x,a) £ ft x A. Dividing the previous inequality for / e (x e ,a e ) and taking the sup we finally get i
0 < sup ^ Since pe(x,p) (27).
b(x fiiA \ _1+'xtm=Ps{x„Pt) _!+^wi. v
fe(x,a) J e e < p(x,p), recalling hypothesis (25), we get a contradiction to •
To get a fully discrete approximation of (3)-(4), we can take a triangulation r of ft and look for a solution of (23) in the space Pl of continuous functions which are linear on the simplices of the triangulation. We end up with the finite dimensional problem v
L(xi)
= inf a€A {vlSXi
+ hKxUa))
+ hfe{Xi,a)}
Xi € ft
where x^ are the vertices of the triangulation (see 5 for details in the case of the eikonal equation). Now we describe a vanishing viscosity approximation of equation (3). It is worth noting that the vanishing viscosity method applied directly to equation (3) does not work (see n for an example). Therefore we prove convergence of the vanishing viscosity passing through the regularized equation (18). T h e o r e m 4.2 Let vtn be a sequence of solutions of -nAvVt + He(x, Dvm) = 0 x £ vflt(x)=g(x) xedft.
ft
,2^ '
[
57
where He(x,p)
is defined as in (19). Assume that 77 = 77(e) is such that 2 -> 0
as c -)• 0 + .
(29)
Then u(a;) = lim ^ ( a : ) uniformly in 0 w/iere v is the singular solution of (3)-(4). Proof. As in Theorem 4.1 we will only prove that v{x) = lim inf«v ns (x) is a singular supersolution of (3), since the remaining part is classical. We assume by contradiction that there exists
x GO
in the viscosity sense. Thanks to Lemma 3.1, it is not restrictive to assume that 4>(x) < v(x) out of BL(X0, 0). Hence we can find a sequence xe of minimum points for vne —
1
xeO.
(30)
where the previous equation is intended in pointwise sense since fa is regular (see for example 1 , Prop. 5.1). Moreover the uniform convergence of cps to
(31)
Choosing e and J sufficiently small in such a way that xe($ € O and such that the right hand side in (31) is positive, we get H(x,D4>$(xes)) > 0 and therefore D
58
References 1. M.Bardi and I.Capuzzo Dolcetta, Viscosity solutions of Bellman equation and optimal deterministic control theory, Birkhauser, Boston, 1997. 2. M. Bardi and M. Falcone, An approximation scheme for the minimum time function, SIAM J. Control Optim. 28 (1990), 950-965. 3. G.Barles, Solutions de viscosite des equations de Hamilton-J'acobi, Springer Verlag, Berlin, 1994. 4. G. Barles, and P. Souganidis, Convergence of approximation scheme for fully nonlinear second order equations, Asymptotic Anal. 4 (1991), 271283. 5. F.Camilli and L.Griine, Numerical approximation of the maximal solution for a class of degenerate Hamilton-Jacobi equations, to appear on SIAM J. Num. Anal. 6. F.Camilli and A.Siconolfi, Maximal subsolutions for a class of degenerate Hamilton-Jacobi problems, Indiana Univ. Math. J. 48(1999), 1111-1132. 7. F.Camilli and A.Siconolfi, Nonconvex degenerate Hamilton-Jacobi equations, to appear on Math.Z. 8. F.H.Clarke, Optimization and nonsmooth analysis, SIAM, Philadelphia, 1983. 9. M.G.Crandall and P.L.Lions, Viscosity solutions of Hamilton-Jacobi equations, Trans. Amer. Math. Soc. 277 (1983),1-42 10. H.Ishii and M.Ramaswamy, Uniqueness results for a class of HamiltonJacobi equations with singular coefficients, Comm. Partial Differential Equations 20 (1995), 2187-2213. 11. S.Kamin, Singular perturbation problems and the Hamilton-Jacobi equation, Integral Equations Operator Theory 9 (1986), 95-105 12. P.L. Lions, Generalized solutions of Hamilton-Jacobi equations, Pitman, London, 1982. 13. P.L. Lions, E. Rouy and A. Tourin, Shape-from-shading, viscosity solutions and edges, Numer. Math. 64 (1993), 323-353.
59 SOME M I C R O S T R U C T U R E S IN T H R E E DIMENSIONS M. CHIPOT Angewandte Mathematik, Universitat Zurich, Winterthurerstr. 190, CH-8057 Zurich V. LECUYER Ecole Nationale Superieure des Industries Chimiques de Nancy, Ecole Nationale Superieure des Mines de Nancy, 2, rue de la Citadelle, F-54001 Nancy The goal of the paper is to analyze the creation of microstructures in problems of Calculus of Variations with wells. More precisely we consider a case with strong incompatibility between the wells in dimension three. This forces the minimizing sequences to use other gradients than the wells in a complicated way.
1
Introduction
In this note we would like to analyse the appearence of microstructures for a three dimensional problem with incompatible wells. Incompatibility is an obstacle to the generation of minimizing sequences. Indeed the impossibility to use incompatible wells in contiguous regions of the space forces the minimizing sequences to adopt a complicated pattern to reach low levels in energy. This is what we would like to show on a particular example. For this purpose let us first introduce the general framework of the problems that we have in mind here. We denote by ft a bounded domain in R 3 . We could work in R n as well but for the clarity of our study we will restrict ourselves to dimension 3. In mechanical terms ft represents the reference configuration of a crystal. We will denote vectors by columns and set W1'°°(n,R3)
= {v = (v1,v2,v3)T\
(1)
Vi : ft —> R is Lipschitz continuous Vi = 1,2,3} T denotes here the transposition. If dQ, denotes the boundary of ft we also introduce W01'oo(ft) = < ' o o ( f t , R 3 ) 1 00
= { v 6 W ' ^) For v e Wo1'00(ft),
(2) 1 00
3
= W ' ^, R ) | v = 0 on aft}.
60
v
-(£L, 3
(3>
will denote the Jacobian matrix of the mapping or deformation v. Let us denote by M 3 the set of 3 x 3 matrices. If
VW^Wi,
i = l,...,k.
(4)
(5)
(p is some density of energy. Then the problems that we would like to address here are of the type Inf
[ tp(Vv(x))dx
(6)
or if I I denotes the euclidean norm in R 3 Inf /
(8)
where rk denotes the rank of matrices. Otherwise we will say that A, B are compatible. Suppose that A, B are two wells of
, Vv = Bon£lB-
(9)
However, in the case where A, B are incompatible, (9) cannot hold on two contiguous regions of fi, i.e. one cannot have a continuous deformation v such that (9) holds - for instance in the distributional sense - if £1^, QB a r e t w 0 contiguous domains. This observation goes back to Hadamard. In particular,
61
when all the wells of ip are incompatible one can imagine that the minimizing sequences have to adopt a complicated pattern since a lot of intermediate zones between the zones where Vv = W* have to be created. This is what we will see below on a three dimensional example. For the case of compatible wells we refer the reader to 6 , 3 , 4 . For a survey of these problems we refer to 12 . Also we would like to mention the pioneering paper 9 . 2
A three dimensional example
A matrix m £ M 3 will be denoted by m = (771^)^=1,2,3- Then, as wells we would like to consider diagonal matrices. More precisely we set W,
W3=\
-1 0 0\ 0 -2 0 , 0 0 1/
- 2 0 0\ /00 0 0 1 0 ] , W5 = 0 0 0 ] . 0 0 1/ \00 - 1 /
W4
(10)
Then in the m^-space these wells are represented by the figure below. "133 i
W'
; W3
Wi
/
Wo
1 WA
W[/
/
/w[ mn
<wx ' W5 m,22 Figure 1.
62
We will also use the matrices
(11) which are not wells but will play an important role. The model that we are considering here is a variant in dimension 3 of 4-well problems considered by various people (see for instance 14 , 15 , 5 ) . Clearly the five wells W% are totally incompatible in the sense that it holds that rk{Wi -Wj)>l
Vi ^ j .
(12)
One can then show Theorem 1 The infima (6), (7) are equal to 0. They are not achieved. Proof. The fact that (6), (7) are equal to 0 will follow from what we will see below. However it is interesting to give a direct proof in the case of (6). For that recall that for any A € M 3 it holds that Q
Inf
/
(13)
where Qtp denotes the quasi-convex envelope of tp, |Q| the Lebesgue measure of O (we refer the reader to 10 for details). It is well known that Qtp is rank-one convex in the sense that it holds that Q
+ {l-t)Q
for any couple of compatible matrices (A,B). infimum (6) is such that Inf
V i e (0,1)
(14)
From (13) it follows that the
/ ip(Wv(x))dx = \il\Qtp(0).
(15)
«6W 0 liOO (fi)7n
Moreover we deduce also from (13) that 0
Inf
[
[tp(Wl)dx
=0
so that Qip{Wi) = 0 Vi = l , . . . , 5 .
(16)
63
Then, noticing that Wl = \wi+l-W[+l
Vi = l , . . . , 4
(17)
with the convention that W$ - W[ we obtain using (14), (16) 0 < Q
< ±Q
< ±Q
(18)
It follows that Qip(Wfi=0
Vi = l , . . . , 4 .
(19)
Using again the rank-one convexity of Qtp we deduce easily that Q
(20)
Ju Due to (5) this imposes Vu(i) = Wi a.e x e fl, i.e. a n dx2 dxi \
* 0 0\
ftft&H
°*°
=
a,l£a
(21)
This forces Ui to depend on Xi only. But if v* vanishes on the boundary of n this imposes u, = 0 Vi = 1,2,3. (In the case of (7), u = 0 follows from JQ \u(x)\2 dx = 0). But then (20) is impossible since ip(0) > 0. This completes the proof of the theorem. Q To understand the structure of the minimizing sequences attached to (6) or (7) we have Theorem 2 Let un be a minimizing sequence of (6) or (7) such that IMaOH,
||Vu»(x)||
a.e. x £ Q.
(22)
64
for some constant C independent of n. (\\ • \\ denotes a norm in E 3 or M3). Then we have un —> 0
uniformly in
Vu„ ^ 0
in L°°(ty
fi,
-* weak,
(23) (24)
moreover, the sequence of gradients Vu n generates a unique homogeneous Young measure in M3 given by 4
1
1
i=l
where 5\Vi denotes the Dirac mass at the point Wi. (We refer the reader to or 13 for the notions on Young measures).
l
Proof. Since un satisfies (22), by a compactness argument there exists u in 1,00 WQ'°°(Q,) in the case (6), u in W (fi) in the case (7) such that up to a subsequence un —> u Vu n ->• Vu
uniformly in
fi,
in L°°(n) -* weak.
(26) (27)
Moreover Vu n defines a Young measure in the sense that there exists a probability ux(X) parametrized by x on M3 such that for a subsequence Vunk it holds that F(VunJ-^ f
F(\)dvx(\)
in L°°(0)-* weak
(28)
JM3
for every continuous function F on M3. Considering first (28) with F =
(29)
that is to say /
p(\)dvx(\)
= 0 a.e. x e f i .
(30)
Prom (5) we deduce that vx is supported on the wells Wi - i.e. one has 5
vx = 2_.ai(x)$Wi
a e
- - a; € Q
(31)
65
where aj, i — 1 , . . . ,5 are nonnegative measurable functions such that (recall that vx is a probability measure): 5
^Tai(x) = 1 a . e . i e ! l .
(32)
»=i
Considering then for F in (28) the function F(X) = A^,
i ^ j we deduce
from (27), (28), (31) that
In the case of (6) this implies u — 0 since u vanishes on the boundary of CI. In the case of (7) u is trivially equal to 0 since un —* 0 in (L2(Cl))3. So, in both cases, since the limit of any subsequence of un is the same we obtain (23), (24). Remains to establish (25). For that we go back to (28) that we apply with F{\) = Xu, i = 1,2,3. It comes by (24), (31) ax + 2ct2 — as — 2a 4 = 0 a.e. x €
fi,
2otx — Q2 - 2a3 + CK4 = 0 a.e. x G
fi,
on + a-2 + c*3 + c*4 - c*5 = 0 a.e. x € fi.
(33) (34) (35)
Moreover applying (28) with F(\) = det(X) and using the fact that the determinant is continuous for the L°°(Jl)-*weak topology we obtain 2 a : - 2a 2 - 2a 3 + 2a 4 = 0 a.e. a; e
fi.
(36)
Combining (32), (33)-(36) we deduce easily c*5 = r ,
"j = x
Vi = 1,...,4.
This completes the proof of the theorem.
• 13
Remark 1 The intuitive meaning of (25) (see ) is the following. At the limit and around each point x, Vu n will take the values Wj with the probabilities indicated in (25). However, since the use of two wells is prohibited on contiguous domains this should lead to a complicated structure for the minimizing sequences. This is what we would like to analyse now.
66
3
Minimizing sequences
We are going to construct minimizing sequences for (6), (7) in some finite element spaces. For that we assume that fi is a polyhedral domain of R 3 and we denote by r^ a regular family of triangulations of fi (see 8 ) composed of tetrahedra. Then we set Vh — {v = {vi,V2iVz)T\vi
: ft —* R is continuous,
Vi\K € Pi, Vi = 1,2,3,
(37)
VKerh}
where Pi denotes the space of polynomials of degree 1 on R 3 , K a simplex of Th, Vi\K the restriction of u* to K. In other words Vh is the set of continuous affine functions on each elements of the triangulation. Further we set V0h = {v e Vh\v = 0 on dtt}.
(38)
Then with this notation the discrete analogues of (6), (7) are respectively Inf / ip(Vv(x))dx, vev0h Jo, Inf
(39)
/
(40)
Even so (6), (7) have no minimizer, (39) could admit one (we refer to 5 for details and conditions on
» = 1,-",M
(41)
a basis of Vh. Then one can write for every v £ Vh M
v = Y^Vi
(42)
/ ¥>(V«(ar)) + \v(x)\2 dx = G{vu ••• , vM), (43) Jn for some function G. Clearly since
VveVh.
(44)
67
So, to minimize G on M.M we can restrict ourselves to a compact set. But then, since G is continuous, the existence of a minimizer follows. This completes the proof of the theorem. • We now turn to the construction of minimizing sequences. Let a 6 (0,1) a parameter that we will fix later on. We define a saw-tooth function s = sa by setting (h is the mesh size of the triangulation) m-J* ~\2ha-t
fort£[0,n {ort€[h«,2h%
Sa[)
[
'
and supposing sa extended by periodicity of period 2ha over M.. sa is represented on Figure 2.
We are then going to use the technique of 5 to define a piecewise affine function on E.2 that will be useful to us. First for a 3 x 3-matrix W = (toy) we will denote by W the 2 x 2-submatrix
W = (W^ WA .
(46)
V 1021 Will
^
'
Then we define v°{xi,x2)
= (sa{xi),sa(x2))T.
(47)
Clearly it holds that Wv°(x) = Wi
a.e. x
eE2
if Vu° denotes the 2 x 2-Jacobian matrix of v°. The repartition of the gradients of v° is depicted in Figure 3 which is supposed to reproduce itself periodically. From (17) we derive easily that W
^
= lW^
+ lWUi
Vi = l , . . . , 4
(48)
68 X2
j.
0
&i
Wi
W[
Wi ha
Xi
Figure 3.
with the convention that W'^ = W\. Then, we proceed like in 5 to construct a function vp using p iterations. More precisely if (49)
we remark that
vlfa) - x2 a 2
(50)
on (0, h ) . Then instead of going up with a slope 1, one can go up and down with a slope 2 and -1 as shown on Figure 4.
Figure 4.
69 This produces a function v° which is not matching v° on the sides of the square so we set on Q = (0, ha)2 vl = v°2 A {dist(x, diQ) + v%}
(51)
where d\Q denotes the set {xi = 0} (~l {x\ = ha}, (A, V are the minima and maxima of numbers). We set
v' = {vl,vl)T. The repartition of gradients is given by Figure 5.
ii
Wi
w^
Wi
w>2
wx
w2
w,
Wi
W,
Wi
other gradients
ha
hi
zi
k Figure 5.
We repeat the process to replace W2 by W2 and W3. More precisely in Figure 5 we consider the rectangles where Vu 1 = W2- The sides of these rectangles have length | j - and ' k'—. So, we can split them into 3(fc — 2) squares - see Figure 6.
hi 3k Figure 6.
On each of them we have Vu 1 = W2. So, on each of them we can replace vl
70
by a function v2 which agrees with v1 on the boundary but with a repartiton of gradients given in Figure 7.
other gradients W2
W,
w2 w2
Wn
Wtr
wt
Wi
Wi
wkr
?**m&WFw* ^ip-if^rwM Tjjsww??
hi
hi
3k
3fe
Xi
Figure 7.
Continuing the process where Vu 2 = W'3 one generates that way a sequence of functions v1,... ,vp. We stop the process after p operations. We then perform the same splitting on the four squares of (0,2h a ) 2 where we have Vv° — W'i we obtain thus a function that we still denote by vp. We extend it by periodicity of period 2ha in both directions we obtain that way a function which gradient is uniformly bounded independently of h —> 0, and defined on all R 2 . It is also easy to show that ha
ha
1,2
i.e
-ha
-ha 2
(52)
(vf could become slightly negative when replacing a slope —1 by slopes - 2 , 1). Then, we define a function u in M3 by setting - and extending it periodically
71
in the x 3 direction - for /3 < a, (3 € (0,1) ( X 2
' '
3j
\(0,0,2^-x 3 ) T forte [/i',2^],
(53)
where u? = - d ( x 3 ) V v? A d(x 3 )
i = 1,2,
(54)
and d(x 3 ) is the distance d(x3) = x 3 A 2/i" - x 3 .
(55)
Since all the gradients that we used are bounded independently of h, Vu is bounded independently of h. Now perhaps u is not vanishing on the boundary of Cl so we set ili = —d{x,dCl) V Ui Ad(x, dd),
u = (ui,U2,u 3 ) T
(56)
where d(x, dd) is the distance to the boundary <9f2 of Q. Finally we set Uh = the interpolant of u
(57)
that is to say the unique element of VQ that coincides with u on the nodes of the triangulation. Since the triangulations is regular it holds that |Vu„| < C
(58)
where C is a constant independent of h. Then one has for some other constant C I tp(Vuh(x))dx < C\{x\Vuh(x) #W}| (59) Jn where W = {W\, W2, W3, W4, W$}, \ | is the Lebesgue measure. Let us then estimate the right hand side of (59). Denote by E = {x| Vu/,(i) ^ W } . E is composed of several subsets. First due to the cut-off with the distance to the boundary, E contains a neighbourhood 5i of dCl where uu = ±d(x,dil). Since by (52), (53) it holds that |«w(a:)| < 2h0
(60)
one has for some constant C \Sx\
(61) a
Next, due to (52), (54) E contains a neighbourhood of size h around each of the hyperplanes x 3 = khP. If 52 is this neighbourhood it holds that \S2\ < Cha~0.
(62)
72
for some constant C depending on fi only. Now remains to analyse what happens in the strip x3 € {2ha, h13 — 2ha) where we have u(xi,X2, x3) = (uf, v\, x3)T
(63)
f
VvV
i.e.
Vu = I
0 I.
(64)
Note that we can always assume that h@ » ha for h small enough since (3 < a. Recall that we will fix these numbers at the end. First due to interpolation along the lines xi = kha
x2 = kha
,
(65)
E contains a neighbourhood of size h of these lines. Let us denote it by 53. Its thickness in the strip 2ha < x3 < h0 - 2ha is bP - 4/i a . The number of such strips is bounded from above by ^ thus it holds
\S3\ < Ch}~a
< Chl~a
J
(66)
Let us leave for the end the estimate of the measure of the bad set due to interpolation along the line of laminations. After p such laminations - p will be fixed later on - there is yet a set S4 where one has Vvp € {W'i, W'2, W'3, W'i}- Of course since the measure of this set decreases at a rate of | at each step one has
\S*\
(67)
where d denotes the diameter of f2. Consider now what happens during the i + 1 t h lamination. We split then a square of size ha/(3h)% into k strips. On such a square we have a part of bad set along two lateral sides. Its measure is bounded by (see Figure 4, 6): 2 ha
ha
Jfc (3fc)« "(3Jfe)*"
(68)
Now, the number of such squares in a square of the grid of size ha is ¥kl(k — 2)\ The number of squares of the grid of mesh size ha contained in Q. is bounded by -^. Thus if Sl+1 denotes the part of the bad set along the sides of the squares where the i + 1 t h lamination occurs one has C_
?s+1l ~< in:3*fc"
(69)
73
Now, in the squares where the i + 1 t h lamination occurs a part of the bad set is due to interpolation along the lines of laminations. Along each such a line the thickness of this set is 2/i, the number of lines in each cube is at most 2k. So, the measure of bad set in the cube is bounded above by
2k 2h
m
- -m
Taking into account the number of such cubes in fi and if one denotes by 5g + 1 the part of the bad set that occurs along the lines of the i + l th -lamination we obtain \Sl+1\
(71)
Combining now (61)—(71) we obtain
\E\
+ h1-akf2(k-2)i+(±y}
i=0
i=0
< c(ha + ha-0 + hl~a + j + hl'akp + (-}
|
(72)
for k > 3. It remains now to choose a, /?, k, p properly. We choose for instance /3 = §, § = 1 — a - i.e. a = \ , /? = I. We obtai am
l*l
. i
i
i
h ^+^> < h ^ + 1 1 - 1 < jfc < /T3TF+IT
(73)
so t h a t I-E7I < CJ/i^itn +
(I
One has h*&+V = (±)P for p(p + 1) = - ln/i/31n3. So, we select p so that it holds that p(p + 1) < -j££
<{p+ l)(p + 2) < 2p2.
Then, for such a p it holds that: \{x\Vuh(x)£W}\ for some constants C\ and C-iThus, we have shown
(74)
74
Theorem 4 Under the above assumptions there exists constants C\, C^ independent of h such Inf
f ip{Vv{x))dx
< C^-0^^^1'2
(75)
Inf [ ip(Vv(x)) + \v(x)\2dx
f
\uh{x)\2dx
ft2/3<e-Ca|lnM
for h small. This completes the proof of the theorem. • Remark 2 Prom (75), (76) it results directly that the infima (6), (7) are equal to 0. 4
Numerical experiments
We first worked with an adaptation of a former software (see 7 , u ) which we successfully used in the two-dimensional case. We divided the cube [0, l ] 3 into 6.n 3 equal tetrahedra, redefined the discretized energy with 3 x 3 matrices on each of those tetrahedra, and used the same descent methods as in the two-dimensional case: • initialization with an already-oscillating deformation, • sequence of Polak-Ribiere conjugate-gradient iterations, and • simulated annealing occuring automatically when the energy freezes. The results we obtained are yet desappointing: 1. The rate of descent is much slower than in two dimensions. 2. The energy itself seems to be much less sensitive to small variations of the deformation, so that simulated annealing loses much of the efficiency we used to observe in the two-dimensional case. 3. Oscillations do not really appear yet.
75
We identified two main reasons those problems seem linked to: 1. The main reason is the rapidly increasing number of tetrahedra (and thus the computation duration) when the number of linear subdivisions n grows up: we only have been able to investigate mesh sizes until n = 30 (1,500,000 matrix coefficients for each step of the deformation). 2. We got also some difficulty in representing the deformed threedimensional structure in order to directly observe and identify oscillations, which may, a priori, occur in any direction of space. At this moment, the only adaptation of our previous two-dimensional code does not seem to be sufficient, mainly due to the huge increase of the number of variables involved. We are currently investigating more specific three-dimensional methods and graphic representations of the computations in order to numerically obtain the theoretically expected oscillations. Acknowledgments This work has been supported by the Swiss National Science Foundation under the contract # 20-58856.99. The first author is very grateful to this institution for its help during the elaboration of the work. References 1. J.M. Ball, A version of the fundamental theorem for Young measures, In: Partial Differential Equations and continuum Models of Phase Transitions, Lecture notes in Physics, vol. 344, M. Rascle, D. Serre, M. Slemrod Eds, 1989, p. 207-215 2. J.M. Ball, R.D. James, Fine phase mixtures as minimizers of energy, Arch. Rat. Mech. Anal. 100, 1987, p. 13-52. 3. M. Chipot, Numerical analysis of oscillations in nonconvex problems, Numer. Math. 59, 1991, p. 747-767. 4. M. Chipot, Energy estimates for Lagrange finite elements. Atti del Seminario Matematico e Fisico dell'Universita di Modena, XLIII, 1995, p. 307316. 5. M. Chipot, The appearence of micro structures in problems with incompatible wells and their numerical approach, Numer. Math. 83, 1999, p. 325352. 6. M. Chipot, C. Collins, D. Kinderlehrer, Numerical analysis of oscillations in multiple wells problems, Numer. Math. 70, 1995, p. 259-282.
76
7. M. Chipot, V. Lecuyer, A new scheme for quasiconvex optimization in Multiple-well problems. 8 t h European Conference on Numerical Mathematics and Advanced Application, (ENUMATH 1997) - Bock and all Edits. World Scientific, 1998, p. 238-249. 8. P.G. Ciarlet, The Finite Element Method for Elliptic Problems, 1978, North Holland, Amsterdam. 9. C. Collins, D. Kinderlehrer, M. Luskin, Numerical approximation of the solution of a variational problem with a double well potential, SIAM J. of Numerical Analysis 28, 1991, p. 321-332. 10. B. Dacorogna, Direct Methods in The Calculus of Variations, 1989, Springer Verlag. 11. V. Lecuyer, Thesis, University of Metz, 2000 12. M. Luskin, On the computation of crystalline micro structure, Acta Numerica, 1996, p. 191-257. 13. P. Pedregal, Parametrized measures and variational principles, Birkhauser, 1997. 14. L. Tartar, Some remarks on separately convex functions, in: Microstructure and phase transitions, D. Kinderlehrer et al. Eds., 1992, Springer Verlag, p. 191-204. 15. M. Winter, An example of micro structure with multiple scales, EJAM 8,2, 1997, p. 185-208.
77
C O N V E R G E N C E OF N U M E R I C A L SCHEMES FOR THE A P P R O X I M A T I O N OF LEVEL SET SOLUTIONS TO M E A N CURVATURE FLOW KLAUS DECKELNICK School of Mathematical Sciences, University of Sussex, Falmer, Brighton, BNl 9QH, England E-mail: [email protected] GERHARD DZIUK Institut fur Angewandte Mathematik, Universitdt Freiburg, Hermann-Herder Str. 10, 79104 Freiburg, Germany E-mail: [email protected]
1
Introduction
The subject of this paper is the numerical approximation of solutions to the level set equation for mean curvature flow. The level set approach can be described as follows: given a compact hypersurface choose a continuous function «o : BT -S- H such that r 0 = {x £ H " | u0(x) = 0}. If u : ET x [0, oo) -> K is the unique viscosity solution of
( Sij u(.,0) = «o
ux ux \ ' ' juXtXj
in IR," x (0,oo)
(1)
inH",
(2)
we then call F(t) — {x E IR." \u(x,t) = 0},< > 0 a generalized solution of the mean curvature flow problem. As T(t) exists for all times, it provides a notion of solution beyond singularities in the flow. For this reason, the level set approach has also become very important in the numerical approximation of mean curvature flow and related problems. In this note we are primarily concerned with convergence results for numerical methods. The first such result was obtained by Crandall & Lions in 3 for a finite difference scheme. We shall present their approach together with a summary of an error analysis recently carried out in 4 . This method will be compared with a natural finite element approach. We shall use techniques developed by the authors in 5 , 6 for the error analysis of graph solutions in order to establish a convergence result for level sets.
78
2
Background
We start by briefly describing the theoretical framework of (1), (2). Definition 1 A function u € C°(IRn x [0, oo)) is called a viscosity subsolution of (1) provided that for each <j> G C°°(IR n+1 ), if u — 4> has a local maximum at {x0,t0) € H n x (0,oo), then
*'
X
' )<j>xtx, at (x0,t0),
ifV
(3) at {x0,t0) for some \p\ < 1, ifV4>(x0.t0) - 0.
A viscosity supersolution is defined analogously: maximum is replaced by minimum and
for |z| > S
(4)
for some S > 0. The following existence and uniqueness theorem is a special case of results proved independently by Evans &: Spruck 10 and Chen, Giga & Goto l. Theorem 1 Assume Ho : H n —> H satisfies (4). Then there exists a unique viscosity solution of (1), (2), such that u{x,t) = l
for\x\+t>R
for some R > 0 depending only on S. The abovementioned authors also established that the sets T(t) — {x £ H " | u(x,t) — 0},t > 0 are independent of the particular choice of uo which has To as its zero level set, so that the generalized evolution (T(i))t>o is well defined for a given To. The level set solution has been investigated further in several papers, among which we mention in particular 11 , 12 , 13 and 18 . Numerical schemes based on the level set approach were first introduced by Osher and Sethian in 16 , see also 17 . Chen, Giga, Hitaka & Honma 2 proposed a finite difference scheme for which they proved stability with respect to the L°°-norm. In 19 , Walkington uses a finite element approach on the dual mesh to construct a discretization which is stable both with respect to L00 and to W1'1. Evans analyzes in 9 a scheme, which is based on the solution of the usual heat equation, continually reinitialized after short time steps. This scheme was proposed by Merriman, Bence and Osher in 15 . The first convergence result for a finite difference approximation of (1), (2) was obtained by Crandall k. Lions in 3 . We shall review their method in the following section and present a summary of a recent error analysis for this scheme.
79
3
The Crandall-Lions scheme
Since (1) is singular and degenerate it is natural to regularize the equation and to construct a numerical scheme for the regularized problem. In fact, Evans & Spruck proved in 10 that the solutions u€ of
u e (.,0) = wo
in I T
(6)
converge locally uniformly as e —>• 0 to the unique viscosity solution of (1), (2). In order to motivate the scheme in 3 , note first that one can write (*i ~ ca + | v « « p ) = E ^ ( V ^ ) ^ ( V ^ ) ,
i,j = l,...,n,
(7)
where ^ ( P ) = * i -
T T =
V : ^ T ,
PGIR"-
(8)
Using the relation (7) we can approximate the right hand side of (5) as follows: e
e
'
TO
*= 1
'
Me(- + /ifle(Vue)efc, •) + M£(- - h$c(Vue)ek,
^
*2,
^
•) - 2ue
for small h. The above relation is the basis for the scheme in 3 , which we describe now: for p > 0 let Qp = {/>(mi, ...,m„) \rrii £ Z , i = 1, ...,n} a space mesh and At > 0 a time step size. To every grid function v : Qp —¥ H we associate a function i?ii £ C°(IR n ) satisfying Ev(x) = v(x)
for all a; £ Qp.
Then W A ^ : IR is defined by (WAtv)(x)
= v(x) E ^ s + h6e{Dpv{x))ek)
A +
/i2
^
fc=i v x
A,p]£\^
A
+ Ev(x - h6e{Dpv{x))ek)
L
£=1
+ Pek) +vix
"-
- pek) ~ 2u(a;)
- 2v{x)
80
where Dpv(x) is the central difference operator, i.e. D„v{x) = —(v{x + pei)-v{x-pei),...,v(x
+ pen)
-v{x-pen)).
Let us briefly comment on the definition of W&t: (i) Our definition (8) of (0e),j slightly differs (by the factor (1 + from the one given in 3 (see Eq. (0.2)). We made this change to ensure (7), the results of 3 however remain valid. (ii) The extension Ev is introduced because x ± h6€(Dpv(x))ek is not necessarily a grid point. A simple way to construct Ev is indicated in 4 . We summarize the main results obtained by Crandall & Lions in the following Theorem 2 Let u be the viscosity solution of (1), (2). Suppose that the following relations between the parameters occuring in the definition of W&t are satisfied:
I") £-0. f - 0 . Then W/\t is nonexpansive in the supremum norm, i.e. \\WM4 - WitriWoo < \\
V^^:^-+]R
(9)
and (W3Atuo)(x) -> u(x,t)
locally uniformly in (x,t) G R n x [0, oo)
as At —> 0, jAt —> t bounded. In the above relations one thinks of h, p, K and e as being given in terms of At. In the error analysis which we are going to describe next, it is more natural to specify h, p, K and At in terms of e. We shall only sketch the main ideas, detailed proofs can be found in 4 . Our starting point is the obvious estimate || w (.,iAi)-V7i t U o ||oo
< Cea
foralloO.
81
Proof, see §2 in 4 , the key idea being the same as for the uniqueness proof of viscosity solutions, namely the doubling of variables technique. I We shall obtain a bound on the second term on the right hand side of (10) by combining the stability estimate (9) for W&t with the following consistency result: Lemma 1 Let u€ be the solution of (5), (6). There exists a constant C > 0 such that for e > 0 sup \ue{x, (j + I)At) - (WAtu£(-,jAt)){x)\ see, ,.;'<[&]
<
CAtLe,
where
Le=(^
+ ^-)||i?V|U- + £||0V|U~ + [D2u%th + A*|K||L-.
Here, we also used the notation [D2u%ih = m&x ''3
sup
\((D2ue(x +
Pey,t)-D2ue{x,t))P'LeilPeej)\,
reS„,0
c
with P* = 9 {Vue(x,t)). 4 Proof, see , §3, in particular Lemma 3.1 and 3.2.
I
e
Remark 1.1 (i) In the definition of L above, L°°-norms are taken over AT x (0,T). (ii) The matrix 0e(p) approximates for p ^ 0 and small e a projection onto the linear subspace which is orthogonal to A . The presence of Pe = f (Vu E (x, t)) in the definition of [D 2 u e ] £| /, therefore has the effect that normal derivatives (in the direction of I V ^ I (x, t) are weighted by a small factor. We are now able to derive a preliminary estimate for the second term on the right hand side of (10). Using Lemma 1 and (9) we obtain ^(•.(j+lJAO-Wit^olloo < \\u<{-, {j + 1)At) - W At u e (-, jAiJHoo + \\WAtu<(;jAt)
- Wlt^oHoo
e
< C A i L + ||(-,jA*)-WVo||oo so that an induction argument implies \\u'{-,jAt)-WituQ\\oo
j < [£]
(11)
since u£(-, 0) = uo- It remains to estimate Le, which contains norms of higher derivatives of ue. These norms will in general not be bounded uniformly in e, so that all we can hope for are bounds in terms of negative powers of e. We
82
obtain such estimates by exploiting an observation made in 10 , namely that the function Ue : H " x [0,oo) ->• 1R, defined by Ue{x,t) := ±u'(x,t) solves the equation Ut = VI + | V t ^ d i v (
Jj^
in JRn x (0,oo).
)
This means, that the graph Tet = {(x,z n + 1 ) £ ]R n+1 | z n + 1 = Ue{x,t)} of Ue(-,t) is moving by mean curvature. Mean curvature evolution of entire graphs has been studied by Ecker k Huisken in 8 , where the authors prove among other things estimates for the curvature and higher order derivatives of the curvature of Tj. It turns out, that these estimates can be translated into bounds on derivatives of ue using the relation between Tj and ue. This analysis is carried out in §4 of 4 and we summarize the results in the following Theorem 4 The solution u£ of (5), (6) satisfies l|£ > 2 « £ (-.<)ll L =. ( ]R» )
WD^i-M^^
3
IK(-.*)IL~(]R-) < Ce- , 0 < t < T. Let f3 e (0,1). Then there exists A > 0 such that for h < Xe2
[D2u%h < Crfe-V. We are now in position to derive an error bound for the Crandall-Lions scheme. Combining (10), Theorem 3, (11) and Theorem 4 (with (3 = 2a) we obtain
< Cea + c(p2h2C2
+ Kph~lr2
+ p2h-le~6
+ h2arAa
+
Ate-3)
provided that h < Xe2. We choose the parameters in such a way that on one hand condition (i) in Theorem 2 is satisfied, on the other hand the two terms on the right hand side of the above inequality balance. This leads to our main result, Theorem 5 Let u be the viscosity solution of (1), (2) and W^tuo,0 < j < [57] ^ e discrete solution obtained from the Crandall-Lions scheme. Then ||U(.,jA<)-^itUo||oo
a<±,
provided that 5
il
h = e2, p = e 2 , At = cje
.17
2
_ 1
, A = c^e
where c\, en are suitably chosen positive constants.
5
,
83
4
Finite element method
Our finite element method is again based on a regularization, but since we intend to work in a variational context it is more appropriate to consider the regularized problem on a bounded domain, i.e. U\ = (ft; - £2 + | v f i * | 2 ) f i ^ i
ln Q X
ue = 1 e
u (.,0) = uO|n
(°> T )
( 12 )
on<9flx(0,T)
(13)
in
(14)
ft.
Here, UQ satisfies (4) above and ft = 5^(0) for some S > S. To simplify matters we assume in addition that -l
<1,
xeM".
(15)
Let us start by discussing the existence and a prion estimates for u e . Theorem 6 The problem (12)-(14) has a unique smooth solution ue. Furthermore, \\(ue,Vue,u5)\\L~{nx(o,T))
(16)
umformly in 0 < T < oo and 0 < e < 1. Proof. We shall primarily focus on proving the a priori estimate (16). It is well-known that the existence of ue essentially follows from (16) with the help of the Schauder method. Suppose that ue solves (12)—(14). The maximum principle implies that max |u e | = maxlwnl = 1 nx[o,T] ft
(17) '
K
by (15) and (13). The next step consists in estimating m a x a n x [ 0 T ] |Vu e |. In view of (13) it is enough to bound maxanx[o,T] 1 ^ 1 , where n denotes the exterior normal to dQ. Observe first that (13) and (17) imply due — >0
ondftx[0,T].
(18)
In order to obtain an upper bound on ^ we introduce d(x) := S — \x\, the distance function to dQ and consider v(x) := log(e — ~fd(x)), x G Qg ; = { i £ fi | 0 < d{x) < 8} {-yS < e). Clearly, 7"r,
e — fd
7 dXiaXj
(e — 7d)
T^r.ij J
e — ~/d
.
.
84
Recalling that \Vd\ = 1, Ad = — •TJT and dXidXjdXxXj = 0 we compute „
(X..
Vx Vx
' > \7: | V ^|2^ *i*i
e2 +
l{ U - - ^ (e-7d)|x|
I ,-2
(e-^)2
€2 +
-7d)2
7(n — 1) eS
,
provided that 7 > ~- (note that e < 1). Choosing d" < 5 — 5, (4) implies 11(2) <
x G fij.
UQ(X)
Furthermore, we have by (17) v(x) < ue{x,t)
x edQ.6,0
provided that 7 > 5~l(e — e _ 1 ) . By choosing 6 smaller if necessary we may assume that S~l(e - e~l) > -^^ and then set 7 = 6~1(e - e~l) < 5~le. The maximum principle yields v(x) < ue(x,t),
x Gfi{,0
If we combine this inequality with (18) and the fact that v — ue = 1 on d£l x (0,T) we deduce that 0 < $ ^ < ? i ~ on ~ on
on3ftx(0,T)
which implies max |Vwe| < C uniformly in 0 < T < 00 and 0 < e < 1. (19) snx[o,T] ~ Differentiating (12) with respect to Xk,k = l,...,n and applying again the maximum principle yields in view of (19) a bound on ||Vu£||i,=o(nx(o,T))- Since u\ — 0 on dQ x (0, T) the estimate for u\ follows in a similar way. I The bounds (16) enable us to apply the Arzela-Ascoli theorem to (ue)o<e
uniformly on fi x [0, T],
for all T < 00 as j -*• 00.
Let us extend u to H n x [0,oo) by denning u(x,t) Clearly, u € C°(IRn x [0,oo)); we claim L e m m a 2 u is a viscosity solution of (1), (2).
(20)
:= l , i e R n \ f i , t > 0.
85
Proof. Clearly, (6), (20) and (4) imply that w(-,0) = u0. We prove that u is a viscosity subsolution of (1). Let
(21)
for all (x,t) in a neighborhood of (xo,to). Choose a parametrization \t : IR n _ 1 D U ->• R n , p M- tf (p) of dfi near x 0 which satisfies $(0) = 2o and 9ij(0) = (* p i (0),* P j (0)> = <Jjj. Let us abbreviate r,- = * P j (0), i = 1,..., n- 1. Since w = 1 on dQ, x (0, oo) we deduce from (21) that (p,t) *-»• 0(\f(p),t) has a local minimum at (0,
<^(xo,*o) = 0,
Wi(*o,to) + V^(xo,
>0.
The first relation implies that V<j>(xo,to) — an for some a G H. Recalling that u(x,t) - 1 for x G E " \ Q we infer from (21) that §£(z 0 ,*o) > 0 and therefore a > 0. By taking the trace we deduce from the third relation above n —1
n —1
n—1
X ] ^ . r , (*o, *o) > - 5 Z W ( * o , M • * P , P , (0) = - a X ! *p*i (°) ' n = - a i ? a n (22) where .ffgn denotes the mean curvature of dQ with respect to n (remember that ^ij(O) = Stj). If V^(a;o,to) = cm ^ 0, (22) implies at (x0,t0)
since a > 0 and Cl is convex. On the other hand, if V4>(xo,t0) = 0 we have as above for the choice p — n
at (x0,to)
proving (3) for the case x0 G dQ. Finally, if x0 G K" \ fl, we immediately deduce that <j> has a local minimum at (x0,to) and (3) then follows in a similar way as before. Thus u is a viscosity subsolution and in an analogous way we prove that it is also a supersolution. This completes the proof of the lemma. I
86 Remark 1.2 We immediately infer from Lemma 2 that u agrees with the solution of u of Theorem 1 and that ue -+ u
uniformly on Q x [0, T] as e ->• 0
(23)
for all T < oo. We next describe our finite element discretization of (12)—(14). Let 7/, be a quasi-uniform triangulation of Q with h :— maxsgr,, diam(S). The finite element space X/, is defined by Xh '•= {
with the usual isoparametric modification at the boundary and we set Xh= Xh fl HQ(Q). It will be convenient to use the following notation for u £
Qe(«):=Ve2 + |VUp,
V e ( u ):=(-^L,-=!-).
VQe(w) Q e (u)y Note that |ve(w)| = 1. Observing that =
(** - .2 • 1 ^ 1 2 ) " ^
W )
d i v
we may write (12) in the following variational form:
A natural semi-discrete finite element method then reads: find ueh : [0,T] —>• X h such that ufft(0) = Ihua, ueh(t) - 1 GX/,,0 < t < T and / 7T7=7T + /
nCM
= 0
'
^eX„,0<*
25
Here, //, denotes the usual Lagrange interpolation operator. Taking the difference of (24) and (25) we derive the error relation {u€t - uehit)
f ( V£t e
+
in
v
<2e«)
Vuj
7777^-777^77 T ^
QeK)'
(26)
87
Next, using <j>h — h^l — u\ t EXh as a test function in (26) we obtain f
Ul
h,t\ h,t\
\Ut
,, //*//
e Vw v "
1">-"h,t)K £ ~ hup
+/
/n
QeK)
vVu\ "ft
\
_ / -
e
_ ~ e
\
f / Vue Vu + / TTT^TT-TTT^T + f 7nVQe(« ) Q e («
• V(«t£ - 7 h u t )
= / + / / + L77. A straightforward calculation yields
+ /"v5< [ Vu< • (
+
V h
^ - V i l + V"£ Qe(K) Q,(u\) Qe(u<)
r( i in W l )
f2
+ V » £ - V ^ _Vue_ Qe(u<)2 Qt(&)
L_W-e f_Z^l_ _ _Z^L^ n M Qe(^)iVU* ' lg,(^) ~ Q£(^)J Q e K )
Recalling the definition of ve we have
1
11 1
(28)
w ' ^" " '* ' ' Vfi£
V«t \ , . 1, , _
._
2
so that the left hand side of (27) can be estimated by |2
/ Ja
>J|^k(« e )-^K)l 2 aK) - - ! ! V M | | U ~ /" k ( « £ ) - i / e ( t i £ ) | 2 Q £ K ) .
(30)
88
Let us next examine the terms on the right hand side of (27). The definition of i/e, (16), Holder's inequality and an interpolation estimate imply
\i\ < ll^lk-- / We("e) - v*Wh)\{\*\ - «MI + K - hu\ e
v
Jn 2
£ 2
< 71 f \*t - *h,t\ 7 W+ ^fit ~ hu t\
4 7n
* i /n ^ I f
C_ f +Z2 +
Q
WeW-VeMWQcM)
t*Jn +
7 'l^"-(") ? /„ Mfi6> - ^ ) I 2 ^ K )
Using similar arguments we further deduce ,-,«
12
|///| < jf M ^ ) - ^ ) l |V(«< - Ihuf)\
< i jT M«£) - „£(^)l2Qe(fie*) + ^/. 2 ||«|||^ (n) . Combining the above estimates with (30) we arrive at 1 f \Vt-Zh,t\2
+
, 1 d /•
u n "o^r 2*y n
,.M|2n
r M
M,i) , e(,ifc)|geK)
-'
< Ci(e)/. 2 + C2(e) f \ve{tf) vt(u\)\2Qe{ui) Jn and Gronwall's lemma yields an error bound for fixed e > 0: f f ^nd^ Jo Jn Qe\uh)
+
SUp / WeW-VeffitfQcM) a
(31)
In what follows we shall assume n — 2 and add a remark on the general case later. In order to control s u p 0 < t < T \\ue(t) — u^(f)||x,«. we first derive a bound on QE(u£h). Let 5 G Th be arbitrary. Using the definition of j / t , (16) and Holder's inequality we obtain
/ \Q^) - QeM)\ JS
< - [ Qe(uE)Qe(il)W^6) - "
JS
89
< j j
(\Qe(u<) - Qe(ul)\^
< \ j
(\Q^1
+ l)y/Qe(u*h)\Ve(Ze)
-
ve(ui)\ uc(i\)\2Qt(u\)
~ Qe{u\)\ + l) + j 2 J \v£(u<) -
so that we infer from (31) since n — 2 sup
\Qe(u'(t))-Qe(ui(t))\
[
0
Hence, as Qe(u\) is constant on S Qe(u{(t))ls
[ \Qe(u<(t))-Qe(ul(t))\+
Q e ({i e )
sup
JS
fix[0,T]
(32) uniformly in 0 < t < T and S 6 Th- Furthermore, using (31) and (32)
ll« e W-«A(*)IU'(n) l < ||«o - huoWncn) + / II"? - &1 h,t\\Li(n,) ds Jo
T
\Jo
<
r l,~e _ ,~,«
f
|2\ 2
r \ ~ Jn
Vel u A
C(e,T,u0)h
uniformly in 0 < t < T. If we combine the above bound with (16), (32) and an interpolation inequality the result is sup \\ue(t) - w£(t)||x,=o(n) 0
(33)
small in (23) and afterwards applying (33) for h = h(e) we finally obtain our main result of this section, n = 2 and u be the viscosity solution of (1), (2) and u\ the Then there exist h(e) \ 0, e \ 0 such that l i m l l u - u ^ l l ^ n ^ o . T ) ) = 0.
Remark 1.3 In the case n > 3 the estimate (31) is not strong enough to prove convergence in L°°(fi x (0, T)). A way to improve (31) is to replace I^u by a suitable nonlinear projection in the relation (27) and then to exploit a
90
superconvergence effect (see 5 , where this technique is applied to the graph case e = 1). In this way one can generalize Theorem 7 to the case n = 3, i.e. for the approximation of two-dimensional surfaces. Moreover, (23) and (31) yield estimates of the form lim sup
||u(t)-u^ ( £ ) (<)|| z , J , ( n ) =0
in any space dimension provided 1 < p < oo is suitably chosen. The above analysis suggests that h(e) has to be chosen very small in order to obtain good results. The following test computation however demonstrates that the method (25) performs very well even for moderate values of h. We consider the function ue(x, t) = sin (|ar|2 — t) — sin (4 — t) + 1 as the solution of a problem of the form (12)—(14) in which (12) has an additional right hand side fQe(ite) for a suitable / and where fi = {x £ IR2| \x\ < 2}. The corresponding modification of (25) then reads
/ 7w=o + /
nVn
= / f*k>
+» eXk,0
(34)
For practical calculations (34) also has to be discretized in time. We used the semi-implicit time discretization analyzed in 7 . In order to eliminate the effect of time discretization the time step r was chosen to be r — 0.5/i2. We are interested in the absolute errors E(h) = \\ue — u^Wx for X = ^ " ( ( O . r ) , L2(Q)),X = L°°{{0,T),Hl{n)) and X = I r o ( ( 0 , T ) , l°°(fl)) with T = 1. The relation between e and h was chosen to be e = h and e = \J~h respectively. The corresponding results for E(h) and the experimental order of convergence
are shown in Table 1 (e = h) and Table 2 (e = y/h). One observes asymptotic convergence even for these moderate values of h. Note also that the fact that the gradient of we vanishes inside Q does not affect the convergence. The above method has also successfully been used in 14 for the computation of two-dimensional dendrites. The underlying free boundary value problem contains an equation of the type (34) as a subproblem. As a second example we computed the evolution according to equation (12) for initial values similar to the surface in Fig. 1. Observe that the initial values are constant to 1 in a neigbourhood of the boundary. And, as expected, this is only slightly perturbed by the regularization parameter e and the discretization.
91 Table 1. Errors for the test problem for the choice e = h.
h
L°°(L2)
eoc
L^iH1)
eoc
L°°(£°°)
eoc
2.8284 1.4736 0.8406 0.4438 0.2274 0.1150 0.0578
2.7493 2.6425 1.8185 0.8228 0.3647 0.2550 0.1795
-
0.3184 6.4574 4.6925 2.6002 2.0332 1.7802 1.1050
-
2.0678 1.7538 0.7199 0.4541 0.2201 0.1350 0.0961
-
0.06 0.67 1.24 1.22 0.53 0.51
-4.62 0.57 0.92 0.37 0.20 0.69
0.25 1.59 0.72 1.08 0.72 0.50
Table 2. Errors for the test problem for the choice t = y/h.
h
l°°(L'2)
eoc
L°°(Hl)
eoc
L°°(L°°)
eoc
2.8284 1.4736 0.8406 0.4438 0.2274 0.1150 0.0578
2.1017 2.9445 1.7974 0.6047 0.1970 0.0903 0.0353
-
1.0552 6.9939 4.5971 1.9731 1.2910 0.7588 0.3481
-
1.3810 1.9644 0.7071 0.3112 0.1094 0.0478 0.0188
-0.54 1.82 1.29 1.56 1.21 1.36
-0.52 0.88 1.71 1.68 1.14 1.37
-2.90 0.75 1.32 0.64 0.78 1.13
A cknowledgment s Figures 1 and 2 were created using the GRAPE visualization package. References 1. Y.-G. Chen, Y. Giga and S. Goto: Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations, J. Diff. Geom 33, 749-786 (1991). 2. Y.-G. Chen, Y. Giga, Y.T. Hitaka and M. Honma: A stable difference scheme for computing motion of level surfaces by the mean curvature, in D. Kim et al (eds), Proceedings of the Global Analysis Research Center Symposium, Seoul, Korea , 1-19 (1994). 3. M.G. Crandall and P.L. Lions: Convergent difference schemes for nonlinear parabolic equations and mean curvature motion, Numer. Math. 75, 17-41 (1996).
92
Figure 1. Slice through the surface after the tenth time step.
4. K. Deckelnick: Error analysis for a difference scheme approximating mean curvature flow, Interfaces and Free Boundaries 2, 117-142 (2000). 5. K. Deckelnick and G. Dziuk: Convergence of a finite element method for non-parametric mean curvature flow, Numer. Math. 72, 197-222 (1995). 6. K. Deckelnick and G. Dziuk: Discrete anisotropic curvature flow of graphs, Math. Modelling Numer. Anal. 33, 1203-1222 (1999). 7. K. Deckelnick and G. Dziuk: Error estimates for a semi implicit fully discrete finite element scheme for the mean curvature flow of graphs, Interfaces and Free Boundaries 2, 341-359 (2000). 8. K. Ecker and G. Huisken: Mean curvature evolution of entire graphs, Ann. of Math. 130, 453-471 (1989). 9. L.C. Evans: Convergence of an algorithm for mean curvature motion, Indiana Univ. Math. J. 42, 533-557 (1993). 10. L.C. Evans and J. Spruck: Motion of level sets by mean curvature I, J. Diff. Geom. 33, 636-681 (1991).
93
Figure 2. Level lines at several time steps.
11. L.C. Evans and J. Spruck: Motion of level sets by mean curvature II, Trans. Am. Math. Soc. 330, 321-332 (1992). 12. L.C. Evans and J. Spruck: Motion of level sets by mean curvature III, J. Geom. Anal. 2, 121-150 (1992). 13. L.C. Evans and J. Spruck: Motion of level sets by mean curvature IV, J. Geom. Anal. 5, 77-114 (1995). 14. M. Fried: Niveauflachen zur Berechnung zweidimensionaler Dendrite, Dissertation, Mathematische Fakultat Freiburg (1999). 15. B. Merriman, J.K. Bence and S. Osher: Motion of multiple junctions: A level set approach, J. Comput. Phys. 112, 343-363 (1994). 16. S. Osher and J.A. Sethian: Fronts propagating with curvature dependent speed: Algorithms based on Hamilton-Jacobi formulations, J. Comp. Phys. 79, 12-49 (1988). 17. J.A. Sethian: Level set methods, Cambridge Monographs on Applied and Computational Mathematics 3, Cambridge University Press (1996). 18. H.M. Soner: Motion of a set by the curvature of its boundary, J. Differ. Equations 101, 313-372 (1993). 19. N.J. Walkington: Algorithms for computing motion by mean curvature, SIAM J. Numer. Anal. 33, 2215-2238 (1996).
95 OPTIMAL DISCRETIZATION S T E P S IN S E M I - L A G R A N G I A N A P P R O X I M A T I O N OF F I R S T - O R D E R PDES
MAURIZIO FALCONE Universita di Roma "La Sapienza", P. Aldo Moro 2, 00185 Roma - Italy e-mail: falconeQcaspur.it
Dipartimento di Matematica,
ROBERTO FERRETTI Dipartimento di Matematica, Universita di Roma "Tor Vergata", Via della Ricerca Scientifica, 00133 Roma - Italy e-mail: ferretti9mat.uniroma2.it TIZIANA MANFRONI Dipartimento di Matematica, Universita di Roma Tre, I.go S. Leonardo Murialdo 1, 00146 Roma - Italy e-mail: manfroniOmat. uniroma3. i t We deal with a class of semi-lagrangian high-order approximation schemes for advection and Hamilton-Jacobi equations focusing our attention on the fine tuning of the algorithm. Starting from some a-priori estimates in Lp we analyse how to choose At and Ax in order to efficiently obtain accurate results. We also analyse some qualitative properties of the algorithms which depend on the At vs. Ax relationship. We discuss several numerical tests from the point of view of accuracy and efficiency.
1
Introduction
The numerical solution of first order Hamilton-Jacobi equations is a crucial topic in many applications like front propagation, image processing, optimal control. This paper is devoted to the study of the HJ equation f jiv(x,t) + H{x,Vv{x,t)) \v(x,0)=vo(x)
=0
infix[0,T]
m [ )
(with fi an open subset of RN, H(x: •) convex) but we will also consider as a model problem the advection equation £v(x,t) = \v(x,t) v(x,0)=vo(x)
+ f(x) • Vu(i,t) + g(x)
in 0 x [0,T]
(A € R) [
^ '
since most of the theoretical results used in the paper have been obtained for this model.
96
A variety of numerical schemes has been proposed for (2) and adapted to more general problems. Some of them have been obtained (see e.g. Douglas and Russel x , Hasbani, Livne and Bercovier 5 , Morton, Priestley and Siili 9 and Pironneau u ) using characteristics, finite elements, finite volumes or a blend of them. The large majority of these methods are conceived to treat equations with a "small" (but nonzero) second order term. Other schemes, based e.g. on stream-line diffusion, finite differences and semi-lagrangian formulation (see e.g. Johnson and Szepessy 7 , Hughes and Mallet 6 , Osher and Shu 10 , Staniforth and Cote 12 ) seem more specifically directed to first order problems. Moreover, most of them have also been extended to more general nonlinear problems like (1) (although in many cases a precise convergence result is missing). We will focus our attention on the efficient implementation of a class of semi-lagrangian schemes which can be applied to both (1) and (2). As reported by the literature (see e.g. Staniforth and Cote 12 and references therein), these schemes are also widely used in massive numerical weather prediction and oceanographic simulations, due to their stability for large Courant numbers. Our idea is that a careful analysis of a model problem like (2) can also be useful and valuable when dealing with more complex issues. We will then start our analysis from the theoretical results obtained in Falcone and Ferretti 2 ' 3 and, in particular, from a-priori estimates (in L°°(Q), L2{0) or pointwise) for the rate of convergence. These estimates depend on the relationship between At and Ax, and the purpose of the present work is precisely to examine how this relationship affects the efficiency of the scheme, as well as other features (mainly, dispersivity). For a qualitative comparison with other algorithms, we refer to Tamamidis and Assanis 13 . The outline of the paper is the following. We will review in Section 2 the basic results of the convergence analysis for the advection equation, and show in Section 3 the explicit form (in R1) of the schemes used for the numerical tests. In Section 4 we will address the problem of optimizing the performance of the schemes with respect to the convergence rate. The last section contains some numerical tests in R1 and R2 with a detailed discussion of advantages and drawbacks of different choices of parameters. 2
Construction of the schemes and basic convergence theory
We will review for reader's convenience the general form of the schemes and some basic results about the order of convergence. We refer to Falcone and Ferretti 3 for an in-depth theoretical analysis of stability and convergence.
97
On the theoretical side, we just want to point out that the construction of semi-lagrangian schemes is based on the discretization of the representation formula for the solution of (2) coupled with some boundary conditions. When we adopt a stationary Dirichlet boundary condition b(x) on dClin (the subset of dQ where characteristics point inward), the formula is given by pt/\0(x)
eXag(y(s))ds + e^tAl>^v0(y(t)) Jo where a A b = min(a, 6), y(t) is defined by v(x,t)=
Ws)J-
(3)
W
{e^g(y(s)))
with initial conditions j/(0) = x, 7(0) = 0, and 0(x) := inf{t > 0 : y(t) € RN \
ft}
(5)
is the so-called "exit time" from fi for a given point x. 2.1
Construction of the scheme
Let i p b e a regular function such that 0 is the set of points {a; :
te:)-(E)+"CM)
(6)
In order to write the Runge-Kutta type scheme (6) in a more concise form we define $(x,Ai) = ( $ / ( z , At),$g(x, At)). Let us set a grid with nodes Xj, j G Q = { 1 , . . . ,q}, and let {I/)J(X)}J € Q be a family of bounded functions such that ipj(xj) = 1, i>j{xm) = 0 ( m ^ j ) , 11 ipj 1100 = 1- We will use those functions to construct a local (and finite dimensional) representation of our approximate solutions. Several choices are possible, for example finite elements or polynomial bases. Fix a positive time step At, for any grid node we define a "variable time step" rjj as rij := min{{<5 € R+ : f(xj + 5§f(xj,6))
= 0}, At}.
(7)
This practically means that when Xj + At$f(xj, At) is in ft, then TJJ = At. If this is not the case, the time step can be computed looking for the smallest solution of the equation F(8) = tp{xj + 6*f(xj,6))
=0
(8)
98 that is, the first time-step 6 bringing Xj + 5$f(xj,5) to the boundary. We can give now the general form of the schemes, + eXAt ZmeQ «m~>m(a:,- + At*f(xj:At)) + eXji'b(Xj + Tu^f(xj,Vj))
«" = &t$g(Xj,At) «" = Vj^g{xj,Vj) V°
if rjj = At if m < At
=V0(Xj).
0)
which can be rewritten in vector form as Vn = G + *Vn-1
(10)
where the elements of the matrix $ and of the vector G read ^ = yj
m
_(eXAtipm(xj+At$f(xj,At)) ~ \ 0
(At$g(Xj,At) I Vj*g(xj,Tl3) + eXvjKxj
if rh = At if % < Ai
+ »&*/(*,•,»&))
ifr1j = At if *?, < Ai
(U)
^
j
Since * is constant, (10) gives a very easy and efficient vectorization of the algorithm. Note also that due to (7) the second expression in (9) can be interpreted as a generalized boundary condition and that there is no need for a structured grid in the first expression. 2.2
Computational complexity
From (9) we see that each time step has a complexity of 0(q2), q being the number of nodes. On the other hand, q = 0(l/AxN)(N being the dimension of the physical space in (2)) when we adopt regular grids (in the sense used in finite element theory). As a consequence the global complexity of the algorithm described by (10) is 0{At~l Ax~2N). 2.3
Convergence
Let us quote the main convergence result from Falcone and Ferretti 3 which will be useful to understand the link between the choice of the discretization steps and the errors. In the statement of the theorem P A denotes an interpolation operator over the grid and M denotes the symmetric (mass) matrix M(tp) with entries m
ij =
4>i(x)ipj{x)dx Jn
(i,j - l,...,q).
(13)
99 Theorem 2.1 Consider the problem (2) with bounded data b, f, g 6 Cv(Vt). Assume that v0 e W1'00^), ||«(t) - PAU(*)||OO < E{Ax) for t € [0,i] /or a fixed i and that the one-step scheme (6) is of order p, that is: At) | < CAtp+1
\y(At) - x - At$f{x,
/ Jo
(14)
eXsg(y(s))ds-At$g(x,At)
(15)
Then, the following estimates hold true for some positive constant C:
*) tf EjeQ \$AX)\ ^ l> then f°r Hi*)
an
V
At
< A°-
~ y(t)\\oo < C (w
+ ~E(&x^J
.
ii) let |*|2 < 1 and /i2 be a positive constant such that |M(V')'|2 < ^2^xN any Ax. Then, for any At < Ao, Hit)
- v(t)h
< C ( A ^ + ~E(Ax^j
.
(16)
for
(17)
(note that the regularity of the solution v appears in the theorem through the interpolation error E(Ax)). The second result states that the estimates (16), (17) hold for a single node Xj with E(Ax) denoting the local interpolation error in a neighbourhood of Xj, provided the functions ipm have support in a ball of radius O(Ax) (this is the case for finite elements discretizations) and Ax = o(At). In fact, solutions of (2) preserve regularity along characteristics, and as a consequence it turns out that the effect of interpolation errors on singularities is restricted to a radius of 0(Atp+Ax/At) around the singularity. This result allow to improve the estimates (16) in the regions of smoothness of the solution (see Falcone and Ferretti 3 for a more precise statement). Moreover, as far as the total variation of the schemes is concerned, one can prove that a local reconstruction based on linear interpolation always gives a total variation diminishing scheme. In the following analysis we will always consider the errors in the L°° norm since we focus our attention on the pointwise convergence of the algorithm. Clearly, the uniform norm gives also a bound for the L2 norm but other direct L2 estimates have been found in Falcone and Ferretti 3 .
100
2.4
Diffusion and dispersion
Another interesting point is the analysis of numerical diffusion and dispersion of semi-lagrangian methods. To this end let us examine the simplest linear equation ut-ux
= 0, for (x,t) € Rx (0,T)
(18)
where a is a constant. We know that the exact solution is of course u{x,t) = u0(x + t).
(19)
Now let us assume that the solution is regular enough to justify our differentiations. The scheme corresponding to (2.12) gives us vj+1 = vn{xj + t)
(20)
where we have adopted the classical notation v^ = v(xj,nAt) and vn(xj +1) means the local reconstruction (by interpolation) based on the values v?. Plugging a regular solution of (18) in the scheme and using the estimate on the Lagrange (order r) interpolation error we get u{x3, (n + 1) At) - U{XJ + At, nAt) + 7 A x r + 1
dr+1u r+1
(21)
where 7 is a positive constant. By standard arguments, we can deduce that the numerical solution corresponding to a local interpolation of order r approximately solves the (modified) equation Axr+1
dr+lu
fnn.
The dispersivity of the scheme might then be analysed by standard selfsimilarity arguments, showing that the resolution of discontinuities is of order OiAx/At1'^^). 2.5
The nonlinear case
Finally, we sketch the construction of a semi-lagrangian scheme for the Hamilton-Jacobi equation (1), as shown in Falcone and Ferretti 2 , Falcone and Giorgi 4 . The solution may be represented as
"If
<»(•) [Jo
H*(y(s),a(s))ds
+ v0(y(t))\
(23)
101
where H*{x,a) by
is the Legendre transform of H(x,p) and y(t) is now denned
y(s) \
f
a(s)
\
with the same initial conditions y(0) = x, 7(0) = 0 (note that 9(x) depends on a). The one-step discretization of (24) is: (2/n+l \
=
( Vn \
A
J * , ( » „ , ft At) \
(
}
and the " variable time step" T)J is accordingly defined as a function of Xj, At and a = (a\,... ,ap). The general form of the scheme for the nonlinear equation (1) is now, ' v" - min{At$ 9 (x ; -,a,At)+ + E C V m f e + to*f(Xj,a, At))} r^Q v? = mm{rij$g(xj,a,T)j) + b(xj +r)j$f{xj,a,T)j))} ^P
if
V =
At
(26) if 7j,- < At
2. =U0(O;J).
We point out that a complete convergence analysis for this nonlinear case has only been carried out for PQ or Pi reconstructions, and that no local convergence result is known. Estimates (16), (17) should therefore be understood as consistency estimates. 3
Fully discrete second and third order schemes
We propose in this section an example of construction of schemes based on the coupling between Heun or Runge-Kutta formula and a P 1 ( P 2 or cubic interpolation formula. We point out that these may not be the usual choices among semi-lagrangian practitioners, but our aim here is to investigate the interaction between two discretizations with given consistency rates, regardless of how this consistency rate is achieved in practice. This choice yields schemes of either second or fourth order with respect to the time step, and of second, third or fourth order with respect to the space step. In order to avoid heavy notations for the base functions, we will restrict to the case of
n = (-i,i)c JJ1. Following Heun's formula, we set: $f(x,At)
= ±f(x) + ±f(x + Atf(x))
(27)
102
*g{x, Ai) = ^g(x) + ^g(x + Atf(x))eXAt.
(28)
In the case of the Runge-Kutta scheme we have: K0 = f(x) , Ki = f(x+At^)
$f(x,At)
, K2 = f(x+At^-)
= -(K0 + 2K1+2K2
, K3 = f(x+AtK2)
+ K3)
,
(29)
* f l (*,At) = I ( s ( a ; ) + 2 c A A ' / 2 5 ( s + A t ^ ) + 2eXAt'2g(x +e A A t 5 (x + Aitf 2 )).
+ At^)
+
,„. ^30j
The domain H may be defined by the inequality x2 - 1 < 0 so that r]j is the minimum between Ai and the smallest positive solution of (XJ + t
(31)
We also define Zj-^Xj+rijQfixjrfi).
(32)
For shortness of notation, we rewrite the interpolation of the discrete solution as: Y, C V r a f e + l j ' f / l l i . r i i ) ) m£Q
= Yl meQ
fyrnVZT1-
(33)
Using a particular interpolation formula will require to plug a particular definition of the coefficients Vjm into (9). We will adopt here the simplest choice of equally spaced grid points, so that the step between the nodes is Ax = 2/{q — 1) and Xj = (j — l)Aa; — 1. In this case, it is convenient to define a normalized displacement to obtain always the interpolation from a standard interval (say, [0,1)). In order to treat P x finite elements interpolation, we define kj :—
ti--=Zi-{k£B-1)
^
+D = 9-^(*i + l)-*i
(34)
(35)
(where [•] denotes the integer part), the point Zj lies in the subinterval [xk+i,Xk-+2) a n d £j € [0,1) represents the normalized displacement with
103
respect to the point x^+icients:
Then, the interpolation is defined by the coeffi-
1}j,kj+i = 1 - £,j , 4>j,kj+2 = Zj , ipj,m = 0 (m^kj + 1, kj + 2).
(36)
with £j, kj defined by (35) and (34), Zj by (32), i\j by (31) and $ by either (27)-(28) or (29)-(30) depending on the time discretization. To interpolate with Pi finite elements, q must be an odd number and the functions ipj should be quadratic on each subinterval between two subsequent odd nodes. In this case, we define 4
* == ^
+ 1
-
(
^
+ 1)A
* =^
(here, Zj € [x2kj +1,^2^+3) and ^ G [-1,1)). defined by Vj,2kj + 1 =
2
(37)
-(*; + !) + 1) - 2k3 - 1
(38)
Then, the interpolation is
' W * J + 2 - 1 - ? j > Vj,2kj+3 -
2
'
^
and V'j.m = 0 for rn ^ 2fcj 4-1, • • •, 2kj + 3, where kj, £j defined by (37) and (38), Zj, rjj and $ as before. Lastly, to apply a cubic reconstruction, we can define kj, £j by (34), (35). For 1 < kj < q — 3 (that is, if the upstream point Zj is not in an extreme cell of the grid) we obtain:
^
=
_ t e -i) t e -2)fe-3) _ ^
_6({,-^-»)_
(40)
* * « - -&«.-'>«>-" , fe« - *'fe - ' » « ' - 2 ) , (41) and ipj,m — 0 for m ^ fcj,..., kj + 3. An i.n obvious modification al allows to define the reconstruction also for Zj belonging to the first or last cell of the grid. 4
Relationship between time and space step
Although the stability of the schemes described in the previous sections is not affected by the size of the time step, a careful choice of At is crucial for their performances. In fact, the estimates (16), (17) show an interplay between At and Aa; which has to be properly taken into account. We will examine this problem, assuming that the space discretization is piecewise polynomial (of
104
degree r), and that the support of each base function is contained in a ball of radius O(Ax). This will allow us to compare the global and the local error. Moreover, we will assume that the solution v has a finite global regularity (v € WS'°°(U)) but is piecewise C°°. First, we can give the following bound for the interpolation error : E(Ax) < CAxmin^s'r+l'>
(42)
Plugging (42) respectively into (16) (global estimate) and into the corresponding local estimate, if the solution is C°° in a small neighbourhood centered at Xj we get, | V ? - v{x„nAt)\
< C Ut"
+ ?—£
j
/ Axr+1 \ |i£ - v(Xj, nAt) | < C (At* + ~ ^ r j .
(43)
(44)
(we recall that in the latter case, we should assume that Aa; = o(At)). Our aim is now to express At as a function of Arc in the form At = Axa and maximize the convergence rate for either (43) or (44) with respect to the parameter a. 4-1
Minimization of the global error
Using the relationship between the two steps, we obtain \v] - v(xj,nAt)\
< C (Axap
+ Axmin<s'r+1)-a)
(45)
so that the convergence rate is min(ap,min(s,r + 1) - a). Its maximum is attained for a =
min(
*'r + p+1
1)
(46) V
;
and it takes the value ap =
pmin(s,r+l) — .
(47)
Note that the convergence rate depends crucially on the (global) regularity, and increasing the order of interpolation does not improve the rate (47). It should also be noted that the optimal exponent a causes time and space discretizations to affect the error by a similar order of magnitude. In smooth regions, the convergence rate may not improve since the time discretization error is not related to local regularity in linear problems.
105
4-2
Minimization of the error in smooth regions
Operating as before, with s — oo, we obtain the optimal exponent r+1 p+ 1
a=-±±
(48)
and accordingly the (local) convergence rate is P ^ (49) p+1 (we explicitly note that this amounts to a maximization of the consistency rate). However, if r > p, the condition Ax = o(Ai) is not satisfied, and therefore the error may not depend only on the local regularity. However, it should be pointed out that this condition ensures that the numerical domain of dependence shrinks to a point as Ax, At —> 0. In fact, this might be a restrictive requirement. The dispersivity analysis carried out in section 2 shows that the resolution of discontinuities (and also the region of significant numerical dependence) is of the order of A x 1 _ a / ( r + 1 ) . Hence, taking into account that characteristics are computed with an error of A x a p , it turns out that the resolution of the scheme is maximized with the choice a
a
P
=
(50)
= PT^TTTT
and its maximum order (with respect to Ax) is v(r + 1) p p(r 4-1) + 1 p + ^^A^i^^Tr+l
On the other hand, applying (48) we get a resolution of order a p
i-TTi-TTi
(51) (52)
which differs significantly from (51) only when p is small and r large. In this situation the value of a which optimizes the consistency rate may not be as satisfactory from the viewpoint of numerical dispersivity. Note however that both choices (48) and (50) ensure that the resolution tends to zero as Ax vanishes. 4-3
Computational efficiency
It is worth checking that the choices (46), (48) give the best convergence rate not only with respect to the discretization step, but also with respect to the
106
number of operations (that is, to computing time). Recalling subsection 2.2, and denoting by v the number of operations, we have v = 0 {ArlAx-N) = 0
(A*-^"))
.
(53)
Writing Ax as a function of v and using it into (45), we obtain \v? - v(xj,nAt)\
< Cv
7T+z
.
(54)
An easy computation shows that the absolute value of the exponent in (54) is maximized by (46) (or (48) if s = oo). It can be easily checked that this conclusion is also true if v = 0(At~1Ax~N) is replaced by v = 0(At~1Ax~l3N) for any positive ft, i. e. it does not depend on the sparseness of the matrix * . 5
Numerical tests
We now compare the theoretical analysis of Section 4 with some numerical results for tests in -R1 and R2. For each problem, we will consider numerical schemes with a second-order (Heun) or fourth-order (Runge-Kutta) time discretization, coupled with a Pi, P^ or cubic space discretization, as shown in Section 3. For each scheme, we will consider two relationships between Ax and At, which (according to the theoretical analysis) should optimize either the L°° or the local error. Moreover, the case a — 1 (constant Courant number) will be included in any case for a comparison, since it turns out to be the usual choice in the literature. For each scheme and each relationship Ax/At, the errors are computed at fixed t. In the error tables, "local" stands for the error obtained on a suitable set in which the solution is C°°, and the order of convergence is computed as log(Ax 1 /Ax 2 )
[0
°>
with Axi, Ax2 chosen as the two extreme steps. The numerical convergence rate is compared with the theoretical rate (in brackets). The rate of convergence with respect to l/v is also computed (along with its theoretical value in brackets) in order to compare the cost-effectiveness of the various choices. 5.1
Linear advection problem in R
Tests 1-3 are related to the following problem: vt(x,t) = xvx(x,t) v(x,0) = vo(x)=sin^
. l0Dj
107
posed on [—1,1]. Its exact solution is r -1 v(x,t) = I voi^x) I +1
if i < -e~* if - e ~ * <x<e~t if x > e _ t
(57)
this function is globally W2'00 but piecewise C°°. For each scheme and each relationship Ax/At, the errors are computed at t = 1. The "local" error is computed on the interval [-0.3,0.3]. For Runge-Kutta/P2 discretization, Test 1 treat respectively the case a = 2/5 which is intended to optimize the L°° convergence rate, and a — 3/5 which should optimize the local convergence rate. The case a — 1 is also included for comparison. The rate behaves, at least qualitatively, as expected, but note that the actual convergence rates are always underestimated by the theoretical analysis (see Remark 2.2). Test 2 is related to Heun/P2 discretization. For this case, the theoretically optimal relationship is a = 2/3 for L°° rate and a — 1 for local rate; the latter does not ensure (see section 4) that the numerical domain of dependence shrinks as Aa: —J- 0. In practice, error is distributed in the first case (as expected), and localized in the second case, with rates close to the theoretical values. Test 3 refers to Heun/cubic discretization. In this case, the relationship maximizing the local rate is a — 4/3, meaning that the Courant number would tend to zero as Ax —• 0, a very unusual situation. Convergence rates computed for this test are also close to the theoretical forecast. Somewhat surprisingly (but in agreement with theory) the best local rate is achieved by the choice a = 4/3 which forces a very large number of time steps. Looking at the cost-efficiency, tests 1-3 show that the best result is given, as expected, in test 1 with the time discretization of higher order. Among second-order time discretizations, the value of a which maximizes the consistency rate has also good performances in terms of L°° error. 5.2
The rotating cone problem in R2
Tests 4-5 are related to the so-called 'rotating cone problem', a typical benchmark test in R2 for the approximation of advection equations (see Staniforth and Cote 12 , Tamamidis and Assanis 1 3 ).. The advecting vectorfield is f{x) = f(xi,x2) = ( x 2 , - z i ) in 0 = (-0.5,0.5) x (-0.5,0.5). The initial condition is: v(x,0) = ( 1 10
J £
T^
for
\x-x0\
( 58 )
108
(with r = 0.13) so that the solution is globally Lipschitz continuous and C°° outside the curve | i - x0\ = r. The errors have been computed at t = 2ir, i.e. after one turn around the origin. Moreover, "local" stands here for the error obtained on the ball |x — x0\ < r / 2 and the convergence rate is again given by (55). In this set of tests we expect that the asymptotic analysis developed in Section 4 applies less precisely, due to the larger discretization steps. In fact, Test 4 seem to give somewhat uncertain conclusions: both local and global convergence rates are close one another in all cases. In test 5 the behaviour is, at least qualitatively, closer to the theoretical forecasts. Note that the best performances are given by the relationship At = Ax, even for L°° error (which converges despite of the theoretical estimate). 5.3
First order Hamilton-Jacobi equation in Ft and R2
Tests 6-8 refer to the HJ equation: vt(x,t) + (1 - x)vx(x,t) v(x,Q)=v0(x) = l-x2.
+ l/2\vx(x,t)\2
= 0
, . ™>
{
The problem is considered again in [—1,1]. The solution of this test problem generates a singularity in the first derivative for t > In V2. Moreover, due to the term (1 — x)vx, characteristics are curved lines and this makes time discretization important. The exact solution of (59) can be computed by optimal control arguments and after the onset of the singularity it reads ( 0 v{t,x) = \ (I ~ 2e-'- x)2 Y ^ l(l-z)2I3^
if x < 1 - 2 " ' if l - 2 e - ' < a: < 1 - e"' ifl-e-«
(60)
The solution (see Figure 1) shows a discontinuity in the first derivative at x = 1 — 1/e and in the second derivative at x — 1 — 2/e. The local error is computed in the interval [0.4,0.5]. Before examining the results of Tests 6-14, it should be recalled that no "local" version of Theorem 1 is available for this case (and in fact, regularity is not preserved along characteristics in Hamilton-Jacobi equations, as this example shows). However, since H(-) is smooth and strictly convex (see Lions 8 ), the exact solution is semiconcave for any t > 0, and is uniformly semiconcave for any t > 0 if VQ is also semiconcave. The semiconcavity of v, along with the assumptions on H, heuristically shows that the minimization in (26) would be performed on a semiconcave function, so that the "upwind" point
109
Xj + L a(s)ds in which the reconstruction is performed (which corresponds to the argmin in (26)) can only be a regular point for v, thus resulting in a better convergence rate. Although this analysis is made on the exact solution, we will check that it also applies to the approximate solution. In Table 6, L°° and local convergence rates are always close one another. Theoretical forecast agrees better with Table 7. In table 8 we show again a situation in which, in order to optimize the local convergence rate, we have a = 4/3 > 1 as for test 3; however, the efficiency of this choice is dramatically lower in this case. A similar situation appears in tables 9-11, which refer to the HJ equation in [-2, 2] x [-2, 2] C R2: vt + (l- xi)vXl + (1 - x2)vX2 + ||Vi;| 2 = 0 vo(x) = max(l - x\ - x\, 0).
(61,
(which is in some sense a 2-dimensional version of (59)). The approximate solution for a test case is shown in figure 2. In order to explain the poor performances of high-order schemes on these tests we first point out that no uniform semiconcavity holds in this case. In fact, upwind points may coincide with singularities of v with empty superdifferential, and this causes some propagation of reconstruction errors due to such singularities, which appear in VQ- A further source of error is the discontinuity of second derivatives for t > 0, which affects higher order reconstructions. On the other hand, if we change the initial condition vo to be v0(x) = mm(xl + a^ - 1,0),
(62)
(figure 3 shows an approximate solution) we obtain uniform semiconcavity of the solution and expect then a better approximation. This is confirmed by tables 12-14 which show a great improvement in the performances of the scheme, although the global regularity of the solution is the same (i.e., W1,oc) as in tests 9-11. Conclusions We have shown how the theoretical convergence analysis may be applied to optimize the performance of this quite general class of semi-lagrangian schemes. The theoretical results are based on a worst-case analysis and may not always give quantitatively precise results. In particular, the actual convergence rates are usually underestimated by the theoretical ones. We can summarize the following points which seem to be confirmed by our numerical experiments:
• optimizing the relationship At vs. Ax on the basis of L°° error usually gives time and space discretization errors of similar orders of magnitude; • optimizing the relationship At vs. Ax on the basis of local error greatly increases the accuracy in smooth regions (although it also causes a small increase in dispersivity); • the ratio Ax/At is directly related to the radius of the region of reduced accuracy around discontinuities. • the consistency analysis carried out for the simplest case of the linear advection equation seems to be applicable, although with some caution to more complicated, possibly nonlinear cases. In the case of HamiltonJacobi equation, a key role seems to be played by semiconcavity which allows to perform reconstruction always at regular points. Moreover, in the tests presented, the relationship optimizing the local error has usually good performances for L°° error as well. In cases where no information about the regularity of solution is available, this is likely to be the best choice for the scheme. On the other hand, in order to keep the ratio Ax/At low, a should not be too large. In this respect, schemes with space discretization of much higher order than time discretization might be critical to tune. References 1. J. Douglas Jr. and T. F. Russell, Numerical methods for convectiondominated diffusion problems based on combining the method of characteristics with finite element or finite difference procedures, SIAM J. Num. Anal. 19, 871 (1982). 2. M. Falcone and R. Ferretti, Discrete-time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations, Num. Math. 67, 315 (1994). 3. M. Falcone and R. Ferretti, Convergence analysis for a class of semilagrangian advection schemes, SIAM J. Num. Anal. 35, 909 (1998). 4. M. Falcone and T. Giorgi, An approximation scheme for evolutive Hamilton-Jacobi equations, in W.M. McEneaney, G. Yin and Q. Zhang (eds.), "Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming", Birkhauser, to appear. 5. Y. Hasbani, E. Livne and M. Bercovier, Finite elements and characteristics applied to advection-diffusion equations, Comput. & Fluids 11, 71 (1983).
111
6. T.J. Hughes and M. Mallet, A new finite element formulation for computational fluid dynamics: IV. A discontinuous-capturing operator for multidimensional advective-diffusive systems, Comp. Meth. Appl. Mech. 58, 305 (1986). 7. C. Johnson and A. Szepessy, On the convergence of a finite element method for a nonlinear hyperbolic conservation law, Math. Comp. 49, 427 (1987). 8. P. L. Lions, Generalized solutions of Hamilton-Jacobi equations (Pitman, London,1982) 9. K. W. Morton, A. Priestley And E. Siili, Stability of the LagrangeGalerkin method with non-exact integration, RAIRO Model. Math. Anal. Numer. 22, 625 (1988). 10. S. Osher and C.W. Shu, High-order Essentially Non-Oscillatory schemes for Hamilton-J acobi equation, SIAM J. Num. Anal. 28, 907 (1991). 11. 0 . Pironneau, On the transport-diffusion algorithm and its applications to the Navier-Stokes equations, Num. Math. 38, 309 (1982). 12. A. Staniforth and J. Cote, Semi-Lagrangian integration schemes for atmospheric models - a review, Monthly Weather Review 119, 2206 (1991). 13. P. Tamamidis and D. N. Assanis, Evaluation of various high-order accuracy schemes with and without flux limiters, Int. J. for Numerical Methods in Fluids 16, 931 (1993).
112
Table 1. L°° and local errors for Test 1.
step Ax 0.04 0.02 0.01 0.005 0.0025 rate Ax rate \jv
At = L°° 1.47-10-3 3.3 • 10~ 4 1.25 - 1 0 - 4 2.8- 10~ b 6.19- 1 0 - " 1.97 (1.6) 1.4 (1.14)
Runge—Kutta/?2 scheme At = A x 3 / 5 Ax2'5 local L°° local 5.48 • 1 0 - 4 5.88 • 1 0 - 4 4.36 • 1 0 - 4 8.92 • 10~ b 4.54- 10~ 4 5.83- 1 0 - 5 4 b 1.59 • 10~ b 1.95 • 1 0 8.88 • 10~ 2.45-10-b 1.44 • 10-*> 3.12- 1 0 " 5 7.86 • 10~ b 4 . 5 3 - 1 0 - ' 4.58- 1 0 - ' 2.56 (2.4) 1.53 (1.4) 2.47 (1.6) 1.6 (1.5) .96 (.88) 1.76 (1.14)
At = L°° 4.47- 10~ 3 1.86-lO" 3 7.18- 10~ 4 2.78 • 10~ 4 1.1- 10~ 4 1.34 (1.0) .67 (.5)
Ax local 1.01 - l O " 3 2.23- 1 0 - 4 5.17- 1 0 " b 1.23- 1 0 - 6 2.99 • 1 0 - b 2.1 (2.0) 1.05 (1.0)
Table 2. L°° and local errors for Test 2.
step Ax 0.04 0.02 0.01 0.005 0.0025 rate Ax rate \ju
Heun/P2 scheme At = Ax2'3 At = local L°° L°° 1.6 - l O - 3 1.6-10-3 4.48 • 10~ 3 1.86- l O " 3 5.04- l O " 4 5.04-10-4 7.18- 10~ 4 1.88 - l O - 4 1.88 • l O - 4 2.78- 1 0 - 4 7.85-10-b 7.85 • 1 0 - b 1.01 • 1 0 - 4 3.16- 1 0 - 5 3.16 - l O " 3 1.36 (1.0) 1.42 (1.33) 1.42 (1.33) .68 (.5) .85 (.8) .85 (.8)
Ax local 1.15- 1 0 - 3 2.59 • 1 0 - 4 6.07 • 1 0 - b 1.45-lO-5 3.55 • H r b 2.08 (2.0) 1.04 (1.0)
Table 3. L°° and local errors for Test 3.
step Ax 0.04 0.02 0.01 0.005 0.0025 rate Ax rate \ju
Heun/cubic scheme At = A x 4 / 3 At = A x 2 ' 3 L°° local local L°° 1.09- 1 0 - 3 2.66- 1 0 - 3 1.45 • 1 0 - 3 1.28 - l O - 3 4.54 • 10~ 4 4.54 • 10~ 4 9.54 • 10~ 4 4.14 - 1 0 - b 1.87 - 1 0 - 4 3.4-lO-4 3.36 • 10~ b 1.87- 1 0 " 4 7.91 • 1 0 - b 1.21 • 10~ 4 3 . 4 3 - l O " ' 7.91 • l O - 3 3.16 - 1 0 - b 3.16- 10~ b 4.24- 10~ 5 4.56 • 10~ 8 1.34 (1.33) 1.28 (1.33) 1.49 (.66) 3.74 (2.66) .77 (.8) .63 (.28) 1.6 (1.14) .81 (.8)
At = L°° 2.18- l O " 3 7.29-10-4 2.44 • 1 0 - 4 8.75 • 1 0 - b 3.17- lO" 5 1.53 (1.0) .77 (.5)
Ax local 1.0- 10~ 3 4.82- 1 0 - b 1.04-lO-5 2.47- 10~ b 6.0- lO""' 2.68 (2.0) 1.34 (1.0)
113
Table 4. L°° and local errors for Test 4.
step Ax 0.04 0.02 0.01 rate Ax rate l/v
Runge—Kutta/P2 scheme At = A x 3 ' 5 At = Ax At = A x 1 ' 5 local L°° local L°° local L°° 0.239 0.239 0.546 0.546 0.0685 0.174 0.270 0.338 0.0274 0.176 0.0217 0.132 0.0313 0.194 0.00688 j 0.0815 0.00413 0.0539 2.06 (2.0) 0.75 (0.0) 2.56 (2.4) 0.78 (.4) 2.03 (.8) 0.84 (.8) 0.68 (.66) .25 (0.0) .98 (.92) .29 (.15) 0.91 (.36) .38 (.36)
Table 5. L°° and local errors for Test 5.
step Ax 0.04 0.02 0.01 rate Ax rate l/i/
Heun/P2 scheme At = Ax At = A x 1 / 3 local L°° L°° local 0.545 0.281 0.545 0.363 0.0974 0.269 0.338 0.285 0.0312 0.193 0.189 0.0543 .75 (0.0) 1.19 (.66) 2.06 (2.0) .47 (.66) .2 (.28) .25 (0.0) .5 (.28) .69 (.66)
Table 6. £°° and local errors for Test 6.
step Ax 0.04 0.02 0.01 0.005 0.0025 rate Ax rate l/v
H e u n / P i scheme At - A x 1 / 3 At = Ax2'3 L°° local £°° local 5.18- 10~ 3 3.73 • 10~ 3 5.21 • 10~ 3 3.86 • 1 0 " 3 3.32 • 10~ 3 2.07- 10~ 3 2.32- 1 0 - 3 1.96- 1 0 - 3 2.27- 10~ 3 1.5- 1 0 - 3 1.03- 1 0 - 3 9.0- 1 0 - 4 3 4 4 1.36- 10~ 8.9-104.43 • 1 0 3.91-10"4 7.63 • 10~ 4 4.88 • 10~ 4 1.95 • 10~ 4 1.63-10- 4 .69 (.66) .73 (.66) 1.18 (.33) 1.14 (1.33) .52 (.5) .55 (.5) .71 (.2) .69 (.8)
At = L°° 1.73-10-* 1.01 -lO"* 5.75 • 1 0 - 3 3.26 • 10~ 3 1.82-lO-3 .81 (0.0) .41 (0.0)
Ax local 1.04 - 1 0 - 2 6.23 • 10~ 3 3.55 • 1 0 - 3 1.98 - 1 0 - 3 1.1 • 10~ 3 .81 (1.0) .41 (.5)
114
Table 7. L°° and local errors for Test 7.
step A i 0.04 0.02 0.01 0.005 0.0025 rate Ax rate l/v
Heun/P2 scheme At - A i 1 / 3 At = local L°° L°° 3.68 • 10~ 3 2.48 • 10~ 3 3.77- 1 0 " 3 6.8-10-4 1.77- l O " 3 2.8- 1 0 - 3 3 J 2.86 • l O " 4 1.32- 10~ 2.42 • 1 0 1.2-lO" 4 8.49- 1 0 " 4 1.3 • 1 0 " 3 4 4 2.95- 10~ 4 4.44- 1 0 7.38 • 10~ .92 (0.0) .62 (.66) .58 (.66) .47 (.5) .44 (.5) .46 (0.0)
Ai local 1.59- 1 0 " 3 5.43- 10~ 4 1.41 • l O - 4 2.15- 10~ b 6.72- 1 0 - ' 2.8 (2.0) 1.4 (1.0)
Table 8. L°° and local errors for Test 8.
step Ax 0.04 0.02 0.01 0.005 0.0025 rate Ax rate \jv
Heun/cubic scheme At = A i 1 ' 3 At = A x 4 / 3 local local L°° L°° 5.08- l O " 3 5.71 • l O - 3 2.37 - l O - 3 3.69- 1 0 " 3 1.63 • 10~ 3 2.8 • 10~ 3 1.8 - 1 0 - J 3.0- H T 3 3 3 J 2.07- l O - 4 3.36- l O " 1.33- 10~ 2.12- 1 0 2.81 • 1 0 - 4 2.15- 10~ 3 8.0-lO"4 1.3 - l O - 3 4 -4 4 1.81 - l O " 4 7.77-lO" 5.99 • l O 9.39 • 10~ 1.2 (2.66) .72 (-.33) .5 (.66) .49 (.66) .51 (1.14) .31 (-.14) .38 (.5) .37 (.5)
At = Ax
i°°
1.28- l O " 3 6.18- l O " 4 4.52 • l O " 4 1.58- 1 0 " 4 7.96 • l O - " 1.0 (0.0) .5 (0.0)
local 8.36- 1 0 - 4 3.73-lO"4 1.94-lO'4 1.07 • 10~ 4 5.53-10-6 .98 (2.0) .49 (1.0)
Table 9. L°° and local errors for Test 9. H e u n / P i scheme Ax1''6 local L°° 4.69- 10"* • 4.4- 10~* At =
step Ax 0.16 0.08 0.04 rate Ax rate l/v
2.25- l O - * .53 (.66) .4 (.5)
1.38- 1 0 " 2 .83 (.66) .63 (.5)
At = Ax 2 ' 3 local L°° 3.56 • 10~* 1.86 • l O " 2 8.23- 1 0 - 3 1.06 (.33) .64 (.2)
3.34- 10-* 1.61 • 1 0 - J 8.09- 1 0 " 3 1.02 (1.33) .61 (.8)
At = Ax
L°° 4.32 • 10-* 2.17- l O - * 1.22- 10"* .91 (0.0) .46 (0.0)
local 3.39 • 10-* 1.98 • l O - * 1.17-10-* .77 (1.0) .39 (.5)
115 Table 10. L°° and local errors for Test 10. H e u n / i ^ scheme At = At = A x 1 ' 3 L°° local L°° 1.68-lO" 2 2.29 • 1 0 - 2 1.86-lO" 2 1.01 - l O " 2 J -2 7.98 • 1 0 - J 7.63 • 1 0 1.58-10 .52 (0.0) .64 (.66) .27 (.66) .26 (0.0) .48 (.5) .2 (.5)
step Ax 0.16 0.08 0.04 rate Ax rate 1/v
Ax local 1.47- 10~ 2 4.91 • 1 0 - 3 2.73 • 1 0 - 1 1.21 (2.0) .61 (1.0)
Table 11. L°° and local errors for Test 11.
step Ax 0.16 0.08 0.04 rate A x rate \/v
H e u n / c u b i c scheme At = A x 4 / 3 At = A x 1 / 3 local L°° local L°° 3.22 • 10~ 2 2.46 • 10-* 3.28 • 10~ 2 2.19 • 1 0 " 2 1.12-10-* 1.79- l O " 2 7.43 • 10~ 3 8.28 • 10~ 3 3 . 9 9 - l O " 3 1.25- 10-* 1.23 (2.66) .99 (-.33) .86 (.66) .68 (.66) .53 (1.14) .42 (-.14) .65 (.5) .52 (.5)
At = L°° 2.78- 10-* 1.03 • 10-* 2.78- 1 0 - J 1.66 (0.0) .83 (0.0)
Ax local 1.8 - 1 0 - 2 7.1 • 10~ 3 1.82 • 1 0 - J 1.65 (2.0) .83 (1.0)
Table 12. L°° and local errors for Test 12.
step A x 0.16 0.08 0.04 rate Ax rate 1/u
H e u n / F i scheme At = A x 2 / 3 L°° local 6.27 • 10-' 2 4 . 7 4 - 1 0 - 2 3.09 • 1 0 - 2 1.98 • 10~ 2 1.66- 1 0 - 2 7.8 • 10~ 3 7.8 • 1 0 " 3 .91 (.66) 1.5 (.33) 1.3 (1.33) .69 (.5) .91 (.2) .78 (.8)
At = A x 1 / 3 L°° local 6.88 • l O - 2 5.87- 10~ 2 2.07 - l O " 2 .87 (.66) .66 (.5)
At = Ax L°° local 7.47 • 1 0 - 2 7.47-10-2 3.35- 1 0 - 2 3.35 • 10~ 2 1.65 • 1 0 " 2 1.65 • 1 0 - 2 1.09 (0.0) 1.09 (1.0) .55 (0.0) .55 (.5)
Table 13. L°° and local errors for Test 13.
step Ax 0.16 0.08 0.04 rate Ax rate 1/u
Heun/P2 scheme At = A x 1 / 3 At = L°° local L°° 6.37 - l O - 2 5.01 - 1 0 - 2 5.28 • 10~ 2 3.14-10-2 1.73 - 1 0 " 2 1.37-10- 2 2.75 • l O " 3 .94 (.66) .94 (.66) 2.13 (0.0) .71 (.5) .71 (.5) 1.07 (0.0)
Ax local 2.04- 10~ 2 1.68 • 10~ 3 6.4- l O - 4 2.49 (2.0) 1.25 (1.0)
116 Table 14. L°° and local errors for Test 14.
step Ax 0.16 0.08 0.04 rate Ax rate \/v
H e u n / c u b i c scheme At = A x 4 / 3 At = A x 1 / 3 local local L°° L°° 1.22 • 1 0 " 2 3.69- 10~ 2 4.61 • 1 0 " 2 6.04- 1 0 - 2 6.41 • 1 0 " 4 1.89- 1 0 " 2 3.66 • 1 0 - 4 9.34 • 10~ 3 1.39- 10~ 2 2.01 • 1 0 - 2 2.53 (2.66) 1.15 (-.33) .7 (.66) .79 (.66) 1.08 (1.14) .49 (-.14) .53 (.5) .6 (.5)
At = Ax
L°°
5.32 • 10~ 2 2.6- 10" 2 2.47- 1 0 " 3 2.22 (0.0) 1.11 (0.0)
local 1.06 • 10~ 2 1.76-lO" 3 6.08 • 1 0 - 4 2.06 (2.0) 1.03 (1.0)
Figure 1. Initial condition, exact and approximate solution (Ax = At = 0.04) for test 7
117
0.16 0.14 0.12 0.1 0.08 0.06 0.04 0.02 0 -0.02
*i "0.5
1.5
r-1.5
<e
Figure 2. Approximate solution ( A i = At = 0.08) for test 11
Figure 3. Approximate solution (Ax = At = 0.08) for test 14
119
C O N V E R G E N C E PAST SINGULARITIES TO T H E FORCED M E A N CURVATURE FLOW FOR A MODIFIED REACTION-DIFFUSION A P P R O A C H F. FIERRO Dipartimento
di Matematica,Universita di Milano, E-mail: [email protected]
20133 Milano,
Italy
The approximation of forced mean curvature flow via a singularly perturbed double obstacle problem is studied. This approach differs from the usual Allen-Cahn approximation because it is insensitive to the choice of the potential. We continue the investigation started in Fierro et al. 6 by analyzing evolutions past singularities. We prove that the zero level sets of the solution to the double obstacle problem converge to the generalized motion by mean curvature with forcing term, provided no fattening occurs. Moreover an order one interface error estimate is proved, if the underlying viscosity solution satisfies an additional non-degeneracy property. The proofs are based on the construction of barriers for the double obstacle problem and on a comparison lemma.
1
Introduction
In this note we continue the investigation started in Fierro et al. 6 of a singularly perturbed double obstacle problem, which is used to approximate forced mean curvature flow. The classical forced mean curvature flow is the motion of an interface £(£) according to the evolution law V(x,t)=K(x,t)+g(x,t).
(1)
Here V{x, t) denotes the velocity of any point x of E(£) in the inner normal direction n(x, t), K(X, t) is the sum of the principal curvatures of S(t) at x, and g(x, t) is a given forcing term. Consider ue solution of the singularly perturbed reaction-diffusion equation sdtu£ - eAue + ^ * ' ( u e ) = y p
in fi x (0, T)
(2)
with $(s) = (s 2 - 1 ) 2 and Co = J_1 y/^(s)ds, as well as appropriate initial and boundary conditions. It is known that the zero level set of uE converges for e i 0 to an interface S(i) which moves according to the law (1). This result has been rigorously established in Evans et al. 4 in case that £(£) does not develop interior, or in other words provided no fattening occurs. An analogous result has been proved in Nochetto et al. 7 ' 8 ' 9 , Paolini et al. 10 , where the regular
120
quartic potential $ in (2) is substituted with the double obstacle one 1-s2
f(-oo,l] -V(s):=l-s
ifs€[-l,l] if s £ [-1,1], if* = - l if . € ( - 1 , 1 )
(3a)
(3b)
[[-l,oo) if« = i The advantage of potential (3) is that the resulting solution ue attains values in ( — 1,1) only into a transition region Te(t) of width 0{e) and the values + 1 or —1 elsewhere. This property allows to solve numerically equation (2) only in the transition region Te, and thus to save computational efforts. Furthermore, in Nochetto et al. 7 ' 8 , optimal interface error estimates of order 0(e2) have been proved for the smooth regime. An (9(e) estimate can be found in Nochetto et al. 9 which is valid even beyond the onset of singularities, provided the limit interface does not develop interior. In this paper we consider a different singularly perturbed double obstacle problem, where the right hand side of (2) is modified following the phase-field equation proposed by Benes 1. The equation reads now edtue - eAu £ + — *'(u s ) 3 e\Vu£\g in fi x (0,T) (4) 2e with "J denned as in (3). Initial and boundary conditions coupled to (4) will be specified later on. The independence of equation (4) from the energy potential $ underlines the convenience of using (4) instead of (2). In Fierro et al. 6 optimal interface error estimates of order 0(s2) are proved before the onset of singularities. The goal of this paper is to prove convergence of the zero-level set £ s (t) of the solution us for the double obstacle problem (4) to the generalized motion E(t), interpreted in the viscosity sense. Moreover an 0{e) interface error estimate, which is valid even beyond the onset of singularities, is proved provided a non-degeneracy property is satisfied by the viscosity solution. The outline of this paper is the following. In §2 we show how to obtain an explicit representation of an approximate traveling wave. In §3 we recall the generalized notion of mean curvature flow by means of the level set approach, as well as the key properties of the distance function d(x, t) from the generalized evolution E(£). Further we introduce the notion of viscosity supersolutions to the double obstacle problem. In §4 we rigorously construct supersolutions to (4), and note that a similar procedure can be used for subsolutions. A comparison lemma is stated and proved in §5. Finally, in §6,
121
we prove the convergence of He(t) to E(i) together with the interface error estimate. 2
Approximate Traveling Wave
We call q G C 1 ' 1 (R) £-approximate traveling wave moving in the direction n with velocity V > 0, if v(x,t) :=q(y)
with
y = - ( - x • n + Vt),
verifies \v\ < 1 and I(v) = edtv - sAv - -v - e\Wv\g = 0{e) for x G E(i) and j, = 0(1). Easy computations give dtv = ~q'(y)V,
Vv = —q'{y)n,
Av = ^q"(y)n
•n =
\q"(y)
and thus X(v) = Vq'(y) - -£q"{y) - \{y)
- \q'(y)\g.
More precisely we characterize our e-approximate traveling wave q as a function in C 1 ' 1 ^ ) satisfying \q(y)\ - 1 for y G R\(-y,j/) and, for all y G (~y,y), q'{y) > 0 and
(^-3)g'(i/)-V(y)--*(!/)= o. e
e
Such a g exists provided V = 5, ?/ = f and
-1 if y < - f 9(j/) = 7(2/) ~ < sin y if y € [ - f , f ] l+l ifl/>f. 3
Viscosity Solutions
Let fi be a bounded Lipschitz domain, T > 0 and Q = Q x (0,T). Assume We recall the generalized notion of mean curvature flow by means of the level set approach, see Chen et al. 2 , Evans et al. 5 . Given an initial surface £ 0 , the
122
evolving front emanating from S 0 is denned by the unique viscosity solution of the following degenerate parabolic PDE
w(-,0)=w°(-)
inM"
provided {w° < 0} = Interior (So) and independently from the special form of u°. Denoted by cfo(-) the signed distance function from S 0 , one can think of UJ° = do- The generalized evolution S(£) is denned to be the zero level set of w. If d(x, t) is the signed distance function from S(i), we have, see Evans et al. 4 , that d satisfies the property dtd-Ad-g(x-d(x,t)Vd(x,t),t)>0
in {d > 0}
(5)
3
in the viscosity sense, see Crandall . In other words, whenever tp £ C°°(Q) is such that d — ip attains a minimum in (xo,to) € Q where d(xo,to) = ip(xo,to) > 0, then dt
-g{xQ
-
> 0.
Moreover d(-) is lower semicontinuous in {d > 0}, upper semicontinuous in {d < 0}, continuous from below in time, and Lipschitz continuous in space. We study the approximation of S(i) via the singularly perturbed double obstacle problem (4) subject to the initial and boundary condition ue(x,0) = sgn(do(x)) for x £ fi and ue = 1 on dfl x (0,T). This problem has a viscosity interpretation. Definition 3.1 We say that uf is a viscosity supersolution of equation (4) if and only if uf > —1, and if uf —
^-e|V(^|3>0
at(x0,t0).
The definition of viscosity subsolution is the same as Definition 3.1 but with reversed inequalities and being (x0,£o) a maximum point. A function ue is called a viscosity solution of (4) if it is both subsolution and supersolution. 4
Supersolutions
In this section we construct supersolutions, to the double obstacle problem (4). To reach this aim we intend to use (5). An equivalent procedure can be used for subsolutions.
123
We define u+(x,£) := j(y(x,t))
for any (x,£) € Q with
d(x,t) TT ,, y(x,t):=-^---(r(t) and a(t) := Ae2G(T-*>, G := | | V 5 | U » ( 0 ) + 1. In the following we will demonstrate, first formally and then rigorously, that uf is a supersolution. Lemma 4.1 For A > 0 sufficiently large uf is a viscosity supersolution to the equation l{uE) = edtue - eAue
uE - e\Vu£\g - 0.
Proof: (formal) By definition u+ > - 1 . We show that l(u+) > 0 in {u+ < 1}. Let (x, t) € Q with u+(x, £) < 1, and suppose that the distance function d is smooth and (5) is fulfilled classically. Easy calculations yield edtut
= j'(y(x,t))dtd(x,t)
Vu+ = 7 ' ( y ( x , t ) ) ^ ^ ,
eAut =
-ej'(y(x,t))a'{t), e|Vu+| = 7 ' ( l / ( x , i ) ) ,
p"(y(x,t))+y'(y(x,t))Ad(x,t),
and thus I(u+) =
7
'(y)dtd - £ 7 '(3/)er ' - V ( j / ) - 7 '(»)Ad - - 7 ( y ) - 7 '(|/)ff e
£
= - | ( V ( 2 / ) + 7(2/)) + 7 '(y)($d - Ad - g) - £ 7 '{y)a '
at (x, i).
Because of — 1 < uf(x,t) < 1 we have y(x, t) < | . We consider two cases. Case 1: liy{x,t) < - f thenj(y(x,t)) = - 1 , ~f'(y(x,t)) = j"(y(x,t)) =0 and I ( u + ) ( x , t ) = 7 > 0. Case 5: If - f < y(x,t) < f, then we have - § < ^f^ - f - a(t) < f, whence 0 < d(x,t) < e(a(t) + n). Therefore we estimate \g(x, t) - g(x - d(x,«)Vd(x, i), t)| < | | V 3 | U ~ W ) d ( x , t) <e(ff(*)+7r)||V ff || i oo ( Q ) <eG(ff(t)+7r). Using that 7" + 7 = 0 in (-f, §), cr '(*) = -2GAe 2 G ( T -') = -2G
124
as 7 € C 1 ' 1 (R) and thus 7" is a bounded function, we can calculate Z(u+)(x, t) = --£{i'{y)
+ 7(2/)) + 7 '(2/)(s(x - d(x, t)Vd(x, t ) , * ) - 5(x, *))
+ 7 '(2/) (&d(x, t) - Ad(x, t) - 5 ( x - d(x, t)Vd(x, *),*)) -^'(*)7'(») >-eG7'(y)W*)+T)-e7'(l/)^'(t) = £7 ' ( I / ) ( - G « T ( * ) -
at (x 0 , t 0 )
(8)
holds. First of all we observe that it is always possible to assume the minimum of uf — ip at (x 0 ,to) to be strict, or in other words U(x,t) := {uf -
for (x,t) ^ (x 0 ,t 0 ).
(9)
In fact, for 0 < a
> U{x,t) > 0
for (x,t) # (x 0 ,io)-
If (8) is satisfied by >a, then edt
at (xo, to)-
Taking a j . 0 we get that (8) is true also for >. In view of the definition of u+, condition u+(xo, to) — y>(xo, to) < 1 entails 2/o := Jv(xo,t0) < -
that is
d{x0,t0)
< e{a{t0)
+ir).
As before we can distinguish two possible cases, namely y0 < — § and — f < Vo< f-
125
Case 1: Let us consider first yo < — | . From the definition oiy(x,t) and the regularity properties of the distance function d, we know that there exists a > 0 such that, for all (x, t) with |x - x 0 | < a and 0 < to — t < a, we have y{x,t) < —-|, whence u+(x,t) = —1. The fact that uf is constant for all those (x, t), and U attains a minimum at (xo,io) imply V
-Aif > 0,
54
at (x 0 , t0).
Therefore, since <£>(xo,£o) = u^(xo,io) = - 1 we get edtip - eAip
at (x 0 , t0),
and (8) is verified. Case 2: Let now yo > - § , that is d(x0,t0) > ecr(to) > 0. Because of the lower semicontinuity of d in {d > 0}, for 0 > 0 sufficiently small there is a neighborhood of (xo,io) where y(x,t) > — | — /3 and thus d(x, t) > e(cr(t) — /3) > 0; in addition we can assume yo < ^ — P- We would like to use the fact that d satisfies (5). To do so, we construct a smooth function S(x, t), that plays the same role for
(10)
« W = 7 a W +c « > « > 0 for all a; £ l , r a (a;) ->a4.o 7(x) uniformly for x in compact sets of E.
(11) (12)
Note that r
Consider the function Ua(x,t)
:=Ta(y(x,t))
-
Using (9),(11),(12), and the fact that d is lower semicontinuous in {d > 0}, we derive the existence of a point (xa,ta), where Ua attains a local minimum, say va, such that limaio(x-a,ta) = (xo,£o) and -|-i8
(13)
for sufficiently small a. The rightmost inequality in (13) is a consequence of lim^o ya = yo < f - /?• Since T" 1 exists, we can now uniquely define S £ C°°(Q) by means of the following relations
where
z(x, t) = - ^ - ^ - | - *(*). (14)
126
Moreover Ta(y(x,t))
-tp{x,t)
= Ua(x,t) >va = Ta(z(x,t))
-
and equality holds at (xa,ta). We thus deduce with the help of (11) that (x Q ,t Q ) is also a minimum for d - 5 and 0 < d(xa,ta) = S(xa,ta). Consequently, (5) leads to dtS(xa,ta)
- A5(xa,ta)
- g(xa - 5{xa,ta)V8{xa,ta),ta)
> 0.
(15)
Since ip,6 € C°°, we can calculate from (14) edt
eA^ = r ^ A 5 + -r'^|V<5| 2 . Property a '(*) = -2G
^ - e|Vy>|5
= T'adtd - e l > ' - T'aA5 - - I ^ V * ! 2 - - r a + -ua - r'JV<% £
£ 2
= T'a{dtS - A5) + 2GeT'aa - -T^\V5\ £
£
- -Ta + -ua - T'a\V5\g. £
£
(16) We now intend to show, upon suitably selecting A > 0, that the rightmost hand side of (16) is almost nonnegative at ( x a , i a ) . Since (xa,ta) is a minimum for d-S we have | V J ( x a , t a ) | = 1 (see Evans et al. 4 , p.1104), and thus (16) at (xa,ta) reads !{
+ 2 G e I > - ± ( ^ +Ta-
va)
8VS, •)) + T'a (g(- - 5VS, •) - g)
+ 2 G e I > - - ( r £ + r a ) + -i/a. £
£
By virtue of (15) and T'a(ya) > 0, we readily get T
'a(y<x) (dtS(xa,ta)
- AS(x
8{xa,ta)V5(xa,ta),ta))
> 0 . (17)
In light of (13), we distinguish two more possible situations, namely — % —
P < Va < - f + 0 and - f + /3 < ya < § - /3.
127
We first consider - f + / 3 < y a < f - / 3 . Recalling that 7" + 7 = 0 in ( - f, §) we can write C ( l f a ) + r a ( y a ) = 7a(Z/a) + 7a (y Q ) + 0.Va =
/
( 7 "(s) + 7(5)) x C a (y a - *)ds + 0(a) = 0(a).
(1§)
TT/2
From the assumption — j+/3
lifal = | and thus 0 < 5(xa,ta)
"
have
7T
,
2~°(a'\
7T
2'
< e(a(ta) + it). Therefore we can write
\g(xa - 6(xa,ta)VS(xa,ta),ta)
-g(xa,ta)\
<
\\Vg\\L^iQ)5(xa,ta)
<£||V5lU»(Q)(o-(i«)+7r) <eG(a(ta)+w), whence g(xa -d(xa,ta)V5(xa,ta),ta)
- g(xa,ta)
> -eG(a(ta)
+ ir).
(20)
Using (17), (18) and (20), for A > 0 sufficiently large, we get l(
> -0(a) S
+
-va+2eGT'a(ya)a(ta)-eGr'a(ya)(cT(ta)+n) E
= i o ( a ) + \va + eGT'a(ya)(a(ta) > eGT'a(ya)(A >
-IT)
- TT) + ±(„ a + O(a))
-(ua-Ca).
(21) Finally let - f - / ? < ya < - § + /?. Since Ta € C 1,:l (K) we can write again the above integral representation of the second term in (18), but now computed in ( - f - 2/3, — § + 2/3). We easily see that such an integral is of order 0(/3). Choosing A = 0(1) appropriately, we again conclude (21) but with C0 instead of Ca. Since
128
5
Comparison Lemma
Lemma 5.1 Let uf be a lower semicontinuous viscosity supersolution and u~ be an upper semicontinuous viscosity subsolution. If uf > u~ at t = 0 and on dfl x (0,T), then uf > u~ for all (x,t) £ Q. Proof: We split the proof into several steps. Step 1: Let g := e~xtg and A := eA — ^, where A > 0 will be chosen later. If uf is a viscosity supersolution of (4) we infer that u£ := e~xtuf dtu£ - eAut + Xut - e\Vuf\g
satisfies
> 0 on {u£ < e~xt}
in the viscosity sense, i.e. if (p is such that u£ —
> 0 in (x 0 ,i 0 )-
An analogous result, but with reversed inequalities can be proved for the viscosity subsolution of equation (4). We prove it in the case of supersolutions. Suppose ifi is such that ut —
-
-${x,t)
> ut(x0,t0)
- ip(x0,t0) = 0
and therefore u+(x,t)-v?(x,t)>0. Moreover as ut(xo,t0) — ip(xo,t0) < e~xt° it follows that u+(xo,*o) = A
(22)
at (x 0 , t0)
because uf is a viscosity supersolution of (4). Therefore as ext > 0 we have dt
>0
at (x 0 ,to),
129
Step 2: Since no confusion is possible we set uf = ue^ and g — g. We argue by contradiction. Suppose uf < u~ somewhere and set v :=
sup (u~ — uf) > 0. (x,t)eQ
Since u~ - uf is upper semicontinuous and Q is bounded, such a sup is attained in Q, say at ( x i , t i ) . Moreover from uj —uf < 0 in dfl x (0,T) and in fi x {0} we know that Xi G fi and t\ > 0. We use a standard argument in the theory of viscosity solution in Crandall et al. 3 , i.e. we double the variables and at the same time we penalize the doubling. Consider the upper semicontinuous function f/(x,y,i,s) := u-(x,t)
-uf(y,s)
for a 10. Since U(x, x, t,t) = u~(x,t) 2>va:=
sup
- - ( | x - y | 2 + \t - s\2) a
— uf(x,t)
we see that
U(x,y,t,s)
> v > 0.
(x,y,i,s)€Q 2 2
Since Q is bounded we conclude that there exists a point (x a , y a , ta, sa) G Q at which the sup is attained, namely U(xa,ya,ta,sa) = va. Using Lemma 4.1 in Crandall et al. 3 we can write -{\xa-y«\2 + \ta-sa\2)->0 fora|0 (23) vaiv=(u--uf){xi,ti)
for a 4.0.
(24)
Moreover from (23) we have ^a? y a
GO, u-(xa,ta)
ta,sa>0
xt
> -e- %
uf(ya,sa)
(25) Xs
< e- ".
(26)
Step 3: Set U+(x,t) := uf(ya,sa) + - ( | x - y a | 2 + |* - sa\2) + va and observe that U{x,ya,t,sa) = u~(x,t) - U+(x,t) + i/a, and u~ - U+ attains a maximum at (xa,ta). Therefore as u~ is a viscosity subsolution of (4) from Step 1, (25), (26) we infer that edtU+ - sAxU+ + XU+ - e|V x f/ + | 5 < 0 in ( x a , t a ) , which can be written in other terms as 2e 2ns 1 — {ta - sa) + A(u+(y a ,s a ) + - ( | x a - y Q | 2 + \ta a
Q
2
<e|-(xa
-ya)\g{x.a,ta).
sa\2)+va) (27)
130
Step 4'- Set (|x„ - y | 2 + \ta - s\2)
U~(y,s) ~u~(xa,ta)
-va
and note that U(xa,y,ta,s) =U~(y,s)-uf(y,s) + va. The function u+-U~ attains a minimum at (ya,sa) and therefore as uf is a viscosity supersolution of (4) from Step 1, (25), (26) we have edsU~ -eAyU-
+ XU~ -s\VyU~\g
>0
in
{ya,sa),
and equivalently 2e 2ne 1 — (ta -sa) + + X(u~(xa,ta) (|xQ - y a | 2 + \ta - sa\2)va) (28) 2 > e[-(x„ -ya)\g(ya,sa). a Step 5: Finally by subtracting (27) from (28) we get 4ne 2 + A(u7(x a ,t Q ) -u+{ya,sa) (|xQ - y a | 2 + \ta - sa\2) a a (29) 2e -2va) > — |x a -ya\{g(ya,sa) -g(xa,ta)), a and thus + \(U{xa,ya,ta,sa)
(|x a - y a | 2 + \ta -
sa\2)
a -2va)
a + — |x a -ya\{g(xa,ta) -g{ya,sa)) > 0. a In view of (23) and (24) we can choose a so small that (|x a - y a | 2 + |*a - sa\2) -2va
U(xa,ya,ta,sa)
(30)
<
a
--v. I
Moreover we note that
|x a -ya\\g{xa,ta)
-g(ya,sa)\
-»0 as a 40,
and thus we can assume that for a sufficiently small 2e , > 4ne — x Q - y Q \ [ g { x a , t a ) - g{ya,sa)) < . a a Therefore (30) reads 0 < ^ f - |(eA - \)v. Finally by selecting A > ^16ra _L + we get \{eX — \)v > ^~- and thus the contradiction 8ne 1. v 1. -{eX - -)v < 0. a 2 e This concludes the proof of the Comparison Lemma. n
0<
I 7?
131
6
Convergence and interfaces error estimates
Let u £ (x, t) be the solution of (4) provided the initial and boundary conditions u e (x,0) = sgn(d 0 (x)) for all x e ft, ue(x,t) = 1 o n 3 f i x (0,T). In the same way as in Nochetto et al. 9 we can prove the convergence of the zero level sets S e (i) = {x € ft : ue(x,t) = 0} to the generalized motion E(i) emanating from SoLet lE := (Ae 2 G r + n)e = (cr(0) + ir)e and S^ g := {x 6 ft : cfo(x) = T* E }. We denote by S f (£) = {x e ft : w(x,£) = =Fie} the generalized evolving fronts emanating from Ejf e . We consider u^ the supersolution and subsolution defined in §4 in terms of the signed distance functions df from £*(£). Since u+ is lower semicontinuous, u~ is upper semicontinuous and it is easy to check that u~ < ue < uf on the parabolic boundary of Q, we can conclude by the comparison Lemma that u~{x,t)
V(x,«) €Q.
This result allows us to prove the following theorem. Theorem 6.1 Let I{t) = {x € ft : u(x,t) < 0}, 0(t) := {x 6 ft : w(x,t) > 0}, and x £ I(t) (or resp. x € O(t)^. TTien /or £ sufficiently small ue(x,t) — - 1 (resp. ue(x,t) = 1,), Theorem 6.1 states the convergence of £ e (t) to E(£) as £ 4- 0 m c a s e S(t) has empty interior. To derive interface error estimates we have to assume more regularity for £(£). We define H*(t), the regular part ofL{t), as the set of all x € S(i) such that cj(-,t) is of class C 1 in a neighborhood of x, and the non-degeneracy condition |Vw(x, t)\ > 0 is satisfied. Then the following theorem holds Theorem 6.2 For x € £(£)*, there exists £o(x,t) > 0 such that dist (x, £ e (i)) < 2/ e |Vw(x, i)!" 1
Ve < g 0 (x, i)
We refer to Nochetto et al. 9 for the proofs of Theorems 6.1 and 6.2. References 1. M. Benes, On a computational comparison of phase-field and sharpinterface model of micro structure growth in solidification, Acta Techn. CSAV 41 (1996) 597-608 2. Y.G. Chen, Y. Giga, and S. Goto, Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations, J. Differential Geom. 33 (1991) 749-786
132
3. M.G. Crandall, H. Ishii, and P.-L. Lions, User's guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc. (N.S.) 27 (1992) 1-67 4. L.C. Evans, H.-M. Soner, and P.E. Souganidis Phase transitions and generalized motion by mean curvature, Comm. Pure Appl. Math. 45 (1992) 1097-1123 5. L.C. Evans and J. Spruck Motion of level sets by mean curvature, I J. Differential Geom. 33 (1991) 635-681 6. F. Fierro and R. Goglione Error estimates and numerical simulations for mean curvature flow through a modified reaction-diffusion equation, Num. Funct. Anal, and Opt. 19 (5-6) (1998) 513-528. 7. R.H. Nochetto, M. Paolini, and C. Verdi Sharp error analysis for curvature dependent evolving fronts, Math. Models Methods Appl. Sci. 3 (1993) 711-723 8. R.H. Nochetto, M. Paolini, and C. Verdi Optimal interface error estimates for the mean curvature flow, Ann. Scuola Norm. Sup. Pisa CI. Sci. (4) 21 (1994) 193-212 9. R.H. Nochetto and C. Verdi Convergence of double obstacle problems to the generalized geometric motion of fronts, SIAM J. Math. Anal. 26 (1995) 1514-1526 10. M. Paolini and C. Verdi Asymptotic and numerical analyses of the mean curvature flow with a space-dependent relaxation parameter, Asymptotic Anal. 5 (1992) 553-574
133
THE VISCOSITY-DUALITY SOLUTIONS A P P R O A C H TO GEOMETRIC OPTICS FOR THE HELMHOLTZ EQUATION LAURENT GOSSE Dipartimento di matematica pura e applicata - Universita degli studi di I'Aquila Via Vetoio, Localitd Coppito - 67100 L'Aquila, ITALY. E-mails:
[email protected], [email protected] FRANQOIS JAMES
MAPMO - UMR CNRS 6628 - Universite d'Orleans - BP 6759 45067 Orleans Cedex 2 - FRANCE. E-mail: [email protected] In these notes, we study an inhomogeneous system arising in various high frequency expansions of some classical partial differential equations. This system is studied in the modern framework of viscosity and duality solutions. We apply our results to the example of geometric optics approximations for the 2D Helmholtz equation and carry out some practical computational experiments.
The objective of these notes is to provide a comprehensive survey on the numerical analysis of a one-dimensional system made of an eikonal equation and a linear conservation law with discontinuous coefficients. As an illustrative example, we shall apply this theory to some practical investigations of high-frequency asymptotics for the two-dimensional Helmholtz equation. This approach of classical geometric optics in a modern framework has been developed in two papers GJ1>GJ2 where the detailed proofs of all the results stated here are to be found. The contents of this contribution correspond to several talks which have been given by the authors since 1999 in various places. Consequently, some comments written throughout this text are following either questions or discussions that occured during these events. We want now to introduce the main example we are about to treat using the theories of viscosity and duality solutions, BJ>CLl. We consider the wave equation in an heterogeneous medium inbedded in R2 whose variable refraction index is 77(21,0:2) > 0: dttu - — Au = 0
(1)
If one looks for planar wave solutions u{t,x\,x-i) = u(xi,x2) exp(ikt) to the wave equation (1), one is led to find a function u satisfying the scalar Helmholtz equation: Au + k2 rj1 u = 0,
(2)
134
And seeking solutions oscillating with a (high) frequency k, it's natural to use the following classical ansatz u(xi,X2) = A(xi,X2)exp(ik
2 < VA, Vip >R2 +AAip = 0.
(3)
We refer the reader to e.g. FEOI,FBO2,RK references therein for a n ( j ^e details on this derivation. The stationary transport equation for A leads to a conservation law for the energy A2 which expresses the fact that energy is preserved inside "ray tubes": V • {A2Vy) - 0.
(4)
One of the motivations for introducing such asymptotics is of numerical order: we replace the brute computation of highly oscillating functions by the study of a system of equations which takes their shape into account. This general idea has been recently exploited in a sophisticate computational approach, si,B2. The present work can therefore be seen as a precise identification of the solutions one gets out of it when refining infinitely the computational cells, even in the presence of singularities. At this level, we select a privileged direction of propagation in (3), say, X2 and we "time-step" it. This is but a par axial-type assumption which enforces the restriction dX2
Consequently, we can set a "time-like" variable t = X2 and a "space-like" one x = xi in order to define: H(t,x,p)=
- y/rp(t,x)
-p2
and a(t,x) — -£—(t,x). (5) OtV We plan to give precise mathematical results about exact solutions and numerical approximations of the following weakly coupled system: dt
(6) (7)
135
where the Hamiltonian H(t,x,p) and a(t,x) are given by (5). The ID setting is of course a severe restriction, which is imposed by the available results on the linear transport equation. However, the study of such a system in the multidimensional setting of PR seems hazardous because of its lack of numerical convergence results. In Section 2, we recall the basics of viscosity and duality solutions and we state an existence and uniqueness result for the Cauchy problem for the system (5)-(6)-(7): see Theorem 1. In Section 3, we present the main numerical tools developed in GJ1 for (7) in the simple context of essentially three-points schemes as summarized in Theorem 2. We apply this in conjunction with some other results for Hamilton-Jacobi equations to establish convergence of a class of numerical approximations: see Theorem 3. At last, in Section 4, we provide some illustrative computational results. 1
Weak solutions to the differential problem
1.1
Some features about viscosity and duality solutions
The resolution of the Cauchy problem for (6)-(7) requires two different theories: we selected viscosity solutions for the inhomogeneous eikonal problem" and duality ones for the linear conservation equation. We stress out that this choice, which corresponds to the one of B^FEOi,FE02,Sy ^ means practically that we are about to reproduce only the fastest wavetrain; superimposed signals will be discarded as a consequence of entropy conditions, see ER. For the reader's convenience, we recall here the basics of both, as well as some fundamental results which are to be used in the sequel. We begin with viscosity solutions, which were introduced under that name by Crandall and Lions in CL1, see also K. Definition 1 Let % £ C([0,T] x R x R). A function
e]0, T[xR, then: < 0;
• if (ip — x) has a local minimum point at (t0,xo) €]0,T[xR, then dtx(to,x0)+'H{t0,XQ,dxx(to,x0))
> 0.
"and this is certainly not the unique strategy; the most classical one being of course raytracing, see B 1 , whereas a kinetic alternative is proposed in BC,ER,G
136
If moreover,
sup \H(t,x,0)\
= M < +oo;
[0,T]xK
(m,) R,
There exists a constant C > 0 suc/i i/iat, /or aZ/ £ £ [0,T], x,y,p 6 |H(t, i , p ) - H(t, y,p)| < C (1 + |p|)
\X
- y\
Consider if0 £ Lip(R.)(~)BUC(M). Then there exists a unique viscosity solution if £ BUC([0,T} x R), which moreover belongs to Lip([0,T] x R). We turn next to the notion of duahty solutions, which were introduced by Bouchut and James in BJ to solve in the context of measures the linear conservation equation (7) when the discontinuous coefficient a is L°° bounded and satisfies the one-sided Lipschitz condition (OSLC) dxa
with
ael^QO,^).
(8)
Recall that duahty solutions are defined as weak solutions, the test functions being Lipschitz solutions to the backward linear transport equation dtp + a(t, x)dxp = 0,
p(T,.) = pT € Lip(R).
(9)
A formal computation shows that dt(pn) + dx[a(t, x)p(i] = 0, and thus — p(t,x).fi(t,dx) = 0, (10) at Ju which defines the duahty solutions for suitable p's. We first introduce the notion of reversible solutions to the backward problems (9). At last, the definitions and fundamental properties of duahty solutions are to be given. Following BJ, we introduce some functional spaces: SM = C([0,T],Moc(K)), SuP = Lip !oc ([0,r] x R). Clearly, SuP is the space of Lipschitz solutions to (9). The key problem here is that there is no uniqueness for solutions in this class (and not even for smoother solutions, say Ck in the x variable, k > 1), as is it evidenced by the example a(x) = — sgn(x).
137
Definition 2 (i) We call exceptional solution any function pe G SuP such that pe(T,.) — 0. We denote by £ the vector space of exceptional solutions. (ii) We call domain of support of exceptional solutions the open set Ve = {(i,x) G [0,T\ x H; 3 pe G £, pe(t,x)
? o}.
(Hi) Any p G Sup is called a reversible solution if p is locally constant in Ve- The vector space of reversible solutions to (9) will be denoted by 11. Roughly speaking, Ve is the region of [0,T] x R where the pathologies leading to the loss of uniqueness in (9) are likely to occur. For the proposed example a(x) = — sgn(x), the exceptional solutions are given by pe(t,x) = /i(max(0,T - t - \x\)) with h G Lip([0,T]), h(0) = 0, and we have Ve = {(t, x) G [0, T] x R; \x\
(ii) If the above function is constant and finite, then p is reversible. 2-. Characterization by monotonicity. p is reversible if and only if there exists p\, pi G iSup solutions of (9) such that dxp\ > 0, dxp2 > 0 and p — p\ — piThese characterizations will be useful for the study of numerical approximations since we shall focus on numerical schemes for which their discrete analogues are available. Definition 3 We say that /x G SM *S a duality solution to (7) if for any 0 < r < T, and any reversible solution p to (9) with compact support in x, the function 11—• / p(t,x)fj,(t,dx) Ju
is constant on [0, r ] .
138
We shall also need the following facts concerning duality solutions. Proposition 4 (Bouchut, James BJ) 1) Given (j,° € Al(oc(R), under the assumptions (8), there exists a unique fj. £ SM, duality solution to (7), such that p.(0,.) = fi°. 2) There exists a bounded Borel function a, a universal representative of a, such that 'a — a almost everywhere, and for any duality solution fi, dtfJ. + dx(afj,) = 0
in the distributional sense.
3) The duality solutions satisfy the entropy inequality dt\ii\ + dx^alnl) < 0
in the distributional sense.
4) Let (an) be a bounded sequence in L°°(]0, T[xR) ; such that an —*• a in L°°(]0, T[xR) - w*. Assume dxan < an(t), where (a„) is bounded in L ^ C T Q , dxa < a e LX{]Q,T\). Consider a sequence (fJ,n) G SM °f duality solutions to dtfin + dx{anfin)
= 0
in
]0,T[xR,
such that /i n (0,.) is bounded in At;0C(M), and /i n (0,.) —»• fi° 6 Mioc(R). Then fin —J- [/, in SM> where fj. € SM is the duality solution to dtiJ. + dx{an) = 0
in
]0,T[xR,
/i(0,.)=/x°.
Moreover, a„p„ —^ an weakly in Al; oc (]0,T[xR). The set of duahty solutions is clearly a vector space, but it has to be noted that a duahty solution is not a priori defined as a solution in the sense of distributions. The product 2/i is defined a posteriori, by the equation itself (see assertion 2 above). 1.2
An existence and uniqueness result
In this section, we study the Cauchy problem associated to (5)-(6)-(7) and any pair of initial data (p°, if0) € M{M) x W 1 ' 0 0 ^ ) , such that the following semiconcavity estimate holds for some 7 £ R + max(O,0M¥>°)<7<+c». 2
(H)
2
Theorem 1 Consider n 6 C D W '°°([0,T] x R), with 0 < r)0 < n and dtV > 0. Assume
(12)
Then there exists a unique couple of viscosity/duality solutions of the Cauchy problem (6)-(7) with
139 The proof consists essentially in three steps: - an existence and uniqueness result for the viscosity solution of the Hamilton-Jacobi equation; - a semiconcavity estimate of the type (11) holds true for any t > 0; - this semiconcavity implies the OSLC condition on a: this gives existence and uniqueness of the duality solution to the conservation equation. Moreover, this estimate garantees an order one convergence rate towards the viscosity solution in L ^ R ) , LT. We are about to give two lemmas corresponding to the first two points whose detailed proofs are to be found in GJ2 modulo simple changes. Lemma 1 Consider 0 < n G C2 n W2>°°{[0,T} x R), with dtn > 0, and let
(13)
where the approximate Hamiltonian TLe(t, x,p) is defined in the following way: we pick up a convex function ^fe which satisfies for s > 0: * e G C°°(R),
¥ e (0) = e/2,
* e ( x ) = |z| for \x\ > e.
2
Then we define He(t,x,p) = —^^fe(r] (t,x) — p2). The classical theory of parabolic equations ensures that there exists a unique solution to (13). Using Taylor expansions, we see that in the last requirement of Proposition 1, we have to choose C = ||T;||OO • ll^s^lloo/v^- Differentiating (13) with respect to x, we find that t n- s u p i e R ( {dxipe(t,x)) — n2{t,x)\ evolves according to a viscous balance law endowed with a sink term under the assumptions prescribed on rj in Lemma 1. This completes the proof. • The following lemma lies at the heart of the matter. Lemma 2 Consider 0 < rj 6 C 2 D W2'°°([0,T] x R) ; with dtr) > 0, and let
max(0, dxx
(14)
Sketch of proof. We mainly follow L T , Appendix A, the main difference coming from the dependance on the t, x variables. We consider another regularized equation 9t
140
respect to x, we find that t H* sup x e R ( max (0, dxx
consequence of Lemma 1. Next, dxa = —1 xx
A class of numerical approximations
Starting from here, we introduce a uniform grid defined by the two positive parameters Ax and At denoting respectively the mesh-size and the time-step. We shall denote Xj — jAx, tn = nAt for some (j, n) G Z x N. We define T" as the computational cell [(j + \)Ax, (j — | ) A x [ x [nAt, (n + 1)At[. As usual, the parameter A will refer to At/Ax, and we shall write for short A —> 0 when At, Ax -»• 0 with a fixed A.
2.1
Some numerical schemes for duality solutions
We consider for (7) the following class of essentially three-points conservative algorithms:
^+1 = « " - | £ (< A ? + ^7-4 >«* - < A " - | > ^ >«2) By analogy with the continuous problem, an important tool for the study of the numerical schemes (15) is the dual algorithm. Definition 4 For every direct scheme (15) operating on ( A 4 ? ) , - ^ - , uie define the dual scheme as the relation operating on the real-valued sequence
141
an
(P7)°€Z~N
d satisfying the formal equality:
vi
(16)
$>?*? = E M " - 1 ? " - 1 -
This equality is of course the discrete analogue of (10) which characterizes the duality solutions of (7). We then define the classical piecewise constant approximations: /x A (i, x) = fi] and pA{t, x) = p] for (i, x) € T?
(17)
A
It is assumed here that there holds At (0,.) —*• fi° as Ax —> 0 in the weak topology of measures. This is achieved for instance by defining fj.® as the local averages of ^° on [XJ_X,XJ+I[. The same way, we suppose that pA(T,.) —> pT in the strong topology of Ljoc(R). Now, we detail the structure of this dual scheme: by definition, we have
j€Z
E
, n-l„n-l *i
P
J
•
jez A summation by parts gives its explicit expression: PT1 = p? + A teJ>" +1 - P7) + q:\,M We rewrite the scheme (18) as p1}*1 = E L - i B^Pj-k
- PU))-
(is)
with:
BU = ^ , o Bh Bh
=l + M^4,i-^i.o) =-Aa»Al
(19)
Next, in order to study its total variation and monotonicity preservation, we denote A p » + i = p»+1 - p] and consider A p ^ = E l - i ^ ' A p ^ j together with another set of coefficients, namely: C"o
= l + A(a«+4il-a»+i0)
(20)
Coefficients B"^ and C"fe characterize various stability properties for the adjoint scheme (18). Some are given in the following lemma whose (easy) proof is but writing convexity inequalities.
142
Lemma 3 Assume that the components of An
k
introduced in (15) are uni-
1 ' 2
formly bounded, and that B
V(j,n)£Zx
(21)
lk > 0.
Then we have the following estimates on the dual scheme (18) for all n £ {0,l,...,iV-l}: sup |p?| < sup|pf I; J€Z
V J > O , ]T
(22)
j€Z
Ipr'-P^^^MHoo
\j\<J
"j-ll-
(23)
\j\<J
Assume moreover that V(j,n) G Z x N ,
B"fc>0,
C£fc>0.
(24)
T/ien £/ie duaZ scheme (18) satisfies the backward TVD estimate •p
i€Z
<
E^i
pfi
(25)
j€Z
and preserves monotonicity. Remark 1 All the properties in Lemma 3 are discrete anologues of those of reversible solutions. Schemes satisfying only (21) do not enjoy all the properties, in particular they lack the monotonicity preservation. This might be the case for instance for some Lax-Friedrichs type discretizations. Next, a notion of consistency for the scheme (15) is to be defined. Therefore, we introduce the following piecewise constant functions: aA(t,x) A
b {t,x)
= a?+i0 + a ? + i /
1 r (^*,o-«M,o) + («M,i-flM,i) Ax
> ioi{t,x)£T?
and state the precise definition: Definition 5 The scheme (15) is said to be weakly consistent with the continuous equation (7) if the components of A™ L are uniformly bounded and (i)
aA ^a
in L°°([0, T]xR)-w*
as A -> 0;
(ii) for each A, there exists ctA € i 1 (]0,T[), with ||aA||z,i(]o,T() < C uniformly in A, such that bA(t,.) < aA(t) for a.e. t e]0,T[.
143
These assumptions are the discrete analogues of those in the stability result for reversible solutions. From assertion (i) it follows that bA —• dxa in the sense of distributions while assumption (ii) allows to precise this convergence: provided a satisfies (8), we have actually bA —> dxa for the weak topology of measures. This leads to the weak consistency for the backward problem and therefore to the following result whose (long) proof is to be found in GJ1. Theorem 2 Assume that the schemes (15), (18) are weakly consistent in the sense of Definition 5 and satisfy the positivity requirements (24)- Then, as A - 4 0, - the sequence (pA) converges in the strong topology of L}oc(]0,T[x'SL) and almost everywhere towards the reversible solution of the problem (9); - the sequence (/i A ) converges in the weak topology of Ai(]0,T[xR) towards the duality solution of the problem (7); - the sequence (a.fi)A(t,x) — J2in < A? j^/i™ i >R2 l(tx)€Tn converges in the sense of distributions towards the product (a.fJ.) • 2.2
Lax-Friedrichs type schemes for the eikonal equation
In this section, we want to state some properties satisfied by the numerical approximations of ip generated by a slight variant of the classical Lax-Friedrichs scheme. Our numerical Hamiltonian is defined as follows: HL'(t,x,p-,p+)
1 = -\n(t,x,p-)+H(t,x,p+)
- -(p+ -p-)j,
(26)
with 0 < 9 < 1. The class of numerical schemes reads
and we introduce the piecewise constant function ipA defined by tpA(t,x) = ip" for (t, x) 6 T". Of course, we assume that the discretization of the initial data has been chosen properly such that
144
and the additional stability assumption: for all (j, n) £ Z x N, min
+n+i ^ ^ 7?(t" ,x) >
X€]ZJ-I,XJ + I[
„,_ max xe]xj-i,xj+i[
,,nn , {-, n(t ,x) 1
Lip(ri)At
(29)
where j3 is the smallest negative number such that „o Vi
- HLF(tn,
xj.x, vU^))•
(31)
Performing a classical analysis of the scheme (31) with the help of Harten's incremental coefficients ensures that, under both (28) and (29), there holds for y £]xj-i,Xj+i[ and n £ N: ,."+l|
v(tn+1,y)
The convergence follows Hamilton-Jacobi equations' theorems, s. • We want now to mimic at the numerical level the semiconcavity estimate shown in Lemma 2 for the continuous viscosity solution. This is the main reason why we restricted ourselves to simple schemes such as the Lax-Friedrichs ones as this property is still unproven for general monotone schemes even in an homogeneous context. Lemma 5 Assume that, in addition to (28) and (29), the following stronger CFL restriction holds: >.Liv{n)\<6
(max(0,
+ tp*(tn,xj-1)))
< KAx2 (33)
for a constant K £ M.+ depending only on rj and tp°.
145
Sketch of proof. We decide to work with the v" quantities. Inequality (33) becomes therefore a weak discrete OSLC property in the sense of Brenier and Osher BO. We refer the reader to GJ2 where it has been given a (tedious) generalization of the early proof by J. Smoller S m . • As at the continuous level, the difficulty was to handle the explicit dependance of H in x without assuming a strict convexity in both x and p variables. Under this unrealistic assumption, one would recover the classical t~l decay for homogeneous problems (see e.g. K'LT). To summarize, we just say now that under the reinforced CFL condition (32), we have proved: - the numerical solutions computed by the Lax-Priedrichs scheme converge to the viscosity solution; - moreover, they satisfy a discrete semiconcavity estimate, which implies an order one convergence rate in L 1 (R). 2.3
Upwind schemes for the linear conservation law
To shed a complete light on the behaviour of the numerical schemes (15) for the linear conservation equation (7), we still have to make precise the way we achieve the discretization of dxip. According to Lemma 5, it is clearly convenient to consider convex combinations of the adjacent quantities (<^?+1 — (f")/Ax. Therefore, we define: D
*U = E 4
%
^
with t% > 0, £
U =1
(34)
This general definition permits to recover for instance the particular value of Dy™ ! proposed in FE°2: I0 = 1, £±1 = 1/4, i0 = 1/2. But it does not
u
•7+2
allowv to recover the rough "Engquist-Osher type" upwind scheme tested in GJ1 . This is not a genuine drawback since this discretization would generate spurious spikes in the neighborood of the local minima of the phase
{ K + 1 - «?)/** ' W i -
together with the choice (34) for Dtpn t . This is obviously not the unique possibility. We want to prove now that the approximation of dt^p remains strictly positive. This is the purpose of the following lemma.
146
Lemma 6 Under the assumptions of Theorem 1, the hypotheses (29), (30), the stronger CFL condition (32), the components of A " ± are well-defined and bounded for all n £ N , j € Z, provided the following restriction holds: there exists K < 0 such that
vjez. H-(o,*„<^i,%^5)<„
(36)
Remark 3 Actually, conditions (30) and (36) are very easy to fulfill if we give a constant phase as an initial datum of the Lax-Friedrichs scheme for the eikonal equation. In this last case, we can choose K — (3 = — inf l€ R 7/(0, x) — — r/oSketch of proof. As before, we will show by induction that property (36) propagates computing H^ - H J _ 1 where H? d= -B.LF(tnXj,v?,vJ+1) using (30), we find that:
and
£ ^ = £ = H? > ( § H ^ + (1 - 60H?- 1 + § H ^ 1 )
> infj € Z
yj
A7
> \K\ > 0
And the components of the vector A™ A (35), (34) are well-defined and uniformly bounded by ||»7||oo/|«|- • Theorem 3 Under the assumptions of Theorem 1, the sequence of numerical approximations (
Sketch of proof. The proof is a direct consequence of Lemmas 4, 5, 6. First, it is straightforward to see that the CFL conditions (37) ensure both the semiconcavity requirement (32) and the nonnegativity of the coefficients BJ,Cy. Next, the convergence of (pA ensures the strong convergence of a A in L}oc (see Theorems 1.1 and 2.2 in CFN^ and, finally, using the inequality | — ^ < j ( a —c) +1c|(4r + 4 r ) , we find a constant upper bound for 6 A , namely C = A\(K + Halloo)- Theorem 2 completes the proof • So, despite the fact (6)-(7) constitute a (weakly) coupled system, each equation is to be treated with a different class of numerical schemes. Indeed, only the Lax-Friedrichs ones for (6) garantee that a discrete semiconcavity
147
estimate propagates as time increases. In contrast, these discretizations can reveal a wildly oscillating behaviour on (7) as it has been evidenced in GJ1 (see Figure 6); in this last case, upwind algorithms deliver far better approximations. 3
Numerical results
In this section, we display some practical computations: both of them have been completed on the same computational domain, namely the square t 6 [0,2], x £ [-1,1]. The parameters were Ax = 0.04, At = 0.02 and we selected the upper bound 0 = ^ in (26). We took IQ = 0, IQ = 1 in (34) with the data: Vz e R,
A concave lens
We simulate a concave lens by choosing the refraction index TJ this way:
n{x, t) = < 3 - cos (7r(t - I)/E) [ 1 in the other cases.
l
<
'
(38)
Since the viscosity solution is differentiable in the whole computational domain, we end up with a global smooth solution which is actually a correct approximation of the infinite frequency expansion of the Helmholtz solution (see Figure 1). The boundary conditions for the phase need a specific treatment. We followed the method indicated in FE°2. 3.2
A convex lens
We simulate a convex lens with the following choice of the refraction index:
v
'
y 1 in the other cases
In this case, we observe on Figure 2 the expected blow-up for the amplitude of the ansatz on the shock curve of the phase. The exact infinite frequency asymptotics for (2) actually settle with three phases beyond the focal point (x = 0,t= 1.5) (see ER and also FEOi,FE02y
148
4
Conclusion
We presented in this contribution both a theoretical study and some numerical computations on the eikonal/transport system one gets out of an infinite frequency expansion for the 2D Helmholtz equation. Since the eikonal equation (6) is nonlinear and can develop kinks in finite time, its solution is understood in a weak sense which induces concentrations in the linear conservation law (7). At this point, it could be more appropriate to consider "multivalued phases" for which a superposition principle would stand still but, so far, very Bl BC ER few analysis has been carried out on such models; see however ' , ,G. Acknowledgements Work partially supported by TMR project HCL #ERBFMRXCT960033. References [Bl] J.D. Benamou, Big ray tracing : multivalued travel time field computation using viscosity solutions of the eikonal equation, J. Comp. Physics, 128 (1996), 463-474. [B2] J.D. Benamou, Direct computation of multivalued phase space solutions for Hamilton-Jacobi equations, Comm. Pure Appl. Math. 52 (1999), 1443-1475 [BJ] F. Bouchut and F. James, One-dimensional transport equations with discontinuous coefficients, Nonlinear Analysis TMA, 32 (1998), 891-933. [BC] Y. Brenier and L. Corrias, A kinetic formulation for multibranch entropy solutions of scalar conservation laws, Ann. I.H.P. 15 (1998), 169190. [BO] Y. Brenier and S. Osher, The discrete one-sided Lipschitz condition for convex scalar conservation laws, SIAM J. Numer. Anal., 25 (1988), 8-23. [CFN] L. Corrias, M. Falcone, R. Natalini, Numerical schemes for conservation laws via Hamilton-Jacobi equations, Math. Comp. 64 (1995), n° 210, 555-580. [CL1] M. Crandall, P.L. Lions, Viscosity solutions of Hamilton-J acobi equations, Trans. Amer. Math. Soc. 282 (1984), 487-502. [CL2] M. Crandall, P.L. Lions, Two approximations of solutions of Hamilton-Jacobi equations, Math. Comp. 43 (1984), 1-19. [ER] B. Engquist and O. Runborg, Multi-phase computations in geometrical optics, J. Comp. Appl. Math., 74 (1996), 175-192.
149
[FEOl] E. Fatemi, B. Engquist and S. Osher, Numerical solution of the high frequency asymptotic expansion for the scalar wave equation, J. Comp. Physics, 120 (1995), 145-155. [FE02] E. Fatemi, B. Engquist and S. Osher, Finite difference methods for geometrical optics and related nonlinear PDEs approximating the high frequency Helmholtz equation, CAM Department report, UCLA, March 1995. [G] L. Gosse, Using K-branch entropy solutions for multivalued geometric optics computations, preprint (2001) [GJ1] L. Gosse and F. James, Numerical approximations of onedimensional linear conservation equations with discontinuous coefficients, Math. Comp., 69 (2000), 987-1015. [GJ2] L. Gosse and F. James, Convergence results for an inhomogeneous system arising in various high frequency approximations, to appear in Numer. Math. [K] S.N. Kruzkov, The Cauchy problem in the large for nonlinear equations and for certain quasilinear systems of the first order in several space variables, Soviet. Math. Dokl., 5 (1964), 493-497. [LT] C.-T. Lin and E. Tadmor, L1 -stability and error estimates for approximate Hamilton-Jacobi solutions, Preprint (1998) [PR] F. Poupaud and M. Rascle, Measure solutions to the linear multidimensional transport equation with non-smooth coefficients, Comm. Partial Diff. Eq. 22 (1997), 337-358. [RK] J. Rauch and M. Keel, Lectures on geometric optics. Hyperbolic equations and frequency interactions, (Park City,UT, 1995), 383-466, IAS/Park City Math. Ser., 5, Amer. Math. Soc, Providence, RI, (1999). [Sm] J. Smoller, Shock-waves and reaction-diffusion equations, Springer (1983). [S] P.E. Souganidis, Approximation schemes for viscosity solutions of Hamilton-Jacobi equations, J. Diff. Equ., 59 (1985), n° 1, 1-43. [Sy] W. Symes, A slowness matching finite difference method for traveltimes beyond transmission caustics, Proceedings of the Workshop on Computation of Multivalued Traveltimes, INRIA, Paris 16 - 18 September 1996 and Tech. Report, Rice University.
150
Figure 1. Numerical values for the phase and the amplitude for the concave lens (38)
151
2.5
2 1.5
1 0.5 0
Figure 2. Numerical values for the phase and the amplitude: the convex lens (39)
153
A D A P T I V E G R I D GENERATION FOR EVOLUTIVE HAMILTON-JACOBI-BELLMAN EQUATIONS LARS GRUNE Fachbereich Mathematik, J.W. Goethe-Universitat, Postfach 111932, 60054 Frankfurt, Germany, grueneemath.vmi-frankfurt.de We present an adaptive grid generation for a class of evolutive Hamilton-JacobiBellman equations. Using a two step (semi-Lagrangian) discretization of the underlying optimal control problem we define a—posteriori local error estimates for the discretization error in space. Based on these estimates we present an iterative procedure for the generation of adaptive grids and discuss implementational details for a suitable hierarchical d a t a structure.
1
Introduction
In the numerical approximation of partial differential equations one of the main sources of computational cost is the number of nodes used for the space discretization, which determines the dimension of the finite dimensional problem to be solved. Two basic strategies are used in order to minimize the number of nodes needed for an accurate computation: high-order interpolation techniques in space and adaptive gridding techniques (and, of course, combinations of both). In this paper we focus on the adaptive gridding technique for the following nonlinear first order Hamilton-Jacobi-Bellman equation —v(x, t) + \v(x, t) + sup {-f{x, u) • Vv(x, t) - g(x, «)} = 0 Cc
u6i7
(1)
v(x, 0) = v°(x) for (x,t) 6 fi x [0,T] where fi is an open and bounded subset of K n . This equation is related to a finite horizon optimal control problem (see l for an extensive discussion of this relation), and it is well known that in general one has to consider viscosity solutions of (1) as smooth solutions do not exist in general. The scheme we are going to use has its origins in the numerical approximation of the infinite horizon problem. Based on a discrete time approximation of the underlying optimal control problem 2 ' 3 a subsequent space discretization 4 ' 9 yields the fully discrete scheme. This scheme is easily adapted to the evolutive equation and for equidistant space discretization a convergence analysis was carried out in 7 . A particular subclass of (1) are the linear advection equations which are obtained if the functions / and g do not depend on u. In this case, the re-
154
suiting scheme is also known as "semi-Lagrangian approximation" which was introduced in 12 and has been extensively used in the simulation of models for weather forecast and oceanography, see e.g. the review 13 . Although this scheme has been applied for quite a while, a rigorous error analysis appeared only recently in 6 . In this reference high-order approximations are investigated, and it is remarked (see 6 , Example 5) that for nonsmooth solutions these high-order approximations in space in general only yield first order convergence rates. It is primarily this situation where we expect an adaptive approach based on a first-order approximation to be advantageous and the numerical tests in the last section confirm this expectation. This paper is organized as follows. First, we introduce the time and space discretization in Section 2, and prove a useful regularity result for the fully discrete approximation. After that, in Section 3 we turn to the definition of local error estimates and prove a number of properties of these values. The basic idea in this part stems from 9 where the analogous results are given for the stationary equation, which corresponds to the infinite horizon optimal control problem. In Section 4 we turn to the implementation of the scheme exploiting in particular properties of a suitable hierarchical data structure. Finally, we end this paper with two numerical examples in Section 5.
2
Discretization in time and space
In this section we describe the discretization for equation (1). Let us first state the assumption on the data of the problem. We assume that U C K m is compact, v° is Lipschitz with constant Lo and the functions / : Q x U —>• Mn and g : fl x U —• R are norm-bounded by constants Mj and Mg for all u £ U, continuous in both variables and Lipschitz in x with constants Lj and Lg uniformly in u £ U. Let
x(Q) = x,
where u £ U := {u : M —>• £/ | u measurable}. For simplicity of presentation we assume that fi is forward invariant under / , i.e.
155
the dynamic programming principle v(x,t + T) = mf I /
eXsg(
+ eXTv{ip(T,x,u)1t)\
(2)
The discretization of (1) now relies on a discretization of (2). For positive time steps ft > 0 we pick a family of finite sets of control values Uh, and a numerical one step scheme $/, (satisfying the usual consistency and stability conditions) as well as a numerical integration scheme //, such that for each uG.lt there exists u/, £ Uh, and for each w/, £ Uh there exists u £ U with \\
h{x,u) < Ch?+l
for some C > 0 which is independent of h. In the case where / and g do not depend on u this can be done e.g. by a Runge-Kutta scheme and an associated quadrature rule, cfr. 6 , for explicitly u-dependent data several schemes are presented e.g. in 5 , 8 or 10 (note that although 5 deals with the stationary equation the results are easily adapted to our setup here). Again, for simplicity, we assume forward invariance of Q with respect to the discretized dynamics, i.e. $/,(x,u) £ Q for all u £ Uh, all x £ ft and all /i>0.
Using these schemes we can replace (2) by the discrete time approximation Vh{x,U+i) = Th{vh)(x,U)
(3)
with ti = ih and i > 0, where for any function w : ft x /iNo -> M the operator Th is given by Th{w){x,t)
:= M
{h(x,u)
+ eXhw($h(x,u),t)}
(4)
We will also refer to (3) as the discrete evolutive Hamilton-Jacobi-Bellman equation. Standard arguments (see 5 or 6 ) imply the existence of a constant K > 0 such that sup \vh{x,U) - v(x,U)\ < Khp for all U £ [0,T]. Our main concern in this paper is the discretization of (3) in space. Instead of an equidistant high-order space discretization as considered e.g. in
156 6
here we are going to use a first order approximation along with a suitable locally refined grid. In the remainder of this section we introduce the class of approximations we are going to use and prove a useful regularity result for these approximations. Since for the problems under consideration the domain fi usually has a rather simple shape (or the problem can be transformed to some simply shaped Q), for the discretization in space we use a partition of Q into cubic elements. This structure has several implementational advantages (e.g. for a given point x the surrounding element is easily determined by integer computations, the gridding procedure works for arbitrary dimensions without extra effort, no linear equations have to be solved for the interpolation), and a certain built in regularity which is exploited in Lemma 2.2, below. Nevertheless, most of the following considerations also apply to triangular grids, see e.g. 9 where Lemma 2.2 is proved for triangular grids under suitable regularity conditions. Formally, the cubic elements are of the form Qj := {x = (x1,...
,xn)T
€Rn\x{
e[a),b)]
for all i=l,...,n}
(5)
for real values a' < &'• for all i — 1 , . . . , n. The nodes of an element are given by the set nodes(<5i) := {x £ ffi" | x* = a) or x{ = b) for all i = 1 , . . . , n) A grid T is a collection of P cubic elements Qj such that clf2 = (J.- =1 and mtQj D intQjt = 0 for all j ^ k. The nodes xi of T are given by nodes(r) :=
M
P
Qj
nodes(<3j),
j=i,...,i>
and N denotes the number of nodes. A node X[ is called regular if x\ 6 nodes(Q J ) for all j with zj G Qj, otherwise it is called hanging. We denote the set of regular nodes of T by reg(T). Figure 1 show a 2d grid in which the hanging nodes are marked. On a grid T we consider the space of multilinear functions W := {w £ C(clQ) | w(x + ae/c) is linear in a on each Qj for each k} where the eft, k — 1 , . . . , n denote the standard basis vectors of M.n. Note that the the assumption w G C(clfi) (i.e. w continuous) implies that w is uniquely determined by its values in the regular nodes reg(r), and the values in the hanging nodes have to be determined by linear interpolation. For some element Qj of T with nodes xi = (xj,..., z " ) T , ' = 1 , . . . , 2" and
157
e-e II
Figure 1. Hanging nodes in a 2d grid
coordinates a'- < &'•, i = l , . . . , n , the value w(x) for x = ( z 1 , . . . , xn)T £ Qj is given by the multilinear interpolation
Ax) = ]T]M:B)u>(a:0 1=1
where n
1
A"! ) = I I #»(*') 1=1
with
9u(x') =
(xl-aj)/(6'-a}),ifx«=6J (b) - z>)/(b)-a)),
if z\ = a)
Remark 2.1 For dimensions n > 3 a grid needs to satisfy some regularity conditions in order to ensure the existence of a continuous function w € W for arbitrary given values in the regular nodes. Consider, for example, a three dimensional grid with two touching elements as in Figure 2.
/
^L
/
.-*"
s s-
_^
^y^
Figure 2. Two touching elements in a 3d grid
In the situation of Figure 2 the value in the central node of the touching faces could either be determinated by interpolating the values in its vertical
158 neighbors (which one would do by looking at the right cube) or by interpolating the values in its horizontal neighbors (as one would do in the left cube). Since these values in general do not coincide, one needs some condition to avoid these situations. A sufficient regularity condition for this purpose is for instance given by (nodes(Qj) U nodes(Qk))
n (Qj f) Qk) C nodes(Qj) for I = j or I = k
for all j , k = 1 , . . . , P with j ^ k, which means that for each two touching elements there is a unique finer one. Furthermore, in order to reduce the number of hanging nodes it is useful to avoid large differences in size of each two neighboring elements. Using the space W we can now define a finite dimensional approximation to Vh • For a sequence of grids F , i > 0 we set w f ( * , , 0 ) = t; o (a:,),
« f ( * « . * 0 = Th(vrh"1)(xl,U_1)
(6)
for i > 1, U = ih < T, and all regular nodes xi 6 r e g ( r ' ) . Note t h a t the evaluation of T/, needs the values of vF_ at the points <3>/,(XI,M), which in general will not be nodes of the grid; hence these values have to be determined by interpolation. T h e discretization error of this approximation will be investigated in the next section. Before turning to this analysis, we will investigate the continuity properties of v£ in a:. For this we need the following Lemma, whose proof is straightforward using the definition of W. L e m m a 2 . 2 Let w £. W be an arbitrary function estimate \w(x) -w(y)\ n Ti I F - y||i
—
max *,y€«od«.(r)
on some grid T. Then the
\w(x) -w(y)\ TTZ zrri 11 a? — 2/| ] i
for all x,y £ Ci with x ^ y. Here \\ • ||i denotes the \~norm
given by \\x\\\ :=
Based on this L e m m a we can now derive a Lipschitz estimate for the approximations «£ . For this we have to make the following assumption on the numerical schemes //, and /,: There exist constants Lihl L$h > 0 such that \h{x,u)
- h{y,u)\
< L / J x - y l l i and | $ A ( i , u ) - $ / , ( y , u ) | < L$h\\x
- y\\i
(7) for all x,y 6 fi and all u 6 Uh- Note t h a t if / and g in (1) are Lipschitz in i £ 1] uniformly in u 6 U then most reasonable numerical schemes (like
159
quadrature rules for //, and Runge-Kutta schemes for $/,) satisfy (7) for suitable constants. Recall that we also assumed v° to be Lipschitz with constant Lo, without loss of generality we may assume this Lipschitz estimate to be valid in the 1-norm. Proposition 2.3 Assume (7), let P be a sequence of grids and consider the functions wjj" defined by (6). Then the estimate \vl'(x,U)
- vl'(y,ti)\
< Li\\x - y\\i
holds, where Li is defined inductively by L,-+i = LjK + exhL$hLi, and Lo is the Lipschitz constant of v° with respect to the 1-norm. Proof: Let w : f2 x /iNo —>• TRL be a function which for some t — ih, i £ No, is Lipschitz in the first argument with constant L. Then the operator T), satisfies \Th{w)(x,t)-Th{w){y,t)\ inf {h{x;u)
+
ueUh
-
exl,w{$li{x,u),t)}
inf {h{y,u) + exllw(h(y, u),t)} u€Uh
< sup \h(x,u)
+ exhw($h(x,u),t)
- h{y,u)
exhw{^h{y,u),t)\
-
u€Uh
< sup \Ih{x,u) -Ih{y,u)\
+ exh\w($h(x,u),t)
-
w($h(y,u),t)\
u£Uh
=
(LIk +
eXkL9hL)\\x-y\\1
for all points x, y £ Cl. Hence the assertion follows by induction using Lemma 2.2. • 3
Error estimation
In this section we present an a-posteriori error estimator for the space discretization (6) of the discrete evolutive Hamilton-Jacobi equation (3). We define the following errors for the approximations v£ (-,<;) on a sequence of grids P . Definition 3.1 We define the local error for each time U = ih, i > 1 by Viae '•= SUP.X'i \Vh {X,U) ~ Th(vh
)(Mi_l)
and for i = 0 by n°oc
•=snp\vl\x,to)-v°{x)
160
The global error for each time U = ih, i > 0 is defined by V'glob : = s u p | ^ ' ( x , < , ) xen
-vh(x,U)\.
Note that while these expressions measure the error in space, the terms "local" and "global" here refer to time, i.e., rfloc measures the spatial error introduced in one time-step, while rflob measures the accumulated error over the whole time interval. The following definition refines this concept to local error estimates in space. Definition 3.2 For each x £ Q we define the pointwise local error by a V
{x):=
l v,r° >
r r 1 r,'(x) := v h'{x,ti)-Th{v h" )(x,ti_1)
(x,0)-vu(x)
and for each element Qj of V we define the elementwise local error by j]) := sup
rf(x).
The following Theorem shows the relation of this value to the errors from Definitions 3.1 and 3.2. Theorem 3.3 Let V be a sequence of grids with P% elements and letv^ (•,<,) denote the corresponding solutions. Then the following inequalities hold SU
rfioc =
P
Vj
i r
)glob
Vl™
= £y*<*-*) suP j
sup k=0,...,i,j
where C(X,h,i)
=
= « + 1 if X = 0 and C{X,h,i)
r/j, l,...,Pk
= (1 - eA*(*'+1))/(l - exh) if
X^O.
Proof: Similarly to the proof of Proposition 2.3 one sees that for each two continuous functions w\, wi : Q x hNo -*• K the operator T/, satisfies \Th(wi)(x,t)
- Th(w2){x,t)\
< exh sup \wx{x,t) r€fi
w2(x,t)\
161
for all x € fi and all t > 0. Hence the assertion follows immediately by induction from the definition of the errors and the identity v/l(x,ti) = T»K)(i,i,-i). • A natural guess for an adaptive strategy is now the following procedure: For i > 0, given some grid I" with P1 elements, and some tolerance tol > 0 for the local error, compute v\ {-,ti) (based on v^ (-,ti-i) or v°) and the errors rf,, j = 1,...,P', refine all elements Qj with rf- > tol. Repeat this procedure iteratively until rf- < tol for all j — 1 , . . . ,PV (A more detailed description of this procedure which also incorporates coarsening of those elements with small errors is given below in Section 4.) In order to ensure that the local error estimates rf, eventually become small (i.e. to ensure termination of this iteration), we need a relation between the size of the element Qj and the size of the local error r)'-. The following lemma gives the necessary estimate L e m m a 3.4 Assume (7). Then
l'/ , 'W-'? , '(i/)l
<\vl\z,ti)-vl'{ytti)\
+
\Th{i$'~1){x,ti-1)-Th{vF~1)(z,ti-i)\.
Since the second term can be estimated as in the proof of Proposition 2.3, the assertion follows from the Lipschitz estimates of u£"(-,*») and v£" (-,^,_i) provided by Proposition 2.3. D The relation between the size of Qj and rf- is now given by the following proposition. Proposition 3.5 Assume (7). Then r]) < Li sup Hz - yd j with Li from Proposition 2.3. Proof: Since rf (x) = 0 for all nodes of the element Qj we immediately obtain the desired inequality by Lemma 3.4. Q Remark 3.6 In particular, these estimates show the convergence of the scheme as the size of the elements tends to 0. More precisely, defining Ax := maxj-i i ... i pdiam(Qj) (where the diameter diam is measured in the 1-norm), and assuming the grid to be constant, we obtain rfaiob < C(X,h,i)
max I.-Az
162
for the constant C(X, h, i) from Theorem 3.3. Note, however, that for the full discretization error (i.e., the error between v\ and v) refined estimates based on viscosity techniques have been obtained in 7 . When looking at the definition of 77} one sees that the computation of this value involves the evaluation of Th (v\' ) at infinitely many points. Of course, this is no feasible task, however, again exploiting Lemma 3.4 we can see that rfj can be approximated by some value fjj which is computable. For this task consider an element Qk and a collection of test points xi £ Qj, I = 1 , . . . ,p. Defining % '•- , m a x
^O.
;=i,...,P
the following lemma shows that this value indeed gives a good approximation tO 7?}. Lemma 3.7 Assume (7), and consider a finite set of points £; E Qj, I = 1 , . . . , p satisfying sup min ||x — xi\\i < a for some a > 0. Then Wj -lj\
< Uct
for Li from Proposition 2.3. Proof: Using Lemma 3.4 we obtain
Wj -n'j\<
SU
P , m i n \v{x) - v(xi)\
< Li sup which shows the assertion. 4
min \\x — xi\\x < Lta D
Implementation details
In this section we will describe several implementational issues of our adaptive scheme in greater detail. Our main focus will be the choice of the test points xi for the numerical evaluation of the local error. As already mentioned in the last section, the exact evaluation of the local errors 77*- is in general not possible; instead by Lemma 3.7 it is justified to use an approximation ff, by an evaluation in finitely many test points xi per cuboid.
163
In what follows we will indicate how a suitable choice of these test points can lead to an efficient implementation. Before going into details, we briefly recall some facts about hierarchical grids which form the basis for our particular choice. The idea of a hierarchical grid is based on a successive local refinement of an equidistant (and coarse) grid. A locally refined grid is obtained by subdividing an element Q in one coordinate direction x'°, io € {1, • • •, n}. We denote this refinement by ref(<3, io)- More precisely, if Q is given by (5) with coordinates a1 < bl, i = 1 , . . . , n then ref(Q, io) consists of the two elements Qi and Qi with coordinates a\ = a% for i — 1, .. ., n, b\ = b% for i = 1 , . . . , n with i ^ io, b[° = aia + {bio -
aio)/2
and b\ — a1 for i — 1 , . . . , n, a'2 = a' for i = 1 , . . . , n with i ^ io, 4 ° = aio + (bio - a''°)/2. For any element Q of the refinement ref(<5, io) we call Q the coarsening of Q, formally coarse (Q) = Q. For a refinement in all coordinate directions we write ref(Q) (i.e. for an n-dimensional grid ref(Q) consists of 2" elements). The refinement of the whole grid is denoted by ref(r), and the m-th refinement by ref m (r), i.e., r e f 1 ^ ) = ref(r), ref m + 1 (r) = ref(ref m (r)). Figure 3 shows the representation of this structure in a binary tree data structure, for more informations on this data structure and hierarchical grids we refer to u .
Figure 3. Representation of a 3d refinement in a binary tree
164
The idea of an efficient choice of the test points is now, that along with some grid T we consider its m-th refinement ref(r,m) for some m > 1 and choose the test points nodes(ref (r, m))\nodes(r). Figure 4 shows the resulting points for m = 1 and m = 2 for a 2d element. e
•
e
1
o
o
o
o
o
I'
O
•
O
II
(I
O
O
O
O
Q
•
9
Figure 4. Testpoints for m = 1 (black) and m = 2 (black and white) in 2d
Doing so, the values in the test points evaluated for the computation of ff- can be used in the next iteration and hence are not "lost" after if- has been evaluated. More precisely, once a solution v\ (-, t»_i) is known the grid generation for the next iteration i is described in the following algorithm: Step 1: Choose an initial grid Tl0 and parameters m > 1 and tol > 0; let f'0 :=ref(r' 0 ,m) and k = 0 pi
_.
Step 2: Compute the solution vhk{-,ti) on T\ Step 3: Compute r)(xi) for all X[ £ nodes(rj.) \ nodes(r^); if r](xi) < tol for all xi go to Step 5 Step 4- Choose a refinement T^.+1 of T'k such that xi G nodes(r^ + 1 ) for all x\ with r){x\) > tol, and let T%k+1 := ref(r' fe+1 , m), k — k + l and go to Step 2 Step 5: Coarsen all elements Q of T'k with 7j(coarse(Q)) < tol, regularize the grid if necessary (cf. Remark 2.1), and let T% be the resulting grid and r := ref(r',m). The condition ?j(coarse(Q)) < tol used for the coarsening in Step 5 ensures that all those nodes are removed from the grid which do not increase the accuracy by more than tol. In other words, all elements Q of the first refined and then coarsened grid satisfy fj(Q) < tol and thus fulfill the desired local accuracy bound.
165
The refinement iteration in the Steps 2-4 can be implemented very efficiently when the following facts are taken into account: (i) Since the hierarchical data structure allows direct access to all subgrids of a given grid, all the operations can be done directly on Tlk, i.e. r^ does not need to be stored seperately (ii) After Step 4 is performed, the computation in Step 2 only involves the f* computation oivhk in those nodes added in the preceding Step 4. f* r* (iii) The evaluation of rj{xi) can be done by comparing vhk and vhk, which are both already computed. In particular, no additional evaluations of Th (i.e. of / and g) are needed. (iv) The function v^ (instead of v£ ) can be used in the computation in Step 2, giving additional accuracy. (v) r ° can be constructed the same way, where in Step 2 we use the initial value v° for the computation of vhk (and omit the coarsening in Step 5). Note that the choice of new nodes in this algorithm results in an anisotropic refinement, i.e. it is not required that an element is refined in all coordinate directions. For the choice of the initial grid Y'0 there are several possibilities. In the numerical tests in the next section we have chosen the grid F - 1 from the last time step. A different possibility would be to start off from a given coarse initial grid in each iteration. In this case no coarsening is necessary in Step 5. 5
Numerical examples
For our first numerical tests we consider the classical "rotating cone" benchmark problem, see e.g. 6 . The equation is given by -v(x,t)-f(x)
— v(x,t) = 0
(8)
for x = (xi,x2)T 6 l 2 with f{xx,x2) {-x2,Xi)T. The initial value was chosen as the "cut" paraboloid v°(x) = m a x i 0 . 0 8 -
0.5 0.5
,0
166
Note that v° is Lipschitz, but not differentiate, and so is v(-,t) for each t > 0. The system was discretized in time by a first order explicit Euler scheme with h = 0.5 and the initial grid TQ was chosen to be equidistant with Ax = 0.2 (in the 1-norm), which results in N = 441 nodes. The parameter m determining the number of test nodes was set to 1. tol = 0.01
tol = 0.1
i 0 1 2 3 4 5 6 7 8 9 10
tol = 0.001
tol - 0.0001
N'
^glob
N'
Vglob
N'
%lob
N'
Iqlob
441 441 441 441 441 441 441 441 441 441 441
0.000000 0.008798 0.012077 0.015598 0.015028 0.018611 0.021677 0.025200 0.027362 0.029064 0.032706
537 514 479 477 475 463 449 451 459 459 459
0.000000 0.008164 0.012468 0.013425 0.014007 0.014441 0.013832 0.016434 0.016546 0.021947 0.021727
2187 2246 1928 1921 1844 1802 1785 1768 1614 1628 1698
0.000000 0.001403 0.001985 0.001999 0.002912 0.004038 0.003452 0.003091 0.005015 0.005061 0.005242
20889 18919 17338 16725 15644 15076 14410 14059 13561 13880 13583
0.000000 0.000182 0.000230 0.000665 0.000678 0.000670 0.000632 0.000673 0.000596 0.001849 0.001829
Table 1. Number of nodes N' and global node error fl' lob for example (8)
Table 1 shows the resulting number of nodes N' and the global error Tfglob in the nodes of the grid I" denned by Vgiob : = a
n ^ x -, K ' O M O -
vh{x,ti)\
r6nodes(r*)
for the iterations i = 0 , 1 , . . . , 10 (i.e. up to t = 5) and different values of tol. As expected for the first order scheme the number of nodes grows approximately like l/tol, which shows the efficiency of the estimate. Furthermore, for all tolerances the global error is of the order of the expected bound lOtol, which indicates that the choice of the test points in this example gives satisfactory results. One can observe that the number of nodes tends to decrease during the iteration. This is mainly due to a "numerical diffusion" effect: During the iteration the steep regions tend to flatten (within the given accuracy bounds) and thus the number of nodes needed to ensure the given error tolerance becomes smaller. The Figures 5-8 show the solution v\ (-,5) and the corresponding grid T 10 after the last iteration for the different values of tol. In addition, Figure 9 shows the evolution of the grid during the computation for tol — 0.001. Observe that the effect of the usage of the preceding grid I " - 1 in the construction
167
[
I
0.333 ^
lul
-0.333"
OflO
-G.333
lx]
0.333
1 . GE
Figure 5. Solution and grid after 10 iterations for example (8) with tol = 0.1
a.33:
(yl
-9.33 i
»-
-0.333
£H]
0.333
Figure 6. Solution and grid after 10 iterations for example (8) with tol = 0.01
of T1 is clearly visible.
168
i;:_i™ 0.333
ly]
-0.333
- 1.009.968
-Q.333[xl
i 0.333
I
Figure 7. Solution and grid after 10 iterations for example (8) with tol = 0.001
-9.333 U l
8.333
Figure 8. Solution and grid after 10 iterations for example (8) with tol = 0.0001
For our second test we consider a nonlinear variation of the first example. Here the equation is given by d_ -v(x,t) + mf { - / ( * , u)~v(x,i)j dt
= 0
(9)
for x — (xx,X2)T &R2 with. f(xx,X2,u) = (-uxz,uxi)T and one-dimensional control range U = [0,1]. The initial value v° is chosen as before. Here the cone is not only rotating but also remains everywhere it has been before, i.e., is is "stretched" along the vectorfield. For this test we used the same discretization in time as above, where the discrete set of control values Uh was chosen as Uh = {0, 1/9,..., 8/9, 1}. Like for our first test, we show the results in Table 2, where we omit the error
169
%iob f° r ^ n e s m a l l e s t tolerance since the evaluation of the exact discrete time solution Vh(x,ti) for this nonlinear problem was not feasible for such a large number of nodes. tol = 0.1
i 0 1 2 3 4 5 6 7 8 9 10
tol = 0.01
tol - 0.001
N'
Vglob
N'
Vglob
N'
441 441 441 441 441 441 441 441 441 441 441
0.000000
537 578 568 575 573 549 557 543 539 539 539
0.000000
2187
0.008164 0.012468 0.012970
3627 4116
0.008798 0.012077 0.015598 0.014353 0.019241 0.022455 0.024617 0.026374 0.027804 0.029047
0.014990 0.020617 0.023129 0.025428 0.027224 0.028628 0.029883
4524 4948 5283 5741 6279 6616 6944 7274
Vglob
tol = 0.0001
N> 25762
0.000000 0.001406 0.003712 0.004612
47293 55915 65767
0.006488 0.007623 0.009144 0.010843 0.012378 0.013855 0.015125
75826 81893 90022 98775 105077 112625 122600
Table 2. Number of nodes N' and global node error Jj' ( o j ) for example (9)
The Figures 10-12 show the solutions after 10 iterations and the corresponding grid for tol = 0.01, 0.001 and 0.0001.
170
References 1. 1. M. BARDI AND I. CAPUZZO DOLCETTA, Optimal Control and Viscosity Solutions of Hamilton- Jacobi-Bellman equations, Birkhauser, Boston, 1997. 2. 2. I. CAPUZZO DOLCETTA, On a discrete approximation of the HamiltonJacobi equation of dynamic programming, Appl. Math. Optim., 10 (1983), pp. 367-377. 3. 3. I. CAPUZZO DOLCETTA AND H. ISHII, Approximate solutions of the Bellman equation of deterministic control theory, Appl. Math. Optim., 11 (1984), pp. 161-181. 4. 4. M. FALCONE, A numerical approach to the infinite horizon problem of deterministic control theory, Appl. Math. Optim., 15 (1987), pp. 1-13. Corrigenda, ibid. 23 (1991), 213-214. 5. 5. M. FALCONE AND R. F E R R E T T I , Discrete time high-order schemes for viscosity solutions of Hamilton-jTacobi-Bellman equations, Numer. Math., 67 (1994), pp. 315-344. 6. 6. M. FALCONE AND R. FERRETTI, Convergence analysis for a class of
7.
8. 9. 10. 11.
12.
high-order semi-lagrangian advection schemes, SIAM J. Numer. Anal., 35 (1998), pp. 909-940. 7. M. FALCONE AND T. GIORGI, An approximation scheme for evolutive Hamilton-Jacobi equations, in Stochastic analysis, control, optimization and applications, W. McEneaney et al., ed., Birkhauser, Boston, 1999, pp. 288-303. 8. R. F E R R E T T I , High-order approximations of linear control systems via Runge-Kutta schemes, Computing, 58 (1997), pp. 351-364. 9. L. GRUNE, An adaptive grid scheme for the discrete Hamilton-J acobiBellman equation, Numer. Math., 75 (1997), pp. 319-337. 10. L. GRUNE AND P . KLOEDEN, Higher order numerical schemes for affinely controlled nonlinear systems, Numer. Math., to appear. 11. L. GRUNE, M. METSCHER, AND M. OHLBERGER, On numerical algorithm and interactive visualization for optimal control problems, Computing and Visualization in Science, 1 (1999), pp. 221-229. 12. A. ROBERT, A stable numerical integration scheme for the primitive meteorological equations, Atmos. Ocean., 19 (1981), pp. 35-46.
13. 13. A. STANIFORTH AND J. COTE, Semi-Lagrangian integration schemes
for atmospheric models—a review, Monthly Weather Review, 119 (1991), pp. 2206-2223.
171
0.333
.333
[y]
-0.33 3
Q.33 3
-0.333 [x]
_,_
,
0.333
0.333
0.333
[y|
-0.33 3
-0.33 3
-0.333 [xl
0.333
LOG
' -1.968
- 0 . 3 3 3 [xl
,
0.333
1. OE
0.332
[y]
-0.333
-9.33 3
l". 008
- 0 . 333 [x)
0.333
1. 0£
* ' ™i~ 008
-0.333 [xl
0.333
Figure 9. Grid after 0, 2, 4, 6, 8, 10 iterations for example (8) with tol = 0.001
172
I" EL"
+
++
8.333
-0.333
-0.333 f x l
0.333
Figure 10. Solution and grid after 10 iterations for example (9) with tol = 0.01
333 [xl
0.333
1.0£
Figure 11. Solution and grid after 10 iterations for example (9) with tol — 0.001
Figure 12. Solution and grid after 10 iterations for example (9) with tol = 0.0001
173
SOLUTION A N D APPLICATION OF ANISOTROPIC CURVATURE D R I V E N EVOLUTION OF CURVES ( A N D SURFACES) KAROL MIKULA Department of Mathematics, Slovak University of Technology, Radlinskeho 11, 813 68 Bratislava, Slovakia E-mail: [email protected] We discuss methods of numerical solution of geometrical equations v = 0(9, k), where v is normal velocity of evolving plane curve with curvature k, 6 is the angle of the tangent to the curve with horizontal axis, and /3 is a smooth function increasing in k. Equations of this type are used to describe important phenomena in physics, material science, artificial inteligence, robotics and image processing. Anisotropic motion of phase interface in free boundary problems with surface tension as well as image smoothing, recognition, segmentation and shape analysis in computer vision are well-known examples. We present approximation schemes and existence and convergence results for the curve evolution leading to the solution of degenerate parabolic problems of slow and fast diffusion type. Approximation of the problem by means of the so called intrinsic heat equation and its numerical solution are discussed too. We also study methods based on level set and phasefield formulations of mean curvature flow, and present a comparison study with the previously mentioned methods and application to image selective smoothing and phase transition problems.
1
Introduction
The aim of this work is to present methods for solving the curve evolution equation v = /3(M),
(1)
where v is (outer) normal velocity of evolving plane closed curve with curvature k (which, by the convention introduced by Angenent and Gurtin 9 , has negative sign for convex curves), 9 is the angle of the tangent to the curve with horizontal axis and j3 is a smooth function increasing in k. The study of such curve motion (as well as its 3D generalization to surface evolution depending on mean curvature) is motivated by many applications in which Eq. (1) arises and also by its relation to the minimal surface problem. Examples of applications include the following: - In the material science dealing with motion of interface (free boundary) between solid and liquid phases Eq. (1) corresponds to the so called Gibbs-Thomson law governing crystal growth in undercooling liquid 30>67>14
174
Angenent and Gurtin theory of interface motion in thermal superconductivity also uses (1) as a natural tool for describing the evolution of phase boundaries 9 . The dependence of the flow on the curvature k is related to surface tension effects on the interface and the dependence on 9 (orientation of interface) introduces anisotropy into the model. The nonlinearity given by the function /3 expresses e.g a dependence of the kinetic coefficient on the normal velocity. Assuming slow interface velocities, this dependence is linear 9 and Eq. (1) corresponds to classical anisotropic curve evolution governed by a!(0)v = a2{6)k - F,
(2)
where on,ct2,F represent physical quantities comming from constitutive description of interface. In the isotropic case we end up with the classical (i.e linear v = k) curve shortening flow 27,1,6,29 - In the context of image processing, the so-called morphological image and shape multiscale analysis is used due to its contrast invariance properties. It has been introduced by Sapiro and Tannenbaum 62 and Alvarez, Guichard, Lions and Morel 2 ' 3 ' 34 as a natural result of axiomatization of computer vision theories. In general, an image silhouette (boundary of distinguished shape) corresponds to a level line of image intensity function. The morphological scaling (shape analysis) of the silhouette leads to the equation of the form (1) without anisotropic part. Namely, affine invariant scale space has special conceptual meaning and importance. It is a generalization of the linear curve shortening flow, and is given by Eq. (1) provided /?(fc) = fc1/3 2,62,83,64,65,11, In the problems of image segmentation 40 ' 43 also "anisotropic like" models have been used recently 18 . - Models involving Eq. (1) are used also in other applied sciences, e.g. in modelling of flame front propagation in combustion, computing of first arrival times of seizmic vawes, in computational geometry, robotics, semiconductors industry, etc. (for a comprehensive overview of applications we refer to Sethian's book 7 0 ). From the computational point of view, two main approaches are used for solving Eq. (1): 1. Direct approach, in which the parameters of evolving curve, namely - position vector in intrinsic heat equation 22,23,24,51,52 or - curvature in porous-medium like equation 46 ' 45 are unknowns in related initial boundary value problems. There are also direct methods based on the so-called crystalline curvature approximation 28 72 ' , special finite difference schemes 41 ' 42 and a method based on erosion of
175
polygons in affine invariant case . 2. Level set approach based on introducing of an auxiliary function (p(x, t), (j>: H d x M j —>• IR (d = 2 or 3) which is an unknown in the so called - level set equation 57,69,70,71,31 or in the so called - phase-field formulations of the curve and surface evolution in the form of reaction-diffusion equations 15,54,58,25,14 In the level set approach, the zero level set of the function
Direct approach using porous-medium like equations
In order to model the curve evolution we consider a vector function x(u: t), x : IR x [0, Tmax) -> 3R periodic in the first argument with a period given by the range of curve parametrization u. Then, x(u, t) corresponds to position vector of the evolving curve T = Image(x) in time t. Of course, the evolving curve admits various parametrizations. First, let us consider closed and strictly convex initial curve x(.,Q). Then, 9 - the angle of the tangent to the curve with the horizontal axes - is a convenient parametrization varying in fixed interval [0,2-7ri/], where u € ]N corresponds to the index of the curve. Let the initial closed strictly convex curve x° = x(9,0) be parametrized by 9 and let k0(9) be its curvature. Then, using 27 ' 9 , we have that the flow x(9,t) of the curves, starting from x0, which solves the problem (1) and remains strictly convex is given uniquely up to a translation by the formula x(90,t) = x(0,t) - j j
^-^d9,
(3)
in which the curvature k(9, t) is the solution of the following doubly-nonlinear porous medium type initial boundary value problem: dtb(k) = d9e0{e,k)+p{8,k), k{9,t) =k(6 + 2irv,t), k(8,0) = ko(9),
(4)
176
with b(k) = -1/fc. For many so far studied curve evolutions, namely classical linear curve shortening 27 , affine invariant scale space 6 2 - u ; anisotropic curve shortening 9 ' 10 , power like nonlinear curve evolution with positive anisotropy 5 ' 5 2 , the conservation of strict convexity has been proved in mentioned references. The proofs are basically based on application of maximum principle to equations of type (4) or Matano's result 44 which leads to the statement that curvature of evolving curves cannot change sign during the evolution. The nonlinear problem (4) with periodic boundary conditions can be solved numerically by a kind of Jager-Kacur algorithm 32,36,33,35 §uch approach for solving the curve evolution problem was developed in 46 ' 45 and has been applied to anisotropic as well as nonlinear curve shortening. The discrete curvature function is computed in each discrete time step of the numerical scheme designed to solve Eq. (4) and the curve flow is reconstructed by the formula (3). Let us briefly recall the main ideas of approximation of Eq. (4). We consider case of separated anisotropy and nonlinearity in the form (3(9,k)=S1(9)1(k)
+ S2(9),
where Si > q > Q,S[,S",S2 are bounded measurable functions, periodic in interval [0, 27Tf] and 7 is C2-function in H — {a} with 7'(z) > 0,z ^ a, V(a) > 0, 7(a) = a. The mathematical and numerical difficulties are caused by degeneracies in Eq. (4). Namely, asymptotical degeneracy of slow diffusion type (&' = 00, 7' = 0) is related to the parts of the curve, where curvature is close to 0 and plays the role in the presence of anisotropy and porous medium like nonlinearity (e.g. j(z) — zm,m > 1). Asymptotical degeneracy oi fast diffusion type (&' = 0, 7' = 00) is related to both, large and small curvatures, and plays the role near the shrinking, singularities formation and influences a more shape preserving (e.g. affine invariant, /3(k) = k1/3) evolution. The special form of the problem causes a blow up of the curvature in a finite time which corresponds to the shrinking of the curve to a point or to other singular behaviour. If we denote I = [0,Tmax], J = [0,2TH/], QT = I x J, V = {w € WJJCO, 2-KV) : w(0) = w(2Ttu)}, V* its dual space, and assuming that 7(^0) € V, we can define weak solution of (4) as a function k € ^ 2 ( Q T ) with dtb(k) G L2(I,V*) for which 0(6,k) € L2(I,V), k{9,0) = k0{9) and / f dtb(k)ipd6dt+ f f de/3(6,k)
L2{I,V).
In order to find the weak solution we use the following approximation
177
scheme for the porous medium like curve evolution equation (4): Let n € lN,r = 3 ^ , ^ = j r for i = 0 , . . . ,n, k0 = ko(0),Ko = j(k0). For ! = l , . . . , n w e look for the functions Ki £ V (Ki m j(ki)), fa € -Loo(^) such that f fii(Ki - 7 (*i_i))¥«W + rf where (3(9,z) = (3(9,1 l(z)) condition A Q
d9p(9, Ki)
6(7~1(Q^ + (l-a)7(fci-i)))-&(fci-i)
...
K^ik-T)
(6)
2 ^ ^
'
holds with 0 < a < 1 (a close to 1) and A is a lower bound of derivative of a regularized b o 7 _ 1 function 46>45. The curvature function ki is obtained by the algebraic correction b(ki) := 6(*i-0 + W(#i - 7(*i-i))-
(7)
In this scheme, the nonlinearity of equation is treated by the optimal choice of relaxation function fa corresponding to dz(b o j~l) constructed in an iterative way 45 - 46 . Using ki,Ki obtained in each time step of (5)-(7), the Rothe functions k{n)(t) = ki,foTti-i
46,45
k(n) -> k in L2(QT),
= l,...,n, = l,...,n,
k{n)(0) = ko, TT(Q)=K0
(8) (9)
we have T1 -> 7(fc) in L2(I, V),
where k is unique bounded weak solution of the initial-boundary value problem (4). The linear elliptic convection-diffusion equation (5) can be solved by finite element discretization or by finite volume method including the so-called upwind principle. 3
Direct approach by intrinsic heat equations
In the concept presented above, the existence and uniqueness of the solution as well as convergence and error estimates of approximations are proved 4 6 ' 4 5 . However, such approach holds only for convex curve motions and, from practical point of view, we would like to handle general nonconvex curve evolution governed by Eq. (1). In the nonconvex case, #-parametrization seems to be not convenient due to a changing of its range during the evolution for each
178
convex/concave piece of a curve. Another idea, originating in Dziuk's algorithm for evolutionary surfaces can be used. Provided /3 = /3(k), we use the representation of Eq. (1) by the so called intrinsic heat equation 51 d2x
dx
m^dsj
^
where s, is a special curve parametrization related to standard arc-length parametrization by ds, =${s)ds,d
=
kll2p{k)-xl2.
Then clearly dX l d ~ d{s)ds ' 9 (\-d{s)ds) ^=m N-^fiT dt ^ w tf3(s)'
where T is the unit tangent vector, T = xs and N is the unit normal vector dx. N) satisfying Frenet's formula Ts = kN. Hence the normal velocity v = (%, • at • fulfills (1). Let u 6 [0,1] be a time independent parametrization of a curve T. Then the arc-length parametrization s of T is related to u by ds — \xu\du. Let us define scalar valued function G : M 2 x IR2 - » I R j , G(j>,q) =
\p\k(p,q)ll2fl(,k{P,
where k(p,q) = \p\~3 (W 2 k| 2 - (P,q)2)1/2
P,9 € K 2
and (.,.) denotes the Euclidean scalar product in IR2 and the corresponding norm is denoted by |.|. With this notation, (10) can be rewritten as follows
% = Tu-1
T#- (rf^
\¥)
> ("-*) € t 0 ' 1 ] x [°- T -x).
(11)
dt G(xu,xuu)du \G(xu,xuu) duj The fully nonlinear system of PDE's (11) is subject to the initial condition x(u,0) = x°(u),u € [0,1] and periodic boundary conditions at u = 0,1. Approximation scheme for the curve evolution based on intrinsic heat equation: Let T = Tm,i', n € IN denote time discretization step. By xl,i = 0,1,..., n, we denote the approximation of a solution of (11) at time t = IT, i.e. x'(.) — X(.JT). The idea of the construction of a time discretization scheme is based on approximation of the intrinsic heat equation (10) by the backward Euler method x* - x*~l <9V . , „ =-Z~2 , i = l,2,...,n, r osi
179
where the parameterization s« is computed from the previous time step x% *. The semidiscrete scheme thus reads as follows
*-5*k{
l l
i=1 2
(12
- "•
l
where G ~ = G{x ~ ,x ~^) and x° is the initial condition. One can prove that the length of the curve P = Image{xl) decreases along the semidiscrete evolution generated by (12) 5 1 . It represets a kind of stability property for the scheme. To derive the fully discrete analogue of (12) we use the uniform spatial grid Uj = jh (j = 0, ...,m) with h = 1/m. The smooth solution x is then approximated by the discrete values x! corresponding to x(jh,ir). Using finite difference approximations of spatial differential terms in (12) we end up with the following semi-implicit fully discrete scheme X
//-n-l
-{Gj
, ri-l\Z3
Z
j
+ Gj+1)—-—
_
X
j+1
-
Gi_x
X
j
X
j
X
(,o-\
Gi_i
(13;
j-l
i — l,...,n,j = 1, ...,m, where (we slightly regularize G!--1 in order to avoid zeroes in denominator) G}- 1
= /i}" 1
,i_! _ |arccos((x};l - ^ . x } -
j
~
h\~l = IT 1 - 1 - a-1-11
-^ 1
- x ^ ) / ( | 4 ; j -x^Hx}-1 -x^|))l
^f1
•
l
The scheme is subject to the periodic boundary conditions x j+m — x^ (j = 0,1). In each discrete computational time step IT the scheme (13) leads to solving of two tridiagonal systems for the new curve position, which are computed in a very fast way. Let us mention that (13) does not involve the spatial grid parameter h (i.e. the scheme respects the intrinsic character of the equation) and in the linear case (l(k) = k it coincides with Dziuk's scheme 23 . Recently, the approach based on intrinsic heat equation has been adopted also to anisotropic motion for general case (1) 52 and to anisotropic case with linear 7(fc) = k 24 . In the end of this section we present several computational results related to the schemes (5)-(7) and (13). They show good correspondence of both methods in convex case (until formation of singularities) and also successful computation of nonconvex curves evolution.
>
180
Figure 1. Comparison of two different methods for evolution of convex curve; tick marks method (13), solid lines - method (5)-(7), affine invariant case 0(k) — fc1/3. We also remark proper redistribution of flowing points representing the discrete curve in the method (13) due to the presence of tangential velocity
Figure 2. Comparison of two different methods for evolution of selfintersecting "convex" curve, y3(jfc) = fc1/3. Tick marks - method (13), solid lines - method (5)-(7). The evolving curve is plotted at the same discrete time moments until the "hair" singularity is formed. The method (5)-(7) cannot continue beyond singularity.
181
0.75 0.5
0.25
0 0.25 -0.5
-
0.75 -1
-0.5
0.5
Figure 3. Evolution of the affine transformed 4-petal through singularities computed by the method (13), /3(k) = A:1/3.
1.5
0.5
-0.5 1.5 Figure 4. The evolution of initial nonconvex plane curve computed by the method (13), /3(Jt) = k.
182
1.5
0.5
-0.5-
1.5 Figure 5. The evolution of initial nonconvex plane curve computed by the method (13) to ellipse rounded point. The affine invariant case /3(fc) = A:1/3.
4
Solution using level set equation
The direct approach, called also Lagrangean, described in previous two sections is very efficient and computationally fast method. However, it can hardly handle splitting and/or merging of curves or surfaces during the evolution (e.g in modeling of phase transition). In spite of this, level set approach, called also Eulerian, allows to overcome this difficulty. It handles implicitly the curvature driven motion passing the problem to higher dimensional space. The level set method of Osher and Sethian ",69,70,71 and phase field models UM&M a r e approaches of such type. The main idea of the level set method is to look for the function <£> : M 2 x ]RQ" —• H, for which the moving curve x is the same level line at each time moment t, i.e.
(14)
for every t € I and certain c 6 1R . As initial datum for
183
e.g. the so-called signed distance function given by 4>(x,0) = ±d(x),
(15)
where d(x) is distance from the point x to the initial curve T and the plus (minus) sign is chosen if the point x is outside (inside) the initial curve F. Differentiating (14) in time one gets
Since only normal component of velocity of flowing curve point influences image of the evolution 65 we can write Eq. (1) in the form — =(3(6,k)N.
(17)
We have also (18 » - & » holding for outer normal vector N to the level set of <j>. Using (17) and (18) in (16) we obtain the following Hamilton-Jacobi partial differential equation
^+/J(M)|V0|=O
(19)
for the unknown function
* - ( & ) which holds for the curvature k of the level line of <j> passing through point x, provided j3(0, k) = k, we get the well-known level set equation
This equation moves all level lines of <j> by the normal velocity proportional to its curvature. Up to a constant and with >: IR3 x IRQ" —• ]R, this equation holds true also for the iso-surfaces evolving by mean curvature (which is given as a sum of principal curvatures of hypersurface). Previous derivation of (20) has been formal assuming that all terms are well defined and smooth enough. In general situation one has to use theory of the so-called viscosity solutions 19 in order to define in a proper way a solution of the level set equation 26 - 17 .
184
Let us note that (20) represents a special type of diffusion process. If we fix coordinate system in point x G H 2 on a level line of 0 in such a way that £, the first coordinate vector is identical with tangent to the level line and the second coordinate vector TJ corresponds to its normal, then the differential operator |V0|V. ( j ^ r ) can be rewritten as f^f. It means that (20) diffuses the solution
185
Figure 6. The heart ventricle in open phase - visualized from the result of aquizition (left) and after 3D image processing by mean curvature flow (right).
Here, we present Figure 7 where two chromozomes are extracted from an initial noisy 3D-image by selective smoothing (21) with g(s) — 1/(1 + s2). The models like (21) are strongly inspired by the original work of Perona and Malik 59 where first nonlinear partial differential equation has been suggested for image selective smoothing and edge detection. Perona and Malik have considered equation of the form 4>t = V((|V>!)V0)
(22)
which is called usually anisotropic diffusion in computer vision community. The nonlinear diffusion term in (22)can be rewritten as 2 V(0(|V0|)V0 = fl(|V0|)0« + G'(|V4>|)0 w
(23)
where G(s) = sg(s) and £, TJ are tangential and orthogonal vectors to the level line, respectively. From this form one can simply see how diffusion behaves along and across image silhouettes with different choices of g. There is always positive but possibly strongly slowed-down diffusion along level lines representing silhouette-edges. Across such silhouettes, there can be either forward diffusion (not too interesting from the point of image enhancement), zero diffu-
186
"
Hi T 'ffki'\tmilt ilinTiliTitTlifri IJi^Tliiiir ' "
•».
Figure 7. Extraction of the chromozomes from 3D image by mean curvature flow with velocity depending on the gradient of solution.
sion (in Rudin-Osher-Fatemi model 61>56) where g(s) = 1/s) or backward diffusion (in the original Perona-Malik choice, where g(s) = l/(l+s2),g(s) = e~a). The character of diffusion depends on monotonicity of G(s). If the product g(s)s is a decreasing function then Perona-Malik equation can behave locally like backward heat equation, which is an ill-posed problem. Thus, for g's used in practice (g(s) — 1/(1 -I- s2),g(s) = e~ s ) both existence and uniqueness of a solution can not be obtained. However, the model has been used in various numerical implementations in wide range of application especially in medical image processing. One way how to prevent this paradox and mathematical disadvantage was proposed by Catte, Lions, Morel and Coll in 16 . They introduced convolution with Gaussian kernel Ga into the decision process for the
187
value of diffusion coefficient, namely, they suggested the following equation <j>t - V ( 5 ( | V G f f * 0 | ) V 0 ) = f(4f> - >),
(24)
d
where Ga £ C°°{TR ) is a smoothing kernel, e.g Gaussian function, and by means of / on the right-hand side of (24), the solution <j> is forced to be close to 0° 5 5 . This slight modification allowed them to prove existence and uniqueness of the weak solution for the modified equation (24) and keep all practical advantages of original formulation. Moreover, the usage of the Gaussian gradient VGa *
n
for the unknown function 4>\ € V/,, where Vj, is the space of linear finite elements on triangular (tetrahedral) grid corresponding to image pixel/voxel structure and a kind of mass lumping is used in the first term in (25). The semi-implicit method (25) can be used for computing the curve evolution equation (1). In Figure 8 we present its comparison with direct method (13). We solve numerically evolution of nonconvex curve plotted on the top left part of Figure 8. As initial function <j>(x, 0) we have chosen signed distance function (15). In the next images (to the right and down) we plot numerical solutions until circular shape is reached and the curve is shrinking into a point. By solid lines we plot solution given by method (25), by dashed lines we present solution given by the scheme (13) (the algorithm (13) is also accompanied with uniform redistribution of curve representation points 5 2 ) . From the comparison one can see a precise coincidence of two methods during evolution as well as a correspondence of numerical extinction times.
188
-1
-0.5
0
0.5
1
-1
-0.5
0
0.5
1
-1
-0.5
0
0.5
1
-1
-0.5
0
0.5
1
-1
-0.5
0
0.5
1
0.5
0.5
-0.5
-0.5
-1
-0.5
0
0.5
1
Figure 8. Computational comparison of level set approach and direct approach based on intrinsic heat equation.
189
5
P h a s e field a p p r o x i m a t i o n of interface m o t i o n
As we have mentioned in introduction, the curve evolution equation (1) arises in thermomechanics with interfacial structure, e.g. in the study of phase transitions on microscopic level. If solid occupies a subset fls(t) C Cl and liquid occupies a subset fij(i) C fi, Q C 1R2, at a time t, then the phase interface is a set T(t) = dfls(t)r\dCli(t) which is assumed to be a closed curve. The sharp-interface description of the solidification process is then described by the Stefan problem with surface tension pc— = XAU at
in H s and
fi/,
(26)
— (U-U*) = -a2(6)k + a1(6)vonT, (28) cr accompanied with initial and boundary conditions for temperature field U and initial position of the interface T(0). The symbols p,c, A represent material characteristics (density, specific heat and thermal conductivity), L is latent heat per unit volume and U* is a melting point. Discontinuity of heat flux on the interface V is described by the Stefan condition (27). The formula (28) is the Gibbs-Thomson relation on T, where Se is difference in entropy per unit volume between liquid and solid phases and a = const is surface tension, ax is a coefficient of attachment kinetics, and dimensionless function Q 2 describes anisotropy of the interface, e.g., it has the form a2{6) = 1 - Ccos(m(0 - 0O)) where ( € [0,1) is a strength of m-fold anisotropy and 80 is principal direction - crystallographic orientation. In 13 ' 14 the following phase-field formulation of (26)-(28) is studied pcf 2
= \AU + L§,
(29)
a
ai(*)€ S$ = «2(0)(£ A0 + a0(l -
= a 2 (*)|V0|V ( j ^ l i ) + | | V 0 | ( £ T - U)
(31)
of the Gibbs-Thomson condition (28). As it is usual in phase field models the first (degenerate diffusion) term on the right hand side of (31) is
190
0
0.04
0.08
0.12
0.1S
0.2
Figure 9. Anisotropic 5-fold mean-curvature flow compared to phase-field model (£ = 0.7, F = 0.0, a = 4.0, £ = 0.005,
replaced by Laplacian and double-well potential term in (30) and moreover the equation depends on small parameter f. However, in spite of another phase field formulations, Eq. (30) contains a modified coupling term b—(U* - t/)^ 2 |V0| = F6£ 2 |V0|, which can help in quantitative correspondence of diffusive and sharp interface models. This fact has been observed in intercomparing study of quantitative correspondence of phase field and sharp interface description of mean curvature flow problem 14 . The results of simulations by the phase equation (30) using numerical approximation based on finite difference method has been compared to the results obtained by the method (5)-(7) solving the sharp-interface problem (1). In Figures 9-11 we present comparison which indicates satisfactory correspondence of both models in case of fine enough choice of phase field parameter f. Acknowledgments The author thanks to M. Benes, A. Handlovicova, J. Kacur, A. Sarti and D. Sevcovic, whose contribution to development of the presented methods and co-authorship is gratefully acknowledged. The work on this paper was supported by the grant VEGA 1/7132/20 of the Scientific Grant Agency of the Slovak Republic.
191 0.5 Phase field Mean-curvature flow
PhaM field Mean-curvature flow
'
0.45
0
0.001
0.002
0.003
0.004
0 005
Isoperimetric ratio
0.0O6
0.007
0.008
0.009
Phase field Mearwajrvature flow
Time 0.04
0.08
0.12 0.16
0.2
0
0.001
0.002 0.003
0.004
0.005
0.006
0.007
0.008
0.009
Figure 10. Anisotropic 3-fold mean-curvature flow compared to phase-field model (£ = 0.7, F = 0.0, a = 4.0, f = 0.0025, Qi = 1).
References 1. U. Abresch, J. Langer, The normalized curve shortening flow and homothetic solutions, J. Diff. Geom. 23, 175 (1986) 2. L. Alvarez, F. Guichard, P.L. Lions, J.M. Morel, Axioms and Fundamental Equations of Image Processing, Arch. Rat. Mech. Anal. 123, 200 (1993) 3. L. Alvarez, J.M. Morel, Formalization and computational aspects of image analysis, Acta Numerica, 1 (1994) 4. L. Alvarez, P.L. Lions, J.M. Morel, Image selective smoothing and edge detection by nonlinear diffusion II, SIAM J. Numer. Anal. 29, 845 (1992) 5. B. Andrews, Evolving convex curves, Calculus of Variations and Partial Differential Equations 7, 315 (1998) 6. S.B. Angenent, On the formation of singularities in the curve shortening flow, J. Diff. Geom. 33, 601 (1991) 7. S.B. Angenent, Parabolic equations for curves on surfaces I: Curves with
192
i 005
0
, 0.1
, 0.15
. 0.2
. 0.25
. 0.3
. 0.35
. 0.4
0.45
, — . ° 0005
0J
, "
. , ° ' 0 1 S aa
, otas
0M
, 0(a5
, 0 M
, 0M5
1 oos
Figure 11. Anisotropic 3-fold mean-curvature flow with force compared to phase-field model (C = 0.7, F = - 1 0 . 0 , a = 4.0, b = 1, f = 0.005, ax = 1).
p-integrable curvature, Annals of Mathematics 132, 451 (1990) 8. S.B. Angenent, Parabolic equations for curves on surfaces II: Intersections, blow-up and generalized solutions, Annals of Mathematics 133, 171 (1991) 9. S.B. Angenent, M.E. Gurtin, Multiphase thermomechanics with an interfacial structure 2. Evolution of an isothermal interface, Arch. Rat. Mech. Anal. 108, 323 (1989) 10. S.B. Angenent, M.E. Gurtin, Anisotropic motion of a phase interphase. Well-posedness of the initial value problem and qualitative properties of the interphase, J. Reine Angew. Math. 446, 1 (1994) 11. S.B. Angenent, G. Sapiro, A. Tannenbaum, On affine heat equation for non-convex curves, J. Amer. Math. Soc. 11, 601 (1998) 12. E. Bansch, K. Mikula, A coarsening finite element strategy in image selective smoothing, Comput. Visual. Sci. 1, 53 (1997) 13. M. Benes, Phase-Field Model of Microstructure Growth in Solidification of Pure Substances, PhD thesis, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University, Prague, 1997 14. M. Benes, K. Mikula, Simulations of anisotropic motion by mean curvature - comparison of phase field and sharp interface approaches, Acta Math. Univ. Comenianae 67, 17 (1998)
193
15. G. Caginalp, The dynamics of a conserved phase field system: Stefanlike, Hele-Shaw, and Cahn-Hilliard models as asymptotic limits, IMA J. Appl. Math. 44, 77 (1990) 16. F. Catte, P.L. Lions, J.M. Morel, T. Coll, Image selective smoothing and edge detection by nonlinear diffusion, SIAM J.Numer.Anal. 29, 182 (1992) 17. Y.-G. Chen, Y. Giga, S. Goto, Uniqueness and existence of viscosity solutions of generalized mean curvature flow equation, J. Diff. Geom. 33, 749 (1991) 18. V. Caselles, R. Kimmel, G. Sapiro, C. Sbert, Minimal surfaces based object segmentation, IEEE Trans. Pattern Analysis and Machine Intelligence 19, 394 (1997) 19. M.G. Crandall, H. Ishii, P.L. Lions, User's guide to viscosity solutions of second order partial differential equations, Bull.(NS) Amer. Math. Soc. 27, 1 (1992) 20. K. Deckelnick, Weak solutions of the curve shortening flow, Calculus of Variations and Partial Differential Equations 5, 489 (1997) 21. K. Deckelnick, G. Dziuk, Convergence of a finite element method for non-parametric mean curvature flow, Num. Math. 72, 197 (1995) 22. G. Dziuk, Algorithm for evolutionary surfaces, Num. Math. 58, 603 (1991) 23. G. Dziuk, Convergence of a semidiscrete scheme for the curve shortening flow, Mathematicals Models and Methods in Applied Sciences 4, 589 (1994) 24. G. Dziuk, Discrete anisotropic curve shortening flow, SIAM Journal on Numer. Anal. 36, 1808 (1999) 25. C M . Elliott, M. Paolini, R. Schatzle, Interface estimates for the fully anisotropic Allen-Cahn equation and anisotropic mean curvature flow, Mathematical Models and Methods in Applied Sciences 6, 1103 (1996) 26. L.C. Evans, J. Spruck, Motion of level sets by mean curvature I, J. Diff. Geom. 33, 635 (1991) 27. M. Gage, R.S. Hamilton, The heat equation shrinking convex plane curves, J. Diff. Geom. 23, 285 (1986) 28. P.M. Girao, Convergence of a crystalline algorithm for the motion of a simple closed convex curve by weighted curvature, SIAM J. Numer. Anal. 32, 886 (1995) 29. M. Grayson, The heat equation shrinks embedded plane curves to round points, J. Diff. Geom. 26, 285 (1987) 30. M. Gurtin, Thermomechanics of Evolving Phase Boundaries in the Plane, Clarendon Press, Oxford, 1993
194
31. A. Handlovicova, K. Mikula, A. Sarti, Numerical solution of parabolic equations related to level set formulation of mean curvature flow, Cornput. Visual. Sci. 1, 179 (1998) 32. W. Jager, J. Kacur, Solution of porous medium type systems by linear approximation schemes, Num. Math. 60, 407 (1991) 33. W. Jager, J. Kacur, Solution of doubly nonlinear and degenerate parabolic problems by relaxation schemes, Mathematical Modelling and Numerical Analysis 29, 605 (1995) 34. P.L. Lions, Axiomatic derivation of image processing models, Mathematical Models and Methods in Applied Sciences 4, 467 (1994) 35. J. Kacur, Solution of some free boundary problems by relaxation schemes, SIAM J. Numer. Anal. 36, 290 (1999) 36. J. Kacur, A. Handlovicova, M. Kacurova, Solution of nonlinear diffusion problems by linear approximation schemes, SIAM J. Numer. Anal. 30, 1703 (1993) 37. J. Kacur, K. Mikula, Solution of nonlinear diffusion appearing in image smoothing and edge detection, Applied Numerical Mathematics 17, 47 (1995) 38. J. Kacur, K. Mikula, Slow and fast diffusion effects in image processing, Comput. Visual. Sci. 3, to appear 39. J. Kacur, K. Mikula, Slowed anisotropic diffusion, in Proceedings of ScaleSpace Theory in Computer Vision (ed. by B.t.H.Romeny, L.Florack, J.Koenderink, M.Viergever), Lecture Notes in Computer Science 1252, Springer, 357 (1997) 40. M. Kass, A. Witkin, D. Terzopulos, Snakes: active contour models, International Journal of Computer Vision 1, 321 (1987) 41. M. Kimura, Accurate numerical scheme for the flow by curvature, Appl. Math. Letters 7, 69 (1994) 42. M. Kimura, Numerical analysis for moving boundary problems using the boundary tracking method, Japan J. Indust. Appl. Math. 14, 373 (1997) 43. R. Malladi, J.A. Sethian, B. Vemuri, Shape modeling with front propagation: a level set approach, IEEE Trans. Pattern Analysis and Machine Intelligence 17, 158 (1995) 44. H. Matano, Non-increase of the lap-number of a solution for a one dimensional semilinear parabolic equation, J. Fac. Sci. Univ. Tokyo Math. 29, 401 (1982) 45. K. Mikula, Solution of nonlinear curvature driven evolution of plane convex curves, Applied Numerical Mathematics 23, 347 (1997) 46. K. Mikula, J. Kacur, Evolution of convex plane curves describing anisotropic motions of phase interfaces, SIAM J. Scientific Computing
195
17, 1302 (1996) 47. K. Mikula, A. Sarti, C. Lamberti, Geometrical diffusion in 3Dechocardiography, in Proceedings of ALGORITMY'97 - Conference on Scientific Computing, West Tatra Mountains - Zuberec, 167 (1997) 48. K. Mikula, Numerical experiments on geometry driven diffusion with application to image processing, in Science and Supercomputing at CINECA, 1997 Report (Ed. M.Voli, CINECA Supercomputing Group), 689 (1998) 49. K. Mikula, N. Ramarosy, Semi-implicit finite volume scheme for solving nonlinear diffusion equations in image processing, Num. Math., to appear 50. K. Mikula, A. Sarti, F. Sgallari, Models and numerical methods for nonlinear multiscale analysis of 3D image sequences, submitted 51. K. Mikula, D. Sevcovic, Solution of nonlinearly curvature driven evolution of plane curves, Applied Numerical Mathematics 3 1 , 191 (1999) 52. K. Mikula, D. Sevcovic, Evolution of plane curves driven by a nonlinear function of curvature and anisotropy, SIAM J. Appl. Math., to appear 53. L. Moissan, Affine plane curve evolution: A fully consistent scheme, IEEE Transactions on Image Processing 7, 411 (1998) 54. R. Nochetto, M. Paolini, C. Verdi, Sharp error analysis for curvature dependent evolving fronts, Mathematical Models and Methods in Applied Sciences 3, 711 (1993) 55. K.N. Nordstrom, Biased anisotropic diffusion - a unified approach to edge detection, Preprint, Department of Electrical Engineering and Computer Science, UC Berkeley (1989) 56. S. Osher, L. Rudin, Feature oriented image enhancement using shock filters, SIAM J. Numer. Anal. 27, 919 (1990) 57. S. Osher, J.A. Sethian, Front propagating with curvature dependent speed: algorithms based on the Hamilton- Jacobi formulation, J. Comp. Phys. 79, 12 (1988) 58. M. Paolini, Fattening in two dimensions obtained with a nonsymetric anisotropy: Numerical simulations, Acta Math. Univ. Comenianae 67, 43 (1998) 59. P. Perona, J. Malik, Scale space and edge detection using anisotropic diffusion, In Proc. IEEE Computer Society Workshop on Computer Vision (Miami Beach, Nov.30-Dec.2,1987), IEEE Computer Society Press, Washington, 16 (1987) 60. Bart M. ter Haar Romeny (Ed.), Geometry driven diffusion in computer vision, Kluwer, Dodrecht, 1994 61. L.I. Rudin, S. Osher, E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D 60, 259 (1992)
196
62. G. Sapiro, A. Tannenbaum, On affine plane curve evolution, J. Funct. Anal. 119, 79 (1994) 63. G. Sapiro, A. Tannenbaum, Affine invariant scale space, International Journal of Computer Vision 11, 25 (1993) 64. G. Sapiro, A. Tannenbaum, Invariant curve evolution and image processing, Indiana Univ. Journal of Math. 42, 985 (1993) 65. G. Sapiro, A. Tannenbaum, Area and length preserving geometric invariant scale-spaces, IEEE Trans. Pattern Analysis and Machine Intelligence 17, 1066 (1995) 66. A. Sarti, K. Mikula, F. Sgallari, Nonlinear multiscale analysis of 3D echocardiographic sequences, IEEE Transactions on Medical Imaging 18, 453 (1999) 67. A. Schmidt, Computation of three dimensional dendrites with finite elements, J. Comp. Phys. 125, 293 (1996) 68. A. Schmidt, Approximation of crystalline dendrite growth in two space dimensions, Acta Math. Univ. Comenianae 67, 57 (1998) 69. J.A. Sethian, Numerical algotithm for propagating interfaces: HamiltonJacobi equations and conservation laws, J. Diff. Geom. 3 1 , 131 (1990) 70. J. A. Sethian, Level Set Methods. Evolving Interfaces in Geometry, Fluid Mechanics, Computer Vision, and Material Science, Cambridge Monographs on Appl. and Comp. Mathematics, Cambridge University Press, 1996 71. J.A. Sethian, Adaptive fast marching and level set methods for propagating interfaces, Acta Math. Univ. Comenianae 67, 3 (1998) 72. T. Ushijima, S. Yazaki, Convergence of a crystalline algorithm for the motion of a closed convex curve by a power of curvature V = Ka, SIAM J. Numer. Anal. 37, 500 (2000)
197 A N A D A P T I V E S C H E M E O N U N S T R U C T U R E D G R I D S FOR THE SHAPE-FROM-SHADING PROBLEM
MANUELA SAGONA Dipariimento di Matematica e Applicazioni, Universita di Napoli "Federico II" via Cintia, 80126 Napoli, Italy, E-mail: [email protected] ALESSANDRA SEGHINI Dipariimento di Matematica, Universita di Roma "La Sapienza" P. Aldo Moro 2, 00185, Roma, Italy E-mail: [email protected] We present some experiments related to the numerical approximation of the viscosity solution of the Hamilton-Jacobi equation with singular coefficients for the Shape-from-Shading problem. The paper is focused on the implementation of a semi-lagrangian algorithm on a triangular grid which can be refined according to some numerical indicators. Since semi-lagrangian schemes allow large time steps, it is crucial to construct a suitable hierarchical data structure that can locate the triangle containing the foot of the characteristic with a small computational load. We will discuss a recursive procedure which solves efficiently this problem. In the numerical tests, we will compare different numerical indicators which can be used to define a strategy for refining the mesh.
Keywords:
adaptive space discretization, Hamilton-Jacobi-Bellman equation, semi-Lagrangian scheme A M S Classification: 49L25, 65M12, 65M50
1
Introduction
One of the most important elements which determines the computational cost of the numerical solution of a PDE is the number of nodes of the space discretization. High-order interpolation techniques or grid adapting strategies are normally used to minimize the dimension of discrete problems without loss of accuracy (Bern et al. 4 , Eriksson et al. 1 0 ) . In this paper we present an adaptive scheme to solve the Eikonal equation related to the Shape-from-Shading (SFS) problem (see Horn-Brooks 1 5 and references therein) with a single vertical light source |v«(i)|=/(i),iefi
u(x) = o,
xedn
m
{>
198
where fi is an open and bounded domain in 1R2 and f(x) > 0 for all x € fi. As it is well known, this equation can be derived from the Image Radiance Equation R(n(x)) = I{x)
(2)
where I{x) is the brightness function measured at each point x of the domain of a Lambertian surface u(x) and R(n(x)) is the reflectance map, giving the value of the reflected light on the surface u as a function of its normal n at each point x. The Eikonal equation (1) is a first order Hamilton-Jacobi equation. Under the assumption f(x) > 0 for all x e fi , the theory of viscosity solutions guarantees the existence and uniqueness of viscosity solution (for more details see Bardi-Capuzzo Dolcetta 1). If the set K = {x € fi : f(x) = 0} is not empty the solution is no longer unique (cfr. Lions et al.17-18) but, requesting a stronger condition on the supersolution, it is possible to prove the uniqueness of the maximal solution (Ishii-Ramaswamy 16 , Camilli-Siconolfi 7 ) . Many authors have proposed numerical schemes to approximate the solution of (1). There are two different way to proceed. The first one is to impose some additional conditions on the solution at the points where / = 0 and discretize the problem, as in Rouy-Tourin 19 . The other possibility is to bound / from below at some level e > 0 so that the related truncated problem has a unique viscosity solution ue. Then u e is computed discretizing the equation directly. In Camilli-Grune 6 it has been proved that the sequence ut converges to the maximal solution of the original problem as e and the discretization parameters tend to 0 (respecting some compatibility conditions). In this paper we follow the last approach using a semi-lagrangian scheme on a triangular grid. This grid allows to follow the domain silhoutte better than a structured grid. However on an unstructured grid it is difficult to locate the triangle containing a given point x 6 fi, f.e. the foot of the characteristics. We construct a hierarchical data structure to "order" the simplices of the triangulation, this procedure allows to solve the localization problem minimizing the number of triangles to be examined. Moreover, we propose an adaptive grid strategy based on an a-posteriori local error given by the difference between the original image and the image corresponding to the approximated solution. This refinement indicator is strictly related to the SFS problem where we can compare the known image intensity I to the computed brightness intensity which is a function of the approximate solution (in fact I depends on the gradient of the solution u). That kind of refinement indicator can be used in every problem where a known data can be expressed as function of the solution, therefore it is possible an a-posteriori comparison.
199
The paper is organized as follows. In Section 2 we introduce the SFS model and the related fully discrete scheme obtained with a double step discretization. In Section 3 we define the local error and we prove that it can be used as refinement indicator for the adaptive grid strategy proposed in Section 4. The computational details are described in Section 5 where we focus our attention on the construction of the hierarchical data structure used to "order" the triangular grid. Finally, in Section 6, we discuss some numerical tests and we compare our results with the results obtained by the refinement strategy based on the error indicator proposed in Griine 14 . 2
A fixed grid fully discrete scheme
Let us consider a Lambertian surface given as a graph z — u(x), x € H 2 . We assume that u > 0 and supp(u) C fi, where fi is an open and bounded subset of H 2 . Moreover we assume to have a single light source at infinity so that all the rays are parallel. Let us denote by CJ the unitary vector pointing in the direction of the light source and by n(x) the normal to the surface at each point x € fi. Under these assumptions the irradiance equation (2) becomes: I(x)=n-u=
, xen (3) y y/l+ | Vu(l) | 2 a first order nonlinear Hamilton-Jacobi equation (cfr. Horn-Brooks 15 , LionsRouy-Tourin 18 and references therein). Now and in the sequel we study the vertical light case corresponding to the choice u = (0,0,1). By substitution in (3) we get the eikonal equation (1) where / is the function
^^vw
- 1 ,
0<1{x) 1
--
(4)
Since (3) depends only on the gradient of u, we have to add a boundary condition. Assuming that the surface lies on a plane we can complement the equation with the Dirichlet homogeneous boundary condition. Note that for a surface given as a graph we do not have shadows in the case of vertical light. In this case I(x) can vanish only at the inflection points with vertical tangent for u. To avoid this we suppose that there exixts £ > 0 such that I(x) > £ > 0,
x € n
(5)
so that / is bounded from above with ||/||oo < \ js ~ 1In order to have an approximation scheme in the form of a fixed point problem,
200
we use the equivalence |VuOr)|=
max: { - a - V u ( x ) } ,
(6)
a€C-O2(0 f l)
where the maximum is achieved for a* = - , ^ r ,, and we apply the Kruzkov change of variable v(x) = l-e~uW.
(7)
Note that by definition 0 < v(x) < 1. In the new variable v the problem (1) becomes (v(x) + max ( - 7 n y V » ; ( i ) - l ) = 0, z £ f i I aedB2(0,l) I ' W J
I u(x) = 0
(8)
xeon
The theory of viscosity solutions guarantees that there exists a unique solution of the first order Hamilton-Jacobi-Bellman equation (8) provided / is Lipschitz continuous in ft and never vanishes in fi. If there are maximum brightness points where I(x) — 1, i.e. f{x) = 0, the solution is no longer unique. These points correspond to local maxima or minima or saddle points of u and only knowing the brightness function, we can not distinguish between convex regions from concave. This is the ambiguity of the model which produces infinitely many admissible solutions. However, Ishii-Ramaswamy 16 proved the uniqueness of the maximal solution provided I is continuous, a Dirichlet boundary condition is given and the set of maximum brightness points is a set of isolated points. Camilli-Siconolfi 7 give a new stronger notion of supersolution and generalize this result in the case of maximum brightness points set with null intersection with the domain boundary. Following the approach used in Camilli-Grune 6 and in Falcone-Sagona 12 , we cut off / so that / is bounded from below and we define a new brightness function I p (a:)=min {/(*), 1 - p }
(9)
where 0 < p < 1. This implies that / > J(1} ,$ - 1. From now on we refer to the truncated problem {vp{x)+ max ( - 7 7 ^ • Vvp{x) - l ) = 0, x € fi py I PK aedB2(o,i) I fpW J (10) [vp(x)=0 xedfi where fp is the function / related to the brightness Ip. We use a semi-lagrangian scheme (see Bardi-Falcone 2 , CamilliFalcone 5 ) to compute the solution of (10) on a regular triangulation 5 of
201
Q, with a finite number of simplices Sj,j — 1,... ,M. Here and in the sequel we assume that fi = supp(u). Let use denote by Xi the nodes, i = 1 , . . . , N, by k the maximum diameter of simplices, by h = (hi,..., /ijv) G K N the vector of the time steps, where hi is related to the node Xi, and by A = (H, hi,. •., ftjv) the set of discretization parameters. We look for the solution wA of (10), related to the regular triangulation 5, in the space of the piecewise affine function Wk (Pi finite elements approximation): Wk = {w€ C(tt)\ Vw = Cj in Sj,j = 1 , . . . , M).
(11)
The fully discrete scheme is >f(xi)= wf(xi)
min
e-hiw£(xl+hiTf-T)}+(l-e-hi)Jorxien\dn
{
= 0,
for Xi € dQ.
With the same arguments used in Bardi-Falcone 2 , it is easy to prove that the numerical solution of the previous scheme exists and is unique. It can be computed by a fixed point iteration on the operator T A : M N —• ]RN f min {e-hA(a)V}i + l-e-h<,Xi efl\dQ (T (V))i = I a€9i?2(0,l) (12) {0 XiEdtt where V is the N-dimensional vector containing the values at the nodes of the simplices, i.e. Vi — wf(xi) and A (a) is the matrix of the local coordinates of the points Xi + hif ?,. More precisely, the i-th raw of A(o), a 6 dB2(0,1), contains the elements Ay (a), j = 1 , . . . , JV, having the following properties: A
N
0 < Xij (a) < 1,
N a
^2 ^j ( ) = 1,
Xi + hi
= Y] \tj (a)xj fp[Xi)
i=i
i=\
A
It is easy to prove that the operator T defined in (12), has the following properties: T h e o r e m 2.1 Let TA be the operator defined in (12) then: 1. 0 < V < 1 implies 0 < TA(V) 2. U < V implies TA(U)
<
<1
TA(V)
3. TA is a contraction mapping in H N with contraction factor j3 — e~hmin with hmin — min ihA. i=l,..,N
202
In particular, the third property guarantees that there exists a unique fixed point VA, VA = T A ( V A ) , which can be computed as the limit in the recursive sequence Vm+1 = TA{Vm) r ° given
*• '
The monotonicity property implies that, starting from a subsolution V° (i.e. V° < TA(V0)), the sequence monotically converges to the fixed point VA. If we want to compute the solution at the nodes of the grid E with accuracy e > 0, we shall stop the fixed point iterations when \\Vm - V " 1 - 1 ^ < e (1 - /?). In fact it can be easily seen that if
| | T / - T A ( 1 / ) | | 0 0 < 5, 6>0
then
\\V - V^
<
S
1-/?
since
l l ^ - v A | | o c < l | v - T A ( y ) | | 0 0 + ||T A (y)-r A (y A )|| 0 0 <<5 + /3 ||v-i/ A ||oc which implies the assertion. For different choices of h the sequence Vm converges towards one of the admissible solutions. For all nodes n € ft, let Di = Uj=i {Sj '• Xj £ Sj} and let di = dist(xi,dDi). It has been proved (Falcone-Sagona 12>13) that if
% * ik
<14)
then the sequence Vm converges to the maximal solution of (10). In fact, if we choose hi such that Xi + hi , . , 6 A , for every ae dB2{0, l),i = l,...,N
(15)
fp{Xi)
the information propagates from the boundary and by the monotonicity of the scheme the sequel reaches the maximal solution. Numerically it's possible to see that if we choose hi such that "•i
Jp\Xi)
we also have the convergence towards the maximal solution. Clearly the solution computed by the above algorithm (13) depends on the discretization A and on the value p. To emphasize this dependence we denote by vA £ Wk the piecewise linear function obtained as linear interpolation of VA € 1RN. An a-priori estimate for the convergence of the scheme is given in Falcone et al. 3 , n provided / is lipschitz continuous and truncated.
203
3
A local error indicator
As we said in the introduction, our aim is to define a grid refinement criterion to achieve "a good" accuracy in the computation of the surface representing the object in the SFS reconstruction with a relatively small number of nodes. To this end we introduce an a-posteriori local error based on the difference between the original brightness of the image and the brightness related to the reconstructed surface. Let uf be u* = - l o g ( l - « * )
(17)
and let l£ be the piecewise constant brightness function computed on the reconstructed surface uf, i.e. lf{x)
= —=
forxens
(18)
yjl+ I V<(x) P where Qs = ft \ Uj=i 9Sj. Definition 3.1 For every x € Qs we define the error E{x)=\Ip(x)-lf{x)\
(19)
and for every simplex Sj of E we define Ej =
max
E{x)
(20)
x€Sj\dSj
Using the irradiance equation (3), it is possible to give a geometric interpretation of the error E(x), observing that E(x) =| cos(ap(x)) - cos(af(x))
|
where ap(x) is the angle between the normal to the surface at the point (x,up(x)) and w, and af(x) is the angle between the normal to the reconstructed surface at the point (x,u£(x)) and CJ. In order to give a convergence result related to this local error we introduce the following lemmas. Lemma 3.2 If E(x)
+ ri
x£tts.
204
Proof Since we use P\ finite elements approximation | Vw^ | is bounded and then Ip^(x) > 0, for every x € fis. For the second inequality we observe that | 7p(x) — lf(x) \< r\ implies I^(x)
•
Lemma 3.3 Under the assumptions of Lemma 3.2, we have V
Vvf{x)\-\Vvp{x)\\<
1
ZI*(xWl-{l-p
X t
1«J
+ 7,)*
Proof By the monotonicity property of the recursive scheme (13) follows that uf(x) < uP(x), for all a; £ fi. Hence using Kruzkov change of variable we have Vvp(x) | - | Vvf{x) < e~<W
|| = e~u^
| Vu„(x) | - e - < ^ » | Vu*(ar)
<
|| Vu p (x) | - | V < ( x ) || < || Vu p (x) | - | V < ( x )
Moreover, y/1-(JP(»))»
VUp(x)|-|V<(x)|| =
fffrVl
yfr-(#(»))*
- (7 p (x)F - JpW^/l - (7*(z)) 2 Ip(x)I?{x) (7 p A (x)-7 p (x))(7*(x) + 7p(x))
7p(x) 7*(x) (l*(xWl
- (7,(x))2 + 7,(x)^/l - (7A(x))2)
<
??
< ^ / A ( x ) / l _ ( l - p + „)2' > where the last inequality is due to the assumption (5) and to the inequalities 1 ^l-(7^(x))
1 2
<
y/l-il-p
+ v)2
205
and Vi-(W)
<
2
<
- Vi-(i-P)2
y/i-{i-p
+ ii)2
D P r o p o s i t i o n 3.4 i e i up and u^ be respectively the unique solution and the numerical solution of (10). Moreover assume that (5) holds true and let n < p, then < r\ in fts implies \\up — u^ ||oo < C (n) in fts
\h
where C (n) tends to 0 as n tends to 0. Proof It is sufficient to prove that \\vp — u^||oo < C (rj) in fts. In fact, 11^ - u^Hoo < M \\vp - vfW^,
where M = max I ^fy
>• Note
that vp(x) y£ 1 for any x £ ft because up(x) is bounded for all x £ ft. Let us consider the continuous equation vp{x) =
VvP(x)
+ 1,
for x £ ft
(21)
for x £ ft*
(22)
obtained from (1) using (7) and let us define
(W) 2
-1,
Hence, for all x £ fts \vP(x) ~ ^ ( * ) | =
Vvp(x) |
fM
adding and subtracting | S7vp(x) | /f^{x) A
| V/ ,(z) - < ( x ) |
.
II Vv^(x) < U
P
I - | VvJx) ,'A/,,'
tf(s)
+
| Vvf(x)
(23)
#(*) in (23) we obtain ,, + I V»P(S)
#(*)
AW
The second term of the right-hand side of the last inequality can be bounded as follows
206
<
(lf(x)-Ip(x))(lf(x) l-a-p+r?)2
If (X) VI - {IMY
+ Ip{x))
+ h (X)
y/l-(I*(x))*
<
1 ( l - ( l - p + r?)2)3/2Then, by the last inequality and Lemma 3.3 we get
which ends the proof.
• 4
The adaptive grid algorithm
In this section we present an adaptive grid algorithm to solve the problem (10). In order to define a strategy of grid adaptive refinement, we want to select all the simplices belonging to the triangulation E, which have a large Ej, j = l,...,M. The exact evalutation of a-posteriori local error Ej defined in (20), involves the computation of I at all points belonging to Sj \ dSj, which is unfeasible. However the Lipschitz continuity condition on / implies the Lipschitz continuity of the brightness function / and this guarantees that Ej can be approximated using Ej =
max
E{zk)
(24)
zh&Sj\dSj
for finitely many test points z\. € Sj \ dSj. More precisely, it easy to show that if / is a lipschitz continuous function then \Ej - Ej\ < Lj • diam(Sj),
for any j = 1 , . . . , M
where diam(Sj) = max{| z\ — z2 \: z\,Z2 € Sj} and Li denotes the Lipschitz constant of i\ The following definition introduces a weighted a-posteriori local error, that we will use as refining indicator. Definition 4.1 For every simplex Sj € E we define the weighted local error Ej=Pj-Ej,
j = l,...,M
(25)
207
where Pj is the weight of simplex Sj and it is given by _
area(Sj) Y^fLi area(Si)
The grid adapting scheme can be described as follows: Step 0: choose the accuracy e > 0 to compute the fixed point related to a given grid 5; choose the refinement parameters tol > 0 and 9 6 (0,1); construct the initial grid HoSet n = 0 Step 1: let Nn and Mn be respectively the number of nodes and the number of simplices belonging to the grid E n ; compute the time steps hn — (/i™,..., /ijv ) ; choose the initial value 1/An,° for the fixed point iterations and compute the solution VA" € H N n related to the grid E n with e accuracy; Step 2: compute the refinement indicators Ej, j = 1 , . . . , Mn, H^IU = . max {Ej} and \\E\\X = £ £ - Ej j=l,...,Mn
W\\E\\i<
J
tol THEN stop ELSE continue with Step 3
Step 3: construct the new grid H n + i , refining all the simplices Si such that Ei > OWEWaa + {I - 6)\\E\\i/Mn with the necessary neighbouring refinements which guarantee that H n + 1 is regular. Let n — n + 1 and go to Step 1 In the numerical tests (see Section 6) one can observe that ||i?||i tends monotonically to zero and the refinement iteration ends with a grid H*. Note that E{x) is bounded in tts, so that H-EHoo tends to 0 when the areas of the simplices tend to 0. As it is possible to observe in the tables related to the examples proposed in Section 6 this convergence is not, in general, monotone. In the adapting process, it is possible to use the solution VAn corresponding to the grid H n to compute the initial value for the fixed point iterations on the new grid Zn+i- In fact we can define the starting solution on every new node (added to H n ) as the minimum of V A n computed on the vertices of the simplex of E n containing the new node. This choice guarantees that the initial value for the new grid is still a subsolution and the convergence of the recursive scheme defined in (13).
208
The above algorithm allows to obtain a good space discretization for the SFS problem with a relatively small number of points without any a priori knowledge of the critical regions. 5
Implementation of the algorithm
A crucial step at each iteration is the construction of the triangulation. Several gridding techniques are available, we have used the package TRIANGLE. TRIANGLE is a C program created by J. R. Shewchuk 20 for two-dimensional mesh generation which constructs a Delaunay triangulation. In a Delaunay triangulation of a domain fi every node of the grid falls outside the circumcircle to a simplex S, excepted the vertices of S. TRIANGLE contains three Delaunay triangulation algorithms: - the incremental insertion algorithm of Lawson; - the divide-and-conquer algorithm of Lee and Schachter; - the plane-sweep algorithm of Fortune. TRIANGLE allows to impose constraint on the minimum admissible angle and this avoids the "degeneration" of the grid during the refinement iteration. The triangulation algorithm is theoretically guaranteed to succes if the minimum admissible angle is less or equal to 20.7 degrees. Different area constraints for each simplex can be easily defined and it may be useful for the refining process based on a-posteriori error estimates. In our program we have used a different refining method: the test points of all simplices with "large" weighted error, are added to the list of nodes and then TRIANGLE is called to construct a new grid based on the "enriched" list of nodes. There are several possible choices for the test points. The simplest one is to use the barycenter as the only one test point in each simplex. One more reasonable choice is to use in each simplex the barycenters of the four triangles obtained dividing the edges of the simplex in the midpoints. Another critical point in the algorithm is to locate the triangle containing a point z € 0 with a fast and memory efficient method. This is essential for the implementation of semi-lagrangian schemes which allow large time steps and need to determine the simplex containing the foot of the characteristic with a small computational load. The foot of the characteristic falls in general far away from the starting point (see Fig. 1). Our goal is to construct a suitable hierarchical data structure which, "sorting" triangular grid, allows to minimize the number of simplices to be examined. Definition 5.1 Let R be a rectangle, q > 0 and C0 a subset of set { 1 , . . . , M}
209
Figure 1. Use of "sorting grid" to locate the foot of the characteristic
of indices of simplices ofE. A Sorting Grid Sg(R,E,C0,q), 1) the rectangle R (defined f.e. right"); 2) a subset C(R,E,C0)
consists of:
by the two vertices "down-left" and "up-
of the set C0;
3) a pointer ptr to a list of sorting grids; and it is constructed by the following recursive process: 1) construct the set of indices C(R, E, C0) = {j € C0 \ Sj D R ^ 0} 2) IF card{C(R,E,C0)) < q THEN set ptr.to point to null and STOP ELSE divide R in submeshes R\, R2, •.., construct on every submesh Rk the sorting grid Sg(Rk, E, C(R, E, C0),q) and set ptr to point to the list of the sorting grids related to the submeshes The recursive algorithm is guaranteed to end if q > 2it/amin where a m i„ is the minimum angle in the triangular grid E. In this way, starting from R, the smallest rectangle containing the domain Cl, and C = {1, . . . , M } , it is possible to construct the sorting grid Sg(R,E,£,q), that allows to locate the triangle containing a given point of
210
Q, examining at most q simplices. To determine this triangle, we first locate the rectangular cell containing the point and we descend recursevely in the submeshes. At the end of this process, we examine only the triangles associated with the final mesh (see Fig. 1). In our program, the first partition of R in rectangular mesh is realized using the same step k on the vertical and horizontal directions, i.e. the step is the maximum edge of the triangles of E. Then, if a mesh has to be refined, it is divided into four submeshes using the midpoints of the edges of the mesh. 6
Numerical experiments
We discuss three 3-dimensional surface reconstructions with vertical light. Following Falcone-Sagona 12 , we have always made a cut-off of the brightness function I at the level 0.99 (p — 0.01). This cut-off is necessary since a/f "blows up" at the points of maximum brightness, where I(x) = 1. All grids have been constructed using TRIANGLE with a m j„ = 20°. The time steps hi,..., /ijv must satisfy (15). In the tests, the fixed point has been computed with an accuracy e = 10~ 5 . The weighted local errors Ej, j = 1 , . . . , M, defined in (25) have been calculated on each simplex Sj using only one test point, the barycenter of the simplex. The refinement strategy, in particular its speed, strongly depends on the choice of the parameter 8 which allows to move the refinement threshold more or less close to ||15||oo- The reported results are related to 0 = 0.1 To describe the adapting procedure, for each experiment we give a table which shows the number of nodes (TV) for the adaptive iterations, the corresponding number of fixed point iterations (Nit) and the related errors ||i?||oo and \\E\\i. Note that ||IS||i is the numerical equivalent of the normalized L1 norm of the error E(x) defined in (19).
a
)
b)
c)
Figure 2. Canadian tent: a) Input image, b) image on the adaptive grid (JV = 2288), c) image on the fixed grid (JV = 2288)
In the first experiment the surface is a "Canadian tent" on fi := [0,2] x [0,1]. In this case the input brightness image (Fig. 2a)
211
e = 0.00001 tol = 0.008 9 = 0.1 #grid 0 1 2 3 4 5 6 7 8 9 10 11 12
N 104 108 127 183 244 317 482 642 805 976 1347 1725 2288
Nu, 13 16 31 38 40 38 59 57 58 59 80 82 83
Halloo .375018E-01 .931529E-02 .249985E-02 .141146E-02 .890703E-03 .308148E-03 .212311E-03 .177722E-03 .136751E-03 .624679E-04 .482687E-04 .292944E-04 .214232E-04
\\E\\x .131986E+00 .830018E-01 .639046E-01 .503079E-01 334384E-01 .270257E-01 .195739E-01 .152417E-01 .131040E-01 .114376E-01 .955142E-02 .842088E-02 .711270E-02
Table 1. Canadian tent: refinement iterations
Fixed Grid Fixed Grid Adaptive Grid
N 2288 5038 2288
Halloo
Plli
.149730E-03 .722984E-04 .214232E-04
.112723E-01 .783426E-02 .711270E-02
Table 2. Canadian tent: errors comparison
has only two grey levels and it is not a continous function. The adaptive grid algorithm described in Section 4 starts from a coarse grid with N = 104 nodes. The required tol = 0.008 is obtained after 12 refinement iterations on a final grid with JV = 2288 nodes (see Table 1). Figures 2b and 2c show respectively the image computed on the surface obtained on the adaptive grid and the image computed on the surface reconstructed on a fixed grid with the same number of nodes (N = 2288). Figure 3 shows the final grid (N = 2288, k ~ 0.087) and the reconstructed surface. As it is pointed out by the figures the adaptive algorithm refines mostly the simplices along the corners and the image on the adaptive grid is better than the image on the fixed grid. It is interesting to observe that to obtain roughly the same accuracy on the final image on a fixed grid, we need more than 5000 nodes (see Table 2).
212
Figure 3. Canadian tent: adaptive grid (N = 2288) and related solution
The other two examples are the reconstruction of a real-grey-level image representing a vase (Fig. 4a) and the plaster of a nai've elk (Fig. 5a) (the elk image has been kindly given by Daniel 8 ) . For each example we give three different numerical tests. Tables 4 and 6 show a comparison of the results related to the three different tests, respectively on the vase and on the elk. The first refers to a fixed grid. In the second test we have used the adaptive grid algorithm described in Section 4 starting from a coarse grid and using the weighted local error Ej, j = 1 , . . . , M defined in (25) as refinement indicator. We have just stopped the adaptive iterations when the error ||I?|[i becomes less than the error obtained on the fixed grid. In both experiments the nodes number of the adaptive grid is less than 54% of the nodes number of the fixed grid. Table 3 and 5 show respectively the adapting procedure for the reconstruction of the vase and of the elk. Figure 6 shows the 10th grid (N = 2805) obtained with the adaptive algorithm on the elk. It is evident that the triangles gather along the elk's features. In the third test we have used the same adaptive grid algorithm with a different refinement indicator. In this case the adapting iteration is based on the aposteriori weighted local error estimate rjj given by: Vj=Pj-r}j,
j = l,...,M
(26)
where pj is defined in (4.1) and rj^
max
\vA(Zk)-TA(vA(zk))\
Also in this case, we have computed the local error estimate rjj using only one test point, the barycenter of the simplex. The properties of this a-posteriori error estimate are investigated in Grune 14 .
213
In both experiments the two different refinement indicators and the related adaptive strategies give similar results. The difference between the errors ||f)||i on the final grids obtained with the two different adaptive strategies is an o(10 - 7 ) on both examples. The difference between the errors p | | i is an o(10~ 5 ) on the vase and an o(lCT4) on the elk. As it could be seen in Fig. 4 and Fig. 5, the images obtained computing the brightness intensity If on the surface reconstructed on the three different grids show that the adaptive strategies give always a good solution. e = 0.00001 tol = 0.012 6 = 0.1 #grid 0 1 2 3 4 5 6 7 8 9 10 11 12 13
N 420 459 529 693 945 1194 1599 2043 2618 2942 3075 4609 5265 6535
Nit
22 27 34 47 46 72 73 79 83 87 72 118 119 139
Plloo
Plli
.487719E-02 .234824E-02 .642118E-03 .323569E-03 .256961E-03 .130157E-03 .929395E-04 .637324E-04 .696375E-04 .755735E-04 .190254E-04 .281856E-04 .169238E-04 .106094E-04
.104901E+00 .795536E-01 .585614E-01 .437873E-01 .351911E-01 .294628E-01 .252086E-01 .224363E-01 .195081E-01 .181231E-01 .173684E-01 .147252E-01 .132936E-01 .119860E-01
Table 3. Vase: refinement iterations
FG AG (£) AG(rj)
N 12121 6535 6870
Plloo
Plli
.312125E-04 .106094E-04 .255884E-04
.120697E-01 .119860E-01 .119966E-01
INIloo .162286E-07 .844313E-08 .157384E-07
llflli .972619E-05 .106040E-04 .102924E-04
Table 4. Vase: comparison between the fixed grid (FG) algorithm and the two adaptive grid (AG) algorithms
e = 0.00001 tol = 0.015 9 = 0.1 #grid 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
iV 650 663 708 804 926 1085 1318 1623 2031 2263 2805 3468 4614 6405 7987 9181 11567
Na 21 24 38 41 45 52 66 83 93 81 96 105 112 130 137 143 152
Plloo
Plli
.110986E-01 .394390E-02 .171723E-02 .908864E-03 .526450E-03 .300608E-03 .185477E-03 .119143E-03 .123922E-03 .704508E-04 .510832E-04 .304054E-04 .181048E-04 .169135E-04 .161074E-04 .102526E-04 .678794E-05
.708690E-01 .755286E-01 .656480E-01 .482032E-01 .399374E-01 .344333E-01 .325082E-01 .285958E-01 .263947E-01 .247349E-01 .232196E-01 .219807E-01 .204161E-01 .187876E-01 .174254E-01 .166357E-01 .153389E-01
Table 5. Elk: refinement iterations
FG AG (E) AG (T))
N 23529 11567 11677
Halloo .131766E-04 .678794E-05 .491460E-05
Plli
Nloo
llflli
.157276E-01 .153389E-01 .154571E-01
.450841E-08 .380023E-08 .183897E-08
.547170E-05 .559804E-05 .544393E-05
Table 6. Elk: comparison between the fixed grid (FG) algorithm and the two adaptive grid (AG) algorithms
Figure 4. Vase: a) input image, b) image on the fixed grid (N = 12121), c) image on the adaptive grid related to E (N = 6535), d) image on the adaptive grid related to fj {N = 6870).
216
^i;ftik? Figure 5. Elk: a) input image, b) image on the fixed grid (JV = 23529), c) image on the adaptive grid related to E (N = 11567), d) image on the adaptive grid related to r) (JV= 11677).
217
Figure 6. Elk: 10th adaptive grid related to E (N = 2805).
Figure 7. Vase: Computed solution on the adaptive grid related to E (N = 6535).
8
1. M. Bardi and I. Capuzzo Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman equations, Birkhauser, Boston, 1997. 2. M. Bardi and M. Falcone, "An approximation scheme for the minimum time function", SIAM Journal of Control and Optimization, 28 1990, 950-965. 3. M. Bardi and M. Falcone, "Discrete approximation of the minimal time function for systems with regular optimal trajectories", in A. Bensoussan, J.L. Lions (eds.), "Analysis and Optimization of Systems", Lecture Notes in Control and Information Sciences, n. 144, Springer-Verlag, 1990, 103112. 4. M. W. Bern, J. E. Flaherty, M. Luskin, Grid generation and adaptive algorithms, New York, Springer, 1999. 5. F. Camilli and M. Falcone, "An approximation scheme for the maximal solution of the shape-from-shading model", Proceedings ICIP 96 "International Conference on Image Processing", IEEE Inc., 1996, 49-52. 6. F. Camilli and L. Grime, "Numerical Approximation of the Maximal Solutions for a Class of Degenerate Hamilton-Jacobi Equations", SIAM J. Numerical Analysis 38 2000, 1540-1560 7. F. Camilli and A. Siconolfi, "Maximal Subsolution for a Class of Degenerate Hamilton-Jacobi Problems", Indiana University Mathematics Journal, Vol. 48, No. 3 (1999) 8. P. Daniel, "Pent-on extraire le relief d'une seul image?", These de Troisieme cycle, IRIT, Univ. Paul Sabatier, Toulouse, 2000. 9. P. Daniel, J.D. Durou, "Creation of Real Images which are Valid for the Assumptions Made in Shape From Shading", ICIAP' 99 Proceedings 10th International Conference on Image Analysis and Processing, 1999. 10. K. Eriksson, D. Estep, P. Hansbo, C. Johnson, "Introduction to adapting methods for differential equations", Acta Numerica, 1995, 105-158, Cambridge Univ. Press, Cambridge, 1995. 11. M. Falcone, "The minimum time problem and its applications to front propagation", in A. Visintin e G. Buttazzo (eds) , Motion by mean curvature and related topics, De Gruyter Verlag, Berlino, 1994 12. M. Falcone and M. Sagona, "An algorithm for the global solution of the Shape-from-Shading model", A. Del Bimbo, "Image Analysis and Processing", Lecture Notes in Computer Sciences 1310, Springer, 1997, 596-603 13. M. Falcone and M. Sagona, forthcoming. 14. L. Griine, "An adaptive grid scheme for the discrete Hamilton-Jacobi-
219
Bellman equation", Numer. Math., 75 (1997), 319-337. 15. B.K.P. Horn and M.J. Brooks, Shape from Shading, The MIT Press, 1989. 16. H. Ishii and M. Ramaswamy, "Uniqueness results for a class of HamiltonJacobi equations with singular coefficients", Comm. Par. Diff. Eq. 20 (1995), 2187-2213. 17. P.L. Lions, Generalized solutions of Hamilton-Jacobi equations, Pitman, London,1982. 18. P.L. Lions, E. Rouy and A. Tourin, "Shape from shading, viscosity solution and edges", Numerische Mathematik, 64, (1993), 323-353. 19. E. Rouy and A. Tourin, "A viscosity solutions approach to Shape from Shading", SI AM J. Numer. Anal. 29 (1992), 867-884. 20. J.R. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator", First Workshop on Applied Computational Geometry (Philadelphia, Pennsylvania), 124-133, ACM, 1996.
221
O N A POSTERIORI E R R O R ESTIMATION FOR C O N S T A N T OBSTACLE PROBLEMS ANDREAS VEESER Institut fur Angewandte Mathematik Hermann-Herder-Str. 10, 79104 Freiburg, Germany E-mail: [email protected] A posteriori error estimators for finite element approximations to variational inequalities are derived in the model case of "Poisson's inequality" for a constant obstacle. These residual-type estimators yield global upper and, partially, local lower bounds for the true error. Further important properties are that the interior residual is localized and that the local error indicators in the discrete coincidence set measure local data resolution only.
1
Introduction
An instrumental ingredient for adaptive finite element methods are so-called a posteriori error estimators. These are quantities that are computable in terms of discrete solution and data, that split into local indicators, and that control the error between discrete and exact solution. We refer to Verfiirth 12 for a review on a posteriori error estimators. There exist several approaches to a posteriori error estimation for obstacle problems; we refer to Chen and Nochetto 3 for a short review. The case of constant obstacles is of particular interest; such obstacles arise, for example, in phase transition problems with order parameter, e.g. Chen et al. 4 , and the minimization of functionals with curvature, see Bellettini et al. x . In these applications the efficiency of the adaptive method crucially hinges on the local error indicators in the discrete coincidence set. This issue already arises in the model case of "Poisson's inequality". In Chen and Nochetto 3 these indicators consist of the interior residual, which is of order "0(/i)". Here h denotes the local meshsize. In the approach presented here, these indicators are at least of order "o(/i)" and measure local data resolution only. Consequently, they should lead to less refinement in the discrete coincidence set. The improved asymptotic behaviour is due to the localization of the interior residual, which arises from the use of numerical integration and the observation that a solution of "Poisson's inequality" for a constant obstacle satisfies a "sharper" inequality. Apart from these issues, positivity preserving interpolation by Chen, Nochetto and Wahlbin 3 ' 9 is a key ingredient in the proof of the global upper bound (as already in Chen and Nochetto 3 ) . Applications of
222
our approach (or its refined version Veeser u ) in more complicated situations are found in Chen et al. 4 as well as Fierro and Veeser 7 . The paper is organized as follows. In Section 2 we first state the continuous problem and its finite element discretization and then present our results: a global upper bound and, partially, local lower bounds for the error between discrete and exact solution. In Section 3 we prove these results. 2
Results and their discussion
We start by stating the continuous problem and its finite element approximation precisely. Let n be a bounded, polyhedral, not necessarily convex domain in Kd with d ^ 2. As usual, L2(Cl) indicates the space of Lebesgue-measurable functions that are square-integrable. Its scalar product is denoted by (•,•)• Let / S L 2 (^) and \* ^ 0 a real number. Set V := H^{U). Here H^(Q) is the subspace of 1*2 (fi) the functions of which possess weak derivatives of first order in L-i^i) and vanish on the boundary dfl. In addition, set K := {v € V | v ^ x* a -e- in Vt). The set K. is non-empty, closed in V and convex. The continuous problem reads as follows. Problem 2.1. Find u £ JC such that V^G/C
( V u , V [ u - u ] ) ^ (f,u-v).
(2.1)
It is well known that Problem 2.1 admits a unique solution, see e.g. Rodriguez 10 or Chipot 5 . For the discretization, let Vh be a regular partition of Q into (closed) simplices. Given a simplex S € Vh, we write hs for its diameter and ps for the maximal radius of a ball that is contained in 5. The shape-regularity of Vh is defined by j(Vh)
:= max — € (l,oo). sevh ps
In the sequel the same letter C will be used to denote different constants depending on the shape-regularity j(Vh)- The set of interior nodes of Vh is denoted by A//, and the one of (closed) interelement sides by Bh- Let Vh indicate the space of continuous piecewise linear finite element functions over Vh that vanish on <9f2. Its nodal basis functions are denoted by ((j>h)zeAfh- Let
223
fh G Vh. be an approximation of / . Let Ih denote the Lagrange interpolation operator onto V), and set {.Vh,i>h)h := / Ih(
for all (phyiph G V/j. Finally, let ICh be the discrete counterpart of /C, that is £ft := W G Vfc | v h ^ x . in 0 } = H G Vh | V « € Afh vh(z) > X*}The set ICh is non-empty, convex, closed and a subset of K.. The discrete problem reads as follows. Problem 2.2. Find Uh 6 ICh such that VuhG/Ch
(Vuh,V[u h -Uh]) < ( / h , u h - u h ) h .
(2.2)
Problem 2.2 admits a unique solution too. The use of numerical integration therein is crucial for the localization of the interior residual - compare the proof of Lemma 3.2. We continue by stating the results: an upper bound for the error in the energy norm ||uh — u\\v := ||V(ti/, — W)IU 2 (Q) and, for certain simplices 5 6 Vh, lower bounds for ||V(u/, — U)||X,2(S*)J where S* is a "neighbourhood" of S. To this end, we use the following notations. Let h € £oo(r2,E + ) denote the local meshsize with h\s = hs for all S G Vh- For any Vh G Vh we define the jump of V«h across an interelement edge e = Sj D 52 G Bh as [VvhJ e := ( V u h k - V u h | s 2 ) - ^ with the convention that the unit normal vector ve of e points from Si to Si. Moreover, if A is a union of simplices, we denote the set of interior interelement sides of A by Bh(A), i.e. Bh{A):={eeBh\enmt(A)^(!)}, and set 1/2 1/2
h lVvhj
L2(A)
with he denoting the diameter of e S Bh- For each vh G /Ch we define Chivh) •= {z £ Nh \ vh = x*
on
supp>h}
and the discrete auxiliary function er/i(u/,) := a/,(u/,; •) G V/, by w ^ A/\/zeMh
/• \ JA( Z )> ah{vh;z) = { 0,
z
G C/>(«h); \ otherwise.
,„ „. (2.3)
224
The discrete function c/ l (u h ) has a continuous counterpart a{v), which is defined in Section 3 below. Finally, we use the dual norm II / ||
(4>h,Vh)
h \\4>h\\vs =vh£Vh\{o} sup v
||V
for any tph e Vh. T h e o r e m 2 . 1 . Let u be the solution of Problem 2.1 anduh the one of Problem 2.2. Then there exists a constant C that depends on the shape-regularity 7(Ph.) only sucn that I K - «llv ^ C ( h}'2 [V« fc ]
+ \\h [fh - ah{uh)] || L a ( n )
+ \\h2V[fh - ah(uh)} | | i a ( n ) + \\h (A - / ) | | L 2 ( f i ) + ||/ h - f\\v.)
.
We do not want to address the issue of estimating \\fh — f\\v, which is related to the question of data approximation. In the following discussion we neglect this term or, alternatively, suppose that fh = Phf, where Ph is the orthogonal projection L^^l) ->• V),. This choice leads to \\fh — / | | y = 0 and corresponds to an optimal, but in general impractical, choice of fhTheorem 2.1 suggests to define the local error indicator n(S) for a simplex
Se Ph by V(S)2 = \
£
he\\lVuhl\\l2{e)+hl\\fh-ah(uh)\\l{s)
eCdSnQ
+ h% \\V[fh - ah(uh)}||ia(s)
+ h% \\fh -
f\\l2{s),
where "e C OS 0 f2" is an abbreviation for "e G Bh and e C <9S". Due to the definition of the auxiliary function ah{uh), we have the following equalities for the local indicator TJ(S). If «/, > ^ , on S £ Ph, then crh(uh) = 0 on 5 and, thus,
v(s)2 = \ £ eCdSnQ
M[v^]eiiL(e) + /4ll/ftllL(s) + 4l|VMIi 2(s) + /i2s||A-/Hi2(s),
which is the local indicator of the non-constrained problem with numerical integration. If z € C/i(«h) for all z 6 A//, n 5, then crh(uh) = fh on S and, thus, »7(S)a = / i | | | A - / " 2i 2 ( 5 ) -
225
In particular, the interior residual hs ||//I||L 2 (S) i s localized (with some "transition region") to simplices with Uh> X*We want to comment on this localization of the interior residual. The upper bound of Chen and Nochetto 3 is (
& 1 / 2 [V« h ] ,
+11/1/11^(0))
in the case of a constant obstacle. They considered a slightly different discrete problem: no numerical integration and no (explicit) discretization of / . Furthermore, they showed — in the case of a stable continuous coincidence set — that the interior residual ||/i/||i 2 (n) cannot be localized to the discrete coincidence set. A careful study of their example suggests that this fact is a consequence of the discretization of the right-hand side that is intrinsic to the finite element method and corresponds to the choice fa = Phf • In our analysis, ||ft/||z,2(n) is replaced by \\h[fh - oh(uh)\ || £ a ( n ) + ||/i 2 V[A - ah(uh)) | | i a ( n ) + \\h(fa - / ) | U 2 ( n ) . As illustrated above, the first two terms \\h[fh - crh(uh)}\\L2{n)
and \\h2V[fa -
crh(uh)}\\L2{n)
exhibit localization, while the third term \\h(fa — /)||i 2 (n) is n ° t localized. This latter term measures the resolution of / by fa and is of higher order than the interior residual ||/i/||z, 2 (n)- F ° r a further discussion of the importance of a term like \\h(fh — /)|U 2 (n) see Morin et al. 8 . In order to present local lower bounds of the error, we split a variant 77*(5) of the local indicator r)(S) into two parts: the principal part 77*(5) and the "data resolution" part r)*d (5). More precisely, for any S E Vh set 5* := {T G Vh I T = S or T n S £ Bh) and V*(S)3~r,;(S)2+r,*d(S)2 with
v;(s)2:=\ Yl ^ii[v«A]eiiL(e) + i^[A-^M]iiU eCdSllU
2 2 Vd(S) := \\h v[fh - ^ K ) ] ! ^ ) + |ft(fk - /)||1 2(5 , ) .
226
Moreover, we need the residual [i £ V* of the variational equation that corresponds to the variational inequality (2.1), V>eV
(/^-(Vu.Vp)-(/)¥>).
Recall that /i = 0 on an open set A C fi, if (/U,V)) = 0 holds for all test functions ip 6 C£° (A), and that supp fx denotes the complement of the maximal open set on which n vanishes. Proposition 2.1. Let uh and u be as in Theorem 2.1 as well as S 6 Vh with S* n supp^i = 0 and S* n suppa/,(u/ l ) = 0. Then there exist constants C\,Ci ^ 0 depending only on j(Vh) such that ||V(n h - u)|U 2 ( s .) ^ Cx T?;(5) - C2 j,2(5). Proposition 2.1 guarantees that, provided data is resolved well, the local error is not overestimated by the corresponding indicators in the intersection of discrete and continuous non-coincidence set. In the "interior of discrete coincidence set" U{S G Vh \ Nh H S C Ch(u/i)} the local indicators already restrict themselves to the measuring local data resolution. However, there remains a region, typically around the continuous free boundary, where the local error might be overestimated. 3
Proofs
We first prepare the proof of Theorem 2.1 with two subsections. The first one introduces new variational inequalities for (2.1) and (2.2) that are crucial for the localization of the interior residual. Moreover, an important property of the auxiliary functions that are used to formulate the afore-mentioned new inequalities is presented. The second subsection recalls some properties of the positivity preserving interpolation operator of Chen and Nochetto. The third subsection then contains the proper proof of Theorem 2.1. Finally, in the forth subsection, Proposition 2.1 about lower bounds is established. 3.1
Sharper inequalities and auxiliary functions
For each v £ K define the auxiliary function ff(") := / lc(„) €L 2 (ft), where C(v) := {x e fl \ 3e > 0 v = x* a-e. in Be(x)} and lc(v) denotes the characteristic function oiC(v). Lemma 3.1. The solution u of Problem 2.1 satisfies Vw6/C
(Vu,V[u-v\)
<: (f
-o-{u),u-v).
227
Proof. Let v € IC. Formal calculations yield that w := u + (1 — lc(u)) (v — u) is a good test function for our purposes apart from the fact that w g H1^). Therefore, we regularize lc(u) : for e > 0 define ipe : = l c . * P e ,
where Ct := {x 6 0 1 Be(a;) C C(u)}, pe := e~dp(-/e), p e C 0 0 ^ ) with p > 0, suppp C £?i(0), / R J / ) = 1, and * denotes the convolution. Clearly, supp
fe -¥ lc(u) - -
m
(3.1a)
^ for e \ 0.
(3.1b)
Set wt :— u + (1 - tpe) (v - u) and write (Vu, V[u - u]) = (Vu, V[u - we]) - (Vu, V[
(3.2)
The inclusion (3.1a) and Vu = 0 in C(u) imply that the second term of the right-hand side of (3.2) vanishes for any e > 0: (Vu,V[vJe(«-u)])=0.
(3.3)
Since we 6 IC, we can use the variational inequality (2.1) in order to estimate the first one: (Vu, V[u - we]) ^ (/, u - we). The definition of cr(u) and (3.1a) yield the identity (/, u - w() = (/ - a(u),u - v) - /
f(l-ipt)(v-u).
JC(u)
With the help of (3.1b) we get l i m ^ o jc,us quently,
f (1 - f€) (v - u) — 0 and, conse-
lim sup (Vu, V[u - iue]) ^ (/ - c(u), U — v). We conclude the proof by taking the limit e \ 0 in (3.2) and then using the last inequality and (3.3). • The discrete counterpart of Lemma 3.1 reads as follows; recall the definition (2.3) of (Jh{vh) and notice that this definition parallels the one of a(v) in nodes. Lemma 3.2. The solution Uh of Problem (2.2) satisfies Vwfc £ ICh
(Vu h , V[uh -vh})
^ (fh -<jh(uh),uh
-vh)
.
228
Proof. Let Vh S /C/,. Define Wh 6 14 by
lu/i(0),
otherwise;
and write (V«h,V[« fc -Wfc]) = (Vu hj V[u fc -u;fc]) + (Vuh,V[u>fc-Vfc]).
(3.4)
Similar as before, the definition of iu/i and Vu/j = 0 in {u^ — X*} imply that the second term of the right-hand side of (3.4) vanishes: {Vuh,V[wh
- vh]) = 0.
(3.5)
Since Wh € Kh, we can use the variational inequality (2.2) in order to estimate the first one: (Vu h , V[u h - wh]) ^ (fh, Uh -wh)hThe use of numerical integration, the definition (2.3) of ^ ( u / , ) and the one of Wh yield
(fh,uh-wh)h =
]C \2€Ch(uh)
+
X!
/*W[«iW-!"i.W] /
z€Mh\Ch(uh)J
= {fh. -Vh(Uh),Uh
~Vh)h
and, thus, {Vuh,V{uh-Wh})
^
{fh,uh-o-h(uh))h.
Using this inequality and (3.5) in (3.4), we obtain the claim.
•
We conclude this subsection by establishing a crucial result for the auxiliary function a{u) and its approximation ah{uh). L e m m a 3.3. Let u and Uh be the solutions of Problems 2.1 and 2.2, respectively. Then {
- u) > 0.
Proof. We first show that a(u) s$ 0.
(3.6)
Let (p e C Q ° ( C ( U ) ) be a test function with ip i> 0. Testing the variational inequality for u with v = u +
229
Next, we show the discrete counterpart of (3.6), namely, <7fc(u/i)<0.
(3.7)
Similar as before, we get (//,,
-u)
= {ah{uh),uh
-u)
+
(a{u),u-uh).
The first term of the right-hand side is estimated in the following way: {
crh(uh) (x*-u) + / crh(uh) (u - uh) "—»—' y v ' Jn\{uh=x.y—v—' <J0 by (3.7)
-go
> 0.
=0
In a similar way, (a(u),u — u^) > 0 by (3.6) and, consequently, the claimed inequality is established. • 3.2
Positivity preserving interpolation
For convenience of the reader, we summarize some properties of the interpolation operator that was introduced in Chen and Nochetto 3 in the following lemma. Note that the case of homogeneous boundary values is special for monotone linear finite element interpolation operators, compare Nochetto and Wahlbin 9 . _ For any set A C 0 define the "smallest discrete neighbourhood" of A as
Uh(A):={J{SeVh\SnA^
(3.8)
(ii) there is a constant C that depends on the shape-regularity j(Vh) only such that the local error estimates llv - I W | U a ( 5 ) ^Chs
\\V
\\
|| V
l|vn^|U 2 ( s ) ^ c IIv^iu 2(c/h(5))
(3.9a) (3.9b)
(3.9c)
230
for any ip £ H^(fl) and all S € Vh, e £ Bh as well as L2(Uh(z))
ll^ft - n h ^ | | i 2 ( e ) ^ C |A [Vy) A ]| L2(t/j , ( e ) )
(3.10a) (3.10b)
for any ifh € Vh and all z £ Nh, e e £h hold. Proof. See Chen and Nochetto 3 .
D
The interpolation operator Uh in Lemma 3.4 is not a projection onto V^; this missing property will be replaced by (3.10) in the following a posteriori analysis. 3.3
Proof of the global upper bound
We continue with the proper proof of Theorem 2.1. Let uh and u be like therein and set &h : = Uh -
u.
Lemma 3.3 yields
\\ehfv = ||Ve fc ||i 2(n) < ||V(u h - u)||i 2 ( n) + {vh(uh) - o-{u),uh - u) = (V%,V[u f t - u ] ) + (o-h(uh),uh + (Vu, V[u -Uh]) + (
-u) -uh).
Since u/, € /C, we can apply Lemma 3.1 in order to estimate the last two terms of the right-hand side: (Vu, V[u - uh}) + {a{u),u - uh) < (/, u - uh).
(3.12)
The first two terms are estimated in a little bit different way; write uh - u - (uh - Uhu) + (eh - Uheh) + {TlhUh - uh). By (3.8) we have TlhU € fCh and Lemma 3.2 thus implies (Wuh,V[uh-Uhu})
- {fh-o-h{uh),uh-nhu)h
SCO-
(3-13)
Keeping this in mind, we write {f,u — Uh) and (a(uh),Uh —u) in the following way: (/, u - uh) = - ( / , uh-u)
= (/h - / , eh) - (fh, e-h - Uheh)
- 6h(/h,riheh) - (fh,U.hUh -uh)h
- (fh,uh - Rhu)h,
(3-14)
231
(vii(uh.),Uk -u)
= (crh(uh),eh - Uheh) + bh [ah{uh),Yi.heh) -uh)h
+ {ch(uh),Uhuh
+ {vh(uh),uh
-Uhu)h,
(3.15)
with bh(iph,tjjh) •= Ja'Ph'^h - Ih(
HVe fc || L2(Q) £
E'<
with 7i := (Vu ft ,V[e/, -Uheh])
- (fh -crh(uh),eh
- Uheh.),
I2 := (Vu h , V[Uhuh -uh})
- {fh -ah{uh),Uhuh
-
uh)h,
h '•= -h{fh - <7h{uh),Uheh), h := {fh ~ f,eh). It remains to estimate I\,..., U appropriately. The estimation of I\ is fairly standard in a posteriori estimation; compare, for example, with Verfiirth 12 . One integrates the gradient term by parts on each simplex and uses (3.9b), (3.9a) as well as VAeBftUPfc
#{SeVh
\Sr\A^
(3.16)
in order to get [iVu^e
h = - Yl
ifih ~ Uheh) - J2
f [h-
e€Vh '
<^l|Ve ft ||i 2(Q) +
c-
•12
ft1/2[V«fc]|
C
+^;\\h[fh-ah(uh)]\\liQ) 111 1 J 2 {*')
^ t
for any e > 0. Similarly, with the help of (3.10) and \/e£Bh,SePh
e n S /
he — ^hs
^ C he
as well as VAe^uBiUPj
# { e e % |enA/0} ^C,
232
one obtains eevhJe - Y] \P-hUh{.z) -uh{z)] z€Mh
[fh(z)-ah(uh;z)]
I JL
J
v ^C
hds/2\\fh-ah(uh)\\L2{s)
£ SCUh(z)
h1/2V7uh]
'
ln+\\h[fh-ah(uh)]\\l2{a)
L2(Q)
Term I3 is estimated with the help of a variant of the Bramble-Hilbert Lemma, see e.g. Theorem 28.1 in Ciarlet 6 , h = - ^2
/ [fa -o-h(uh)]
Tlheh-Ih{[fh
-Vh(uh)}
nfteh)
S€VhJs
^C
Y,
h
\\D2{[h-*h(uh)}nheh)\\wr2{s)
s
S€Vh
"
v
'
^\Mfh-^h)\\L,{S)\M^heh)\\L3{S) ^
\ HVe h ||i 2 ( n ) + — \\h2V[fa
(3.9c),(3.16) 2
2K
'
- ah{uh)} || 2 L2(n) , iy
It
I
2
where W*~ (S) denotes the Sobolev space of functions in Lx(S) that have weak derivatives up to order d — 2 in L\{S). Finally, h = I (fa ~ f) (eh - Uheh) + f (fa - / ) Tiheh JQ
JQ
< e l|Ve f t ||i 2 ( n ) + -
\\h(fh - / ) | | i 2 ( Q ) + -
||/ h - f\\\
for any e > 0. Collecting all the above estimates with sufficiently small e > 0, we have proved Theorem 2.1. 3.4
Proof of local lower bounds
We next prove Proposition 2.1. To this end, we adapt the constructive argument by Verfiirth, see for example Verfurth 12 . Let 5 be as in Proposition 2.1 and denote the mean value of a function
= \
£ ^\\[yuh\e\\l2le)+\\hfh\\l2is.). ecdsnci
(3.17)
233
The interior residual on each simplex T C S* can be estimated by the Poincare-Inequality with mean value, see e.g. (4.3.14) in Brenner and Scott 2 , in the following manner:
hT\\h\\L2(T) ^
hT\\fh,T\\L2(T)+Ch2T\\Vfh\\L^T).
As S* nsupp^j = 0, we obtain (compare inequalities (1.23) and (1.27) in Verfiirth 12 ):
\
£
Ml [VufcU£a(e) + E
eCdSnQ
4IIA,T|I!2(T)
TCS"
^C (||V( U A -u)||i a { S . ) + £
4ll/-A,rllia(T))-
Moreover,
hT 11/ - A,rlU2(T) ^ hT ||/ - M| i 2 ( T ) + C h2T ||VM| i2(T) for any T £ Vh- Using the last three inequalities in (3.17), we get the claimed lower bound. Acknowledgments This research was supported in part by the TMR network "Viscosity solutions and their Applications". Its main part was carried out during a stay at the Dipartimento di Matematica, Universita di Milano, in the working group of Professor Claudio Verdi. I would like to thank him and Francesca Fierro for their kind hospitality and interesting discussions on the topic of this note. References 1. G. BELLETTINI, M. PAOLINI, AND C. VERDI, Convex approximations of junctionals with curvature, Atti Accad. Naz. Lincei, CI. Sci. Fis. Mat. Nat., IX. Ser., Rend. Lincei, Mat. Appl., 2 (1991), pp. 297-306. 2. S. C. BRENNER AND L. R. SCOTT, The mathematical theory of finite
element methods, vol. 15 of Texts in Applied Mathematics, Springer, New York, 1994. 3. Z. CHEN AND R. H. N O C H E T T O , Residual type a posteriori error estimates for elliptic obstacle problems, Numer. Math., 84 (2000), pp. 527548. 4. Z. C H E N , R. H. N O C H E T T O , AND A. SCHMIDT, Adaptive finite element methods for diffuse interface models. In preparation.
234
5. M. CHIPOT, Variational inequalities and flow in porous media, vol. 52 of Applied Mathematical Sciences, Springer-Verlag, New York etc., 1984. 6. P . G. CIARLET, Basic error estimates for elliptic problems, in Handbook of Numerical Analysis, P. G. Ciarlet and J.-L. Lions, eds., vol. II, NorthHolland, 1991, pp. 17-352. 7. F. FiERRO AND A. VEESER, A posteriori error estimators for minimization with regularized total variation. In preparation. 8. P . M O R I N , R. H. N O C H E T T O , AND K. G. SIEBERT, Data oscillation and convergence of adaptive FEM, SI AM J. Numer. Anal., 38 (2000), pp. 466-488. 9. R. H. N O C H E T T O AND L. B. WAHLBIN, Positivity preserving finite element approximation. To appear in Math. Comput. 10. J.-F. RODRIGUES, Obstacle problems in mathematical physics, vol. 134 of North-Holland mathematics studies, North-Holland, 1987. 11. A. VEESER, Efficient and reliable a posteriori error estimators for elliptic obstacle problems. Preprint No. 02, Mathematische Fakultat Freiburg (to appear in SIAM J. Numer. Anal.), 2000. 12. R. VERFURTH, A review of a posteriori error estimation and adaptive mesh-refinement techniques, Wiley-Teubner Series Advances in Numerical Mathematics, Chichester: John Wiley & Sons. Stuttgart: B. G. Teubner, 1996.
Series on Advances in Mathematics for Applied Sciences Editorial Board N. Bellomo Editor-in-Charge Department of Mathematics Politecnico di Torino Corso Duca degli Abruzzi 24 10129 Torino Italy E-mail: [email protected]
M. A. J. Chaplain Department of Mathematics University of Dundee Dundee DD1 4HN Scotland C. M. Dafermos Lefschetz Center for Dynamical Systems Brown University Providence, Rl 02912 USA S. Kawashima Department of Applied Sciences Engineering Faculty Kyushu University 36 Fukuoka 812 Japan M. Lachowicz Department of Mathematics University of Warsaw Ul. Banacha 2 PL-02097 Warsaw Poland S. Lenhart Mathematics Department University of Tennessee Knoxville, TN 37996-1300 USA P. L. Lions University Paris Xl-Dauphine Place du Marechal de Lattre de Tassigny Paris Cedex 16 France
F. Brezzi Editor-in-Charge Istituto di Analisi Numerica del CNR Via Abbiategrasso 209 1-27100 Pavia Italy E-mail: [email protected]
B. Perthame Laboratoire d'Analyse Numerique University Paris VI tour 55-65, 5ieme etage 4, place Jussieu 75252 Paris Cedex 5 France K. R. Rajagopal Department of Mechanical Engrg. Texas A&M University College Station, TX 77843-3123 USA R. Russo Dipartimento di Matematica Universita degli Studi Napoli II 81100 Caserta Italy V. A. Solonnikov Institute of Academy of Sciences St. Petersburg Branch of V. A. Steklov Mathematical Fontanka 27 St. Petersburg Russia J. C. Willems Mathematics & Physics Faculty University of Groningen P. O. Box 800 9700 Av. Groningen The Netherlands
Series on Advances in Mathematics for Applied Sciences Aims and Scope This Series reports on new developments in mathematical research relating to methods, qualitative and numerical analysis, mathematical modeling in the applied and the technological sciences. Contributions related to constitutive theories, fluid dynamics, kinetic and transport theories, solid mechanics, system theory and mathematical methods for the applications are welcomed. This Series includes books, lecture notes, proceedings, collections of research papers. Monograph collections on specialized topics of current interest are particularly encouraged. Both the proceedings and monograph collections will generally be edited by a Guest editor. High quality, novelty of the content and potential for the applications to modem problems in applied science will be the guidelines for the selection of the content of this series.
Instructions for Authors Submission of proposals should be addressed to the editors-in-charge or to any member of the editorial board. In the latter, the authors should also notify the proposal to one of the editors-in-charge. Acceptance of books and lecture notes will generally be based on the description of the general content and scope of the book or lecture notes as well as on sample of the parts judged to be more significantly by the authors. Acceptance of proceedings will be based on relevance of the topics and of the lecturers contributing to the volume. Acceptance of monograph collections will be based on relevance of the subject and of the authors contributing to the volume. Authors are urged, in order to avoid re-typing, not to begin the final preparation of the text until they received the publisher's guidelines. They will receive from World Scientific the instructions for preparing camera-ready manuscript.
SERIES ON ADVANCES IN MATHEMATICS FOR APPLIED SCIENCES Vol. 17
The Fokker-Planck Equation for Stochastic Dynamical Systems and Its Explicit Steady State Solution by C. Soize
Vol. 18
Calculus of Variation, Homogenization and Continuum Mechanics eds. G. Bouchitte et al.
Vol. 19
A Concise Guide to Semigroups and Evolution Equations by A. Belleni-Morante Global Controllability and Stabilization of Nonlinear Systems by S. Nikitin
Vol. 20 Vol. 21
High Accuracy Non-Centered Compact Difference Schemes for Fluid Dynamics Applications by A. I. Tolstykh
Vol. 22
Advances in Kinetic Theory and Computing: Selected Papers ed. B. Perthame
Vol. 23
Waves and Stability in Continuous Media eds. S. Rionero and T. Ruggeri
Vol. 24
Impulsive Differential Equations with a Small Parameter by D. Bainov and V. Covachev
Vol. 25
Mathematical Models and Methods of Localized Interaction Theory by A. I. Bunimovich and A. V. Dubinskii
Vol. 26
Recent Advances in Elasticity, Viscoelasticity and Inelasticity ed. K. R. Rajagopal
Vol. 27
Nonstandard Methods for Stochastic Fluid Mechanics by M. Capinski and N. J. Cutland
Vol. 28
Impulsive Differential Equations: Asymptotic Properties of the Solutions by D. Bainov and P. Simeonov
Vol. 29
The Method of Maximum Entropy byH. Gzyl
Vol. 30
Lectures on Probability and Second Order Random Fields by D. B. Hernandez
Vol. 31
Parallel and Distributed Signal and Image Integration Problems eds. R. N. Madan et al.
Vol. 32
On the Way to Understanding The Time Phenomenon: The Constructions of Time in Natural Science - Part 1. Interdisciplinary Time Studies ed. A. P. Levich
SERIES ON ADVANCES IN MATHEMATICS FOR APPLIED SCIENCES
Vol. 33
Lecture Notes on the Mathematical Theory of the Boltzmann Equation ed. N. Bellomo
Vol. 34
Singularly Perturbed Evolution Equations with Applications to Kinetic Theory by J. R. Mika and J. Banasiak
Vol. 35
Mechanics of Mixtures by K. R. Rajagopal and L. Tao
Vol. 36
Dynamical Mechanical Systems Under Random Impulses by R. Iwankiewicz
Vol. 37
Oscillations in Planar Dynamic Systems by R. E. Mickens
Vol. 38
Mathematical Problems in Elasticity ed. R. Russo
Vol. 39
On the Way to Understanding the Time Phenomenon: The Constructions of Time in Natural Science — Part 2. The "Active" Properties of Time According to N. A. Kozyrev ed. A. P. Levich
Vol. 40
Advanced Mathematical Tools in Metrology II eds. P. Ciarlini et al.
Vol. 41
Mathematical Methods in Electromagnetism Linear Theory and Applications byM. Cessenat
Vol. 42
Constrained Control Problems of Discrete Processes by V. N. Phat
Vol. 43
Motor Vehicle Dynamics: Modeling and Simulation by G. Genta
Vol. 44
Microscopic Theory of Condensation in Gases and Plasma by A. L. Itkin and E. G. Kolesnichenko
Vol. 45
Advanced Mathematical Tools in Metrology III eds. P. Cianlini et al.
Vol. 46
Mathematical Topics in Neutron Transport Theory — New Aspects by M. Mokhtar-Kharroubi
Vol. 47
Theory of the Navier-Stokes Equations eds. J. G. Heywood et al.
Vol. 48
Advances in Nonlinear Partial Differential Equations and Stochastics eds. S. Kawashima and T. Yanagisawa
SERIES ON ADVANCES IN MATHEMATICS FOR APPLIED SCIENCES
Vol. 49
Propagation and Reflection of Shock Waves by F. V. Shugaev and L S. Shtemenko
Vol. 50
Homogenization eds. V. Berdichevsky, V. Jikov and G. Papanicolaou
Vol. 51
Lecture Notes on the Mathematical Theory of Generalized Boltzmann Models by N. Bellomo and M. Lo Schiavo
Vol. 52
Plates, Laminates and Shells: Asymptotic Analysis and Homogenization by T. Lewinski and J. J. Telega
Vol. 53
Advanced Mathematical and Computational Tools in Metrology IV eds. P. Ciarlini et al.
Vol. 54
Differential Models and Neutral Systems for Controlling the Wealth of Nations by E. N. Chukwu
Vol. 55
Mesomechanical Constitutive Modeling by V. Kafka
Vol. 56
High-Dimensional Nonlinear Diffusion Stochastic Processes — Modelling for Engineering Applications by Y. Mamontov and M. Wlllander
Vol. 57
Advanced Mathematical & Computational Tools in Metrology V eds. P. Ciarlini et al.
Vol. 58
Mechanical and Thermodynamical Modeling of Fluid Interfaces by R. Gatignol and R. Prud'homme
Vol. 59
Numerical Methods for Viscosity Solutions and Applications eds. M. Falcone & Ch. Makridakis
SERIES ON ADVANCES IN MATHEMATICS FOR APPLIED SCIENCES Published: Mathematical Topics in Nonlinear Kinetic Theory II: The Enskog Equation by N. Bellomo et al. Discrete Models of Fluid Dynamics ed. A. S. Alves Fluid Dynamic Applications of the Discrete Boltzmann Equation by R. Monaco and L. Preziosi Waves and Stability in Continuous Media ed. S. Rionero A Theory of Latticed Plates and Shells by G. I. Pshenichnov Recent Advances in Combustion Modelling ed. B. Larrouturou Linear Kinetic Theory and Particle Transport in Stochastic Mixtures by G. C. Pomraning Local Stabilizability of Nonlinear Control Systems by A. Bacciotti Nonlinear Kinetic Theory and Mathematical Aspects of Hyperbolic Systems ed. V. C. Bom Vol. 10
Nonlinear Evolution Equations. Kinetic Approach by N. B. Maslova
Vol. 12
Mathematical Problems Relating to the Navier-Stokes Equation ed. G. P. Galdi Thermodynamics and Kinetic Theory eds. W. Kosihski et al. Thermomechanics of Phase Transitions in Classical Field Theory by A. Romano
Vol. 13 Vol. 14
Applications of Pade Approximation Theory in Fluid Dynamics by A. Pozzi
Vol. 15
Advances in Mathematical Modelling of Composite Materials ed. K. Z. Markov
Vol. 16
Advanced Mathematical Tools in Metrology eds. P. Ciarlini et al.
www. worldscientific. com 4781 he