Analysis of Multiscale Methods for Stochastic Di erential ...

1 Analysisof MultiscaleMethods forStochasticDi erentialEquationsWEINANEP rincetonUniversityDILIUC ourantInstituteANDERICVANDEN-EIJNDENC ourantInstituteAbstractWe analyzea classof numericalschemesproposedin [25] forstochasticdi anddi usive wellas turnallow us to providea thoroughdiscussiononthee ciencyas wellas IntroductionMultiscalemodelingandcomputa tionhave receiveda greatdealof in-terestin recent years(fora review,see[6]).Yet therearerelativelyfewanalyticalresultsav ailablethathelpto assesstheperformanceandpro-videguidancef orthedesigningof paper is to providea thoroughanalysisof a recentlyproposednumericaltechnique[25] (seealso[9]) forstochasticdi (x; y)2Rn Rm:( )8<:_X"t=f(X"t; Y"t; ");X"0=x;_Y"t=1"g(X"t; Y"t; "); Y"0=y:Heref( )2 Rnandg( )2 RmareO(1)functions(possiblyrandom)in",an d"is a smallparameterrepresentingtheratioof thetime-scalesin have assumedthatthephasespacecanbe decomposedintoslow degreesof freedomxandfastonesy.

2 Systemsof thistype arisefrommoleculardynamics,materialscien ces,atmosphere-oceansciences, faildueto theseparationbetweenCommunicationsonPure andAppliedMathematics, ,0001{0048(2003)c 2003 JohnWiley& Sons, {3640/98/000001-48 MULTISCALESTOCHASTICSYSTEMS2theO(") time-scalethatmustbe dealtwithandtheO(1)andO(" 1)time-scalesthatareof [10, 16, 21, 23], thefollowingis knownabout( ). OnO(1)time-scale(advective time-scale),if thedynamicsforY"twithX"t=x xedhasaninvariant probability measure "x(dy) andthefollowinglimitexists:( ) f(x) = lim"!0 ZRmf(x; y; ") "x(dy);thenin thelimitof"!0,X"tconvergesto thesolutionof( )_ Xt= f( Xt); X0=x:OnO(" 1) time-scale(di usive time-scale), uctuationsbecomeimpor-tant. Withtherescaledtimes="t, ( )becomes:( )8>> <>>:_X"s=1"f(X"s; Y"s; ");X"0=x;_Y"s=1"2g(X"s; Y"s; ");Y"0=y:Underappropriateassumptionsonfa ndg, thee ective dynamicsforX"sin thelimitof"!}}

3 0 is a stochasticdi erentialequation,( )_ Xs= b( Xs) + ( Xs)_Ws; X0=x;whereWsis a Wienerprocessandthecoe cients band areexpressedin termsof limitsof expectationssimilarto ( ).Detailswillbe given is oftenthecasethatthedynamicsof thefastvariablesY"tis toocomplicatedforthecoe cients f, band to be [25] is to approximate f, band numericallyby solvingtheoriginal nescaleproblemontimeintervalsof anintermediatescale,andusethatdatatoevol ve theslow beenproposed[5,12, 13].ForkineticMonte Carloschemesinvolvingdisparaterates,Novo tny et [13] a techniquecalledprojective dynamicswhich reducestheMarkov chainonto a smallerstatespaceinvolvingonlytheslow similaridea,alsonamedprojective dynamics,was proposedin [12] fordissipative [12] canalsobe viewedas a specialcaseof a generalclassof methodscalledChebychevmethods forsti ODEs[17].

4 MULTISCALESTOCHASTICSYSTEMS3 Ofparticularrelevanceto thepresent workis theframeworkof Het-erogeneousMultiscaleMethods proposedin [5] (HMMforshort),sinceitprovidesa verynaturalsettingforthemethod proposedin [25]. At thesametime,it alsogives a generalprinciplefortheanalysisof thepresent setting,thegeneraltheoremproved in [5]statesthatif themacro-solver is stable,thenthenumericalerrorconsistsof twoparts:a partdueto theerrorin themacro-solver anda newpart,dueto theapproximationof themacro-scaledata(herethe , aand b) generalthesecondpartconsistsof theerrorin themicro-solver, severalclassesof multiscalemethods (seein particular[4, 7, 11, 22]).It is alsothestrategythatwewillfollow in thealgorithmwereanalyzedin [4, 8].We willstudyequationslike ( )bothontheadvective time-scale(section2) andthedi usive time-scale(section3).

5 Afterpresentingthemultiscalenumericalsch emes( , , ),we prove con-vergencetheoremsfortheseschemes( , , ),andusetheseresults( )to determinetheoptimalsetof numer-icalparametersto be usedat a alsoillustratetheschemesandtestourtheore msonnumericalexamples( ).Beforeendingthisintroduction,letusnote thata simpletrick fordealingwiththemultiscalednatureof theproblemabove is to increasetheparameter"to an optimalvalueaccordingto a given indeedusedin thearti cialcompressibility method forcomputingnearlyincompressible ows[2],andtheCar-Parrinellomethod [1],andhasprovento be much moree cient thandirectsolutionsof themicroscalemodelwiththeoriginal" , ourresultsshow thatif usedcorrectly, themultiscaleschemeis at leastas e cient (ontheadvective time-scale)ormuch moree cient (onthedi usive time-scale)

6 Thana directschemeevenif anoptimalvalueof"is usedin themicroscalemodelto addition,themultiscaleschemecanbe appliedeven in situationswhenexplicitlyincreasingtheval ueof"in theoriginalequationscanbedi Advective time-scaleConsiderthefollowingdynamics:( )8> <>:_X"t=a(X"t; Y"t; ");X"0=x;_Y"t=1"b(X"t; Y"t; ") +1p" (X"t; Y"t; ")_Wt; Y"0=y;wherea2Rn,b2 Rmand 2Rm RdaredeterministicfunctionsandWtis a neC1bto bethespaceof smoothfunctionswithboundedderivatives of any cientsa,band , viewed asfunctionsof(x; y; "), are inC1b,aand are existsan >0suchthat8(x; y; "),j T(x; y; ")yj2 jyj2 existsa >0suchthat8(x; y1; y2; "),h(y1 y2);(b(x; y1; ") b(x; y2; "))i+k (x; y1; ") (x; y2; ")k2 jy1 y2j2;wherek weakenedbutis usedhereforthesimplicity usionis a dissipative ,onecanshow thatforeach (x; "), thefollowingdynamics( )_Yx;"t=1"b(x; Yx;"t; ") +1p" (x; Yx;"t; ")_Wt;Yx;"0=y;is exponentiallymixingwitha uniqueinvariant probability measure "x(dy).

