MULTIGRID IN H(div) AND H(curl)

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

http://www.math.psu.edu/dna/

http://www.math.rutgers.edu/ falk/

http://www.i .uio.no/ ragnar/index

1991MathematicsSubjectClassi cation.65N55,65N30.

Keywordsandphrases.multigrid,preconditioner,mixedmethod, niteelement.

The rstauthorwassupportedbyNSFgrantDMS-9500672.ThesecondauthorwassupportedbyNSFgrantDMS-9704556.ThethirdauthorwassupportedbytheNorwegianResearchCouncil.

TypesetbyAMS-TEX

1

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

2DOUGLASN.ARNOLD,RICHARDS.FALK,ANDRAGNARWINTHER

ThespacesH(div)andH(curl)arisenaturallyinmanyproblemsof uidme-chanics,solidmechanics,andelectromagnetism.Frequentlytheseapplicationsre-quireafastsolutionmethodforoneorbothoftheequations(1.1).Insomeappli-cations,essentialboundaryconditionsareimposed.Thatis,thebilinearformΛdis (div),thesubspaceofH(div)consistingofvector eldswhosenor-restrictedtoH (curl),malcomponentvanisheson ,orthebilinearformΛcisrestrictedtoH

thesubspaceofH(curl)consistingofvector eldswhosetangentialcomponentvanisheson .Althoughwewillnottreatthissituationexplicitlyhere,there-sultsandanalysiswegiveadapttothecaseofessentialboundaryconditionswithonlyminorandstraightforwardmodi cations.

In§7of[2],wediscussindetailtheapplicationoffastsolversfortheequationΛdhu=ftobothmixedandleastsquaresformulationsofsecondorderellipticboundaryvalueproblems,includingoneinwhichκ 1.Severalotherapplicationsarediscussedbrie yaswell.ApplicationsoffastsolversforΛchp=gariseinvariouscontextsinelectromagnetism.Forexample,insimpletime-discretizationsofMaxwell’sequations,thisoccurswithκproportionaltothetimestep.See[11]foradetaileddiscussion.SuchsolversalsohaveapplicationstosomeformulationsoftheNavier–Stokesequationsasdiscussedin[7]and[8].

Multigridmethodshavebeenestablishedasamongthemoste cientsolversfordiscretizedellipticproblemsandaconsiderabletheoryhasbeendevelopedtojustifytheiruse.See,e.g.,[4],[9],[15].Unfortunately,someofthesimplestandmostfrequentlyusedsmoothersforellipticproblemsdonotyielde ectivemulti-griditerationswhenappliedtotheproblemsconsideredhere(see,forexample,[6]).Thisfailurecanbetracedtoakeydi erencebetweentheoperatorsΛdandΛly,theeigenspaceassoci-atedtotheleasteigenvalueoftheformeroperatorscontainsmanyeigenfunctionswhichcannotberepresentedwellonacoarsemesh(whileloweigenvalueeigenfunc-tionsforstandardellipticoperatorsarealwaysslowlyvarying).ThisisbecausetheoperatorΛdreducestotheidentitywhenappliedtosolenoidalvector elds,althoughitbehaveslikeasecondorderellipticoperatorwhenappliedtoirrota-tionalvector elds.ExactlythereverseholdsforΛc.ItisthereforenotsurprisingthattheHelmholtzdecompositionofanarbitraryvector eldintoirrotationalandsolenoidalcomponentsplaysanimportantroleintheunderstandingandanalysisoftheseproblems.Inparticular,wemakesubstantialuseofdiscreteversionsoftheHelmholtzdecompositioninouranalysisofmultigridmethods.

ThemainresultofthispaperisaproofthatthestandardV-cyclemultigridal-gorithmisane ectivesolverorpreconditionerforproblemsinvolvingtheoperatorscΛdhorΛhinthreedimensionsif(1)appropriate niteelementsubspacesofH(div)andH(curl)aretaken,and(2)appropriatesmoothersareused.Moreprecisely,weshowthatifwetakeVhtobetheRaviart–Thomas–Nedelecspaceofanyorderwithrespecttoatetrahedralmeshofsizeh,andifΘdhistheapproximateinverseofΛdhde nedbytheV-cyclealgorithmusinganyofseveraladditiveormultiplica-

dtiveSchwarzsmoothers,thenI ΘdhΛhisapositivede nitecontraction,whose

normisboundedawayfrom1uniformlyinthemeshsizeh,thenumberofmeshlevels,andtheparametersρ,κ∈(0,∞).Ofcourse,thisimpliesthatΘdhisagood

dpreconditioneraswell:theconditionnumberofΘdhΛhisboundedindependently

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

MULTIGRIDINH(div)ANDH(curl)3

ofh,thenumberofmeshlevels,andρandκ.Tode netheSchwarzsmoothers,wecanuseadecompositionofVhintolocalpatchesconsistingofallelementssur-roundingeitheranedgeoravertex,orathirddecompositioncanbeusedbasedontheHelmholtzdecomposition(see(4.2)).PreciselyanalogousresultsholdintheH(curl)caseifwetakeQhtobetheNedelecedgespacesofanyorder.Inthiscase,thesmootherscanbebasedeitheronadecompositionbasedonvertexpatchesoronthedecomposition(4.4)arisingfromtheHelmholtzdecomposition.

TheresultsofthispapergeneralizetothreedimensionsoneswhichweobtainedforH(div)intwodimensions[2].ThespacesH(div)andH(curl)areessen-tiallythesameintwodimensions,andsoouranalysisofmultigridin[2]adaptstoH(curl)withonlythemostmechanicalchanges.Inthreedimensions,whiletherearemanysimilaritiesbetweenH(div)andH(curl),therearealsosigni cantdi erences,especiallybetweentheir niteelementdiscretizations.Forthisreason,theanalysisforH(curl)requiresanumberofadditionalideas.Inourpresentation,wehavestressedthesimilaritybetweentheH(div)andH(curl)casesasmuchaspossible,limitingthedi erencestotheproofsofthetwo-levelestimatesformixedmethodsinthe nalsection,wheretheyaredescribedexplicitly.

