搜索
Konrad-Zuse-ZentrumfürInformationstechnikBerlinHeilbronnerStr.10,D-10711Berlin-WilmersdorfRalfKornhuberMonotoneMultigridMethodsforEllipticVariationalInequalitiesIIPreprintSC93{19(M arz1994)RalfKornhuberMonotoneMultigridMethodsforEllipticVariationalInequalitiesIIAbstract.Wederivefastsolversfordiscreteellipticvariationalinequalitiesofthesecondkindasresultingfromtheapproximationbypiecewiselinear niteelements.Followingthe rstpartofthispaper,monotonemultigridmethodsareconsideredasextendedunderrelaxations.Again,thecoarsegridcorrectionsarelocalizedbysuitableconstraints,whichinthiscaseare xedby negridsmoothing.Weconsiderthestandardmonotonemultigridmethodinducedbythemultilevelnodalbasisandatruncatedversion.Globalconvergenceresultsandasymptoticestimatesfortheconvergenceratesaregiven.Thenumericalresultsindicateasigni cantimprovementine ciencycomparedwithpreviousmultigridapproaches.Keywords:convexoptimization,adaptive niteelementmethods,multi-gridmethodsAMS(MOS)subjectclassi cations:65N30,65N55,35J85Chapter1IntroductionLet beapolygonaldomainintheEuclideanspaceR2.Weconsidertheoptimizationproblemu2H10( ):J(u)+ (u) J(v)+ (v);v2H10( );(1.1)wherethequadraticfunctionalJ,J(v)=12a(v;v) ‘(v);(1.2)isinducedbyacontinuous,symmetricandH10( ){ellipticbilinearforma( ; )andalinearfunctional‘2H 1( ).Theconvexfunctional oftheform (v)=Z (v(x))dx;(1.3)isgeneratedbyascalarconvexfunction .Denotingz =minfz;0gandz+=maxfz;0gforz2R,then istakentobethepiecewisequadraticconvexfunction (z)=12a1(z 0)2 s1(z 0) +12a2(z 0)2++s2(z 0)+;z2R;(1.4)with xed 02Randnon{negativeconstantsa1;a2;s1;s22R.Moregeneralboundaryconditionscanbetreatedintheusualway.Itiswell{known(c.f.Glowinski[8])that(1.1)canbeequivalentlyrewrittenastheellipticvariationalinequalityofthesecondkindu2H10( ):a(u;v u)+ (v) (u) ‘(v u);v2H10( );(1.5)andadmitsauniquesolutionu2H10( ).Notethat(1.1)becomesalower(orupper)obstacleproblem,ifs1(ors2)tendstoin nity.Non{smoothoptimizationproblemsoftheform(1.1)ariseinalargescaleofapplications,rangingfromfrictionproblemsornon{linearmaterialsinelas-ticitytothespatialproblemsresultingfromtheimplicittime{discretizationoftwo{phaseStefanproblems.Roughlyspeaking,theunderlyingphysicalsituationissmoothinthedi erentphasesu 0andu 0,respectively,butchangesinadiscontinuouswayasupassesthethreshold 0.WerefertoDuvautandLions[4],Glowinski[8]andElliotandOckendon[7]fornumerousexamplesandfurtherinformation.LetTjbeagivenpartitionof intrianglest2Tjwithminimaldiameteroforder2 j.ThesetofinteriornodesiscalledNj.Discretizing(1.1)by1continuous,piecewiselinear niteelementsSj H10( ),weobtainthe nitedimensionalproblemuj2Sj:J(uj)+ j(uj) J(v)+ j(v);v2Sj:(1.6)Observethatthefunctional isapproximatedbySj{interpolationoftheintegrand (v),giving j(v)=Z Xp2Nj (v(p)) (j)p(x)dx;(1.7)where j=f (j)p;p2NjgstandsforthenodalbasisinSj.Ofcourse,(1.6)isuniquelysolvableandcanbereformulatedasthevariationalinequalityuj2Sj:a(uj;v uj)+ j(v) j(uj) ‘(v uj);v2Sj:(1.8)ForconvergenceresultswerefertoElliot[6].Inthispaperwewillderivefastsolversforthediscreteproblem(1.6).Clas-sicalrelaxationmethodsbasedonthesuccessiveoptimizationoftheenergyJ+ jinthedirectionofthenodalbasisarediscussedtosomeextendbyGlowinski[8].Toovercomethewell{knowndrawbacksofsuchsingle{gridrelaxations,HoppeandKornhuber[15]havederivedamultigridalgorithm,whichwasappliedsuccessfullytovariouspracticalproblems[13,16].Asabasicconstructionprinciple,thedi erentphasesmustnotbecoupledbythecoarsegridcorrection.UsingadvancedrelaxationstrategiesofHackbuschandReusken[11,12],Hoppe[14]recentlyderivedagloballydampenedver-siondisplayingaconsiderableimprovementinasymptotice ciencyrates.TheconstructionofthepreviousmultigridmethodswasbasedonthefullapproximationschemesothatthepossibleimplementationasamultigridV{cyclewasclearfromtheverybeginning.However,suitableconditionsforcon-vergencewerelessobvious.Followingthe rstpartofthispaper[18],wewillderivemonotonemultigridmethodsbyextendingthesetof(high{frequent)searchdirections jbyadditional(intentionallylow{frequent)searchdirec-tions.Asaconsequence,ourconstructionstartswithagloballyconvergentmethod,whichthenismodi edinsuchawaythatthee cientimplementa-tionasamultigridV{cyclebecomespossiblewhiletheglobalconvergenceisretained.Itisthemainadvantageofourapproachthatsuchmodi cationscanbestudiedinanelementaryway.Thecorrespondingtheoreticalframeworkwillbederivedinthenextsection.Weformallyintroduceextendedrelaxationmethodsanddescribeso{calledquasioptimalapproximations,preservingtheglobalconvergenceandasymp-toticallyoptimalconvergencerates.TheactualconstructionofquasioptimalapproximationstakesplaceinSec-tion3.Thereasoningisguidedbythebasicobservationthatthestandard2V{cycleforlinearproblemsreliesonsimplerepresentationsoflinearopera-torsandlinearfunctionalsonthecoarsegridspaces.Fornonlinearproblemssuch(approximate)representationscanbeexpectedonlylocally.Conse-quently,thecoarse-gridcorrectionsofourmonotonemultigridmethodsareobtainedfromcertainobstacleproblems,whichare xedbythepreceding negridsmoothing.Inthisway,thecouplingofdi e