Vitesse de convergence d'une méthode particulaire stochastique avec branchements

C. R. Acad. Sci. Paris, t. 332, Série I, p. 933–938, 2001Probabilités/Probability Theory

Vitesse de convergence d’une méthode particulairestochastique avec branchements

Hervé RÉGNIER a,b, Denis TALAY a

a Inria, 2004, route des Lucioles, B.P. 93, 06902 Sophia-Antipolis cedex, Franceb CAR, 33, rue Mogador, 75009 Paris, France

Courriel : denis.talay@inria.fr; herve.regnier@car.caissedesdepots.fr

(Reçu le 3 octobre 2000, accepté après révision le 6 février 2001)

Résumé. Cette Note est consacrée à la vitesse de convergence d’une méthode particulaire stochas-tique avec branchements introduite par Sherman et Peskin pour certaines équations dediffusion-réaction-convection unidimensionnelles. Nos estimations d’erreur sont expriméesen fonction du nombre de particules à l’instant0 et du pas de discrétisation en temps. 2001Académie des sciences/Éditions scientifiques et médicales Elsevier SAS

Convergence rate of a branching stochastic particle method

Abstract. In this Note we analyse the convergence rate of a branching stochastic particles methodproposed by Sherman and Peskin for the numerical resolution of one dimensionalconvection-reaction-diffusion equations. Our estimates are in terms of the number ofparticles at time 0 and the time discretization step. 2001 Académie des sciences/Éditionsscientifiques et médicales Elsevier SAS

Abridged English version

In this Note we state convergence rate estimates for the branching stochastic particle method introducedby Sherman and Peskin [5] to solve diffusion-reaction-convection partial differential equations of thetype (1) below, whereV0 is the distribution function of a probability law onR, andf is a differentiablefunction such thatV (t, ·) also is a distribution function for allt > 0. The method is based upon theprobabilistic interpretation of the equation (2) satisfied byu(t, x) := ∂V

∂x (t, x).The main result of the note concerns an extension of the Sherman and Peskin method to equation (3)

which is more general than (1). The algorithm is as follows:(i) at time 0, N particles with mass1/N are located at pointsV −1

0

(iN

), i = 1, . . . ,N − 1, and

V −10

(1− 1

2N

);

(ii) let ∆t be the time discretization step; between timesk∆t and(k + 1)∆t each particle living at timek∆t moves independently of the other particles; its position at time(k+ 1)∆t is

Note présentée par Marc YOR.

S0764-4442(01)01857-2/FLA 2001 Académie des sciences/Éditions scientifiques et médicales Elsevier SAS. Tous droits réservés 933

H. Régnier, D. Talay

Y (k+1)∆t = Y k∆t +{σ(Y k∆t)σ′(Y k∆t)− b(Y k∆t)

}∆t+ σ(Y k∆t)(W(k+1)∆t −W∆t)

+12σ(Y k∆t)σ′(Y k∆t)

{(W(k+1)∆t −W∆t)2 −∆t

};

(iii) at each time step one creates and deletes particles according to the following rule. LetNN(k+1)∆t denote

the number of particles living at time(k+ 1)∆t, and

V N((k+ 1)∆t, x

):=

1N

NN(k+1)∆t∑j=1

H(x− yj

(k+1)∆t

),

where{yj(k+1)∆t} is the set of the simulated particles which are living at time(k+1)∆t andH is the

Heaviside function.The particle numberedj dies with probability∆t

∣∣f ′ ◦ V N ((k + 1)∆t, yj(k+1)∆t)

∣∣. If f ′ ◦ V N ((k +

1)∆t, yj(k+1)∆t) � 0, it gives birth to two particles.

THEOREM 1. –Suppose:(i) the function f belongs to C1

b(R) and satisfies:

f(0) = f(1) = 0; f ′(0)> 0;

f ′(x) � f ′(0) for all x ∈ [0,1]; f ′(x)< 0 for all x ∈ R+ � [0,1];

(ii) the functions b and σ belong to C∞b (R). In addition, there exists a real number C0 > 0 such that

σ(x) �C0 > 0 for all x;(iii) the function V ′

0 is a probability density such that

∃M > 0, ∃η > 0, ∃α > 0, ∀|x|>M,∣∣V ′

0(x)∣∣ � η exp

(−αx2

).