The rstresultsformultigridinH(div)inthreedimensionsareduetoHiptmairin[10].Thesameauthorobtainedthe rstresultsformultigridinH(curl)in[11].Auni edandsimpli edtreatmentofthoseimportantworksisgivenbyHiptmairandToselliin[12].Ourresultsarecloselyrelatedtotheresultsin[10],[11],[12],andsomeofourargumentsderivefromthem.Themajordi erencebetweenourapproachandtheirsisthatweemployamultigridframeworkaspresented,forexample,in[4],andverifythehypothesesrequiredbythisapproachbydevelopingnecessaryestimatesformixed niteelementmethodsbasedondiscretizationsofH(div)andH(curl).Speci cally,wetakeTheorem3.1belowasthebasisforouranalysis,anddeveloptwo-levelestimatesformixedmethodsin§5inordertoapplythistheorem.Bycontrast,HiptmairandToselliuseanoverlappingSchwarzmethodframeworkaspresented,forexamplein[13].Animportantbene tofourapproach,whichisalsosomewhatlesscomplicated,isthatweobtainestimateswhichareindependentoftheparametersρandκoccuringinthebilinearform.Bycontrast,in[11],theconditionnumberofΘhΛhisonlyshowntobeO(1/κ3)whenρ=1andκissmall(andthecaseofκ/ρlargeisnotdiscussed).

Concerningnotation,weuseboldfacetypeforvector-valuedfunctions,operatorswhosevaluesarevector-valuedfunctions,andspacesofvector-valuedfunctions.ThenormintheSobolevspacesHs( )andHs( )arebothdenotedby · s,withtheindexs=0suppressed.ThenormassociatedtothebilinearformΛdisdenoted · Λd,orsimply · H(div)ifρ=κ=1,andanalogouslyforthenormassociatedtoΛc.

Weconcludewithanoutlineoftheremainderofthepaper.Inthenextsec-tion,weintroducethe nitedimensionalsubspacesofH(div)andH(curl)thatweshallconsiderinthispaper,namelytheRaviart–Thomas–NedelecspacesandNedelecedgespaces,respectively.Wethenstatesomeofthekeypropertiesofthesespaceswhichweshalluseinthesubsequentanalysis,themostimportantofwhicharediscreteHelmholtzdecompositionsofeachspace.In§3,westatesomestandardresultsformultigriditerations,inordertoisolatesu cientconditionsonadditiveandmultiplicativeSchwarzsmoothersfore cientalgorithms.In§4,we

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

4DOUGLASN.ARNOLD,RICHARDS.FALK,ANDRAGNARWINTHER

applytheseresulttoobtaintheconvergenceofthestandardmultigridV-cycleforctheoperatorsΛdhandΛhusingappropriatelyde nedadditiveandmultiplicativeSchwarzsmoothers.Theproofhingesoncertaintwo-levelerrorestimatesformixedmethodsbasedontheRaviart–Thomas–NedelecandNedelecedgespaces.Theseestimatesarestatedandprovedin§5.

2.Finiteelementdiscretization.Wesupposethat isaboundedandconvexpolyhedroninR3andThameshof consistingofclosedtetrahedra.Weassumethatthemeshisshaperegularandquasi-uniform.Moreprecisely,theconstantsthatappearintheestimatesbelowmaydependontheshaperegularityconstant(themaximumratioofthediameterofanelementtothediameterofthelargestballcontainedintheelement)andthequasi-uniformityconstant(themaximumratioofthelargesttothesmallestelementdiameter)ofthemesh,butareotherwisemesh-independent.WedenotebyVh,Eh,andFhthesetsofvertices,edges,andfacesofthemesh,respectively.Forν∈Vh∪Eh∪Fh∪Thwede ne νννTh={T∈Th|ν T}, h=interior(Th).

Thus νhisthesubdomainof formedbythepatchofelementsmeetingν,andνistherestrictionofthemeshThto νThh.

Fixanintegerk≥0.Wethenrecallthefollowingspaces:

Wh:

Qh:

Vh:

Sh:continuouspiecewisepolynomialsofdegreeatmostk+1,theNedelecedgediscretizationofH(curl)ofindexk,theRaviart–Thomas–NedelecdiscretizationofH(div)ofindexk,arbitrarypiecewisepolynomialsofdegreeatmostk.

Tode nethesespaces,wespecifythecorrespondingpolynomialspacesusedoneachelementandthecorrespondingsetsofdegreesoffreedom.RestrictedtoatetrahedronT,theelementsofWhandShare,ofcourse,arbitraryelementsofPk+1(T)andPk(T),respectively,wherePk(T)denotesthespaceofpolynomialsofdegreeatmostkrestrictedtoT.TherestrictionsoftheelementsofVharefunctionsoftheformp(x)+r(x)xwithp∈Pk(T)andr∈Pk(T).TheelementsofQharefunctionsoftheformp(x)+r(x)withp∈Pk(T)andr∈Pk+1(T)suchthatr·x≡0.Thedegreesoffreedomforu∈Vhareoftwosorts.First,themomentsofu·noforderatmostkoneachfacef(morepreciselythefunctionalsthatassociatetouitsinnerproductinL2(f)witheachelementofabasisforPk(f));andsecond,themomentsofuofdegreek 1oneachtetrahedron.Thedegreesoffreedomofq∈Qhare(1)themomentsofq·soforderatmostkoneachedge,(2)themomentsofq×noforderatmostk 1oneachface,and(3)themomentsofqoforderatmostk 2oneachtetrahedron.ForShweuseasdegreesoffreedomthetetrahedralmomentsoforderatmostk.ForWh,weuse

