Monotone multigrid methods for elliptic variationa

MonotoneMultigridMethodsforEllipticVariationalInequalitiesI1RalfKornhuberKonrad{Zuse{ZentrumfurInformationstechnikBerlinHeilbronnerStr.10,D{10711Berlin,Fed.Rep.ofGermanyAbstract.Wederivefastsolversfordiscreteellipticvariationalinequali-tiesoftherstkind(obstacleproblems)asresultingfromtheapproximationofrelatedcontinuousproblemsbypiecewiselinearniteelements.Usingbasicideasofsuccessivesubspacecorrection,wemodifywell{knownrelax-ationmethodsbyextendingthesetofsearchdirections.Extendedunder-relaxationsarecalledmonotonemultigridmethods,iftheyarequasioptimalinacertainsense.Byconstruction,allmonotonemultigridmethodsaregloballyconvergent.Wetakeacloserlookattwonaturalvariants,thestan-dardmonotonemultigridmethodandatruncatedversion.Fortheconsid-eredmodelproblems,theasymptoticconvergenceratesresultingfromthestandardapproachsuerfrominsucientcoarse{gridtransport,whilethetruncatedmonotonemultigridmethodprovidesthesameeciencyasintheunconstrainedcase.Keywords:obstacleproblems,adaptiveniteelementmethods,multigridmethodsAMS(MOS)subjectclassications:65N30,65N55,35J851toappearinNumer.Math.1IntroductionLetbeapolygonaldomainintheEuclideanspaceR2.Weconsidertheoptimizationproblemu2K:J(u)J(v);v2K;(1.1)onaclosed,convexsubsetKH10()oftheformK=fv2H10()jv(x)’(x)a.e.ing;(1.2)withsomeobstaclefunction’2H1()\C(),satisfying’(x)0ontheboundary@.ThequadraticfunctionalJ,J(v)=12a(v;v)‘(v);v2K;(1.3)isinducedbyacontinuous,symmetricandH10(){ellipticbilinearforma(v;w)=Z2Xi;j=1aij@iv@jwdxandalinearfunctional‘2H1().Itiswell{known(c.f.Glowinski[15])thattheobstacleproblem(1.1)canberewrittenasthefollowingellipticvariationalinequalityoftherstkindu2K:a(u;vu)‘(vu);v2K;(1.4)andadmitsauniquesolutionu2K.Obstacleproblemsplayanimportantroleinthemathematicalmodelingofavarietyoffreeboundaryproblems,arisingforinstanceinporousmediaow,devicesimulationornonlinearmechanics.WerefertoBaiocchiandCapelo[1],Cottleetal.[10],Glowinski[15],KinderlehrerandStampaccia[23]orRodrigues[31]fordetailedinformation.LetTjbeagivenpartitionofintrianglest2Tjwithminimaldiameteroforder2j.WedenotethesetofinteriornodesandedgesbyNjandEj,respectively.Discretizing(1.1)bycontinuous,piecewiselinearniteelementsSj,weobtainthenitedimensionalproblemuj2Kj:J(uj)J(v);v2Kj:(1.5)HerethesetKH10()isreplacedbyitsdiscreteanalogueKjSj,Kj=fv2Sjjv(p)’j(p);p2Njg;1inducedforexamplebytheSj{interpolate’jof’.Ofcourse,(1.6)isuniquelysolvableandcanbereformulatedasthevariationalinequalityuj2Kj:a(uj;vuj)‘(vuj);v2Kj:(1.6)Itiswell{known(c.f.Glowinski[15])thatujisconvergingtouinH10(),ifthemeshsizeofTjtendstozeroandtheinterioranglesoft2Tjareuniformlyboundedfrombelow.LetjdenotethesetofnodalbasisfunctionsofSj.ThestandardprojectedGauss{Seidelmethodfortheiterativesolutionof(1.5)isresultingfromthesuccessiveoptimizationofJinthedirectionofthebasisfunctions2j.Thissingle{gridrelaxationtypicallysuersfromrapidlydeterioratingconver-gencerateswhenproceedingtomoreandmorerenedtriangulations.Thisundesirablebehaviorstimulatedthedevelopmentofvariousmultigridmeth-odsbasedonahierarchyoftriangulations[9,4,18,19,20,21,29,30,32].However,evenifappliedtosimplemodelproblems,allthosemethodssuf-fereitherfrommissingrobustnessorfromunsatisfactoryconvergencerates.Monotonemultigridmethodstobepresentedinthispaperaregloballyconver-gentandtheasymptoticconvergenceratesarealwaysboundedby1O(j3).Moreover,inournumericalexperimentsweobservedthesameeciencyasforclassicalmultigridmethodsinthecorrespondingunconstrainedcase.Thepaperisorganizedasfollows.InSection2,weintroduceextendedrelax-ationmethodsfortheiterativesolutionof(1.5)byextendingthesetof(high{frequent)searchdirectionsjbyadditional(intentionallylow{frequent)searchdirectionsMc.Moreprecisely,foragiven{thiterateuj,0,wechooseasuitablesetMcSj,tocomputethenextiterateu+1jbysuccessive,con-strainedoptimizationofJinthedirectionof2M=j[Mc.VariableextensionsMc,0,areusedtoreecttheapproximationofthediscretefreeboundaryincourseoftheiteration.Thisgeneralapproachincludesvariousextensionsofclassicalmultigridmeth-odsfromtheunconstrainedcasetothenonlinearvariationalproblem(1.5).Asanexamplewecanchoosethemultilevelnodalbasisas(constant)setofsearchdirectionsM=,0,torecovertheclassicalmultigridV{cyclewith(incomplete)Gauss{Seidelsmootherinthelinearcase.SeetheexcellentoverviewsofXu[33]andYserentant[35]forfurtherinformation.Ofcourse,extendedrelaxationscanbealsoregardedasnonlinearsuccessivesubspacecorrectionsornonlinearmultiplicativeSchwarzmethods.Usually,thelocaloptimizationproblemscorrespondingtothe(coarse{grid)functions2Mccannotbeevaluatedecientlysothatwehavetoapplysuitableinexactsolvers.Replacingtheconstraintsbymorerestrictivelocalobstacles,weobtainextendedunderrelaxations.Theresultingapproximatecorrectionsarestillpreservingnon{increasingenergy.Itisshownthatex-tendedunderrelaxationsaregloballyconvergent.2InSection3,weusethisgeneralframeworktoconstructtwofamiliesofmonotonemultigridmethodsbyselectingtwosuitablesetsM,0.AsfortheclassicalV{cycle,werstconsiderthemultil