Let Φ be a positive function in L1(R)∩ L∞(R). We set

‖g‖L1,Φ(R) :=∫

R

∣∣g(x)∣∣Φ(x)dx

for all Lebesgue integrable function g. Then it holds: there exists C > 0 such that

supk∈{0,...,T/∆t}

E∥∥V (k∆t, ·)− V N (k∆t, ·)

∥∥L1,Φ(R)

� C√N

+C√

∆t

for all N � 1 and 0<∆t < 1.

1. Introduction

Cette note est consacrée à la vitesse de convergence d’une méthode particulaire stochastique avecbranchements introduite par Sherman et Peskin [5] pour les équations aux dérivées partielles de diffusion-réaction-convection du type

∂V

∂t(t, x) =

12∂2V

∂x2(t, x) + f ◦ V (t, x),

V (0, x) = V0(x),

(1)

934

Vitesse de convergence d’une méthode particulaire stochastique avec branchements

où V0 est une fonction de répartition de loi de probabilité surR, et f est une fonction dérivable telleque, pour toutt > 0, V (t, ·) est aussi une fonction de répartition. La méthode repose sur l’interprétationprobabiliste de l’équation satisfaite paru(t, x) := ∂V

∂x (t, x) :

∂u

∂t(t, x) =

12∂2u

∂x2(t, x) + f ′ ◦ V (t, x)u(t, x),

u(0, x) = V ′0 (x).

(2)

La construction probabiliste est la suivante.

Initialisation des particules. – À l’instant 0, N particules de masse1/N sont situées aux pointsV −1

0

(iN

), i = 1, . . . ,N − 1, et V −1

0

(1 − 1

2N

). Ces particules sont destinées à diffuser, à brancher et à

interagir. Pour tout tempst > 0, on noteNNt le nombre de particules vivantes à l’instantt. On introduit les

mesures atomiques

ZNt :=

NNt∑

j=1

δzjt

et µNt :=

1N

ZNt ,

oùzjt représente la position de la particulej vivante à l’instantt.

Diffusion des particules. – NotonsH la fonction de Heaviside, et

V N (t, x) :=1N

NNt∑

j=1

H(x− zj

t

)la fonction de répartition de la mesure finieµN

t . La probabilité qu’entret et t+ dt il y ait une particule quibranche parmi lesNN

t particules vaut

dtNN

t∑j=1

∣∣f ′ ◦ V N(t, zj

t

)∣∣,et c’est la particule numéroJ avec la probabilité

∣∣f ′ ◦ V N(t, zJ

t

)∣∣[ NNt∑

j=1

∣∣f ′ ◦ V N(t, zj

t

)∣∣]−1

.

Elle est remplacée par0 particule sif ′ ◦ V N (t, zJt ) � 0, et par deux particules sif ′ ◦ V N (t, zj

t )> 0.Sous des hypothèses très naturelles sur la fonctionf , Chauvin et Rouault [3] ont montré que la suite de

processus(µN· ) converge faiblement dansD([0, T ],W2,−3) vers un processus déterministeµ· ; de plus, le

flot (µ·) est solution au sens des distributions de (2), et donc la fonction de répartition deµt est solutionde (1). Ce résultat a été largement précisé par Chauvin, Olivares-Rieumont et Rouault [2] qui ont établila propagation du chaos pour le système de particules, ainsi qu’un résultat de fluctuation :

√N(µN

· − µ·)converge faiblement dansD([0, T ],W2,−5) vers un processus d’Ornstein–Uhlenbeck généralisé. Il restaità donner des estimations non asymptotiques pour l’erreur d’approximation deV (t, x) parV N (t, x) afin demettre en évidence :(a) pour toutN , la dépendance en1/

√N de l’erreur globale de la méthode ;

935

H. Régnier, D. Talay

(b) l’effet de la discrétisation en temps puisque la mise en œuvre numérique de la méthode décrite ci-dessus nécessite l’introduction de grilles de pas∆t qui modifient les horloges exponentielles des tempsde branchement ;

(c) l’effet de l’approximation du processus régissant les libres parcours des particules dans le cas où,dans (1), on remplace l’opérateur de la chaleur par un opérateur elliptique plus général (on estalors conduit à approcher des trajectoires de processus de diffusion au lieu de simples trajectoiresbrowniennes).