(1)thevaluesatthevertices,(2)theedgemomentsoforderatmostk 1,(3)thefacemomentsoforderatmostk 2,and(4)thetetrahedralmomentsoforderatmostk 3.

Wenowconsiderthedecompositionofthesespacesassumsofspacessupportedinsmallpatchesofelements.De ne

¯νQνh={r∈Qh:suppr h},ν∈Vh∪Eh∪Fh∪Th,

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

MULTIGRIDINH(div)ANDH(curl)

5

Fig.1.DegreesoffreedomforthespacesWh,Qh,Vh,andShinthe

lowestordercasek=0.

andanalogouslywithQhreplacedbyWh,Vh,orSh.Then

Wh=

Qh=

(2.1)Vh=

Sh= vWh,v∈Vhv∈Vh QvhvVhvSh===v∈Vh

v∈Vh e∈Eh Qeh,eVheShe∈Eh e∈Eh ==f∈Fh f∈FhfSh fVh,=T∈Th TSh.

(2.2)ForeachofthesedecompositionsthereisacorrespondingestimateonthesumofthesquaresoftheL2normsofthesummands.Forexample,wecandecomposean arbitraryelementq∈Qhasq=e∈Ehqewithqe∈Qehsothattheestimate

e∈Eh qe 2≤c q 2

holdswithcdependingonlyontheshaperegularityofthemesh.Weremarkalso thatethedecompositionsnotstatedinfactdon’thold.Forexample,Wh=e∈EhWh.

Theproofofthesedecompositionsandthecorrespondingestimatesallfollowthesamelines.Forexample,toprovetheedge-baseddecompositionofQhandtheestimate(2.2),wenotethatthedegreesoffreedomofthespaceQhdeterminea canonicaldecompositionofanarbitraryelementq∈Qhasq=qξwherethesumrunsoverallthedegreesoffreedomofQh,andqξistheelementofQhwithalldegreesoffreedomotherthanξsetequaltozero.Astandardscalingargumentthenimpliesthat qξ ≤c q L2(suppqξ).Nowtoeachdegreeoffreedomξ,wemayassignanedgeeofthemeshsuchthatsuppqξ eh(foranedge-baseddegreeoffreedom,chooseetobethatedgeandforaface-ortetrahedron-baseddegreeoffreedom,chooseetobeanyedgecontainedinthefaceortetrahedron).Combiningthecorrespondingqξgivesthedesireddecomposition.

Thesedegreesoffreedomspeci edforthespacesWh,Qh,Vh,andShdeter-QVSmineinterpolationoperatorsΠW,Πhh,Πh,andΠhmappingfunctionswhichare

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

6DOUGLASN.ARNOLD,RICHARDS.FALK,ANDRAGNARWINTHER

su cientlysmooththattherequiredfunctionvaluesandmomentsexistintothesubspaces.Speci cally,ΠWhisastandardinterpolationoperatorandisde nedon

22continuousfunctions,andΠShistheL-projectionoperator,de nedonallLfunc-

1tions.AsthedomainforΠVh,wecanchooseH.Moreover,astandardargument

basedontheBramble–Hilbertlemmaandscalinggivestheerrorestimate(2.3) v ΠVhv ≤ch v 1,v∈H1.

Becauseofthedependenceonedgemoments,thesituationismorecomplicated

1fortheoperatorΠQ

h.ItisboundedonthespaceofHvector eldswhosecurl

belongstoLp,forany xedp∈(2,∞].ThisfollowsfromLemma4.7of[1]andtheSobolevembeddingtheorem.Inparticular,itisde nedforH1vector eldswhosecurlbelongstoVh.Moreoverwehave

(2.4) q ΠQ

hq ≤ch q 1,q∈H1suchthatcurlq∈Vh.

Toshowthis,wefollow[12].Firstconsiderthecasewherethemeshconsistsof .LetQ andV denotethecorrespondingspacesandΠ QonlytheunitsimplexT ,ingtheequivalenceofnormsinV

Qq ≤c( q 1+ curlq L∞)≤c q 1 Π

