; TeX output 1998.07.20:1113޷#HTvDSˍtff$$ffȍ"V cmbx10ComputingTandVisualizationinScienceman9uscriptNo. 8K`y cmr10(willUUbGeinsertedbytheeditor)34$ffffffHNff cmbx12Anffadaptivesubs3divisiontechniquefortheapproximation ՍofffattractorsandinvariantffmeasuresyMic9haelTDellnitz^ 0ercmmi7?,OliverJungeo cmr9Mathematisc9hesTInstitut,Universit`atBayreuth,D-95440Bayreuth,Germany 8Cscmtt8(http://www.uni-bayreuth.de/departments/math/~mdellnitz;http://www.uni-bayreuth.de/departments/math/~ojunge)ҍReceiv9ed:T13January1997/Accepted:29SeptembAer19974Comm9unicatedTby:P:.Deu hardU,vAbstract.2Recently\subGdivisiontechniqueshavebGeen <.introGducedy1inthenumericalinvestigationofthetempGo-ralLbGehaviorofdynamicalsystems.Inthisarticlewein-tertwineu!thesubGdivisionprocesswiththecomputationofinvqariantmeasuresandpropGoseanadaptiveschemeforthePbGoxre nementwhichisbasedonthecombinationofthesemethoGds.Usingthisnewalgorithmthenumericale ortD0forthecomputationofbGoxcoveringsisingene-ral3signi cantlyreduced,andweillustratethisfactbyseveralUUnumericalexamples. ff޳-퍍1 yIn9troQductionRecentlyHsubGdivisionmethodshaveHbeensuccessfullyap-plied}tothenumericalanalysisofcomplexdynamicalbGe-haviorA&(e.g.[7,3,2,4,5]).A&ThesemethoGdscanbeusedfortwoaessentiallydi erentpurpGoses:the rstistounder-standJthegeometricstructureofanunderlyingattractor.Secondly thegoalmaybGetoapproximatetheobservqa-ble dynamicalbGehavioroftheunderlyingsysteminaspGeci cregionofstatespacebythecomputationofin-vqariantmeasures.ThispapGerconcernsthesecondpossi-bility*,kandwepropGoseanadaptiveschemeincorpGoratedintopDthesubGdivisiontechniquewhichallowstoreducethenumericalUUe ortsigni cantly*. »Obviously7)thedynamicalbGehaviorjustneedstobGeapproximatedonthesuppGortofacertaininvqariantmea-sure.EIndeed,theideafortheadaptiveprinciplestatedhereistointertwinethesubGdivisiontechniqueswiththecomputationofanaturalinvqariantmeasure,an&': cmti10SBR-me}'asure,3say*.RoughlyspGeaking,thesizeofthecoveringbGoxesXeisreducedinthosepartsofstatespacewherethenaturalinvqariantmeasure b> cmmi10isconcentrated,and,ontheotherhhand,bGoxesarenotsubdividedinareaswhichhave-measureUUzero. rbffa  -=;cmmi6?Researc9hׅoftheauthorsispartlysuppAortedbytheDeut- 8sc9hejF:orschungsgemeinschaftunderGrantDe448/5-2andbytheTKonrad-Zuse-Zen9trumfA;urInformationstechnikBerlin.,v!MThe${maingoalofthisarticleistoillustratetheef- <.!M ciencyofthenewmethoGdbynumericalexamples.F*or!Mthatw*purpGoseweconsiderseveraldynamicalsystemsfor!MwhichARtheSBR-measureisknownanalyticallysincethis!Mallowsustocomparethenumericalresultsobtainedby!Mthe adaptivesubGdivisionalgorithmtothoseobtainedby!Mthestandar}'d-subGdivisionprocedure.Theadaptivealgo-!Mrithmisessentiallybasedonthecombinationoftwoexi-!Msting\methoGdsforwhichconvergenceresultsareknown.!MHowever,bthisfactdoGesnotimmediatelyimplyconver-!MgencedoftheadaptivemethoGdaswell.Ratherthistheo-!Mreticalbutrelevqantproblemiscurrentlyunderinvesti-!Mgation,UUandtheresultswillbGepublishedelsewhere. Uʍ!MAnGoutlineofthepapGerisasfollows:inSect.2were-!McallthestandardsubGdivisiontechniquefrom[3].Thenu-!Mmerical'wmethoGdfortheapproximationofSBR-measures!MisdescribGedinSect.3.Then,inSect.4,wepresentour!MadaptiveNsubGdivisiontechnique,andtheeciencyofthis!MmethoGdUUisillustratedbyseveralexamplesinSect.5."4!M25TheTstandardsubQdivisionalgorithmf!MThe?apurpGoseistoapproximateinvqariantsetsofdiscrete!MdynamicalUUsystemsoftheform!MxjgٓRcmr7+1Dz=f(xj6); jY=0;1;:::;!MwhereUfisacontinuousUmappingon msbm10R^nq~.Thecentralob-!MjectwhichisapproximatedbythesubGdivisionalgorithm!MdevelopGedUUin[3]istheso-calledr}'elativeglobalattractor,fs!MAQ S=2nu cmex10\ jg O!cmsy70dfjJ;(Q);2(1)!MwhereZQu !", cmsy10R^n Lزisacompactsubset.RoughlyspGeaking,!Mthed setAQ 0HshouldbGeviewedastheunionofunstable!Mmanifoldsofinvariantobje}'ctsinsideQ.FInparticular,AQ!MmayfcontainsubsetsofQwhichcannotbGeapproximated!MbyUUdirectsimulation.!MThemsubGdivisionalgorithmfortheapproximationof!MAQ 'egenerates[*asequenceB0|s;B1;B2;:::yof[* nitecollecti-!MonsAofbGoxeswiththepropertythatforallintegersk>زthe!MsetJQk K=`nS şBW=2BO \cmmi5k$KPBaisacoveringJoftherelativeglobal*޷#HT2]1ɍattractor?underconsideration.Moreover?thesequenceof <.coverings-isconstructedinsuchawaythatthediameterofUUthebGoxes,lύdiam(Bk됲)=.Omaxs3BW=2Bkܣdiam/R(Bq)convergesUUtozerofork!1. VGiven|aninitialcollectionB0|s,oneinductivelyobtainsBk@fromUUBk+B1}Yfork=1;2;:::inUUtwosteps.rq(i)Sub}'division:AConstructanewcollectionx䍑Zv^BksuchthatU][ %BW=2;e^Bk-B8=M &[ 7C}BW=2Bk 0ncmsy5Zcmr51cdaBTand diam"q(x䍑S5^Bk |)8C}Ųdiamt(Bk+B1()TforUUsome0<5<1.ު(ii)Sele}'ction:UUDe nethenewcollectionBk@byVBk=`n qĵBG2x䍑M^Bk`:pf1 (Bq)8\x䍑^B 6=;forUUsomex䍑4^2\B;,2x䍑o^Bk n`os:ThefollowingpropGositionestablishesageneralcon-vergenceUUpropGertyofthisalgorithm.PropQositionT2.13y([3]).bL}'etJYAQ betheglobalattractorr}'elativetothecompactsetQ,andletB0)`bea nitecol-le}'ctionofclosedsubsetswithQ0C=Q.Thenlύ0glJanduk=j^uk l&jBk %H:QR}'emark4.1.(a)+kIn^therealizationofthealgorithmwetypically[subGdividetheboxesinthecollectionB䍐M۱+K[k Ʋbybisection.sThisguaranteesthatthenumbGerofboxesisnotgrowingtoGofast.F*orthedetailsconcerningtheimplementationUUthereaderisagainreferredto[3,4].ު(b)In~principlethereissomefreedominchoGosingthesequence fk됸gofpGositivenumbGersusedinthesub-division step.Notehowever thatthissequencedeter-minesEthenumbGerEofboxeswhichwillbGesubdividedandShenceithasasigni cantin uenceonthestoragerequirement.InthecomputationsitturnedouttobGequiteUUecienttochoGosetheaverageWk=<$1Kwfe s (֍NkI&X 7̙BW=2Bk*$uk됲(Bq)=<$1Kwfe s (֍Nk!;$whereUUNk@isthenumbGerUUofboxesinBk됲.(c)In(thenumericalrealizationoftheselectionstep(iii)wecheckwhether^ukɲ(Bq)l>where>0ischosensucientlysmallwithrespGecttothemachinepreci-sion.䧍5yNumericalTexamplesxInthissectionweillustratetheeciencyoftheadaptiveschemeTbyseveralnumericalexamples.Firstweconsi-derthreeone-dimensionalmappingsforwhichtheSBR-measuresaareknownanalytically*.Forthesecaseswewillseeathat,asexpGected,thenewtechniqueisparticularlyusefuliftheunderlyinginvqariantdensityhassingulari-ties.nAdditionallyweconsidertheHGenonmapasatwo-dimensionalexampleandshowthebGoxre nementpro-duced`bytheadaptivesubGdivisionalgorithmatacertainstep.BeforeYproGceedingletusindicatesomedetailscon-cerningdtheimplementationoftheadaptivesubGdivisionalgorithm:ŘJ!M(t : cmbx9Table)1.Comparison;bAet9weenthestandardandtheadaptive 8!MsubAdivisionwalgorithmfortheLogisticMap.Theminimalbo9x!Mv9olumeTineachrowis2-=q% cmsy6`/ !M]ff-5" cmmi9`"n9umbAerTofbo9xesL-=Aacmr61*-error 7?standardJadaptiv9ey6standardadaptiv9e,ff-}q6?64J17y60.13900.14318?256J34y60.06700.076512?4096J151y60.02100.025816?65536J679y60.00640.0073 f20?2-=20J2831y6-0.0021ff-Z.(a)!MThexEsubGdivisionisalwaysxEdonebybisectionandthe <.!MbGoxesarestoredinabinarytree.Thiswaywekeep!MtheUUstoragerequirementatalowlevel.(b)!MF*orHthecomputationofthetransitionprobabilities!Mm(f^1 (BiTL)\Bj6)Ain(2)weuseanexhaustiontechni-!MqueasdescribGedin[8].Thismethodisparticularly!Musefulf*when{asinourexamples{loGcalLipschitz!MconstantsL5areavqailablefortheunderlyingdynamical!Msystem.h(c)!MThecomputationofthediscretemeasuresisdoneby!ManfinversepGowermethoGd.Inthesolutionofthecor-!MrespGonding linearsystemsthefactistakenintoac-!McountthatthediscretizedF*robGenius-PerronopGerator!MisUUextremelysparse. Ƽ!MTheݙadaptivealgorithmisintegratedintotheC++coGde!M'm#R cmss10GAIO(GlobalAnalysisofInvqariantOb8jects).Alink!Mto+adetaileddescriptionofGAIO+ecanbGefoundonthe!MhomepagesUUoftheauthors.?!MThr}'eeone-dimensionalexamplesꍒ!MMotivqatedDbythenumericalinvestigationsin[6]weap-!Mply1theadaptivesubGdivisionalgorithmtothreedi e-!Mrentl5one-dimensionaldynamicalsystemsontheintervqal!M[0;1].Ineachcasewehavechosentheinitialcollection!MB0C=f[0;1]g._1.!MAsJa rstexampleweconsidertheLogisticMapf1C:!M[0;1]![0;1],!Mf1|s(x)=x(18x)!MforT=4.Theuniqueabsolutelycontinuousinvqariant!MmeasureUUoff1Ȳhasthedensity!Mh1|s(x)=<$1Kwfe4}T ɍ[ٟs0p [ڟs0fe$n5Ѝx(18x)W\!M(seee.g.[10]).Usingthestandardandtheadaptive!Malgorithmwehaveapproximatedthisdensityonse-!Mveral"ZlevelsandtheresultsareshowninT*able1.We!MremarkJthateventhecomputationfor`_=20Jonly!MtakesUUabGout50seconanMIPSR4400cpu.!MInJFig.5weillustratethefactthatthesizeofthe!MbGoxes~ismuchsmallerforthosewhicharecloseto!MzeroO&orone.Indeed,thisiswhatweexpGectsincethe!MdensityUUhassingularitiesinthesepGoints.2.!MW*eUUconsiderthemapf2C:[0;1]![0;1], !Mf2|s(x)=8 >>< >>:P<$2x]ڟwfeln (֍18xr2-{forCb0x cmmi10 0ercmmi7O \cmmi5K`y cmr10ٓRcmr7Zcmr5u cmex10