2. L’algorithme particulaire complet et sa vitesse de convergence

Nous nous intéressons à une équation un peu plus générale que (2), à savoir

∂u

∂t(t, x) =

12σ2(x)

∂2u

∂x2(t, x) +

[b(x) + σ(x)σ′(x)

]∂u∂x

(t, x) + b′(x)u(t, x)

+ f ′(∫ x

−∞u(t, y)dy

)u(t, x),

u(0, x) = V ′0(x).

(3)

L’équation (3) est l’équation au gradient correspondant à une équation du type (1) où l’opérateur de dérivéeseconde a été remplacé parb(x) ∂

∂x + 12 σ

2(x) ∂2

∂x2 . L’extension correspondante de la méthode de Shermanet Peskin (qui avaient considéré le casb≡ 0, σ ≡ 1 et donc n’avaient pas eu à identifier la bonne diffusionà discrétiser pour simuler les libres parcours des particules) est la suivante :(i) à l’instant0, on initialise les particules comme décrit au paragraphe 1 ;(ii) on fixe un pas de temps∆t ; entre les instantsk∆t et (k + 1)∆t chaque particule vivante à l’instant

k∆t se déplace indépendamment des autres ; sa position à l’instant(k+ 1)∆t est

Y (k+1)∆t = Y k∆t +{σ(Y k∆t)σ′(Y k∆t)− b(Y k∆t)

}∆t+ σ(Y k∆t)(W(k+1)∆t −W∆t)

+12σ(Y k∆t)σ′(Y k∆t)

{(W(k+1)∆t −W∆t)2 −∆t

}.

On remarque qu’on utilise le schéma de Milstein pour discrétiser l’équation différentielle stochastique

dYt =(σ(Yt)σ′(Yt)− b(Yt)

)dt+ σ(Yt)dWt,

dont l’équation de Fokker–Planck associée est

∂p

∂t(t, x) =

12σ2(x)

∂2p

∂x2(t, x) +

[b(x) + σ(x)σ′(x)

] ∂p∂x

(t, x) + b′(x)p(t, x),

ce qui établit le lien avec (3).(iii) À chaque pas de temps on crée et on détruit des particules selon la règle suivante. Nous notons

NN(k+1)∆t le nombre de particules vivantes à l’instant(k + 1)∆t, et

V N((k+ 1)∆t, x

):=

1N

NN(k+1)∆t∑j=1

H(x− yj

(k+1)∆t

),

où{yj(k+1)∆t} est l’ensemble des particules simulées vivantes à l’instant(k+ 1)∆t.

La particule numéroj branche avec probabilité :∆t∣∣f ′ ◦ V N ((k + 1)∆t, yj

(k+1)∆t)∣∣.

Elle meurt et, sif ′ ◦ V N ((k+ 1)∆t, yj(k+1)∆t) � 0, elle donne alors naissance à deux particules.

936

Vitesse de convergence d’une méthode particulaire stochastique avec branchements

THÉORÈME 2.1. –Supposons :(i) la fonction f appartient à C1

b(R). Elle vérifie :

f(0) = f(1) = 0; f ′(0)> 0;

f ′(x) � f ′(0) pour tout x ∈ [0,1]; f ′(x)< 0 pour tout x ∈ R+ � [0,1];

(ii) les fonctions b et σ appartiennent à C∞b (R). De plus, il existe un réel C0 > 0 tel que σ(x) � C0 > 0

pour tout x ;(iii) la fonction V ′

0 est une densité de probabilité telle que

∃M > 0, ∃η > 0, ∃α> 0, ∀|x|>M,∣∣V ′

0(x)∣∣ � η exp

(−αx2

).

Soit Φ une fonction positive de L1(R)∩ L∞(R). En notant

‖g‖L1,Φ(R) :=∫

R

∣∣g(x)∣∣Φ(x)dx

pour toute fonction g Lebesgue intégrable, on a : il existe C > 0 telle que pour tout N � 1 et tout0<∆t < 1,

supk∈{0,...,T/∆t}

E∥∥V (k∆t, ·)− V N (k∆t, ·)

∥∥L1,Φ(R)

� C√N

+C√

∆t.

Remarque 2.2. – 1. L’introduction de la norme‖ · ‖L1,Φ(R) est due au fait que, contrairement àV (t, x),la fonction aléatoireV (t, x) ne tend pas vers 1 quandx tend vers+∞ ; par conséquent, presque sûrementla fonctionV − V N n’est pas intégrable à l’infini.