.ABramble–Hilbertargumentthengives )suchthatcurlq ∈H1(T ∈Vforallq Qq )suchthatcurlq wherenowonlytheH1 Π ≤c|q |1forq ∈H1(T ∈V q

seminormappearsontherighthandside.Ifwescalethisestimatetoageneral withFa ne,usingtheappropriatecontravarianttransformsimplexT=F 1T

→(DF) (q F),andaddupoverallthesimplicesinthemesh,weget(2.4).q

Theinterpolationoperatorsalsosatisfythecommutativityproperties

VcurlΠQ

h=Πhcurl,SdivΠVh=Πhdiv,QgradΠWh=Πhgrad

whenappliedtosu cientlysmoothvector elds.Thesewell-knownrelationsfollowfromthede nitionsoftheinterpolationoperatorsandthetheoremsofGreenandStokes.dInadditiontotheseinterpolationoperators,wealsode nePhtobetheorthog-conalprojectionontoVhwithrespecttotheinnerproductinH(div)andPhtobetheorthogonalprojectionontoQhwithrespecttotheinnerproductinH(curl).AkeypropertyrelatingthespacesWh,Qh,Vh,andSh,isthatthefollowingsequenceisexact:

0 →Wh/R →Qh →Vh →Sh →0,

i.e.,thattherangeofeachoftheoperatorsinthesequencecoincideswiththenullspaceofthefollowingoperator.Itfollowsthatifwede negradh:Sh→VhastheL2adjointofthemap div:Vh→Sh,andcurlh:Vh→QhastheL2adjointofcurl:Qh→Vh,thenwehavethetwoorthogonaldecompositions:

Vh=curlQh⊕gradhSh,Qh=curlhVh⊕gradWh.gradcurldiv

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

MULTIGRIDINH(div)ANDH(curl)7

ThesediscreteHelmholtzdecompositionsareorthogonalinL2andinH(div)forthe rstandH(curl)forthesecond.

Remark.Ifweweretoconsiderthecasewhereessentialboundaryconditionsare h=Wh∩H 1,Q h=Qh∩H (curl),imposed,theappropriatespaceswouldbeW h=Vh∩H (div),andthecorrespondingexactsequencewouldbeandV

gradcurl div h h 0 →W →Q →Vh →Sh/R →0.

3.Abstractmultigridconvergences.Inthissection,werecallsomestandardresultsformultigriditerations,whichwillbethestartingpointforouranalysisofmultigridmethodsforthelinearsystemsofequationsdiscussedintheprevioussection.Suppose

X1 X2 ··· XJ=X

isasequenceof nitedimensionalsubspacesofaHilbertspace,Y,andΛ:X×X→Risasymmetricpositivede nitebilinearform.Foreachj,wede neΛj:Xj→Xjby(Λjx,y)=(Λx,y)forallx,y∈Xj.Ourgoalistheconstructionofane cientmultigriditerationtosolveorpreconditionequationsoftheformΛJx=f.LetMj:X→XjdenotetheY-orthogonalprojection,Pj:X→XjtheΛ-orthogonalprojection,andRj:Xj→Xjalinearoperator(thesmoother).Foreachj,wede neanY-symmetricoperatorΘj:Xj→XjbythestandardmultigridV-cycle1recursionwithm≥1smoothings.Thatis,wesetΘ1=Λ andforj>1and1f∈Xj,wede neΘjf=y2m+1where

y0=0∈Xj,

yi=yi 1+Rj(f Λjyi 1),

ym+1=ym+Θj 1Mj 1(f Λjym),

yi=yi 1+Rj(f Λjyi 1),i=m+2,m+3,...,2m+1.

ThenΘJistheV-cyclepreconditionerforΛJ.Thefollowingtheoremgivescondi-tionsonthesmoothersRjwhichensureconvergenceofthemultigridV-cycle(cf.,

[3],[4,Theorem3.6],or[2,Theorem5.1]).

Theorem3.1.Supposethatforeachj=1,2,...,J,thesmootherRjisY-symmetricandpositivesemide niteandsatis estheconditions

Λ([I RjΛj]x,x)≥0,

and 1(Rjx,x)≤αΛ(x,x),i=1,2,...,m,x∈Xj,x∈(I Pj 1)Xj,

whereαissomeconstant.Then

0≤Λ([I ΘJΛJ]x,x)≤δΛ(x,x),

whereδ=α/(α+2m).

Hence,themultigriderroroperatorI ΘJΛJisapositivede nitecontractionwithnormatmostδ<1independentofJanddecreasinginm,andtheprecondi-tionedoperatorΘJΛJhaseigenvaluesbetween1 δand1.x∈X,

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

8DOUGLASN.ARNOLD,RICHARDS.FALK,ANDRAGNARWINTHER

ToobtainsmootherswhichsatisfytheconditionsofTheorem3.1,weconsideradditiveandmultiplicativeSchwarzoperators.Todescribethese,weassumethatkforeachj,therearespacesXj Xjsuchthateachx∈Xjcanbewrittenin Kktheformk=1xk,withxk∈Xj.LettingPjkdenotetheΛ-projectionoperator

kontothespaceXj,wecanthende netheunscaledadditiveSchwarzsmootherby ak 1aRj=KandthenthesmootherRj=ηRj,whereηisascalingfactor.k=1PjΛmWealsodenotebyRjtheusualmultiplicativeSchwarzsmootherassociatedwith

kmthespacesXj,i.e.,forf∈Xj,Rjf:=x2K,where

x0=0,

1xk=xk 1 Pjk(xk 1 Λ

jf),k=1,...,K,

k=K+1,...,2K.1xk=xk 1 Pj2K+1 k(xk 1 Λ

jf),

ThefollowingtheoremgivesconditionsonthedecompositionsoftheXjunderwhichtheSchwarzsmoothersleadtoaconvergentmultigriditeration.

Theorem3.2.Supposethat

K 1/2 K 1/2K K Λ(xk,yl) ≤β,Λ(xk,xk)Λ(yl,yl)

k=1l=1(3.1)k=1l=1

klxk∈Xj,yl∈Xj,

and

(3.2)infK kxk∈Xjk=1 x=xkΛ(xk,xk)≤γΛ(x,x),x∈(I Pj 1)Xj,

forsomeconstantsβ>0,γ>0.Then,

a(i)Ifη≤1/β,thescaledadditivesmoothersRj=ηRjsatisfythehypotheses

ofTheorem3.1withα=γ/η.

m(ii)ThemultiplicativesmoothersRj=RjsatisfythehypothesesofTheorem3.1

withα=β2γ.

Resultsofthistypecanbefoundinmanyplaces,forexamplein[4,Chapters3and5],[5],[13,Chapter5],and[15].Thereforewemerelysketchaproofhere.The rsthypothesisofTheorem3.1fortheadditivesmootherfollowsfrom(3.1)withxk=yk=PjkxandSchwarz’sinequality.Itiswellknownthattheleft

a 1handsideof(3.2)ispreciselyequalto(Rjx,x)(cf.equation(2.1)of[2]).The

secondhypothesisofTheorem3.1followsdirectlyfortheadditivesmoother.Forthemultiplicativesmoother,the rsthypothesisfollowsfromtheidentityΛ([I RjΛj]x,x)=Λ(Ex,Ex)whereE=(I PjK)(I PjK 1)···(I Pj1).Thesecond

amhypothesisisaconsequenceoftheinequality(Rjx,x)≤β2(Rjx,x),whichisjust

Corollary4.3of[2],usingtheargumentgivenattheendof§5ofthatpaper.

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

MULTIGRIDINH(div)ANDH(curl)9

4.MultigridconvergenceinH(div)andH(curl).Weconsideranestedsequenceofquasi-uniformtetrahedralmeshesTj,1≤j≤J.Thesegiveriseto

cspacesWj,Qj,Vj,andSjandoperatorsΛdj:Vj→VjandΛJ:Qj→Qj.In

thissection,weuseTheorem3.2toobtainaconvergenceresultforthemultigridcV-cycleappliedtotheequationΛdJu=forΛJp=ginthespaceX=VJorQJ.FortheenclosingHilbertspaceYwetakeL2.Wenotethatproperties(3.1)and(3.2)onlyinvolvesubspacesattwolevels.LethdenotethemeshsizeofsomemeshTjandletHdenotethemeshsizeofthenextcoarsermeshTj 1.Tosimplifynotation,weshallwriteThandTHforTjandTj 1,andsimilarlyinothercaseswherethesubscriptsjandj 1arise.

Tode netheSchwarzsmoothers,wemustdecomposethespaceVhorQh.ForthespaceVh,threepossibledecompositions,basedonfacepatches,edgepatches,andvertexpatches,aregivenin(2.1).FromthepointofviewofimplementationofthecorrespondingSchwarzsmoother,theface-baseddecomposition,whichhasonlytwoelementsperpatch,ismoste cient,theedge-basedlesse cient,andthevertex-basedSchwarzsmoothertheleaste cient.However,asourtheorywillsuggestandnumericalcomputationsinanalogoussituationsreinforce[6],theface-basedSchwarzsmootherdoesnotleadtoane cientmultigridalgorithm.Belowweshallprovethatbothdecompositions ev(4.1)Vh=VhandVh=Vh,

e∈Ehv∈Vh

Theimplementationofthecorrespondingsmoother,whichmaybemoree cientthanthesmootherbasedonedgepatches,isdiscussedin[hiptmair-hdiv].Ouranalysisbelowappliestothissmootheraswell.

ForthespaceQhwemayuseeitherthedecomposition (4.3)Qh=Qvh,

v∈VhyieldSchwarzsmoothersthatsatisfytheconditionsofTheorem3.2withconstantsindependentofhandκ.In[10]Hiptmairgeneralizestothreedimensionadecom-positionusedintwodimensionsbyVassilevskiandWang[14],namely, f (4.2)Vh=Vh+curlQeh.f∈Fhe∈Eh

oroneduetoHiptmair[11],

(4.4)Qh=

e∈Eh

Itiseasytocheckthatsincenopointbelongstomorethansixofthe ehor

ffourofthe vhor h,allthesedecompositionssatisfythecondition(3.1)withβ

independentofh,ρ,andκ(βwillneverexceed10).Itthusonlyremainstoverifycondition(3.2),whichwestatefortheparticularcaseofthe rstsmootherin(4.1)andthesmootherin(4.3)inthefollowingtwotheorems.Theveri cationfortheothersmootherswillberemarkedonbelow.Forthesetheorems(only)werequiretheboundedre nementhypothesisH≤ch.(Inpractice,valuesofcaround2arecommon.) Qeh+v∈Vh vgradWh.

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

10DOUGLASN.ARNOLD,RICHARDS.FALK,ANDRAGNARWINTHER

dTheorem4.1.AssumethatH≤chandthatv∈(I P)Vhbegiven.ThereH eexistsadecompositionv=e∈Ehve,whereve∈Vh,andaconstantγdepending

oncbutindependentofh,ρ,andκsuchthat

e∈Eh

cTheorem4.2.AssumethatH≤chandthatq∈(I P)Qhbegiven.ThereH vvvexistsadecompositionq=v∈Vhq,whereq∈Qh,andaconstantγdepending

oncbutindependentofh,ρ,andκsuchthat Λd(ve,ve)≤γΛd(v,v).

v∈Vh Λc(qv,qv)≤γΛc(q,q).

Toprovetheseresults,wewillmakeuseofthediscreteHelmholtzdecompositionsdescribedin§2.Forthesedecompositions,thefollowingtwopropositions,forH(div)andH(curl),respectively,willbethekeyingredientsoftheanalysis.Theproofsofthesepropositions,unliketheproofofTheorems4.1and4.2,donotrequirethath≤cH.Also,sinceTheorems4.1and4.2areuna ectedbyscalingofthebilinearform,intheremainderofthepaperweassume,withoutlossofgenerality,thatρ=1.

dProposition4.3.Supposethatu∈Vhandthatu PHu∈Vhhasthediscrete

Helmholtzdecomposition

du PHu=gradhsh+curlqh,

forsomesh∈Shandqh∈curlhVh.Then

dκ gradhsh ≤cH u PHu Λd,d qh ≤cH u PHu .

cProposition4.4.Supposethatp∈Qhandthatp PHp∈Qhhasthediscrete

Helmholtzdecomposition

cp PHp=gradwh+curlhvh,

forsomewh∈Wh/Randvh∈Vhwithdivvh=0.Then

cp , wh ≤cH p PHcp Λc.κ curlhvh ≤cH p PH

Theproofoftheseresultsrequiresaseriesofintermediateresultsandwillbegiveninthenextsection.WenowshowhowthesepropositionsmaybeusedtoestablishTheorems4.1and4.2.

dProofofTheorem4.1.Sincev∈(I PH)Vh,itfollowsfromProposition4.3andthe

boundedre nementhypothesisthatvadmitsadiscreteHelmholtzdecomposition

+curlq,v=v

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

MULTIGRIDINH(div)ANDH(curl)11

∈gradhShandq∈Qhsatisfytheboundswherev

(4.5) ≤ v , v ≤ch v Λd,κ v q ≤ch v .

e∈Eh =Followingthediscussionof§2,wecanwritev

(4.6)

Thenv=

(4.7) ≤c v , ve22vandq= ee∈Ehe∈Eh qe 2≤c q 2. e∈Ehqewithe∈Eh e+curlqe.Moreover,usinganinverseinequality,vewhereve:=v= e2 e 2( v+ curlq )dΛ

e∈Eh ve 2Λde∈Eh

≤c

e∈Eh e 2+h 2 qe 2],[(1+κ2h 2) v

andthetheoremfollowsfrom(4.5)–(4.7).

cProofofTheorem4.2.Sinceq∈(I PH)Qh,itfollowsfromProposition4.4and

theboundedre nementhypothesisthatqisgivenby

+gradw,q=q

∈curlhVhandw∈Whsatisfytheestimateswhereq

≤ q , q

v ≤ch q Λc,κ q w ≤ch q .

=v∈Vhq andw=v∈Vhwv,andsettingqv=q v+gradwv,weWritingqcompletetheproofasfortheprecedingtheorem.

Remark.TheproofofTheorem4.1appliesalmostwithoutmodi cationifthede- ecompositionVh=e∈EhVhisreplacedbyeithertheseconddecompositionin(4.1)orthedecompositionin(4.2).Similarly,theproofofTheorem4.2appliestothedecompositionin(4.4)aswell.Itisalsoclearwhywecannotusetheface-baseddecompositionofVhinTheorem4.1,sincetheproofwouldrequireacorrespondingface-baseddecompositionofQh,whichdoesnotexist.

5.Two-levelestimatesformixed niteelements.InthissectionweprovePropositions4.3and4.4.Ourproofsarebasedonestimatesfortheapproximationofdiscretelyirrotationalvector eldsinVhanddiscretelysolenoidalvector eldsinQhbydiscretelyirrotationalandsolenoidal eldsinVHandQH,respectively.Thesetwo-levelapproximationresults,inturn,relyonestimatesformixed niteelementmethodsbasedonH(div)andH(curl).Webeginthissectionwithadiscussionofsuchmethods.

FortheH(div)case,letf∈L2andde ne(s,v)astheuniquecriticalpoint(asaddle)of1Ld(s,v):=

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

12DOUGLASN.ARNOLD,RICHARDS.FALK,ANDRAGNARWINTHER

overL2×H(div).ThisisamixedvariationalformulationoftheDirichletboundaryvalueproblem

(5.1)v=grads,divv=fin ,s=0on .

Themixed niteelementapproximation(sh,vh)to(s,v)istheuniquecriticalpointofLdoverSh×Vh.Itisdeterminedbytheequationsvh=gradhsh,divvh=ΠShf,andvhaloneischaracterizedastheuniquefunctioningradhShsatisfyingthelatterequation.Abasicestimateformixedmethodsis

(5.2) v vh ≤ v ΠVhv ,v∈H1,

SwhichisaconsequenceofthecommutativitypropertydivΠVh=Πhdiv.Fromthe

propertiesoftheoperatorΠVhonealsoeasilyderivestheinf–supcondition:

s∈Shv∈Vhinfsup(divv,s)

2 q 2 (curlq,z)+(f,z).

Thiscorrespondstotheboundaryvalueproblem

(5.4)q=curlz,curlq=f,divz=0in ,z×n=0on .

Forthisproblemwehaveq,z∈H1and

(5.5) q 1≤c f , z 1≤c q .

Indeed,sincethenormalcomponentofq=curlzisthetangentialdivergenceofz×n,whichvanisheson ,itfollowsthatq·n=0on .TheestimatesonqandzarethengiveninTheorems2.1and2.2of[7],respectively.

Themixed niteelementapproximation(zh,qh)istheuniquecriticalpointofLcoverZh×Qh.Itisdeterminedbytheequationsqh=curlhzh,curlqh=ΠZhf,

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

MULTIGRIDINH(div)ANDH(curl)13

22whereΠZh:L→ZhistheLprojection,andqhaloneischaracterizedasthe

uniquefunctionincurlhVhsatisfyingthelatterequation.Atthispoint,anessentialdi erencebetweenthemixedapproximationof(5.4)and(5.1)arises.Itisnottrue

ZZthatcurlΠQ

hq=Πhcurlqforallsmoothfunctionsq(sinceΠhdoesnotcoincide

withΠVh,evenwhenappliedtoirrotational elds).Asaresult,itisnotingeneraltruethat q qh ≤ q ΠQ

hq .However,thisestimateistrueinthespecialcase

thatf∈Zh,i.e.,

(5.6) q qh ≤ q ΠQ

hq ,q∈H1suchthatcurlq∈Vh.

Indeed,inthiscase

VZcurlΠQ

hq=Πhcurlq=curlq=Πhcurlq=curlqh,

soΠQ

hq qhiscurl-free.Itthenfollowsdirectlyfromthede ningequationsofthemixedmethodthat(q qh,ΠQ

hq qh)=0,whichgives(5.6).

Noticethatthehypothesiscurlq∈Vhisalsowhatisneededfortheapproxima-tionestimate(2.4).Combining(5.6),(2.4),andthecontinuousinf–supcondition,wegetthediscreteinf–supcondition,

infsup(curlq,z)

z∈Zhq∈Qh

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

14DOUGLASN.ARNOLD,RICHARDS.FALK,ANDRAGNARWINTHERProofofLemma5.1.De ne(v,s)from(5.1)withf=divvh.ThenvhandvHarethemixedapproximationstovinVhandVH,respectively.Applying(5.2),(2.3),and2-regularityfortheDirichletproblem,weobtain

v vH ≤ v ΠVHv ≤cH v 1≤cH divvh ,

and,similarly, v vh ≤ch divvh .The rstestimatethusfollowsfromthetriangleinequality.

Nextweprovethatforanyrh∈Sh,

(5.8) rh ΠSHrh ≤cH gradhrh .

Inparticular,wemaytakerh=divvhinthisestimate,toget

divvh divvH ≤cH gradhdivvh .

Toprove(5.8),wede neafunctionuwhichsatis es

divu=rh ΠSHrh,

Then

2SSS rh ΠSHrh =(divu,rh ΠHrh)=(divu,Πhrh ΠHrh)

VVS=([ΠSh ΠH]divu,rh)=(div[Πh ΠH]u,rh)

VVV=([ΠVh ΠH]u,gradhrh)≤( Πhu u + u ΠHu ) gradhrh u 1≤ rh ΠSHrh .

≤cH u 1 gradhrh ≤cH rh ΠSHrh gradhrh ,

whichimplies(5.8).

ProofofProposition4.3.Thepropositiondirectlygeneralizesthecorrespondingtwo-dimensionalresult,Lemma3.1of[2].Theproofoftheboundongradhshisentirelyanalogoustotheargumentin[2],buttheboundforqhrequirestheuseofamorecomplicateddualityargument.First,observethat

(5.9)d(curlqh,curlr)=Λd(u PHu,curlr)=0,r∈QH.

De ne(q,z)asin(5.4)withfreplacedbycurlqh.Thenqh∈Qhisthemixedapproximationtoq,andhence,by(5.6),(2.4),and(5.5),

(5.10) q qh ≤ q ΠQ

hq ≤ch q 1≤ch curlqh .

VSincedivz=0,divΠVHz=0,andsoΠHz∈curlQH.Wemaythereforeapply

(5.9),(2.3),and(5.5)toobtain

q 2=(q,curlz)=(curlq,z)=(curlqh,z)=(curlqh,z ΠVHz)

≤cH z 1 curlqh ≤cH q curlqh .

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

MULTIGRIDINH(div)ANDH(curl)15

Hence, q ≤cH curlqh .Combiningthiswith(5.10),weobtain

d qh ≤cH curlqh ≤cH u PHu .

Thiscompletestheproofofthesecondestimateoftheproposition.

Sincethe rstestimateisvacuousifκ=0,weassumeκ>0.SinceΛdhmaps

1gradhShontoitself,wehavevh=(Λdgradhsh∈gradhSh.De ningvH∈h)

VHasinLemma5.1,wehave

2222 vh vH 2≤cH( divv +κ graddivv )dhhhΛh

≤cH2κ 2( vh 2+2κ2 divvh 2+κ4 gradhdivvh 2)

22 2=cH2κ 2 Λd gradhsh 2.hvh =cHκ

Hence,

dd gradhsh 2=Λd(gradhsh,vh)=Λd(u PHu,vh)=Λd(u PHu,vh vH)

dd≤ u PHu Λd vh vH Λd≤cHκ 1 u PHu Λd gradhsh .

WenowproveLemma5.2,fromwhichProposition4.4willfolloweasily.TheproofissubstantiallymoreinvolvedthanthatofLemma5.1,becausetheerrorestimate q qH ≤ q ΠQHq isnotvalid(re ectingthelackofthecommutativity

ZproperycurlΠQ

h=Πhcurl).

ProofofLemma5.2.Thelemmadoesnotinvolvetheparameterκ.Soasnottointroduceadditionalnotation,thenotationΛdisusedinthisprooftodenotedtheunweightedinnerproductinH(div)(κ=1),andPHisusedtodenotethecorrespondingorthogonalprojection.Z2SincecurlqH=ΠZHcurlqhwhereΠHistheLprojectionontoZH,weobvi-ouslyhave

(5.11) curlqH ≤c curlqh .

De ne(q,z)bytheboundaryvalueproblem(5.4)withfreplacedbycurlqh.SinceqhisthemixedapproximationofqinQhandcurlq∈Vh,weareabletouse(5.6)toestimateq qh.WhileqHisthemixedapproximationofqinQH,itisnottruethatcurlq∈VH,sowecannotestimateq qHinthesameway.Thereforewe

¯,z¯)by(5.4)withfreplacedbycurlqH.(Theanalogouscomplicationdidde ne(q

¯andψ=z z¯,weobtainnotariseintheproofofLemma5.1.)Settingφ=q q

curlψ=φ, ψ 1≤c φ ,

¯)=curl(qh qH),curlφ=curl(q q

φ 1≤c curlqh +c curlqH ≤c curlqh ,

¯ qH ≤cH curlqh , φ (qh qH) ≤ q qh + q

whereinthelastestimatewehaveused(5.6),(2.4),and(5.5)twice,andthen(5.11).

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

16DOUGLASN.ARNOLD,RICHARDS.FALK,ANDRAGNARWINTHER

Weestimate φ usingthesamedualityargumentweusedtoestimate q intheproofofProposition4.3.SinceΠVHψ∈ZH(whichfollowsfromthecommutativitySrelationdivΠVH=ΠHdiv),andcurl(qh qH)⊥ZH,we nd

φ 2=(φ,curlψ)=(curlφ,ψ)=(curl[qh qH],ψ)

=(curl[qh qH],ψ ΠVHψ)≤cH curl(qh qH) ψ 1

≤cH curl(qh qH) φ .

Thisimpliesthat φ ≤cH curl(qh qH) ≤CH curlqh ,andsoweobtainthe rstestimateofthelemma.

Itremainstoprovethesecondestimate.Forthisestimate,too,wecannotsimplyusetheanalogueoftheargumentthatestablishedthesecondestimateofProposition4.3.Thistimetheproblemcanbetracedtothefailureofthecom-QmutativitypropertyΠZcurl=curlΠHH,eventhoughtheanalogousproperty

VΠSHdiv=divΠHisvalid.Insteadweshallderivetheestimatebyestablishingthe

followingthreefacts:

d(5.12)curlqh curlqH=(I PH)curlqh+gradHsH,forsomesH∈SH,

(5.13)

(5.14)d)curlqh , gradHsH ≤c (I PHd u PHu ≤cH curlhu ,u∈curlQh.

Thedesiredestimatefollowsbytakingu=curlqhin(5.14)andusing(5.12)and(5.13).

The rststatementfollowsfromtheequations

(curlqH,curlrH)=(curlqh,curlrH)=Λd(curlqh,curlrH)

dd=Λd(PHcurlqh,curlrH)=(PHcurlqh,curlrH),rH∈QH.

dcurlqhandToprove(5.13),wenotefromtheHelmholtzdecompositionofPHd,thatforanyvH∈VH,thede nitionofPH

d(divgradHsH,divvH)=(divPHcurlqh,divvH)

(5.15)dd=Λd(PHcurlqh,vH) (PHcurlqh,vH)

dd=(curlqh,vH) (PHcurlqh,vH)=([I PH]curlqh,vH).

Now

gradHsH 2= (divgradHsH,sH)≤ divgradHsH sH

≤c divgradHsH gradHsH ,

bythediscretePoincar´einequality(5.3).Thus gradHsH ≤c divgradHsH ,andtakingvH=gradHsHin(5.15),weget

d gradHsH 2≤c divgradHsH 2=c([I PH]curlqh,gradHsH)

d≤c (I PH)curlqh gradHsH ,

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

MULTIGRIDINH(div)ANDH(curl)17

asdesired.

Itremainstoprove(5.14).Foru∈curlQh,weusethediscreteHelmholtzdecompositiontowrite

d(I PH)u=curlp+gradhs,s∈Sh,p∈curlhVh,

andthentowrite

d(I PH)curlp=curlm+gradhr,r∈Sh,m∈curlhVh.

Fromthe rstestimateofProposition4.3andthefactthatuisdivergence-free,wehavethat

d gradhs ≤cH u PHu H(div)≤cH u H(div)=cH u .

Againusingthevanishingofdivu,weobtain

dd]curlp,u) curlp 2=Λd(curlp,[I PH]u)=Λd([I PH

d=([I PH]curlp,u)=(curlm,u)=(m,curlhu).

FromthesecondestimateofProposition4.3wethenget

d m ≤cH (I PH)curlp H(div)≤cH curlp H(div)=cH curlp .

Hence, curlp ≤cH curlhu .Finally,

du ≤ curlp + gradhs ≤cH( u + curlhu ), u PH

which,togetherwith(5.7),establishes(5.14).

References

1.C.Amrouche,C.Bernardi,M.Dauge,andV.Girault,Vectorpotentialsinthree-dimensionalnonsmoothdomains,Math.MethodsAppl.Sci.(1998)(toappear).

2.D.N.Arnold,R.S.Falk,andR.Winther,PreconditioninginH(div)andapplications,p.66(1997),957–984.

3.D.BraessandW.Hackbusch,AnewconvergenceproofforthemultigridmethodincludingtheV-cycle,SIAMJ.Numer.Anal.20(1983),967–975.

4.J.H.Bramble,Multigridmethods,PitmanResearchNotesinMathematicsSeries294(1993).

5.M.DryjaandO.B.Widlund,SchwarzmethodsofNeumann–Neumanntypeforthree-dimen-sionalelliptic niteelementproblems,Comm.PureAppl.Math48(1995),121–155.

6.Z.Cai,C.I.Goldstein,andJ.E.Pasciak,Multileveliterationformixed niteelementsystemswithpenalty,put.14(1993),1072–1088.

7.V.Girault,Incompressible niteelementmethodsforNavier–Stokesequationswithnonstan-dardboundaryconditionsinR3,p.51(1988),55–74.

8.V.GiraultandP-A.Raviart,FiniteElementMethodsforNavier–StokesEquations,Springer-Verlag,Berlin,1986.

9.W.Hackbush,MultigridMethodsandApplications,Springer-Verlag,Berlin,1986.

10.R.Hiptmair,MultigridmethodforH(div)inthreedimensions,ETNA6(1997),133–152.11.

Abstract. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite el

18DOUGLASN.ARNOLD,RICHARDS.FALK,ANDRAGNARWINTHER

12.R.HiptmairandA.Toselli,OverlappingSchwarzmethodsforvectorvaluedellipticprob-

lemsinthreedimensions,ParallelsolutionofPDEs,IMAVolumesinMathematicsanditsApplications,Springer,Berlin,1998(toappear).

13.B.Smith,P.Bj¨orstad,andW.Gropp,DomainDecomposition,CambridgeUniversityPress,

Cambridge,1996.

14.P.S.VassilevskiandJ.Wang,Multileveliterativemethodsformixed niteelementdiscretiza-

tionsofellipticproblems,Numer.Math.63(1992),503–520.

15.J.Xu,Iterativemethodsbyspacedecompositionandsubspacecorrection,SIAMReview34

(1992),581–613.

DepartmentofMathematics,PennState,UniversityPark,PA16802

E-mailaddress:dna@math.psu.edu

DepartmentofMathematics,RutgersUniversity,NewBrunswick,NJ08903E-mailaddress:falk@math.rutgers.edu

DepartmentofInformatics,UniversityofOslo,Oslo,Norway

E-mailaddress:ragnar@i .uio.no

本文来源：https://www.bwwdw.com/article/s0ym.html