PARTICLE APPROXIMATION FOR FIRST ORDER STOCHASTIC

PARTIAL DIFFERENTIAL EQUATIONS*

Patrick FLORCHINGER t Universit6 de Metz

D~partement de Math6matiques URA CNRS 399

Ile du Sa.ulcy F-57045 METZ C~dcx

Francois LE GLAND INRIA Sophia-Antipolis

Route des Lucioles F-06565 VALBONNE C6dex

Abs t r ac t

A class of degenerate second order stoch~tlc PDE is cousldered, for which a representa- tion result in terms of stochastic characteristics h ~ been proved by Krylov-Rozovskii [2] and Kunita [3,4]. An example of a stochastic PDE in this class has been exhibited in Florclfinger- LeGland [1] as the result of a Trotter-like product formula for the Zakai equation of diffusion processes observed in correlated noise. Particle approximations are introduced for this class of stochastic PDE, and error estimates are provided which extend the results of Raviart [6] on first order deterministic PDE.

1 I n t r o d u c t i o n

Consider tile following stochastic differential equation

dX, = b( X,) at + a(X,) [dW, - e(X,) all , (1.1)

where {W~, l > 0} is a d-dimenslonal staHdard Wiener process, and the associated stochastic flow of diffeomorphisms {~,.t('), 0 < s < t}, and define

-'z0,~(x) exp C"

*l~esearch partially supported by USACCE under Contract DAJA45-90-C--0008. lalso : INRIA Lorrai~m, CESCOM, Te¢|mopole de Metz 2000, 4 rue Marcmfi, F-57070 METZ.

122

Introduce the following partial differential operators

L ~ 1 '" b ' ~ a '~ .............. + + c , id=l OXiOZJ OXi

m • 0 ~_,q' B k ~ e k + k~-~X , l < k < d ~ i=1 *

with a = ~r a °, and the stochastic PDE

d

dq, = L'q, ,tt + ~ B~q, , l w , ' . k = l

0.2)

Because of the relation a = a a" between coefficients of higher order partial derivatives in op- erators L and Bk, equation (1.2) is a degenerate second order stochastic PDE or equivalently, after transformation into Stratonovich form, a first order stochastic PDE. Existence and representation results have been obtained by Kunita [4] for (generally nonlinear) first order stochastic PDE, based on the notion of stochastic characteristics.

In a previous work [1], tile Zakai equation for the nonlinear filtering of diffusion processes ob- served in correlated noise has been considered. A decomposition of the Zakai equation has been introduced, exhibiting a degenerate second order stochastic PDE similar to (1.2) in the correction step. In addition, a time discretization scheme has been proposed for this degenerate second order stochastic PDE, with rate of convergence of order V~, where g is tile time step.

The purpose of this paper is to provide a discretization scheme of the degenerate second order stochastic PDE (1.2) with respect to the space variable x E R '~. This approximation relies on the representation of the solution in terms of stochastic characteristics, and approximation of the initial condition by a convex linear combination of Dirac masses. This kind of aproximation is called a particle approzimation, see Raviart [6].

More specifically, for any probability measure tt(dx) on R m, define the transformed measure Qt l'(dx) by

(Qt #, ~b) = f ¢(~0.,(x)) E0,t(x) #(dx) , (1.3)

for any test function ~b, or equivalently

Q, ~,(A) = f~z.~c,~} zo.,(x) t,(dx).

Note that, if ~ is regular enough, then the It6 formula gives

d

aI ¢(¢0.,(x) z0. , (~) l = L¢(~0.,(~)) • -:0,,(x) a~ + ~ Bk¢(¢o,,(~)) • Z0,,(=) aW, ~ • k = l

Therefore #,(dx) = Ot #(dx) solves equation (1.2) in weak form, i.e.

d

dp, = L'pt dt + ~ BZpt dWt k , P0 = P . (1.4) k = l

Consider next tile following two different assumptions on the original measure po(dx) :

123

1:3 Assume tha t the original measure #(dx) has a density q(z) with respect to the Lebesgue measure on R ' , i.e. tt(dr) = q(x) dr. Then, tile transformed measure Qt/~(dx) has itself a density qt(x) which satisfies

qtC~o,,Cx))" So,,(z) = ~o,,(z)" qCr) ,

