35Monotone multigrid methods for elliptic variatio

Konrad-Zuse-ZentrumfürInformationstechnikBerlinHeilbronnerStr.10,D-10711Berlin-WilmersdorfRalfKornhuberMonotoneMultigridMethodsforEllipticVariationalInequalitiesIIPreprintSC93{19(Marz1994)RalfKornhuberMonotoneMultigridMethodsforEllipticVariationalInequalitiesIIAbstract.Wederivefastsolversfordiscreteellipticvariationalinequalitiesofthesecondkindasresultingfromtheapproximationbypiecewiselinearniteelements.Followingtherstpartofthispaper,monotonemultigridmethodsareconsideredasextendedunderrelaxations.Again,thecoarsegridcorrectionsarelocalizedbysuitableconstraints,whichinthiscasearexedbynegridsmoothing.Weconsiderthestandardmonotonemultigridmethodinducedbythemultilevelnodalbasisandatruncatedversion.Globalconvergenceresultsandasymptoticestimatesfortheconvergenceratesaregiven.Thenumericalresultsindicateasignicantimprovementineciencycomparedwithpreviousmultigridapproaches.Keywords:convexoptimization,adaptiveniteelementmethods,multi-gridmethodsAMS(MOS)subjectclassications:65N30,65N55,35J85Chapter1IntroductionLetbeapolygonaldomainintheEuclideanspaceR2.Weconsidertheoptimizationproblemu2H10():J(u)+(u)J(v)+(v);v2H10();(1.1)wherethequadraticfunctionalJ,J(v)=12a(v;v)‘(v);(1.2)isinducedbyacontinuous,symmetricandH10(){ellipticbilinearforma(;)andalinearfunctional‘2H1().Theconvexfunctionaloftheform(v)=Z(v(x))dx;(1.3)isgeneratedbyascalarconvexfunction.Denotingz=minfz;0gandz+=maxfz;0gforz2R,thenistakentobethepiecewisequadraticconvexfunction(z)=12a1(z0)2s1(z0)+12a2(z0)2++s2(z0)+;z2R;(1.4)withxed02Randnon{negativeconstantsa1;a2;s1;s22R.Moregeneralboundaryconditionscanbetreatedintheusualway.Itiswell{known(c.f.Glowinski[8])that(1.1)canbeequivalentlyrewrittenastheellipticvariationalinequalityofthesecondkindu2H10():a(u;vu)+(v)(u)‘(vu);v2H10();(1.5)andadmitsauniquesolutionu2H10().Notethat(1.1)becomesalower(orupper)obstacleproblem,ifs1(ors2)tendstoinnity.Non{smoothoptimizationproblemsoftheform(1.1)ariseinalargescaleofapplications,rangingfromfrictionproblemsornon{linearmaterialsinelas-ticitytothespatialproblemsresultingfromtheimplicittime{discretizationoftwo{phaseStefanproblems.Roughlyspeaking,theunderlyingphysicalsituationissmoothinthedierentphasesu0andu0,respectively,butchangesinadiscontinuouswayasupassesthethreshold0.WerefertoDuvautandLions[4],Glowinski[8]andElliotandOckendon[7]fornumerousexamplesandfurtherinformation.LetTjbeagivenpartitionofintrianglest2Tjwithminimaldiameteroforder2j.ThesetofinteriornodesiscalledNj.Discretizing(1.1)by1continuous,piecewiselinearniteelementsSjH10(),weobtainthenitedimensionalproblemuj2Sj:J(uj)+j(uj)J(v)+j(v);v2Sj:(1.6)ObservethatthefunctionalisapproximatedbySj{interpolationoftheintegrand(v),givingj(v)=ZXp2Nj(v(p))(j)p(x)dx;(1.7)wherej=f(j)p;p2NjgstandsforthenodalbasisinSj.Ofcourse,(1.6)isuniquelysolvableandcanbereformulatedasthevariationalinequalityuj2Sj:a(uj;vuj)+j(v)j(uj)‘(vuj);v2Sj:(1.8)ForconvergenceresultswerefertoElliot[6].Inthispaperwewillderivefastsolversforthediscreteproblem(1.6).Clas-sicalrelaxationmethodsbasedonthesuccessiveoptimizationoftheenergyJ+jinthedirectionofthenodalbasisarediscussedtosomeextendbyGlowinski[8].Toovercomethewell{knowndrawbacksofsuchsingle{gridrelaxations,HoppeandKornhuber[15]havederivedamultigridalgorithm,whichwasappliedsuccessfullytovariouspracticalproblems[13,16].Asabasicconstructionprinciple,thedierentphasesmustnotbecoupledbythecoarsegridcorrection.UsingadvancedrelaxationstrategiesofHackbuschandReusken[11,12],Hoppe[14]recentlyderivedagloballydampenedver-siondisplayingaconsiderableimprovementinasymptoticeciencyrates.TheconstructionofthepreviousmultigridmethodswasbasedonthefullapproximationschemesothatthepossibleimplementationasamultigridV{cyclewasclearfromtheverybeginning.However,suitableconditionsforcon-vergencewerelessobvious.Followingtherstpartofthispaper[18],wewillderivemonotonemultigridmethodsbyextendingthesetof(high{frequent)searchdirectionsjbyadditional(intentionallylow{frequent)searchdirec-tions.Asaconsequence,ourconstructionstartswithagloballyconvergentmethod,whichthenismodiedinsuchawaythattheecientimplementa-tionasamultigridV{cyclebecomespossiblewhiletheglobalconvergenceisretained.Itisthemainadvantageofourapproachthatsuchmodicationscanbestudiedinanelementaryway.Thecorrespondingtheoreticalframeworkwillbederivedinthenextsection.Weformallyintroduceextendedrelaxationmethodsanddescribeso{calledquasioptimalapproximations,preservingtheglobalconvergenceandasymp-toticallyoptimalconvergencerates.TheactualconstructionofquasioptimalapproximationstakesplaceinSec-tion3.Thereasoningisguidedbythebasicobservationthatthestandard2V{cycleforlinearproblemsreliesonsimplerepresentationsoflinearopera-torsandlinearfunctionalsonthecoarsegridspaces.Fornonlinearproblemssuch(approximate)representationscanbeexpectedonlylocally.Conse-quently,thecoarse-gridcorrectionsofourmonotonemultigridmethodsareobtainedfromcertainobstacleproblems,whicharexedbytheprecedingnegridsmoothing.Inthisway,thecouplingofdie