2. Il existe des jeux d’hypothèses autres que (i) et (iii) qui conduisent à des estimations très similaires ; parexemple,V0 peut être la fonction de répartition d’une mesure discrète : voir la thèse d’Hervé Régnier [4].

Idée de la démonstration. – L’erreur globale de la méthode est décomposée en plusieurs termes :– L’erreur due à l’approximation de la condition initialeV0 parV N

0 : il s’agit de contrôler l’écart entre lessolutions de (1) avec conditions initiales respectivesV0 etV N

0 ; on applique le lemme 2.2 de Bernard, Talayet Tubaro [1].– L’erreur due à la discrétisation des temps de branchement : pour la contrôler, on introduit uneapproximation du processus de branchement sous-jacent à l’équation (3) en imposant à l’horloge desbranchements de prendre les valeurs discrètesk∆t ; on montre ainsi que siV N est la fonction de répartitionempirique des particules vivantes de l’arbre correspondant, on a

supk∈{0,...,T/∆t}

E∥∥V (k∆t, ·)−EV N (k∆t, ·)

∥∥L1,Φ(R)

�C√

∆t.

– L’erreur due à l’approximation des libres parcours à l’aide du schéma de Milstein : si on modifiel’arbre correspondant àV N en remplaçant(Yt) par (Y k∆t), en notantV N (k∆t, ·) la nouvelle fonctionde répartition empirique, on obtient :

supk∈{0,...,T/∆t}

E∥∥V N (k∆t, ·)−E V N (k∆t, ·)

∥∥L1,Φ(R)

�C√

∆t.

– L’erreur statistique consistant à estimerE V N (k∆t, ·) par V N (k∆t, ·), pour laquelle on obtient

supk∈{0,...,T/∆t}

E∥∥V N (k∆t, ·)−E V N (k∆t, ·)

∥∥L1,Φ(R)

� C√N.

937

H. Régnier, D. Talay

– Enfin, l’erreur de dépendance, qui reflète la non-linéarité de l’équation (3) : l’arbre correspondant àV N (k∆t, ·) n’est pas simulable numériquement puisque sa loi de reproduction dépend de la fonctioninconnueV (t, x) :=

∫ x

−∞ u(t, y)dy ; on remplace doncV (t, x) par la distribution empirique des particulessimulées, ce qui produit l’interaction entre les particules ; l’analyse de la propagation en temps de l’erreurinduite est extrêmement longue et technique ; elle conduit à la récurrence suivante : en notant

εk∆t := E∥∥V N (k∆t, ·)− V N (k∆t, ·)

∥∥L1,Φ(R)

,

on a :

εk∆t �C∆t

k−1∑�=2

E∥∥V N

((k− #)∆t, ·

)− V N

((k− #)∆t, ·

)∥∥L1,Φ(R)

+C√

∆t,

à partir de laquelle on peut déduire la vitesse de convergence annoncée.Un lemme technique préalable aux estimations ci-dessus montre que tout moment d’ordrep du nombre

de particules simulées vivantes est fini et vérifie :

∃C > 0, ∀0<∆t < 1, E(NN

k∆t

)p �CNp, ∀k = 1, . . . ,T

∆t.

Pour le détail des preuves, nous renvoyons à la thèse [4].

Références bibliographiques

[1] Bernard P., Talay D., Tubaro L., Rate of convergence of a stochastic particle method for the Kolmogorov equationwith variable coefficients, Math. Comp. 63 (208) (1994) 555–587.

[2] Chauvin B., Olivares-Rieumont O., Rouault A., Fluctuations for spatial branching process with mean-fieldinteraction, Adv. Appl. Probab. (1991).

[3] Chauvin B., Rouault A., A stochastic simulation for solving scalar reaction–diffusion equations, Adv. Appl.Probab. 22 (1990) 88–100.

[4] Régnier H., Vitesse de convergence de méthodes particulaires stochastiques avec branchements, Thèse de doctorat,Université de Provence, 1999.

[5] Sherman A.S., Peskin C.S., A Monte Carlo method for scalar reaction–diffusion equations, SIAM J. Sci. Statis.Comput. 7 (4) (1986) 1360–1372.

938