or in integrated form

fA qt(x) dx = f~l .a l -'-o,t(x) . q(x) dx .

llere, Jo,t(') is the Jacobian (i.e. tile determinant of the Jacobian matr ix) of the stochastic flow ~0,t('). In addition, the density q4(x) solves the degenerate second order stochastic PDE

d

dqt = L'qt dt + ~ BZqt d i e ? , qo = q . (1.5) k=l

o Assume tha t the original measure #(dz) is a convex linear combination of Dirac masses, also called particles

iEI

where {a d, i E I} arc the particle weights, and {x d , i E I} arc the particle locations. Then, the transformed measure Qt p(dx) has a similar representation

iEl

where the particles have been transported by the flow i.e. x I = ~o,t(x;), and the weights have been updated according to a~ = a i F.o,l(xi).

The idea behind particle approximation for equation (1.2) is tile following :

• given an initial condition tto(dx) with density qu(x), find an approximation ~ho(dx ) in terms of a linear convex combination of Dirac masses,

• use the exact solution of equation (1.4) with the approximation ttao(dx) as initial condition, as an approximation for the solution of the original equation (1.5), and get an error est imate if possible.

This can be i l lustrated by the following diagram

qo(x)dx = #0(dx) . Itho(dx)

Q,t Q~

q,(x) ax = ~,,(dr) ~,,~(dr)

124

The remainder of this section is devoted to recalling standard results concerning stochastic flows of diffeomorphisms and stochastic PDE.

Propos i t ion 1.1 Let n > 0 be fixed. Assume that

• b, a and e have bounded derivatives up to order (n + 1),

• e has bounded derivatives up to order n.

