Postprocessing the Galerkin method: the finite-element case

POSTPROCESSING THE GALERKIN METHOD: THE FINITE-ELEMENT CASE∗ BOSCO GARC´ IA-ARCHILLA†AND EDRISS S. TITI‡ SIAM J. NUMER. ANAL.c °2000 Socie y o Indus ial and Applied Ma hema ics Vol. 37, No. 2, pp. 470–499 Abs ac . A pos p ocessing echnique, de eloped ea lie o spec al me hods, is ex ended he e o Gale kin ini e-elemen me hods o dissipa i e e olu ion pa ial di e en ial equa ions. The pos p ocessing amoun s o sol ing a linea ellip ic p oblem on a ine g id (o highe -o de space) once he ime in eg a ion on he coa se mesh is comple ed. This echnique inc eases he con e gence a e o he ini e-elemen me hod o which i is applied, and his is done a almos no addi ional compu a ional cos . The nume ical expe imen s p esen ed he e show ha he esul ing pos p ocessed me hod is compu a ionally mo e e icien han he me hod o which i is applied (say, quad a ic ini e elemen s) as well as s anda d me hods o simila o de o con e gence as he pos p ocessed one (say, cubic ini e elemen s). The e o analysis o he new me hod is pe o med in L2and in L∞no ms. Key wo ds. dissipa i e equa ions, pos p ocessing ini e-elemen me hods, mul ile el me hods, nonlinea Gale kin me hods AMS subjec classi ica ions. 65P25, 65M70, 65M15, 65M20 PII. S0036142998335893 1. In oduc ion. Fini e-elemen me hods do no seem o ha e bene i ed as much as spec al me hods om some o he ecen ad ances in he dynamical sys- ems app oach o pa ial di e en ial equa ions (PDEs) like hose in [15], [14], [13], and [41]. Since hese ad ances a e mos ly based on spec al decomposi ions, hey a e eadily adap ed o spec al me hods, bu do no seem o ha e a clea -cu ansla ion o ini e elemen s. In [21] and based on he esul s o [15] and [13], an inexpensi e no el echnique o inc ease he accu acy and compu a ional e iciency o Fou ie spec- al me hods was de eloped. In his pape , we p esen a gene al echnique o imp o e he con e gence a e o Gale kin me hods which applies o ini e-elemen me hods (and in he pa icula case o Fou ie –Gale kin me hods i coincides wi h ha in [21]; see also [37]). We do his wi h no di ec add ess o [13]. Le Ω ⊂Rdbe a domain wi h a smoo h bounda y. We conside dissipa i e PDEs (see, o ins ance, [8], [24], [25], [41]) which can be w i en as e olu ion sys ems o he o m du d +νAu +F(u)=0,(1) in he Hilbe space H(in his wo k H=L2(Ω)), wi h solu ions de e mined uniquely by he ini ial condi ion u(·,0) = u0.(2) ∗Recei ed by he edi o s Ma ch 19, 1998; accep ed o publica ion (in e ised o m) Ma ch 8, 1999; published elec onically Janua y 5, 2000. This wo k was pa ially inanced by DGICYT p ojec PB95-216 and he Na ional Science Founda ion and was comple ed while he second au ho was he O son Ande son Visi ing Schola a he Ins i u e o Geophysics and Plane a y Physics (IGPP) a he Los Alamos Na ional Labo a o y. h p://www.siam.o g/jou nals/sinum/37-2/33589.h ml †Depa amen o de Ma em´a icas, Uni e sidad Au ´onoma de Mad id, 28049 Mad id, Spain (b[email p o ec ed]). Cu en add ess: Dep o. Ma ema ica Aplicada II, Uni e sidad de Se illa, Escuela Supe io de Ingenie o , Camino de lo Descub imien o S/N, 41092 Se illa (Spain) ‡Depa men o Ma hema ics and Depa men o Mechanical and Ae ospace Enginee ing, Uni- e si y o Cali o nia, I ine, CA 92697-3875 ([email p o ec ed]). 470 Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php POSTPROCESSING FINITE-ELEMENT METHODS 471 He e, ν>0 is a scala , A:D(A)⊂H→His a densely de ined, unbounded, sel -adjoin , and posi i e ope a o wi h compac in e se. Fo simplici y, we ea he e only he case A=−∆, whe e ∆ s ands o he Laplacian ope a o subjec o homogeneous Di ichle bounda y condi ions, bu ou esul s also apply o o he ellip ic ope a o s in di e gence o m wi h su icien ly smoo h coe icien s and (wi h adequa e modi ica ions) o o he bounda y condi ions. The (nonlinea ) ope a o F ha we conside is one o he ollowing wo ypes: 1. eac ion-di usion equa ions, F(u)=g(u),(3) o some smoo h unc ion g:R→R; 2. eac ion-di usion equa ions plus nonlinea con ec ion, F(u)=g(u)+b(u)·∇u,(4) o some smoo h mapping b:R→Rd, and gis as abo e. Fo simplici y, we concen a e he e on he wo ypes o nonlinea i y abo e, bu bo h gand bcan be made dependen on xand as well. Also, al hough we concen a e on scala equa ions, he esul s he e can be ex ended o sys ems. We ea he e he case whe e Ω ⊂Rdwi h d>1; he case d= 1 is pa icula and much simple o analyze. Le Th=(τ h i,φ h i) i∈I h,h>0, be a amily o pa i ions o sui able domains Ωh, whe e he pa ame e his he maximum diame e o he elemen s τh iin Th, and φh i a e he mappings o he e e ence simplex τ0on o τh i.Fo ≥2 we conside he ini e-elemen spaces Sh, =nχh∈C(Ωh)|χh|τh i◦φh i∈P −1(τ0),χ h (x)=0 ∀x∈∂Ω h o, whe e P −1(τ0) deno es he space o polynomials o deg ee a mos −1onτ 0 . Le us deno e by a(·,·) he posi i e de ini e, bilinea o m induced by A, ha is, a(u, )=(A 1/2 u, A1/2u)=(∇u, ∇ ) o u, ∈D(A1/2)=H 1 0(Ω), whe e (·,·) deno es he s anda d inne p oduc in L2(Ω) (o in L2(Ω)d). In a simila manne le ah(·,·) be he co esponding bilinea o m on Sh, (in ou case ah(χh,ψ h)=(∇χ h ,∇ψ h ) h , χ h ,ψ h∈S h, , whe e (·,·)hs ands o he s anda d inne p oduc in L2(Ωh)); and le us deno e by Ah he associa ed posi i e, sel -adjoin ope a o in Sh, , ha is, ah(χh,ψ h)=(A h χ h ,ψ h) h=(χ h ,A hψ h) h∀χ h,ψ h∈S h, . Le us also deno e by Ph he s anda d L2o hogonal p ojec ion on o Sh, , and by Rh he ellip ic p ojec ion on o Sh, (also known as he H1p ojec ion) which, o u∈H1 0(Ω) is de ined by ah(Rhu, χh)h=ah(u, χh)=(∇u, ∇χh)h∀χh∈Sh, . The disc epancy be ween Ω and Ωhis usually sol ed by an adequa e selec ion o quad a u e ules, al hough o he al e na i es a e also possible (see sec ion 2.1). The Gale kin app oxima ion o he solu ion uo (1)–(2) is desc ibed as ollows: Find uh:[0,T]→S h, such ha d d uh+νAhuh+PhF(uh)=0,(5) Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php 472 BOSCO GARC´ IA-ARCHILLA AND EDRISS S. TITI uh(0) = Rhu0.(6) We use (6) o simplici y in he analysis. Ou esul s may be easily ex ended o he case whe e uh(0) = Phu0. Nex , we mo i a e and in oduce he me hod s udied he e. Suppose ha we a e in e es ed in he solu ion uo (1)–(2) a a gi en ime T. A ime T, ew i ing (1), we ha e ha νAu(T)=−F(u(T)) −d d u(T). Thus, u(T) can be seen as he solu ion o an ellip ic p oblem whose igh -hand side is no known bu can be app oxima ed. The me hod we p opose is as ollows. (i) Fi s , in eg a e (5)–(6) up o T o ob ain he Gale kin app oxima ion uh(T). (ii) Then sol e (o , in p ac ice, app oxima e) he ollowing linea ellip ic p oblem: Find ˜u∈D(A) such ha νA˜u=−F(uh(T)) −d d uh(T).(7) We call his app oxima ion p ocedu e he pos p ocessed Gale kin me hod. Unde ce ain assump ions ( o be speci ied in sec ion 2.1) we can s a e Theo em 1 below, whose p oo is de e ed un il sec ion 2.3 (a e sion o his esul in L∞is p esen ed in sec ion 4.1). In Theo em 1 and in he es o he pape , he cons an s µand a e µ=2i ≥4 and (3) holds, 1 o he wise, =0i = 3 and (3) holds, 1 o he wise. Theo em 1. Le T>0and ≥3.The e exis s a cons an C>0which depends on K(u),de ined in (22) below, such ha o hsu icien ly small he pos p ocessed Gale kin app oxima ion ˜usolu ion o (7) sa is ies ku(T)−˜ukL2(Ω) +hku(T)−˜ukH1(Ω) ≤Ch +µ|log(h)| .(8) We no ice ha he bound (8) is an imp o emen o e he s anda d Gale kin e o bound, ku−uhkL2(Ω) +hku−uhkH1(Ω) ≤Ch , which is op imal e en in he case o linea p oblems. We ema k ha in p ac ice, o cou se, ˜ucanno be compu ed exac ly since in gene al i does no belong o a ini e-dimensional space, as opposed o uh. Howe e , one can app oxima e he solu ion ˜uo (7) by some ˜uhbelonging o a ini e-elemen space o piecewise polynomials ei he o deg ee +µ−1 o e Th, o o deg ee −1 bu o e some ine pa i ion Th0wi h h +µ=h0 . I mus be no iced ha , om he p ac ical poin o iew, he compu a ional cos o he pos p ocessing s ep (7) is a e y small ac ion o he cos o compu ing uh(T)by ime in eg a ion om =0 o =T. Thus, ˜uhis an app oxima ion o u(T) o highe o de (i.e., asymp o ically mo e accu a e) han uh(T), bu i cos s (almos ) no hing once uh(T) is a ailable. We will see he implica ions o his ac in he nume ical expe imen s in sec ion 3. Obse e ha he combina ion o he Gale kin me hod (5)–(6) and he pos p o- cessing s ep (7) can be seen as a no el wo-le el o wo-g id me hod o e olu ion equa ions. Two-le el me hods o nonlinea p oblems ha e mos ly been de eloped and implemen ed o s eady equa ions (see, e.g., [5], [31], [47], [48], and he e e ences he ein). The basic idea in he s eady-s a e case is o sol e he nonlinea p oblem on a low-o de app oxima ion space (o coa se g id) and hen ob ain a be e app oxi- ma ion wi h one o wo New on i e a ions on a highe -o de app oxima ion space (o Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php POSTPROCESSING FINITE-ELEMENT METHODS 473 on a ine g id). In his way, he nonlinea i ies a e ea ed in he (cheape ) low-o de app oxima ion space o coa se g id, and only linea sys ems a e sol ed in he (mo e cos ly) highe -o de app oxima ion space. On e olu ion p oblems, wo-le el (o u he , mul ile el) me hods can ob iously be used in he nonlinea sys ems ha a ise when using implici ime in eg a o s. O he mo e e ined ideas ha e ecen ly been sugges ed [3], [9], [33], [34], bu , so a , he wo le els o disc e iza ion a e used a e e y ime s ep along he ime e olu ion. On he con a y, Theo em 1 in his pape s a es ha i is sa e o pe o m he ime e olu ion on he low-le el (o coa se g id) app oxima ion space and ob ain he highe - o de co ec ion only once,a =T, ha is, when he ime-ma ching is inished. The p ice o be paid is ha he low-le el (o coa se g id) app oxima ion space mus be composed o piecewise polynomials wi h a deg ee o a leas 2 ( ≥3), since he pos p ocessing s ep (7) does no inc ease he con e gence a e i uh(T) is compu ed by in eg a ing on ime on a space o piecewise-linea polynomials. The pos p ocessing s ep (7) is a gene aliza ion o ini e-elemen me hods o an ea lie pos p ocessing p ocedu e de eloped o spec al me hods in [16], [21], and [22]. To be mo e speci ic, suppose ha ins ead o Sh, , he app oxima ion space is Hmspanned by he eigen unc ions o Aassocia ed wi h he lowes meigen alues o equencies. Then, he Gale kin app oxima ion (5) would be um:[0,T]→H msuch ha dum d +νAum+PmF(um)=0,(9) whe e Pmis he L2p ojec ion on o Hm. The pos p ocessing s ep (7) would be νA˜u=−dum d (T)−F(um(T)).(10) P ojec ing (10) on o Hm, since Pmand Acommu e, we ge νAPm˜u=−PmF(um(T))− dum( ) d  =T, and hence, Pm˜u=um(T), he Gale kin app oxima ion a ime T. Thus, one has only o compu e he high- equency modes ˜q=(I−P m )˜u. Applying (I−Pm) o (10) we ob ain νA˜q=−(I−Pm)F(um),(11) which is he pos p ocessing s ep p oposed in [21], [22]. Obse e also ha ˜q=Φ(u m )= (νA)−1(I−Pm)F(um). The o mula ion (11) o he pos p ocessing s ep is mo e na u al in he case o spec al me hods. Howe e , when de eloping his pape , (7) (o (10)) was seen o be mo e meaning ul and use ul. This poin o iew was also eached independen ly in [17], [18]. In ac , in he case o spec al me hods, he pos p ocessed Gale kin me hod was de eloped he opposi e way. In he con ex o ine ial mani olds [14] and app oxi- ma e ine ial mani olds, i was shown in [13] (see also [15]) ha gi en he low modes Pmuo he solu ion uo (1)–(2), Φ(Pmu)=(νA)−1(I−Pm)F(Pmu) is a high-o de app oxima ion o he high- equency modes (I−Pm)uo u. Based on his ac , he so-called nonlinea Gale kin me hods (NLG) [12], [28], [32] we e de eloped (see also [10], [11], [15], [29], [42], [43], and he many e e ences he ein). In hese NLG me h- ods, nonlinea e ms a e ypically e alua ed in he whole spec um (o some gene ous unca ion o i ), o example, F(ym+Φ(ym)), whe e ym( )∈Hmis he low- equency Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php 474 BOSCO GARC´ IA-ARCHILLA AND EDRISS S. TITI componen o he NLG app oxima ion ym+Φ(y m ). This is compu a ionally cos ly, and ( o add o he cos ) i is done along he ime e olu ion in NLG me hods. Cu en ly, he e is enough a ailable e idence [20], [21], [35], [46] ha NLG me h- ods a e no compe i i e om he poin o iew o e iciency (o a leas , no necessa ily compe i i e). Fo his eason, he pos p ocessed Gale kin (spec al) me hod (9)–(10) was de eloped. The aim was o exploi he app oxima ion capabili ies o Φ bu wi hou paying o he compu a ional cos o NLG me hods (no ice ha in (9)–(10) nonlinea e ms a e applied only o elemen s o Hm, and Φ is compu ed only once). The pos p ocessed Gale kin me hod was seen o be compu a ionally mo e e i- cien han classical Gale kin spec al me hods in [16] and [21]. This is also he case o Gale kin ini e-elemen me hods, as is shown in sec ion 3 and in [30]. The compu- a ional gain is e en mo e signi ican in he maximum no m. The las sec ion o his pape is de o ed o he e o analysis in L∞. We end his sec ion by gi ing an idea o he p oo o Theo em 1. E alua e he PDE (1) a ime =Tand sub ac i om (7). A e ea anging e ms and applying A−1one sees ha u(T)−˜u=1 νA−1d d uh(T)−d d u(T)+1 νA−1(F(uh(T)) −F(u(T))). Thus, a i s sigh , u(T)−˜udepends on uh(T)−u(T) (and (duh/d )−(du/d )| =T) which is only O(h ). Howe e , in due cou se we will show ha ° °A−1(F(uh(T)) − F(u(T)))° °L2(Ω) can be bounded in e ms o ° °A−1(u(T)−uh(T))° °L2(Ω) (A−1/2ins ead o A−1when Fis gi en by (4)). We w i e u−uh=(u−R h u)+(R hu−u h). Since i is well known (see, e.g., [44]) ha ° °A−1(I−Rh)u(T)° °L2(Ω) =O(hmin(2 −2, +2)) (and he same bound o A−1(I−Rh)u (T)), we ha e ha ku(T)−˜ukL2(Ω) ≤C νð °A−1(uh(T)−Rhu(T))° °L2(Ω) +° ° ° ° A−1d d uh(T)−Rh d d u(T)° ° ° °L2(Ω)!+O(hmin(2 −2, +2)).(12) The O(hmin(2 −2, +2)) e m abo e clea ly shows ha he pos p ocessed me hod will ha e a s ic ly highe con e gence a e han he Gale kin me hod on which i is based, only i ≥3, ha is, uh(T) is a piecewise polynomial wi h a deg ee o a leas 2. We will duly show ha he o he wo e ms on he igh -hand side o (12) a e O(h +µ|log(h)| ). The a gumen abo e shows ha he e is no hing especially nonlinea abou he idea behind he pos p ocessed Gale kin me hod, and he esul s would be he same i Fwe e linea . No ice ha e en in he linea case he me hod p esen ed he e allows an O(h +2) (o O(h +1)) e o a he “same” p ice o a cheape O(h ) me hod. In any case, since mos o he in e es ing phenomena a ise in nonlinea p oblems, o comple eness we conside Fas in (3)–(4). The es o his pape is o ganized as ollows. Sec ion 2 is de o ed o p o ing Theo em 1. Nume ical expe imen s a e p esen ed in sec ion 3. Finally, we ca y he L∞analysis in sec ion 4. Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php POSTPROCESSING FINITE-ELEMENT METHODS 475 2. The pos p ocessed Gale kin me hod. 2.1. P elimina ies. We now p esen he assump ions unde which Theo em 1 holds. We es ic ou sel es o quasi-uni o m meshes Th, so ha he ollowing in e se es ima e holds o any elemen τ∈T hand h∈Sh, (see, e.g., [39]): k hkWm,p(τ)≤Chl−m−d(1 q−1 p)k hkWl,q (τ),0≤l≤m≤2,1≤q≤p≤∞.(13) Also, we assume he ollowing es ic ion be ween he o de o app oxima ion and he dimension d: d≤2 −1.(14) This is equi ed by he p esence o he nonlinea e m F, bu i can be loosened i Fis linea . Since ini e elemen s a e mos ad an ageous when dealing wi h complex geome ies, we conside only d≥2. Following he ideas p esen ed he e, he one- dimensional case admi s a much simple ea men . In his si ua ion, o 1 ≤p≤∞, and o any ∈D(A)∩W ,p(Ω), an in e polan Ih( )∈Sh, exis s such ha k −Ih( )kLp(Ω) +hk −Ih( )kW1,p(Ω∩Ωh)≤C¡h +δ(h)k kW ,p (Ω) ,(15) (we ex end by ze o Ih( )inΩ Ω h ), whe e δ(h) = maxx∈Ωhdis (x, ∂Ω). Fo x∈Ω∩Ωh, his bound ollows om he s anda d heo y o in e pola ion and he B amble–Hilbe lemma. Fo x∈Ω Ωh, (x) can be bounded using o he mean- alue heo em (see, e.g., (19) below). Howe e , o he pu pose o analysis, we may assume (see, e.g., [39]) ha Ωh⊆Ω, since one may conside a domain Ωδwi h a smoo h bounda y such ha Ω ∪Ωh⊂Ωδ, and max {dis (x, ∂(Ω ∪Ωh)) |x∈∂Ωδ}≤c 0 δ(h) o some c0>0. Then, o each , eplace u( ) by he solu ion uδ( )o −∆u δ ( )= u ( ), whe e u( ) is a sui able ex ension o −∆u( ) oΩ δ(see [39] o de ails). The se s Ωδmus be buil so ha o δsu icien ly small we ha e ha k δkWl+2,p(Ωδ)≤Cpk kWl,p(Ωδ)=Cpk∆ kWl,p(Ω) ,0≤l≤ , o e e y p∈[2,∞) and e e y ∈W +2(Ω). He e Cp>0 cons an ha depends on pbu no on δ. This can be eadily done i Ω is bounded and + 2 smoo h, o uni o mly + 2 smoo h [1, p. 67]. We will also assume ha he solu ion o (1) sa is ies M3= max 0≤ ≤T° °A3/2u(·, ) ° °L 2(Ω) <+∞.(16) To ensu e he es ima e (16) o e e y solu ion o (3), (4), wi h ini ial da a in D(A3/2), i is su icien o equi e, o example, ha bo h gand bsa is y g(0) = 0 and b(0)=0. I , in addi ion, he igh -hand side o (1) has a smoo h o cing e m = (x, ) ins ead o ze o, hen i is su icien ha (x, ) has a ze o ace a he bounda y o Ω. In he unde s anding o he pos p ocessed Gale kin me hod, he ellip ic p ojec ion Rhuo uwill play a p ominen ole. To simpli y no a ion we w i e h=Rhu. Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php 476 BOSCO GARC´ IA-ARCHILLA AND EDRISS S. TITI Unde hese condi ions he ollowing bounds hold o 1 ≤l≤ : ku−PhukL2(Ω) ku− hkL2(Ω) +hku− hkH1(Ω) ≤ChlkukHl(Ω) ,(17) and, o 0 ≤s≤2, ° °A−s/2(u−Phu)° °L2(Ω) ° °A−s/2(u− h)° °L2(Ω) )≤Chl+skukHl(Ω) , s = min(s, −2).(18) Fo hese bounds o hold, ca e mus be aken o app oxima e he bounda y wi h he necessa y accu acy (see, e.g., [44, sec ion 5.1]). Hence o h, we will assume ha o some cons an cδ>0, δ(h) = max x∈Ωh dis (x, ∂Ω) ≤cδh +2. We also ema k ha (16) plays a ole in o de o bound k∇(u− h)kL2(Ω) in e ms o hl−1kukHl(Ω) in (17), due o he skin-laye Ω Ωh. To be mo e p ecise, le D⊂Ω be such ha max{dis (x, ∂Ω) |x∈D}≤cδ(h). Fo any ∈D(A), since =0on ∂Ω, one can check ha k kL2(Ω D)≤Cδ(h)k∇ kL2(Ω) .(19) Hence, aking D=Ω h , we ha e ha k∇ kL2(Ω Ωh)≤Ck k1/2 L2(Ω Ωh)k k1/2 H2(Ω Ωh)≤Cδ(h)1/2k kH2(Ω) . Fo ∈D(A3/2) be e es ima ions can be ob ained as ollows. Conside Ω1⊂⊂ Ωhwi h a su icien ly smoo h bounda y such ha max{dis (x, ∂Ωh)|x∈Ω1}≤ c 0 δ(h) o some c0>0. Then k∇ kL2(Ω Ωh)≤k∇ k L 2 (Ω Ω1). Using he di e gence heo em, ace heo ems, and he smoo hness o Ω, one can show ha k∇ k2 L2(Ω Ω1)≤ k∆ kL2(Ω Ω1)(k kL2(Ω Ω1)+k∇ kL2(Ω Ω1)). Now, ecalling (19), we ha e ha ° °∇ ° °L2(Ω Ωh)≤Cδ(h)k kH3(Ω) . Fo he L2p ojec ion Phwe will use s onge es ima es han hose in (17). Mo e p ecisely, he e exis s a cons an C>0 such ha k −Ph kLq(Ω) ≤Ck kLq(Ω) ,1≤q≤∞,(20) ∀ ∈Lq(Ω) (see, e.g., [44, p. 39]). Simila ly, o he ellip ic p ojec ion kRhk∞≤C(21) (see [39]), whe e, he e and in he es o he pape , k·kpdeno es he ope a o no m in L(Lp(Ω)) o 1 ≤p≤∞. We ema k ha o piecewise-linea ini e elemen s (i.e., = 2) he bound (21) does no hold (Cshould be eplaced by C(1+|log(h)|)). In his pape , howe e , we es ic ou sel es o ≥3. The e o es ima es in sec ions 2.2 and 2.3, as well as he cons an Cin Theo em 1 depend on K(u, )=ku(·, )kH (Ω) +ku (·, )kH (Ω) ,K(u) = max 0≤ ≤TK(u, ).(22) Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php POSTPROCESSING FINITE-ELEMENT METHODS 477 No ice hen, ha we a e assuming su icien smoo hness o he solu ion as well as o he ini ial condi ion. I mus be s a ed ha i (1) is au onomous and gand bin he nonlinea e ms Fin (3)–(4) a e analy ic, due o he analy ici y in ime o he solu ions o (1)–(2), o mos ini ial condi ions u0, i is possible o bound ku (·, )kH (Ω) in e ms o maxz∈Sku(·,z)kH (Ω) o zin an adequa e neighbo hood So [0,T] in he complex plane (see, e.g., [7, pp. 104–109]). We will equen ly use he ollowing e sion o Sobole ’s lemma: o p∈[1,∞), he e exis s a cons an C=C(Ω,p) such ha k kLp0(Ω) ≤Ck kWs,p(Ω) o 1 p≥1 p0≥1 p−s dand ∈Ws,p(Ω) whene e p0<∞.Fo p 0=∞ he abo e inequali y holds o 1 p≥1 p0>1 p−s d, and, u he mo e, in his case is also a con inuous unc ion. Also he ollowing inequali y, which is easily ob ained om H¨olde ’s inequali y, will be equen ly used: |( , w))|≤k k L 2 (Ω) k kLp(Ω) kwkLq(Ω) ,1 p+1 q=1 2.(23) 2.2. Analysis o he Gale kin me hod. In his sec ion we ob ain bounds o uh− h. The main esul is Theo em 2 a he end o he sec ion. I s p oo will be ob ained as a consequence o se e al p e ious lemmas. In he ollowing, we need he esidual o unca ion e o Tho he ellip ic p o- jec ion h= h( )=R h u( ). No ice ha hsa is ies d d h+νAh h+PhF( h)=T h ,(24) whe e he unca ion e o This Th=Ph(F( h)−F(u)) + d d h−Phu .(25) In gene al, kThkL2(Ω) is no smalle han ku −d h/d kL2(Ω) =O(h ). In ac , he abo e is de ini ely ue in he linea case when F= 0. On he o he hand, no ice ha in Lemma 4 below, we bound no only kThkL2(Ω) bu also an in eg al o e−ν( −s)AhTh(s) wi h espec o s. I is he smoo hing e ec o he semig oup e−ν Ah ha gi es he ex a powe hµ|log(h)| in Theo em 2 wi h espec o he O(h ) decay o kThkL2(Ω). Lemma 1. Le h:[0,T]→S h, sa is y he h eshold condi ion, k h( )− h( )kL2(Ω) ≤c hh ,(26) o ∈[0,T]. Se µ=0i he nonlinea i y Fis gi en by (3); o he wise se µ=1 when Fis gi en by (4). Then he e exis s a cons an C, which depends on c h and max0≤ ≤Tku( )kH (Ω), such ha o ∈[0,T] ° °A −µ/2 hPh(F( h( )) −F( h( )))° °L2(Ω) ≤Ck h( )− h( )kL2(Ω) .(27) Fu he mo e, o Fgi en by (4) we ha e ha kPh(F( h( )) −F( h( )))kL2(Ω) ≤C¡k∇( h( )− h( ))kL2(Ω) +h−1k h( )− h( )kL2(Ω).(28) Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php 478 BOSCO GARC´ IA-ARCHILLA AND EDRISS S. TITI P oo . Le us ake ∈[0,T], and o simplici y, le us d op he explici dependence on . We i s no ice ha bo h hand ha e bounded in L∞in e ms o u, since k hkL∞(Ω) ≤k h− h k L ∞ (Ω) +k hkL∞(Ω), which, hanks o he in e se es ima e (13) and he h eshold condi ion (26), is bounded by c hh −d/2+k hkL∞(Ω). Then in iew o he ac ha Rhis bounded in L∞( ecall (21)), Sobole ’s lemma, and he es ic ion (14) be ween he dimension dand we ha e ha k hkL∞(Ω),k hkL∞(Ω) ≤CkukH (Ω). As a consequence, o any smoo h unc ion , ( h), ( h)∈L p(Ω) o 1 ≤p≤∞.(29) Thus, o Fas in (3), he s a emen (27) is a di ec consequence o he mean- alue heo em. Fo Fas in (4) we i s p o e (27). No ice ha A−µ/2 hPh=A1−µ/2 hA−1 hPh= A1−µ/2 hRhA−1. In addi ion, o χh∈Sh, , we ha e ha kA1/2 hχhkL2(Ω) =k∇χhkL2(Ω), and kA−1·kH1(Ω) ≤CkA−1/2·kL 2(Ω). Then, using (17) we ha e ha ° °A−1/2 hPh(F( h)−F( h))° °L2(Ω)≤C° °A−1/2(F( h)−F( h))° °L2(Ω). Le us es ima e he igh -hand side abo e by duali y. Since A−1/2is bounded, we need only o s udy he con ec ion e m. Le us deno e eh= h− h. We ha e ha b( h)·∇ h−b( h )·∇ h=b( h )·∇e h+(b( h )−b( h )) ·∇ h .(30) Le φ∈C∞ 0(Ω) be a es unc ion. Taking he inne p oduc in (30) wi h φand in eg a ing by pa s he i s e m on he igh -hand side abo e becomes ¡b( h)·∇e h ,A −1/2φ =¡e h,di ¡b( h)A−1/2φ =¡eh,b 0( h)·∇ h A −1/2φ +¡e h ,b( h)·∇A −1/2φ .(31) We now ake psuch ha 1 p=1/4i d=2 1/2−1/d i d>2. Then, by Sobole ’s lemma, we ha e ha k·kL p(Ω) ≤Ck·kH 1(Ω), and, in pa icula , kA−1/2φkLp(Ω) ≤CkφkL2(Ω). We also ake qsuch ha 1/q +1/p =1/2. Fo his alue o q, hanks o (14), i is immedia e o check ha kukW1,q(Ω) ≤CkukH (Ω) .(32) Applying (23) o he igh -hand side o (31), we ha e ha ¡eh,b 0( h)·∇ h A −1/2φ  ≤Cke h kL 2(Ω) kb0( h)kL∞(Ω) k∇ hkLq(Ω) kφkL2(Ω) , ¡eh,b( h)·∇A −1/2φ  ≤Cke h kL 2(Ω) kb( h)kL∞(Ω) kφkL2(Ω) . Also, o he second e m on he igh -hand side o (30), hanks o he mean- alue heo em and (29), a guing as abo e we ha e ha ¡(b( h)−b( h))∇ h,A −1/2φ  ≤Cke hkL 2(Ω) k∇ hkLq(Ω) kφkL2(Ω) . Thus, (27) is p o ed, p o ided we show ha k∇ hkLq(Ω) ,k∇ hkLq(Ω) ≤CkukH (Ω) (33) Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php POSTPROCESSING FINITE-ELEMENT METHODS 485 P oo o Theo em 1. Sub ac ing (7) om (1) and applying νA−1we ha e ha u(T)−˜u=ν−1A−1(F(uh(T)) −F(u(T))) + A−1duh d (T)−du d (T).(59) Since k∇·kL2(Ω) =° °A1/2·° °L2(Ω), hen by Lemma 3 and an a gumen simila o ha leading om (50) o (47), we ob ain he ollowing bounds: ku−˜ukL2(Ω) ≤C° °A−1(uh−u)° °L2(Ω) +° °A−1(uh−u) ° °L2(Ω) +2,(60) ku−˜ukH1(Ω) ≤C° °A−1/2(uh−u)° °L2(Ω) +° °A−1/2(uh−u) ° °L2(Ω) +1,(61) whe e o µ=1,2, µ=ku−uhkLq(Ω)ku−uhkHi(Ω), wi h qas indica ed in Lemma 3 and i= 1 when Fis gi en by (4); o he wise i=0. Le us i s ind an uppe bound o µ. We w i e u− h=(u− h )+( h−u h ).(62) Fo h−uh, using he in e se es ima e (13) and Theo em 2, we ha e ha k h−uhkLq(Ω) ≤Chd q−d 2k h−uhkL2(Ω) ≤CK(u)h +µ+d q−d 2|log(h)| . Bu d/q−d/2=−d/p, which, in iew o (38), allows us o w i e +µ−d/p ≥µ+µ−1, whe e we ha e used ha ≥3 in he case d/2<µ. This and (52) lead o ku−uhkLq(Ω) ≤CK(u)hmin(µ+µ−1,µ)|log(h)| . Using again (62), applying (17), (13), and Theo em 2, one can show ha ku−uhkHi(Ω) ≤CK(u)h −i, whe e i= 1 when Fis gi en by (4); o he wise i= 0. Hence, i ollows ha 2≤CK(u)h +µ|log(h)| , 1 ≤CK(u)h +1−i|log(h)| . Le us now u n o he o he e ms in (60)–(61). Using (62) and aking in o accoun ha A−µ/2is bounded, we ha e ha ° °A−µ/2(u−uh)° °L2(Ω) ≤° °A−µ/2(u− h)° °L2(Ω) +Ck h−uhkL2(Ω) , ° °A−µ/2(u−uh) ° °L2(Ω) ≤° °A−µ/2(u− h) ° °L2(Ω) +° °A−µ/2( h−uh) ° °L2(Ω). Then, (17)–(18) and Lemma 6, oge he wi h (54), yield he bound (8). 3. Nume ical expe imen s. We conside he eac ion-di usion sys em ∂u1 ∂ =1−4u 1+u 2 1 u 2+ν∆u 1 ∂u2 ∂ =3u 1 −u 2 1 u 2 +ν∆u 2  known as he B ussela o (see, e.g., [27]), in Ω ×[0,T], whe e Ω = [0,1]2and T= 10, subjec o he Neumann bounda y condi ion ∂u1 ∂n =∂u2 ∂n =0 on ∂Ω. Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php 486 BOSCO GARC´ IA-ARCHILLA AND EDRISS S. TITI 0 5 10 15 20 2.5 3 3.5 4 4.5 || u || L 2 Fig. 1.E olu ion o kukL2(Ω)2. 00.5 1 0 0.5 1 1 2 3 4 x y u 2 Fig. 2.Componen u2o he solu ion a T=10. Al hough o simplici y we ha e de eloped he analysis o Di ichele bounda y con- di ions, ou analysis can be modi ied o co e he Neumann bounda y condi ions case as well. We se ν=0.002. We complemen his sys em wi h he ini ial condi ion u1(x, y, 0)=1−1 4(2y−1)((2y−1)2−3), u2(x, y, 0)=3−(2x−1)((2x−1)2−3). The co esponding solu ion becomes nea ly pe iodic in ime, and de elops mode a ely la ge g adien s. Figu e 1 shows he e olu ion o kukL2(Ω)2up o ime T= 20, and a pe iodic beha io can be obse ed. In Figu e 2, he componen u2o he solu ion, a ime T= 10, is po ayed; he g adien akes alues abo e 50 in some poin s o he domain. In ou calcula ions we ake he so-called egula pa e n iangula ions o Ω, which a e induced by he se o nodes (j/N,k/N), 0 ≤j, k ≤N, whe e N=|Ω|/h is an in ege . Fo he Gale kin me hod (5) we used Lag ange quad a ic elemen s on hese iangula ions (i.e., = 3) and o he pos p ocessing s ep, since he solu ion u= (u1,u 2) Tis smoo h, we choose Lag ange cubic elemen s on he same iangula ions. Since he Laplacian is nonin e ible when subjec o Neumann bounda y condi- ions, o he pos p ocessing s ep we sol e ν˜ Ah˜u1,h +4˜u 1,h =1+ ˜ P h (u 2 1,hu2,h)−d d u1,h,(63) ν˜ Ah˜u2,h +˜ Ph¡˜u2 1,h ˜u2,h)=3˜u 1,h −d d u2,h,(64) sol ing i s (63) (no ice ha ν˜ Ah˜ +4Idis in e ible) and hen (64). Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php POSTPROCESSING FINITE-ELEMENT METHODS 487 Fo he ime in eg a ion, a a iable- o mula, a iable-coe icien implemen a ion o he backwa d di e en ia ion o mulae (BDF) was used wi h o de s up o six (see, e.g., [26]). This me hod is widely used in he nume ical in eg a ion o s i o dina y di e en ial equa ions (ODEs), like hose a ising om he spa ial disc e iza ions o dissipa i e PDEs. This BDF code was p e iously used in [16],[19], [20]. In [19], his code is shown o be mo e e icien han o he widely used in eg a o s in dissipa i e PDEs (including semi-implici me hods). Wi hou an e icien ime in eg a o , as shown in [19], [20], i may ake an una o dable amoun o compu ing ime o each he le els o accu acy desc ibed below. Fo each hused in he iangula ions o Ω, e e y expe imen was ca ied ou wi h di e en alues o he ole ance TOL (an inpu alue o he ime in eg a o ) below which local ime disc e iza ion e o s a e desi ed. The smalles e o ob ained was selec ed o he plo s. The e was always a poin , depending on h, a which u he educing he ole ance did no educe he e o s any mo e. This means ha he e o a ising om ime disc e iza ion is much smalle han he e o a ising om he ini e-elemen spa ial disc e iza ion. When his happens, one can be su e ha he e o s obse ed a e due only o he spa ial disc e iza ion and do no depend on he ime in eg a o used. In iew o [19] we we e pa icula ly ca e ul o ensu e ha he dominan e o in all he compu a ions p esen ed he e was he spa ial disc e iza ion e o in o de o a oid w ong conclusions om ou nume ical expe imen s. Also, o he compu a ional cos in Figu es 4–6 below, he la ges ole ance among hose wi h which he spa ial disc e iza ion e o was dominan was used. We e e o his alue o he ole ance as he op imal ole ance. A smalle ole ance would esul in a la ge cos bu no smalle e o . A la ge one, on he o he hand, would imply a la ge e o , bu hen he same e o could be ob ained a less cos wi h he same ole ance and la ge h. In Figu e 3 we p esen a con e gence diag am showing he e o s commi ed by he me hods when used wi h h=|Ω|/N ,N=12,24,48. By e o s we mean he di e ence be ween he app oxima ions (u1,h,u 2,h)o (˜u 1,h,˜u2,h) and he exac solu ion (a he end o he sec ion we explain how i was ob ained). In his and in he es o he plo s, he compu a ional esul s o he classical quad a ic elemen s a e joined by con inuous lines, and hose o he pos p ocessed me hod by discon inuous (dashed) lines. Wi h his, we ge an idea o wha he esul would ha e been o in e media e alues o h. I can be seen ha as his dec eased om le o igh , he e o s in bo h me hods dec ease om op o bo om, bu hey dec ease as e in he pos p ocessed me hod. Measu es o he slopes o he plo s con i m he a es p edic ed by he heo y (i.e., he e o s in he plo dec ease like Nslope = cons .h−slope). The imp o ed con e gence a e o he pos p ocessed me hod obse ed in Figu e 3 also implies imp o ed e iciency. This can be checked in Figu e 4, whe e he same e o s as in Figu e 3 a e plo ed agains he smalles amoun o CPU ime ha he me hods needed o achie e hem, ha is, he cos o in eg a ing he me hod wi h he op imal ole ance (no ice ha , o a gi en h, he op imal ole ance o he pos p ocessed quad a ics is, in gene al, smalle han ha o he quad a ics). The eason o his imp o emen is ha he e o o he Gale kin me hod is educed when he pos p ocessing is done, bu his is done a e y li le cos (less han 10% o he whole compu a ion, including he ex a cos o in eg a ing in ime wi h smalle ole ances). In ac , he cos o he pos p ocessing s ep is equi alen o he cos o oughly 10 ime s eps, and he numbe o ime s eps in he esul s shown in Figu e 4 a ies be ween 109 and 344. Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php 488 BOSCO GARC´ IA-ARCHILLA AND EDRISS S. TITI 101102 105 104 103 102 N=|Ω|/h L2 ela i e e o s B ussela o wi h nu=0.002: T=10 slope=3.0563 slope=3.8084 Quad a ics Pos p ocessed Quad a ics N=48 N=12 Fig. 3.Con e gence diag am. 101102103 105 104 103 102 CPU ime L2 ela i e e o s B ussela o wi h nu=0.002: T=10 Quad a ics Pos p ocessed Quad a ics N=48 N=24 N=12 Fig. 4.E iciency diag am. The pos p ocessed quad a ic elemen s a e no only mo e e icien han he classical quad a ics bu also mo e e icien han he classical cubic elemen s, which ha e he same con e gence a e as he pos p ocessed quad a ics. In Figu e 5 we ha e plo ed, besides he esul s o Figu e 4, hose o he classical cubic elemen s, ha is, he s anda d Gale kin me hod (5)–(6) bu wi h = 4. These a e ep esen ed by as e isks joined by do ed lines. No ice how he discon inuous line (pos p ocessed me hod) is always on he le (less CPU ime) o he do ed line o he cubics. In his example, Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php POSTPROCESSING FINITE-ELEMENT METHODS 489 101102103 105 104 103 102 CPU ime L2 ela i e e o s B ussela o wi h nu=0.002: T=10 Quad a ics Pos p ocessed Quad a ics Cubics N=6 N=12 N=12 N=24 N=48 N=48 N=48 Fig. 5.E iciency diag am. 101102103 104 103 102 101B ussela o wi h nu=0.002: T=10 L∞ ela i e e o s CPU ime Cubics Pos p ocessed Quad a ics N=6 N=12 N=12 N=24 N=24 N=48 N=48 Fig. 6.E iciency diag am in L∞. he pos p ocessed quad a ics sa e be ween 15% and 17% o he cos o he cubics. Mo e signi ican is he gain in he maximum no m in Figu e 6, whe e he pos p ocessed quad a ics equi e be ween 21% and 25% less compu ing ime han he classical cubics. A signi ican de ail can be obse ed in Figu es 5 and 6: The pos p ocessed me hod is mo e e icien han classical me hods o qui e la ge e o s (al eady abo e 10−3). This is in con as o ou p e ious expe ience wi h spec al me hods, whe e, ypically, pos p ocessing b ings a subs an ial imp o emen only o qui e small e o s (below 10−5) [16], [21]. Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php 490 BOSCO GARC´ IA-ARCHILLA AND EDRISS S. TITI 0 2 4 6 8 10 0 5 10 15 i e a ions CPU ime = 1082 s CPU ime = 739 s CPU ime = 780 s Fig. 7.E olu ion o PCG i e a ions o h=√2/48 and TOL =0.001: −·−MAXIPCG =8,−− MAXIPCG =11,−− MAXIPCG = 18818. We end his sec ion by commen ing on he mo e ele an de ails o he me hods used. Recall ha he ime in eg a ion is done wi h he BDF. Since hese a e ully implici me hods, hen, a e e y ime s ep, a sys em o nonlinea equa ions o he o m α h+(δ )(νAh h+PhF( h))=0,(65) has o be sol ed, whe e δ is he ime s epleng h. This was done by New on i e a ion. The exac Jacobian ma ices we e eplaced by he Jacobian ma ix o he linea e ms, ha is, αMh+(δ )νSh,(66) whe e Mhand Sha e he mass and s i ness ma ices (see, e.g., [45]). The co esponding linea sys ems we e sol ed by he p econdi ioned conjuga e g adien me hod (PCG) wi h incomple e Cholesky (ICH) ac o iza ion o (66) as p econdi ione (see, e.g., [23]). Bo h PCG and ICH algo i hms we e aken om he SLAP lib a y. A single ICH ac o iza ion o (66) p o ed o be ex emely cos ly (be ween 5% o 10% o he whole compu a ion om =0 oT= 10). Thus, i was compu ed a he i s s ep and eused in la e s eps un il he PCG did no con e ge, when i was ecalcula ed again. By con e gence in he PCG me hod we mean achie ing a ela i e e o below a p esc ibed alue TOLPCG in less han a ixed numbe o i e a ions MAXIPCG. In ou p esen case, we chose TOLPCG =10 −3 o he linea sys ems in he New on i e a ion o (65), and 10−9 o hose in he pos p ocessing (63)–(64). To se he alue o MAXIPCG, we pe o med a p ac ical s udy o a ious alues o hand se le i o MAXIPCG = 11, which usually o ced he compu a ion o wo ICH decomposi ions. In Figu e 7, he numbe o PCG i e a ions ( he maximum o he wo o h ee linea sys ems sol ed pe s ep) o di e en alues o MAXIPCG a e shown, oge he wi h he CPU imes o he co esponding uns. I can be seen how i MAXIPCG is gene ous (dashed line) he code compu es only one ICH ac o iza ion a = 0 bu in he end pe o ms a c ippling numbe o i e a ions. I MAXIPCG is oo igh (dash-do ed line) he second ICH decomposi ion is compu ed oo soon, a =1.6662; he numbe o PCG i e a ions is d as ically educed om hen onwa d, bu he o e all numbe o i e a ions (and hence he cos ) is la ge han o MAXIPCG = 11 (con inuous line). No ice how in his las case, he numbe o i e a ions is d as ically educed a = 2.5005 when he second ICH ac o iza ion is compu ed, and emains he lowes om hen onwa d. Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php POSTPROCESSING FINITE-ELEMENT METHODS 491 Fo he linea sys ems in he pos p ocessing s ep (63)–(64), i p o ed a mo e e ec i e o use he diagonal o he co esponding ma ices as a p econdi ione . A a g ea e numbe o PCG i e a ions we e aken (in he example o Figu e 7, 70 o ˜u1,h and 308 o ˜u2,h o sys ems o 21025 unknowns), bu i compensa ed o he cos o a new ICH ac o iza ion (no ice ha he ma ices in he pos p ocessing s ep a e o la ge dimension han hose in (66)). The ini ial guess o New on’s me hod in (65) was compu ed by s anda d ech- niques o ex apola ion in he BDF code (see, e.g., [26]), and o he PCG me hod in he co esponding linea sys ems he ini ial i e a es we e se o 0 (no ice ha he solu ions o his sys ems a e he inc emen s o New on i e a ions ha a e supposed o be small). Fo he linea sys em in he pos p ocessing s ep (63)–(64), he ini ial guess was he Gale kin app oxima ion uhexp essed in he nodal basis o he cubic elemen s. I may be asked i o he linea algeb a echniques would ha e changed he esul s shown he e. This would be especially he case i a as e (i exis ing) linea algeb a would ha e a o ed he cubic elemen s bu no he quad a ics (and hence, nei he he pos p ocessed me hod), al hough i is di icul o de ise why i should be so. Ob iously, i is ou o he scope o his pape o es all possible linea sys em sol e s, especially when he e does no seem o be a clea -cu c i e ion o when o apply he many exis ing echniques compe ing o a en ion. The PCG used he e seems o us a e y easonable choice, especially i we ake in o accoun he e y low numbe o i e a ions ha i ook o sol e he sys ems in ou examples ( ecall Figu e 7). Fu he mo e, a signi ican imp o emen could ha e been made o he pos p ocessing s ep wi h mul ile el echniques (see, e.g., [4]), which would ha e a o ed ye u he he pos p ocessed Gale kin me hod. We es ed di ec (spa se) sol e s, bu hey we e ema kably mo e cos ly han he PCG. We also checked ha explici ime in eg a o s we e much less e icien han he BDF (i.e., he sys em o ODEs (5) is genuinely s i ). In all he esul s shown he e, he ini ial condi ion (6) was eplaced by he in e - polan Ih(u0), which is much cheape o compu e han he ellip ic p ojec ion in (6). We also pe o med he expe imen s wi h (6), and obse ed ha he di e ences wi h hose shown he e we e insigni ican . The heo e ical (“exac ”) solu ion uwas compu ed wi h cubic elemen s and h=√2/96, using alues o he ole ance anging om 10−9 o 10−12, so ha he compu ed solu ion aken as exac is easonably mo e accu a e han hose shown in he expe imen s. All expe imen s we e ca ied ou on a SUN Ul a-1, Mod. 140 wo ks a ion wi h 64 MB RAM, unde Sola is 2.5.1. All p og ams we e w i en in FORTRAN, used double p ecision a i hme ic, and we e compiled wi h he Spa cWo ks 4.0 compile wi h he - as op ion. 4. L∞analysis. 4.1. P elimina ies and main esul . In compa ison o sec ion 2, we u he es ic ou sel es he e in he ollowing sense. 1. The esul s he e apply only o eac ion-di usion equa ions wi h nonlinea e ms as in (3). 2. We conside only p oblems in Rd, wi h d=2,3. (As wi h he L2analysis, he case d= 1 is pa icula and easie o s udy). The e o es ima es in his sec ion depend on K∞(u, )=ku(·, )kW ,∞(Ω) +ku (·, )kW ,∞(Ω) ,K ∞ (u) = max 0≤ ≤TK∞(u, ).(67) Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php 492 BOSCO GARC´ IA-ARCHILLA AND EDRISS S. TITI Unde hese condi ions, he e o bounds o he pos p ocessed Gale kin me hod a e s a ed in he ollowing heo em whose p oo is gi en in sec ion 4.3. Theo em 3. The e exis cons an s C=C(K∞(u)) >0and h0>0such ha o e e y h∈(0,h 0] he solu ion ˜uo (7) sa is ies he ollowing bound: ku−˜ukL∞(Ω) ≤Ch +2−d/2|log(h)|4−d/2i =3.(68) ku−˜ukL∞(Ω) ≤Ch +2 |log(h)|3i ≥4.(69) We now s a e he equi alen o (17)–(18) in he L∞no m. Ins ead o (17) we ha e ku− hkL∞(Ω) +hku− hkW1,∞(Ω∩Ωh)≤ChlkukWl,∞(Ω) ,1≤l≤ .(70) This es ima e ollows om Theo em 5.1 in [39], (15), and (13). We a e unawa e o an es ima e like (18) in L∞, al hough simila esul s in Lpcan be ound in he li e a u e. Thus, we p o e he ollowing esul . Lemma 7. Assume ha d≥2, ≥3,and δ(h)=O(h min( +2,2( −1))). Then he e exis s a cons an C>0such ha o ∈W ,∞(Ω) he ollowing bound holds: ° °A−1( −Rh )° °L∞(Ω) ≤Ck kW ,∞(Ω) hmin( +2,2( −1)) |log(h)|.(71) P oo . Following [39], we ake χh=Ih¡A−1(I−Rh) ) he in e polan o A−1(I− Rh) . Then ° °A−1(I−Rh) ° °L∞(Ω) ≤° °A−1(I−Rh) −χh° °L∞(Ω) +kχhkL∞(Ω) . Le us ake pwi h 2 ≤p≤∞. Fo he i s e m on he igh -hand side abo e we ha e ha (c . [6, Thm. 3.1.6]) ° °A−1(I−Rh) −χh° °L∞(Ω) ≤Ch2−d/p° °A−1(I−Rh) ° °W2,p(Ω). Le us ecall he ollowing inequali y (see, e.g., [39] and [49]) which, o linea ellip ic equa ions, illus a es he a e a which he Agmon–Douglis–Ni enbe g egula i y and well-posedness es ima e [2] de e io a es as p→∞. Namely, he e exis s a cons an C>0, which is independen o p, such ha ° °A−1w° °W2,p(Ω) ≤CpkwkLp(Ω) ,2≤p<∞.(72) Thus, i ollows ha ° °A−1(I−Rh) −χh° °L∞(Ω) ≤Cph2−d/p k(I−Rh) kLp(Ω) ≤Cph +2−d/p k kW ,p (Ω) . Using (13) we ha e ha kχhkL∞(Ω) ≤Ch−d/pkχhkLp(Ω), and hus kχhkL∞(Ω) ≤Ch−d/p° °χh−A−1(I−Rh) ° °Lp(Ω) +° °A−1(I−Rh) ° °Lp(Ω).(73) In iew o he in e pola ion e o bound (15), (70) and (72) we ob ain he ollowing es ima e o he i s e m on he igh -hand side o (73): Ch−d/p° °χh−A−1(I−Rh) ° °Lp(Ω) ≤Cph +2−d/p k kW ,p (Ω) . Also, i is well known (see, e.g., [40, Example 3.2]) ha Ch−d/p° °A−1(I−Rh) ° °Lp(Ω) ≤Cphmin( +2,2( −1))−d/p k kW ,p (Ω) ,(74) wi h Cindependen o pand h. Taking p=|log(h)|, (71) ollows easily. Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php POSTPROCESSING FINITE-ELEMENT METHODS 493 4.2. L∞analysis o he Gale kin me hod. The ollowing esol en es ima e, which is due o Palencia [38], will be needed la e o ou L∞e o es ima es. Lemma 8. Fix α∈(0,π/2) and h0∈(0,e −1].Le β(h)deno e β(h)=k(P h− R h )A −1 k ∞(= O(h2|log(h)|)).Then he e exis posi i e cons an s C∞and σ<1) such ha he bounds ° °(zI −Ah)−1° °∞≤C∞|z|−1i |z|≤σβ(h)−1, C∞h−d/2|z|−1i |z|≥0 hold o z∈Cwi h π≥|a g(z)|≥αand o 0<h≤h 0 . Taking o example a=(d+3)/(2σcos(α)), i easily ollows ha he e exis s a cons an C0>0 such ha o hsu icien ly small ° °e− Ahχh° °L∞(Ωh)≤C0kχhkL∞(Ωh),χ h ∈S h , ≥ 0 =aβ(h)|log(h)|.(75) We will also use he ollowing bound om Ni sche and Wheele [36], ° °e− Ahχh° °L∞(Ωh)≤C1kχhkL∞(Ωh),χ h ∈S h , ≥0, ≥4.(76) The lack o a bound like (76) ∀ ≥0, i = 3, is he eason ha he con e gence a e depends also on he dimension d. This will be seen in Lemma 11 below. Lemma 9. Fix c h >0and T>0. Then he e exis s a cons an S>0such ha o h:[0,T]→S h, sa is ying h(0) = h(0) and he h eshold condi ion k h( )− h( )kL∞(Ωh)≤c h,(77) o ∈[0, 1]whe e 1≤T, he ollowing bound holds o hsu icien ly small: max 0≤ ≤ 1k h( )− h( )kL∞(Ωh)≤Smax 0≤ ≤ 1° ° ° °Z 0 e−ν( −s)Ah(ˆ Th(s)−Th(s)) ds.° ° ° °L∞(Ωh) , (78) whe e ˆ Tis as in (35). P oo . We no ice ha he h eshold condi ion (77) and he ac ha Rhis bounded ensu es ha bo h k hkL∞(Ω) and k hkL∞(Ω) a e bounded by some cons an C= C(c h,max0≤ ≤Tku( )kL∞(Ω)). Since Fis smoo h, i ollows ha kF( h)−F( h)kL∞(Ωh)≤Ck h− hkL∞(Ωh).(79) Now ake no ms in (36). Fo ≥4, hanks o (76), he ac ha Phis bounded in L∞( ecall (20)) and (79) abo e, s anda d a gumen s wi h he G onwall lemma lead o (78). Fo = 3, simila a gumen s (wi h a gene alized G onwall lemma as in Lemma 2) will also lead o (78) as long as we p o e ° ° ° °Z 0 e−ν( −s)AhPh(F( h)−F( h)) ds° ° ° °L∞(Ωh)≤CZ 0 k h(s)− h(s)kL∞(Ωh) ( −s)γds, (80) o some C>0 and γ<1. To do his, we conside he alue 0in (75) and le us call = max(0, − 0/ν), so ha o s∈[0, ], ν( −s)≥ 0. Then, hanks o (75), (79), and he ac ha Phis bounded, we ha e ha ° ° ° °Z e−ν( −s)AhPh(F( h)−F( h)) ds° ° ° °L∞(Ωh)≤CZ k h(s)− h(s)kL∞(Ωh)ds. (81) Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php 494 BOSCO GARC´ IA-ARCHILLA AND EDRISS S. TITI On he o he hand, ake p=dand κ=d/2−1 so ha 1/p =1/2−κ/d. Then, o s∈[ , ] and wh∈Sh, , hanks o he in e se es ima e (13) and Sobole ’s lemma, we ha e ha ° ° °e−ν( −s)Ahwh° ° °L∞(Ωh)≤C h° ° °e−ν( −s)Ahwh° ° °Lp(Ωh)≤C h° ° °e−ν( −s)Ahwh° ° °Hκ(Ωh) ≤C h° ° °e−ν( −s)Ahwh° ° ° 1−κ L2(Ωh)° ° °A1/2 he−ν( −s)Ahwh° ° ° κ L2(Ωh) ≤C h¡ν( −s)κ/2kwhkL2(Ωh).(82) Now obse e ha o s∈[ , ], since ν( −s)≤ 0≤Ch3/2, i ollows ha h−1≤ C(ν( −s)−2/3). Thus, aking in o accoun ha κ 2+2 3=d 4−1 2+2 3=d 4+1 6≤3 4+1 6=11 12 =γ<1, we ha e ha ° ° °e−ν( −s)Ahwh° ° °L∞(Ωh)≤C ¡ν( −s)11 12 kwhkL2(Ωh)≤C|Ωh|1/2 ¡ν( −s)11 12 kwhkL∞(Ωh). This ( eplacing whby Ph(F( h)−F( h))) oge he wi h (79) and (81) leads o (80)wi h γ=11/12. Ha ing es ablished s abili y in he p e ious lemma, we now ace he ask o es i- ma ing he igh -hand side o (78) when h=uh. Recall ha in he L2case, his was s aigh o wa d hanks o he e y a o able L2-bounds o Ahe−µ( −s)Ah, which can be ob ained by means o he spec um o Ah. In he p esen case, i.e., he L∞case, he lack o such bounds o e−µ( −s)Ah(le alone Ahe−µ( −s)Ah) makes he ask much ha de . Since he di icul y lies when −sis small ( ecall o example he es ic ion in (75)), we will decompose he in eg als in (78) in o wo pa s co esponding o −s la ge (Lemma 10 below) and small (Lemma 11 below). Lemma 10. Fix α∈(0,π/2),le σand β(h)be as in Lemma 8, and se τ1= dβ(h)|log(h)|/(2νσcos(α)).Then he e exis s a cons an C>0such ha o ≥τ1 he ollowing bound holds o hsu icien ly small: ° ° ° °Z −τ1 0 eν( −s)AhTh(s)ds° ° ° °L∞(Ωh)≤C ν log  h max 0≤s≤ −τ1° °A−1 hTh(s)° °L∞(Ωh).(83) P oo . By w i ing eν( −s)AhTh(s)=A h e ν( −s)A hA −1 hT h (s), we only need o bound Aheν( −s)Ah. Le Γ be he bounda y o he sec o {z||a g(z)|≤α}, endowed wi h he posi i e o ien a ion. Then Ahe−ν( −s)Ah=1 2πi ZΓ ze−ν( −s)z(zI −Ah)−1dz. We ake ρ1=σβ(h)−1, and di ide Γ in he wo pa s Γ ∩{|z|≤ρ 1 }and he wo hal -lines Γ ∩{|z|≥ρ 1 }. Taking in o accoun he esol en es ima e in Lemma 8, we can w i e ° °Ahe−ν( −s)Ah° °∞≤2C∞Zρ1 0 e−ν( −s) cos(α)ρdρ +2C ∞ h d/2Z∞ ρ1 e−ν( −s) cos(α)ρdρ, Downloaded 04/17/17 o 150.214.182.208. Redis ibu ion subjec o SIAM license o copy igh ; see h p://www.siam.o g/jou nals/ojsa.php