7 De ne( ) a(x) = lim"!0 ZRma(x; y; ") "x(dy):It is proved later(witherrorestimates) , , ,X"tconvergesstronglyas"!0 to thesolution Xtof thefollowingdynamics( )_ Xt= a( Xt); X0= usuallyof interestis thebehaviorof theslow variableX"twhoseleadingordertermforsmall "is Xt. Butthecoe cient ain thee ectiveequation( )for Xtis givenviaanexpectationwithrespectto mea-sure "x(dy) which is usuallydi cultor impossibleto obtainanalytically,especiallywhenthedime nsionmis [25] is to solve ( )witha macro-solver inwhich ais estimatedby solvingthemicro-scaleproblem( ). Thisleadsto multiscaleschemeswhosestructureis explainednext.(For simplicitywe restrictourselves to implicitsolversisstraightforward,butit tendsto make thealgorithmandimplementationmoreinvolve d.)At each macro-time-stepn, havingthenumericalsolutionXn, we needto estimate a(Xn) in orderto move to stepn+1.

8 Since Xtis deterministic,as macro-solver we may useany stableexplicitODEsolver such as a for-wardEuler,a Runge-Kutta,or a linearmulti-stepmethod. For instance,in thesimplestcasewhenforwardEuleris selectedas themacro-solver,we have( )Xn+1=Xn+ ~an t;where tis themacro-time-stepsizeand~anis theapproximationof a(Xn)which we obtainin a two-stepprocedure:1. We solve ( )usinga micro-solver forstochasticODEsanddenotethesolutionbyf Yn; replicascanbe created,in which casewe denotethesolutionsbyfYn;m;jgwherejis We thende neanapproximationof a(Xn) by thefollowingtimeandensembleaverage:~an=1 M NMXj=1nT+N 1Xm=nTa(Xn; Yn;m;j; ");whereMis thenumber of replicas,Nis thenumber of stepsin thetimeaveraging,andnTis thenumber of stepswe skipto themicro-solver,denotingby`its weakorderof accuracy, foreachMULTISCALESTOCHASTICSYSTEMS6reali zationwe may usethefollowing rstorderscheme(`= 1):( )Yin;m+1=Yin;m+1p"Xj ij(Xn; Yn;m; ") jm+1p t+1"bi(Xn; Yn;m; ") t+1"XjkAijk(Xn; Yn;m; ")skjm+1 t;or thesecondorderscheme(`= 2):( )Yin;m+1=Yin;m+1p"Xj ij(Xn; Yn;m; ") jm+1p t+1"bi(Xn; Yn;m; ") t+1"XjkAijk(Xn; Yn;m; ")skjm+1 t+12"3=2 XjBij(Xn; Yn;m.)

9 ") jm+1 t3=2+12"2Ci(Xn; Yn;m; ") t2:For theinitialcondition,we takeY0;0= 0 and( )Yn;0=Yn 1;nT+N 1; macro-time-stepnarechosento be their nalvaluesfrommacro-time-stepn ( )and( ) tis themicro-time-stepsize(notethatit onlyappearsin termof theratio t="=: ), andthecoe cients arede nedas8>>>>>>> <>>>>>>>:Aijk=Xl(@l ij) lk;Bij=Xl lj@lbi+bl@l ij +12 Xklgkl@k@l ij;Ci=Xjbj@jbi+12 Xjkgjk@j@kbi;whereg= Tandthederivatives aretakenwithrespecttoy. Therandomvariablesf ,andskjm=8>>>> <>>>>:12 km jm+zkjm;k < j;12 km jm zjkm;k > j;12 ( jm)2 1 ; k=j; 12g= thissection,we give therateof strongconvergencefortheschemede-scribed above , , at thebeginningof section2. Throughouttheremainingof thepaper,we willdenotebyCa genericpositive constant which may changeitsvaluefromlineto stableandkth orderac-curatefor( )and tand t="are small >0,there existsa constantC >0independentof("; t; t; nT; M; N)suchthat( )supn T0= tEjX"tn Xnj C p"+ tk+ ( t=")`+e 12 nT( t=")pN( t=") + 1(R+pR) +p tpM(N( t=") + 1)!

10 ;wheretn=n tand( )R= t1 e 12 (nT+N 1)( t="):TheerrorestimateonjX"tn Xnjin ( )canbe dividedinto "t Xtj, where Xtis thesolutionof thee ective equation( ). Xtn Xnj, where Xnis theapproximationof Xtngivenby theselectedmacro-solver assumingthat a(x) is Xn rstpartis a principleof averagingestimateforstochasticODEs,andwe willshow in t T0 EjX"t Xtj Cp":Thispartgives riseto the rsttermin ( ).Thesecondpartis a standardODEestimateandbasedon thesmooth-nessof agivenby theAppendix,we have( )supn T0= tj Xtn Xnj C tk:MULTISCALESTOCHASTICSYSTEMS8 Thisis thesecondtermin ( ).Thethirdpartaccounts fortheerrorcausedby using~aninsteadof a(Xn) in riseto a termof orderO(")which is dominatedbyCp", andto theremainingthreetermsin ( )which willbe thispartof theerror,theterm( t=")`is dueto themicro-timediscretizationwhich inducesadi erencebetweentheinvariant measuresof 12 nT( t=")pN( t=") + 1(R+pR)accounts fortheerrorscausedby relaxationof ,thefactorRappearsdueto theway in ( )thatwe initializethefastvariablesat each erentinitializationwillleadtoa similarerrorestimatewithdi erent valuesofR.