Then ~,,t(') is a C"-diffeomorphism in R m. In addition, the following estimates hold for all p >_ 1

sup E [[D°'~s,t(x)[P] < oo , l < l o t [ _ < n ,

sup E [ID"'~s,t(z)IP] < ~ , 0_< la l_<n . zER m

Restricting to compact sets of R " , it is possible to invert the supremum and the mathematical expectation in the estimates above, see the Corollary 4.6.7 of Kunlta [5]

Propos i t ion 1.2 Under the assumptions of the Proposition 1.1, there exists a constant C > O, such that for any compact set B C R " and e > 0 the following uniform estimates hold for all p >__ 1

E

[sup ID~E,,,(x)V] ___ C [1 + *~-'] , 0 _< lal _< n , E LxEB J

where ~ = ~(B) denotes the diameter of B.

For all n > 0, p > 1, let W "'v =_ W",P(R") denote the space of real-valued Lebesgue-measurable functions on R " whose generalized derivatives up to order n are integrable in p-mean, and define the corresponding norm I1" I1-,~ and semi-norm 1.1,,, by

Ilull~..p ~ E flD"u(=)l"d= a.d 1~1.%~ ~ flD" ( )lPd=, 0_<lal_<n I,~l=n

respectively.

Consider the following degenerate second order stochastic PDE

d dq, = L*qt dt + y~ B~.q, dlYt k , qo = q . (1.6)

k=l

Although no coercivity hypothesis is satisfied, the following existence, uniqueness and regularity result is proved in Krylov-Rozovskii [2].

125

T h e o r e m 1.3 Let n > 1 bc fixed. Assume that

• a has bounded derivatives up to order max(n, 2),

• b, tr, c and e have bounded derivatives up to order n,

• the initial condition satisfies qo E H/~'~.

Then equation (1.6) has a unique solution q E MP(0, T ; Wn'P). In addition

q E L"(ft ; C~([0,T] ; Wna')),

E[ sup IIq, llZ~] < IlqollZ,p e o r , o<t<_T ' -

2 Q u a d r a t u r e - b a s e d p a r t i c l e a p p r o x i m a t i o n

With the quadrature formula (A.1)

fg(~) d~ ~ ~ ' 9(x'), iEl

is associated the following particle approximation for the initial dcnslty qo(x)

qo(x) dx = Ito(dx) .-~ tth(dx) = ~ w i qo(x i) gx~(dx) . (2.1) iEl

This induces the following particle approximation for the solution qt(x) of equation (1.6)

qt( x ) dx = lq( dx ) ,,~ ltat ( dx ) = Z.., -o,t~ ) qo( x i) 6 ~o.l( xi) ( dx ) . iEl

The following error estimate holds in Sobolcv space with negative exponent, which extends the result of Raviart to the case of first order stocll~tic PDE.

T h e o r e m 2.1 Let n > m be fixed. Assume that

• b, or, C and e have bounded derivalives up to order (n + 1),

• the initial condition satisfies qo E W "'p.

T/ten there exists a constant C > 0 independent of h, such that

EIIm - ~'hll-.,~ -5< C h" llqoll.,p •

PROOF. Let ~b E W "~'p' be an arbitrary test function. Since

(lq,¢) =/qJ(¢o , t (x ) )Zo. t (x )qo(x)dx , ( t , ~ ' , ¢ ) ) " ~ w ' i -- i i = ¢(~o,,(~ )) ~, , (x )qo(~ ) , , 1

iEl

it follows from Theorem A.2 that

and the following estimate holds

126

I(u,,¢) - (uL ¢)1 _< c h- Igl. .~,

with g = ¢ , ~0.t" Z0.t qo, provided g E W nJ, n > m .

Under the assumptions on the coefficients, ¢ o ~0.t E I¥ n'v' and ---o,t • qo E W n'p, for conjugate p and p'. Moreover, the generalized Leibniz formula yields

Igl.,, -< ~ j Ix°,a(x) D~¢(~o,,(x)) Daqo(z) l dx , ( ~, ,# ff: I.

where In denotes the set of pairs (a, fl) of multi-indices such that ]a] + I/?t < n, and X~d(') are random fields involving the derivatives of (o,t(') and Eo,t(-) up to order n. Using back and forth the changes of variable induced by the differomorphisms (o,t(') and ~ff)(-), and the HSlder inequality, gives

Igl.,, < ~ f -~ Ix,.,a(~o,, (z)) O"¢(x) Daqo(~1(x))l -x -~ _ [Jo,,ffo, ,( .))] d . (c,,#)el.

r r , ~llp' ~ [ I X o ~ ( ~ f f . : ( x ) ) < E ( J IO=¢(z)F ~tx~ t J ' D%°(¢ffJ(x))l~ (0,#)¢I.

. ~ lip [Jo.,ff~:(x))l-'d~

v. - _ D"q°( - ) l ' [Jo,,{-)]-~'-''a~=~ . (a,~)et.

Therefore

and

# ~ I/p I O qo (x ) l "dx~ .

From estimates in Proposition 1.1, it holds

suo E {Ix~,a(x)l" [go.,(~)] -c~-')} < ~ , x E l / . m

so that EIIm- t¢ll-..p --- c h" [Iqoll.,~ • []

R e g u l a r i z a t i o n

Let ((x) be a continuous cut-off function defined on R " , which satisfies

] ¢ ( ~ ) d ~ = 1 , (i)

(ii) I x ~" ¢(z)dx = 0 , 1 _< I=t -< a - 1 , J

( i i i ) f Ixl ~ I¢(x)l,tx < oo,

127

for some k _> 2. For any e > 0, ~(x) is defined by the following scaling

¢~(x) £rrt

With the particle approximation

iEl

is associated the regularized measure

t~"(dx) = t'~ * ¢,(dx) = q ~ " ( x ) d z ,

where the density q~X(x) is given by

q,~-(~) = ~ 0 , ' Zo,,(~') qo(~') ¢,(~ - ~i). iEl

The main result of this section is the following theorem, which is an extension of the Theorem 4.2 in [6], to the case of first order stochastic PDE.

T h e o r e m 2.2 Let n > m be fixed. A s s u m e thai

• the cu t -o f f funct ion ~ satisfies ( i ) -( i i i ) for some k > 2, and ~ E W n'l,

• b, a, e and e have bounded derivatives up to order ( g + 1),

. the initial condition satisfies qo E W e'p,

where/~ = max(k, n).

They, there exists a constant G independent o f both h and ~, such that

¢.'llo".,}'"_< c i1,,0,, + (h/,)" II 011..,} •

PItOOF. Obviously qt - qnt " = [qt - qt * (~1 + [q, * (¢ - qat"] .

First, it follows from Lemma 4.4 in [6] that

llq, - qt * Gllo,p <: c' ~k [qt[~,p

provided qt E W ~a'. Under the assumptions, Theorem 1.3 gives

On the other hand, using the change of variable induced by the diffeomorphism ~ffJ(.), it holds for aU z fi R "~

qt * C,(x) -- q~'¢(x) = f Zo.t(z) qo(z) ¢,(x - ¢0.,(z)) dz

- ~ w i F.o,,(x i) qo(x i) ¢, ( z - ~o , , (x i ) ) = E ( g ( z , .)) iE1

198

with g(x, .) = =-.o,t qo" G(x - ~o,t). Therefore, it follows fl.om Theorem A.1 that for all x E R "

Iqt * ¢,(z) - qth'~(x)l -< C h ~ Ig(z, ")lna

provided g(z, .) E W "'1, n E m. Moreover, the generalized Leibniz formula yields

la(x,-)l.., _< ~ f Ix'.a(z) D a q o ( z ) D ~ ( x - ~o,t(z))ldx,

where In denotes the set of pairs (a, fl) of multi-indices such that Ictl + I~1 -< n, and X'~.a(') are random fields involving the derivatives of ~o.t(-) and Eo.t(.) up to order n. From the technical lemma below, it follows that

[J0.,(x)]-(~-') dx} I

Making use of 1 c, x

D°G(x) = ~ D ~(7) ,

taking mathematical expectation on both sides, and raising to the power l ip gives

c=ll ll, ,, l l /P

ID qo(x)lP dx~ •

From estimates in Proposition 1.1, it holds

sup E { I x ' A x ) l ~ Vo,,(,~)] -(~-~1} < ~o. zEIl."

Therefore

h,~ ~ "I.1/P p "ll/P

_< c (h./~)" ll¢ll,,a I l qo l l . ,~ • [ ]

L e m m a 2.3 Let f ~ LP and g E L I, and define

l(x) = f f(z) g ( x - ~o,t(z)) dz.

Then I E LP and in addition

(f I/(x)l ' dx} ' lP< {f I f(x)lp [,/oa(x)] -(~-') dx} '11" f Ig(x)l dx"

PROOF. ~,~(-), and the Lemma 4.3 in [6], gives

and

129

Using hack and forth the changes of variable induced by the differomorphisms ~to,t(-) and

3 Adapted particle approximation

Consider the particle approximation (A.3) for the initial condition po(dz)

#o(dX) ,,, t,o~(d,~ ) = ~ ' ~ ,(d~) X

iEI

where the particle weights {a i , i 6 I} and the parlAcle locations {x / , i E I} are defined in the following way

.' .oCn')= f. , a f . . a-- 7 , z l ~ o ( d z ) ,

depending on the measure Ito(dz). This induces the following particle approximation for the solution #,(z) of equation (1.4)

i _~ i . , (dz) ~ .,~(d~) = ~ . _0,,(x ) ~0 , , (z , ) (dx) . iEI

Parallel to tile Theorem 2.1 above, the following error estimate holds in Sobohv space with negative exponent.

Theo rem 3.1 Assume that

• b, a, c and e have bounded derivatives up lo order 3,

• for all i E I , the set B i C R m is compact.

Then there exists a constant C > O, such that

E l l m - ~¢It-~., < c ~ 6~ a' , iE t

where a i = po(B i) and 6i = 6(B i) denotes the diameter of the set B i.

PROOF. Let ~b E W 2'~ be an arbitrary test hmction. Since

¢~,,¢) f¢C¢o,,Cx)).--o,,Cz)t,o(a~) (~,I',¢) a' ' - e = , = ~ ¢C¢0,,C~ ) ) = 0 , , ( ) , iEl

J

130

it follows from estimate (A.6) that

I 2 al i ( l

with g = ~ o ~oa" Eo,~, where/~i denotes the convex hull of B ~. The generalized Leibniz formula yields

Igl2,oo,B _.< ~ sul, Ix°(.~)D~¢(~o,,(~))l hi_<2 ~eB

1~1<2 LxeU L x~rt~

I*I<~ ~et~

where X,,(') are random fields involving the derivatives of ~0.,(-) and -Z0,t(.) up to order 2. Therefore

I(/,,, ~') - ( / ¢ , ¢) I ~ ¢ ~ __. -~ ~ ~ sup Ix.(x)l ~? ~ , iel k,l_<2 ~c~'

and I" "1

let lal_<7 L.~,Ew J From estimates in Proposition 1.2, it ]raids

L~eB ' J

for some p, where & = 6(B i) denotes the diameter of both B i and its convex hull/~i, so that

R e f e r e n c e s

[1] P. FLORCIIINGER and F. LE GLAND, Timc-diserctization of tile Zakai equation for diffusion processes observed in correlated noise, Slochastics aud Stochastics Reports 35 (4) 233-256 (1991).

[2] N.V. KRYLOV and B.L. ROZOVSKII, Characteristics of degenerating second-order parabolic It6 equations, J.Sovict Math. 32 (4) 336-348 (1982).

[3] It. KUNITA, Stochastic partial differential equations connected with nonlinear filtering, in: Nonlinear Filtering and Stochastic Conl~vl (Cortona-1981) (eds. S.K.Mitter and A.Moro) 100- 169, $pringer-Vcrlag (LNM-972) (1982).

[4] H. KUNITA, First order partial differential equations, in: Stochastic Analysis (I(atata and Kyoto-1982) (cd. K.ItS) 249-269, North-I[olland (1984).

131

[5] H. KUNITA, Stochastic Flows and Stochastic Differential Equations, Cambridge University Press (1990).

[6] P.A. RAVIART, An analysis of particle methods, in: Numerical Methods in Fluid Dynamics (0omo-1989) (ed. F.Brezzi) 243-324, Springer-Verlag (LNM-1127) (1985).

A Particle approximation of functions

Consider tile following quadrature formula on R "

f g(x) dx ,',, ~ w i g(xi) , (A.1) iEl

where {x i , i E I} is a coordinate grid of size h > 0, I = Z '~ and w i = h" is the Lebesgue measure of the m-dimensional cube B; with center x; and edge size h. For all g E C ( R ' ) , the quadrature error associated with tile quadrature formula (A.1) is defined by

E~(g) = '~ f . . g(~) d= - o/ , j (x~), E(g) ~ ~ Ei(g) . iEl

The following estimate is proved in Raviart [6]

T h e o r e m A.1 There is a constant C > 0 independent of h such that

IE(a)I -< C h" la l . . l ,

for aIl g E W "'t, n > m.

Let #(dz) be a probability measure on R " having a continuous density q(x) with respect to the Lebesgue measure, i.e. #(dz) = q(z)dz. With the quadrature formula (A.1) is associated the foUowing particle approximation for tile density q(z)

q(x) dz = g(dz) ,.~ #h(dx) = ~ w i q(x i) ~zi(dz) , (A.2) iEl

so that, for any test function (k

(#, +) = f ¢(x) q(x) d x , (tt h, ¢) = y~.w i ¢(x/) q(xl) . iEl

The following result is proved in Raviart f6]

T h e o r e m A.2 There is a constant C > 0 independent of h such that

lit - Ithll-,*,v <-- C h" Ilqll,*,p ,

for all q E W "'~, n > m.

132

PROOF. From Theorem A.1, it holds

I(~,¢) - (/,h, ¢)1 = IE(g)I _< C h" b t . , t ,

with g = ~b.q, provided g 6 W "'1, n _> m. The gellcralizcd Leibniz formula and the HSlder inequality yield

lab,,, _< c 114II.,., llqll.,p, for conjugate p and p', and therefore

11/~-~11_. ,~= .~up I("' ¢) - (/'~' ¢) l < c h" llqll . , . . m

Another possible approximation is to consider a partition {B i , i 6 I} of R r~, and to define the following particle approximation for tile probability me~ure i,(dx)

~(a~) ""/,h(dx) = ~ a' ~ , ( d 4 , (A.3) iEI

where the particle weights {a i , i £ I} and tim particle locations {x i , i E I} are defined in the following way

a i =:" I'(B;) = / m / , ( d x ) , xl zx a -71 /B' x/~(dx) , (A.4)

depending on tile measure tt(dx) so that, for any test function ¢

(~,¢) = f ¢(~)~,(d~), (j,", ¢) = ~ a ' ¢ ( x ' ) . iEl

For all ¢ 6 C(R") , the quadrature error associated with the formula (A.3), is defined by

Z~(¢) ~ f~ ¢(x) l,(dx) - a i ¢(x ' ) , Z'(¢) ~ ~ E~(¢). i iEl

Parallel to the Theorem A.2 above, the followit,g rest, ll± holds

Theorem A.3 For any parlition {B i , i 6 1}

tll,-/,hll_,: < ~ ~ a ' , ( i .5) iEl

where a ~ = t t(B i) and 61 = 6(B ~) denotes the diameter of lhe set Bq

PrtooF. Let ~ C W 2'~ be an arbitrary test-fnnction. Using Taylor expansion around the point x = x i yields

¢(~) = ¢(x') + (~ - ~')" D¢(x i)

+(z -x l )* { fo l (1 -u )D2¢[ux -F(1 -u )x i ]du} ( x - z i ) ,

and the definition (A.4) gives

Therefore

133

E~(~) = / B , ( x - x i ) * { / l ( l - u ) D 2 ¢ [ v x + ( 1 - u ) x l ] d u ) (x - x i ) d x .

IEI(¢)I _<_ ~ 1¢12.~,~./~, I1= - x;ll2t,(d~) < ' ¢2 ~.~, ~2 a ' ,

where/~i denotes tim convex hull of B i. Then

I(~, ¢) - (ph, ff)l = IE'(¢)I < ½ ~ 1~12,oo.~, by a', (A.6) iE1

and II / ' - ,h l l -2 , , = s n p I(1' ,¢)-(1'h,¢)1 < , . []

iE!

Remark A.4 If the partition {Bi, i E 1} is given, with 5~ < C h for all i E f, then

I1~,- I,~'11-2,, -< c h 2 .

On the other hand, i f the partit ion {B i , i E I } has to be chosen so as to make the quadrature error as small as possible, then estimate (A.5) can be used to derive the following criterion

6~ a i = c for a l l i E I .

This criterion based on equidislribution of the local quadrature error, has the following interesting property

• a set with a large mass, will be split into some smaller subsets,

• conversely, nelghbouring sets with small masses, will be packed together into one single set.