A GENUINELY HIGH ORDER TOTAL VARIATION DIMINISHING

SIAMJ.NUMER.ANAL.c2010SocietyforIndustrialandAppliedMathematicsVol.0,No.0,pp.000–000AGENUINELYHIGHORDERTOTALVARIATIONDIMINISHINGSCHEMEFORONE-DIMENSIONALSCALARCONSERVATIONLAWS∗XIANGXIONGZHANG†ANDCHI-WANGSHU‡Abstract.Itiswellknownthatfinitedifferenceorfinitevolumetotalvariationdiminishing(TVD)schemessolvingone-dimensionalscalarconservationlawsdegeneratetofirstorderaccuracyatsmoothextrema[S.OsherandS.Chakravarthy,SIAMJ.Numer.Anal.,21(1984),pp.955–984],thusTVDschemesareatmostsecondorderaccurateintheL1normforgeneralsmoothandnon-monotonesolutions.However,Sanders[Math.Comp.,51(1988),pp.535–558]introducedathirdorderaccuratefinitevolumeschemewhichisTVD,wherethetotalvariationisdefinedbymeasuringthevariationofthereconstructedpolynomialsratherthanthetraditionalwayofmeasuringthevari-ationofthegridvalues.Byadoptingthedefinitionofthetotalvariationforthenumericalsolutionsasin[R.Sanders,Math.Comp.,51(1988),pp.535–558],itispossibletodesigngenuinelyhighorderaccurateTVDschemes.Inthispaper,weconstructafinitevolumeschemewhichisTVDinthissensewithhighorderaccuracy(uptosixthorder)intheL1norm.NumericaltestsforafifthorderaccurateTVDschemewillbereported,whichincludetestcasesfromtrafficflowmodels.Keywords.hyperbolicconservationlaws,finitevolumescheme,totalvariationdiminishing,totalvariationbounded,highorderaccuracy,conservativeformAMSsubjectclassification.65M06DOI.10.1137/0907643841.Introduction.Weconsidernumericalsolutionsofone-dimensionalhyper-bolicscalarconservationlaw(1.1)ut+f(u)x=0,u(x,0)=u0(x),whereu0(x)isassumedtobeaboundedvariationfunction.Themaindifficultyinsolving(1.1)isthatthesolutionmaycontaindiscontinuitieseveniftheinitialconditionissmooth.Successfulnumericalschemesforsolving(1.1)areusuallytotalvariationstable,forexample,thetotalvariationdiminishing(TVD)schemes[1]orthetotalvariationbounded(TVB)schemes[14],oressentiallynonoscillatory,forexample,theessentiallynonoscillatory(ENO)schemes[2,15]ortheweightedENO(WENO)schemes[6,4].ENOandWENOschemes,althoughuniformlyhighorderaccurateandstableinap-plications,donothavemathematicallyprovableTVBpropertiesforgeneralsolutionsanddonotsatisfyamaximumprinciple.ItiscertainlydesirabletohaveaTVDorTVBscheme,whichsharestheTVDpropertyoftheexactentropysolutionof(1.1),satisfiesamaximumprinciple,andhasatleastaconvergentsubsequencetoaweaksolutionof(1.1)duetoitscompactness.∗ReceivedbytheeditorsJuly9,2009;acceptedforpublication(inrevisedform)April2,2010;publishedelectronicallyDATE.ThisresearchwassupportedbyNSFgrantDMS-0809086andAFOSRgrantFA9550-09-1-0126.†DepartmentofMathematics,BrownUniversity,Providence,RI02912([e-mail]).‡DivisionofAppliedMathematics,BrownUniversity,Providence,RI02912([e-mail]).12XIANGXIONGZHANGANDCHI-WANGSHUTypically,forafinitedifferenceschemewiththenumericalsolutiongivenbythegridvaluesuj,orafinitevolumeschemewiththenumericalsolutiongivenbythecellaveragesuj,thetotalvariationofthenumericalsolutionismeasuredby(1.2)TV(u)=j|uj+1−uj|,whichisthestandardboundedvariationseminormwhenthenumericalsolutionisconsideredtobeapiecewiseconstantfunctionwiththedatauj.AschemeisTVDifthenumericalsolutionsatisfiesTV(un+1)≤TV(un),whereunreferstothenumericalsolutionatthetimeleveltn.ATVBschemeisonewhichsatisfiesTV(un)≤Mforallnsuchthattn≤T,wheretheconstantMdoesnotdependonthemeshsizesbutmaydependonT.AsufficientconditionforaschemetobeTVBisTV(un+1)≤TV(un)+MΔtorTV(un+1)≤(1+MΔt)TV(un),whereMisaconstantandΔtisthetimestep.ItiswellknownthatfinitedifferenceorfinitevolumeTVDschemessolving(1.1),wherethetotalvariationismeasuredby(1.2),necessarilydegeneratetofirstorderaccuracyatsmoothextrema[8];thusTVDschemesareatmostsecondorderaccurateintheL1normforgeneralsmoothandnonmonotonesolutions.WhiletheTVBschemesin[14]canovercomethisaccuracydegeneracydifficulty,theschemesarenolongerscale-invariant(scale-invariancereferstothefactthattheschemedoesnotchangewhenxandtarescaledbythesamefactor)andinvolveaTVBparameterMwhichmustbeestimatedandadjustedforindividualproblems.In[12],SandersintroducedathirdorderaccuratefinitevolumeschemewhichisTVD.Themainideain[12]istodefinethetotalvariationbymeasuringthevariationofthereconstructedpolynomials,ratherthanthetraditionalmeasurementasin(1.2).TheschemeofSandersin[12]canbesummarizedinthefollowingsteps:•Startfromthecellaveragesu0jandthecellboundaryvaluesu0j+12foralljfromtheinitialconditionu0(x).•Forn=0,1,...,performthefollowing:1.Reconstructapiecewisequadraticpolynomialsolutionun(x),basedontheinformationunjandunj+12forallj,suchthatun(x)isthirdorderac-curate(degeneratestosecondorderatisolatedcriticalpoints;thereforestillthirdorderintheL1norm),andTVD(1.3)TV(un(x))≤TV(un−1(x)),wherethetotalvariationismeasuredbythestandardboundedvariationseminormofthepiecewisequadraticpolynomialsolutionun(x).Forn=0,TV(un−1(x))istakenastheboundedvariationseminormoftheinitialconditionu0(x).2.EvolvethePDE(1.1)exactlyforonetimestepΔtfromthe“initialcondition”un(x)atthetimeleveltn,andtakethecellaveragesun+1jandthecellboundaryvaluesun+1j+12foralljfromthisexactlyevolvedsolution.Thenreturntos