08.dvi

Transcription

1 METHODS AND APPLICATIONS OF ANALYSIS. c 2003 International Press Vol. 10, No. 2, pp , June ON A ONE-SIDED POST-PROCESSING TECHNIQUE FOR THE DISCONTINUOUS GALERKIN METHODS JENNIFER RYAN AND CHI-WANG SHU Dedicated to Professor Stanley Oser on te occasion of is 60t birtday Abstract. In tis paper we study a class of one-sided post-processing tecniques to enance te accuracy of te discontinuous Galerkin metods. Te applications considered in tis paper are linear yperbolic equations, owever te tecnique can be used for te solution to a discontinuous Galerkin metod solving oter types of partial differential equations, or more general approximations, as long as tere is a iger order negative norm error estimate for te numerical solution. Te advantage of te one-sided post-processing is tat it uses information only from one side, ence it can be applied up to domain boundaries, a discontinuity in te solution, or an interface of different mes sizes. Tis tecnique allows us to obtain an improvement in te order of accuracy from k+1 of te discontinuous Galerkin metod to 2k+1 of te post-processed solution, using piecewise polynomials of degree k, trougout te entire domain and not just away from te boundaries, discontinuities, or interfaces of different mes sizes. 1. Introduction. In tis paper we study a class of one-sided post-processing tecniques to enance te accuracy of te discontinuous Galerkin metods. Tis is a modification of te local post-processing tecnique originally developed by Bramble and Scatz [1] in te context of continuous finite element metods for elliptic problems, and later by Cockburn, Luskin, Su and Süli [6, 7] and by Ryan, Su and Atkins [15] in te context of te discontinuous Galerkin metods for linear yperbolic equations. Two key ingredients of tis post-processing tecnique are a negative norm estimate for te numerical solution, wic sould be of iger order tan te L 2 error estimate, and a local translation invariance of te mes witin te support of te local post-processor. Te tecnique ten allows te recovery of te L 2 error of te post-processed solution to te order of accuracy in te negative norm estimate. Te main advantages of tis tecnique, compared to oter post-processing tecniques, include its local feature, ence its efficiency and its easiness in te parallel implementation framework, and its effectiveness in almost doubling te order of accuracy rater tan increasing te order of accuracy by one or two. Te original local post-processor in [1, 6, 7, 15] is based on a symmetric local stencil, using te information in about 2k neigboring elements to eiter side of te element being post-processed, for P k (piecewise polynomials of degree up to k) elements. Te mes must be uniform witin tis local stencil, and te post-processed solution is (2k+1)-t order accurate in te L 2 norm instead of te usual (k+1)-t order accuracy before postprocessing, for te discontinuous Galerkin metod applied to linear yperbolic equations, wic maintains a (2k+1)-t order accuracy in te negative k norm of te numerical solution. Te symmetric nature of te local stencil prevents te application of te postprocessor to te following situations: near a boundary of a computational domain; near a discontinuity in te solution; and near an interface of meses wit different mes sizes. We can see clearly in te numerical examples in [15], tat te post-processor fails in all Received Marc 31, 2003; accepted for publication August 21, Current address: Oak Ridge National Lab, P.O. Box 2008, MS 6367, Oak Ridge, TN , USA (ryanjk@ornl.gov). Researc supported by NASA Langley grant NGT Division of Applied Matematics, Brown University, Providence, Rode Island 02912, USA (su@dam.brown.edu). Researc supported by ARO grant DAAD , NSF grant DMS and NASA Langley grant NCC

2 296 J. RYAN AND C.-W. SHU suc cases, rendering te enancement of te order of accuracy not uniform across te computational domain wen any one of tese situations exist. In tis paper we develop a one-sided local post-processor based on a one-sided biased or completely one-sided stencil. Tat is, te stencil uses more elements to te left tan to te rigt of te element being post-processed, or in te extreme case it uses only elements to te left, for te left-sided post-processor. Te rigt-sided post-processor is a mirror image of te left-sided post-processor. Under te same assumptions as before, namely te numerical solution as a negative norm estimate wic is iger order tan te L 2 error estimate, and te mes is translation invariant (uniform) witin te stencil of te post-processor, te same accuracy enancement can be expected and is verified by numerical experiments. Tis tecnique tus allows us to obtain an improvement in te order of accuracy from k+1 of te discontinuous Galerkin metod to 2k+1 of te postprocessed solution trougout te entire domain and not just away from te boundaries, discontinuities, or interfaces of different mes sizes, for problems wit negative error estimates to te order of 2k+1, suc as te discontinuous Galerkin metod using P k elements for linear yperbolic equations wit smoot solutions. Te applications considered in tis paper are mainly linear yperbolic equations, owever te tecnique can be used for te solution to a discontinuous Galerkin metod solving oter types of partial differential equations as long as tere is a iger order negative norm error estimate for te numerical solution, for example te local discontinuous Galerkin metods for convection diffusion equations [11, 7] and for partial differential equations wit even iger spatial derivatives [17]. We remark tat te idea of one-sided post-processors or filters as been developed before in [2, 13] for spectral metods, and mentioned in [14] for finite difference metods, for similar purpose of enancing accuracy up to a boundary or a discontinuity. Te details of te discontinuous Galerkin metod tat we will be using can be found in [9, 8, 5, 4, 10, 3, 12]. We use te tird-order TVD Runge-Kutta metod in time [16]. Te outline of te paper is as follows. In section 2, we discuss te form of te one-sided post-processor. Te numerical examples, mostly tose given in [15], are ten presented using tis one-sided form of te post-processor in section 3 to demonstrate te accuracy enancement capability of tis tecnique. Altoug only one dimensional scalar examples are given in tis paper, te one-sided post-processor is expected to work equally well for multi-dimensional linear yperbolic systems; see [7, 15] for suc examples using te symmetric post-processors. 2. Te one-sided post-processor. Te structure of te post-processor we will be using was initially designed by Mock and Lax [14] and Bramble and Scatz [1]. A discussion of tis tecnique for te discontinuous Galerkin metod can be found in [6, 7, 15]. For te purposes of tis paper, we introduce a one-sided tecnique to andle post-processing near a boundary, a discontinuity, or an interface of meses wit different mes sizes. Te post-processed solution for te numerical solution u (x) isofteform u (x) =K u (x) were te symmetric post-processing kernel is given by K 2(k+1),k+1 (x) = k γ= k c 2(k+1),k+1 γ ψ (k+1) (x γ), (2.1) and K = 1 K( x ) for a locally uniform mes ( = x i,i=1,,n). Here c 2(k+1),k+1 γ

3 ONE-SIDED POST-PROCESSING FOR DISCONTINUOUS GALERKIN METHODS 297 are constants and ψ (k+1) (x) are(k+1)-t order B-splines. Recall tat te post-processor can be implemented by doing small matrix-vector multiplications, [15]. Te matrixvector format is found from evaluating were u (x) = 1 = C(j, l, k, x) = 1 2k j= 2k 2k k j= 2k l=0 k γ= k I i+j K 2(k+1),k+1 ( ) k y x l=0 u (l) i+j ( ) l y xi+j dy u (l) i+j C(j, l, k, x) (2.2) ( )( y x y c 2(k+1),k+1 γ ψ (k+1) xi+j γ I i+j ) l dy is a polynomial of degree 2k+1 on te cell I i =(x i 2,x i + 2 ). Notice tat in tis symmetric version te post-processed solution as a support of 2k cells on eiter side for a total support of 4k+1 cells. In order to perform a one-sided version of tis, we simply extend tis support biased to one-side. Tus, to perform a purely left-sided post-processing, te post-processed solution would be of te form u (x) (2.3) 0 k = u (l) 1 1 ( )( ) l y x y i+j c 2(k+1),k+1 xi+j γ γ dy. j= 4k l=0 γ= 2k 1 I i+j ψ (k+1) Altoug we do not provide te details ere, we note tat it is only necessary to find te new coefficients, c 2(k+1),k+1 γ, in te post-processing kernel - te evaluation of te integral does not cange. As sown in [7, 15], te coefficients used in te kernel can be found easily by implementing te property tat K p = p. In te case of te symmetric post-processing tis property olds for polynomials p up to degree 2k+1. For te one sided post-processor, we can only require tis property to old for polynomials up to degree 2k. As an example, we can look at te left-sided post-processor used for a linear polynomial approximation (wic gives second order accuracy). Te left-sided post-processed solution is given by u (x) = were te c 4,2 γ 0 1 j= 4 l=0 u (l) i+j 1 1 γ= 3 ( )( y x y c 4,2 γ ψ (2) xi+j γ I i+j ) l dy, (2.4) are found from K p = p for p =1,x,x 2. Tis gives te coefficients 11 c 3 12 c 2 =. c Te rigt-sided post- We proceed similarly for partially left sided post-processing. processing is a mirror image of te left-sided post-processing.

4 298 J. RYAN AND C.-W. SHU 3. Numerical Examples On te approximation level. To confirm te properties of one-sided postprocessing, we take as an example te L 2 -projection of u(x) =sin(x) onto te piecewise -and -polynomials for x (0, 7π 2 ) and calculate te errors trougout te domain bot before and after post-processing. Te one-sided biased or completely one-sided post-processor is applied near te domain boundaries wen it is necessary, and te usual symmetric post-processing is applied in te interior of te domain wenever possible. In Table 3.1 we can see tat te post-processor does indeed give us te designed (2k+1)-t order accuracy. In fact, te L 2 errors are even alf an order iger tan te designed (2k+1)-t order, due to te fact tat in te interior te symmetric postprocessor is (2k+2)-t order accurate on te approximation level. However, looking at te L errors, we can see tat unless te mes is sufficiently refined it is not advantageous to apply te one-sided post-processor. Tis is a clear indication tat te constant in front of te leading error term 2k+1 is muc larger for te one-sided post-processor tan for te symmetric post-processor. In Figure 3.1 it is illustrated tat near te boundaries, were te one-sided post-processor is applied, te error is larger tan in te interior, were te symmetric post-processor is applied. We also see tat unless te mes is sufficiently refined, it is not advantageous to apply te one-sided post-processor at te domain boundaries. Next we look at te accuracy enancement of te post-processor for te derivatives of te numerical solution. In [15], it is verified tat te symmetric post-processor can improve te order of accuracy for te r-t derivative from k+1-r to 2k+2-r. Tis is also te case for te one-sided post-processor, see Table 3.1 and Figure 3.1. We can see tat, for te derivatives (especially for te second derivative), it is advantageous to do te one-sided post-processing even for coarse meses Domains wit different mes sizes. In [15] we presented te example of a domain wit two different mes sizes. We explored te case of te linear yperbolic equation u t + u x = 0 wit u(x, 0) = sin(3x) forx (0, 2π). Te left alf of te mes contains two-tirds of te elements and te rigt-alf of te domain contains one-tird of te elements as sown in Figure 3.2. Te problem is solved over te entire domain at a final time of T =12.5. In te case of using te symmetric version of te post-processor, we found tat wen we evaluated te solution away from te mes interface we did obtain te expected (2k+1)-t order accuracy in te post-processed solution. However, in te region near te mes interface, tere was contamination in te post-processed solution due to te post-processor taking information from bot sides of te interface, violating te local translation invariance assumption in te post-processing stencil. Here, we present te results of implementing te one-sided biased or completely one-sided form of te post-processor near te mes interface and domain boundary wen necessary. Te symmetric version is used in te interior of te two meses wenever possible. We evaluate te error trougout te entire domain, and not in te individual mes regions as done in [15]. In Table 3.2, we see tat for piecewise -and -polynomials we do indeed obtain te improvement in te order of accuracy to 2k+1 trougout te entire domain, altoug te mes as to be sufficiently refined in order for te one-sided post-processor to sow an effect of reducing te errors near te interface. In Figure 3.3 we can compare te post-processed solution wit te original solution. We can see an apparent improvement in accuracy after te post-processing. Comparing wit te figures in [15] using te symmetric post-processor, we can see tat te one-sided post-processor successfully eliminates a region of O(1) errors near te interfaces of two different mes

5 ONE-SIDED POST-PROCESSING FOR DISCONTINUOUS GALERKIN METHODS 299 Table 3.1 Errors for te L 2 -projection of u(x) =sin(x) onto te piecewise -and -polynomials for x (0, 7π 2 ). Before Post-Processing After Post-Processing mes L 2 error order L error order L 2 error order L error order Errors for u(x) E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E Errors for du(x)/dx E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E Errors for d 2 u(x)/dx 2 20 N/A N/A 3.06E E N/A N/A 3.37E E N/A N/A 5.54E E N/A N/A 1.26E E N/A N/A 3.12E E E E E E E E E E E E E E E E E E sizes. Next, we look at te accuracy enancement of te post-processor for te derivatives of te numerical solution. Te errors and orders of accuracy are listed in Table 3.3. Figure 3.4 plots te errors before and after post-processing for te first and second derivatives in te case. Clearly, we obtain an improvement for te order of accuracy

6 300 J. RYAN AND C.-W. SHU Table 3.2 One dimensional discontinuous Galerkin approximations to te advection equation over a domain wit two different mes sizes as sown in Figure 3.2. Errors calculated over te entire domain. Before post-processing After post-processing mes L 2 error order L error order L 2 error order L error order E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E approximating te r-t derivative from k+1-r to 2k+2-r, and te order of accuracy is uniform trougout te computational domain. Also, for derivatives, te one-sided post-processor improves te accuracy even for coarse meses Discontinuous coefficient yperbolic equations. Te second case we address using te one-sided post-processing tecnique is tat of a linear yperbolic equation wit a discontinuous coefficient were a(x) is piecewise constant, u(x, t) t +(a(x)u(x, t)) x = 0 (3.1) a(x) = { 1, x [ a, a]\( b, b), 1 2, x ( b, b) wit 0 <b<aas given in [15]. Te first example is one wit two stationary socks located at x = ± 1 2 solution. Te initial condition is given by { 2 cos(4πx), x ( 1 u(x, 0) = 2, 1 2 ), cos(2πx), oterwise in [-1,1] for te exact and extended periodically outside [-1,1]. Here a =1andb = 1 2, and te boundary condition is 2-periodic. In [15], wen a symmetric post-processor was used, te errors were calculated 0.4 away from te stationary socks at a final time T =12.5. Here we implement te one-sided version of te post-processing tecnique at te boundaries and te regions near te stationary socks wenever necessary. In Table 3.4 we can see tat te post-processing gives us (2k+1)-t order accuracy trougout te entire domain, including te regions containing te discontinuities. Te errors for te -polynomial case are also plotted in Figure 3.5 in logaritmic scale bot before and after implementing

7 ONE-SIDED POST-PROCESSING FOR DISCONTINUOUS GALERKIN METHODS 301 Table 3.3 One dimensional discontinuous Galerkin approximations to te advection equation over a domain wit two different mes sizes as sown in Figure 3.2. Errors in te first and second derivatives calculated over te entire domain. Before post-processing After post-processing mes L 2 error order L error order L 2 error order L error order First Derivative E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E Second Derivative 20 N/A N/A 3.41E E N/A N/A 5.77E E N/A N/A 9.86E E N/A N/A 1.43E E N/A N/A 2.63E E E E E E E E E E E E E E E E E E E E E E te one-sided form of te post-processor. From Figure 3.5 we can see tat te one-sided post-processor works even near te sock regions. We next consider te more complex situation wen tere are two moving socks in addition to te two stationary socks. Te equation (3.1) is wit a =2,b =1andte initial condition is given by { cos( π u(x, 0) = 2 x), x [ 2, 2]\( 1, 1), 2 3 sin(πx) x ( 1, 1). and extended periodically outside [-2,2]. We use a 4-periodic boundary condition and compute up to te final time T = 1, before te socks cross eac oter. Te two stationary socks are located at cell interfaces, wereas te two moving socks are located inside te cells. In tis example, te discontinuous Galerkin metod as no problem andling te stationary socks, as tey are at cell interfaces. However, te moving socks are located inside te cells and will degenerate te accuracy nearby. In tis case, te errors for te symmetric version of te post-processor were calculated 1.1 away from

8 302 J. RYAN AND C.-W. SHU Table 3.4 Errors for te discontinuous metod applied to te linear yperbolic equation wit discontinuous coefficient wit two stationary socks. Errors calculated over te entire domain. Before post-processing After post-processing mes L 2 error order L error order L 2 error order L error order E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E Table 3.5 Errors for te discontinuous metod applied to te linear yperbolic equation wit a discontinuous coefficient wit two stationary and two moving socks. Errors calculated outside a radius of 0.4 of te moving socks. Before post-processing After post-processing mes L 2 error order L error order L 2 error order L error order E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E te socks in [15]. However, implementing te one-sided post-processor in te region of te discontinuities allows us to calculate te error in a larger region wic includes te stationary socks. Since te discontinuous Galerkin approximation itself does not give good information near te moving socks, we do not expect te accuracy of te post-processor to improve upon tis information, even in te case of implementing te one-sided post-processor. Te errors contained in Table 3.5 sow tat outside a radius of 0.4 of te moving socks, te one-sided post-processed solution improves te accuracy to 2k+1. Te errors for te case are also plotted in Figure 3.6 in logaritmic scale bot before and after post-processing. 4. Concluding Remarks. We ave presented a one-sided version of a local postprocessing tecnique tat enances te accuracy of any approximation wit ig order

9 ONE-SIDED POST-PROCESSING FOR DISCONTINUOUS GALERKIN METHODS 303 negative norm error estimates, wit application to te discontinuous Galerkin solution for linear yperbolic equations. Te one-sided nature of te post-processor allows us to enance te accuracy trougout te entire domain and not just away from te boundaries, discontinuities, or interfaces of different mes sizes. Numerical examples are given to verify suc accuracy enancement capability of te post-processor for te discontinuous Galerkin solution and its derivatives trougout te entire domain for multi-domain problems wit different mes sizes and discontinuous coefficient equations. REFERENCES [1] J.H. Bramble and A.H. Scatz, Higer order local accuracy by averaging in te finite element metod, Matematics of Computation, 31 (1977), pp [2] W. Cai, D. Gottlieb and C.-W. Su, On one-sided filters for spectral Fourier approximations of discontinuous functions, SIAM Journal on Numerical Analysis, 29 (1992), pp [3] B. Cockburn, Discontinuous Galerkin metods for convection-dominated problems, inhig-order Metods for Computational Pysics, T.J. Bart and H. Deconinck, editors, Lecture Notes in Computational Science and Engineering, volume 9, Springer, 1999, pp [4] B. Cockburn, S. Hou and C.-W. Su, Te Runge-Kutta local projection discontinuous Galerkin finite element metod for conservation laws IV: te multidimensional case, Matematics of Computation, 54 (1990), pp [5] B. Cockburn, S.-Y. Lin and C.-W. Su, TVB Runge-Kutta local projection discontinuous Galerkin finite element metod for conservation laws III: one dimensional systems, Journal of Computational Pysics, 84 (1989), pp [6] B. Cockburn, M. Luskin, C.-W. Su and E. Süli, Post-processing of Galerkin metods for yperbolic problems, Proceedings of te International Symposium on Discontinuous Galerkin Metods, Newport, May 1999, G. Karniadakis, B. Cockburn and C.-W. Su, editors, Lecture Notes in Computational Science and Engineering, Springer, 11 (1999), pp [7] B. Cockburn, M. Luskin, C.-W. Su and E. Süli, Enanced accuracy by post-processing for finite element metods for yperbolic equations, Matematics of Computation, 72 (2003), pp [8] B. Cockburn and C.-W. Su, TVB Runge-Kutta local projection discontinuous Galerkin finite element metod for conservation laws II: general framework, Matematics of Computation, 52 (1989), pp [9] B. Cockburn and C.-W. Su, Te Runge-Kutta local projection -discontinuous-galerkin finite element metod for scalar conservation laws, Matematical Modelling and Numerical Analysis (M 2 AN), 25 (1991), pp [10] B. Cockburn and C.-W. Su, Te Runge-Kutta discontinuous Galerkin metod for conservation laws V: multidimensional systems, Journal of Computational Pysics, 141 (1998), pp [11] B. Cockburn and C.-W. Su, Te local discontinuous Galerkin metod for time-dependent convection-diffusion systems, SIAM Journal on Numerical Analysis, 35 (1998), pp [12] B. Cockburn and C.-W. Su, Runge-Kutta Discontinuous Galerkin metods for convectiondominated problems, Journal of Scientific Computing, 16 (2001), pp [13] D. Gottlieb, C.-W. Su, A. Solomonoff and H. Vandeven, On te Gibbs penomenon I: recovering exponential accuracy from te Fourier partial sum of a nonperiodic analytic function, Journal of Computational and Applied Matematics, 43 (1992), pp [14] M.S. Mock and P.D. Lax, Te computation of discontinuous solutions of linear yperbolic equations, Communications on Pure and Applied Matematics, 31 (1978), pp [15] J. Ryan, C.-W. Su and H.L. Atkins, Extension of a post-processing tecnique for te discontinuous Galerkin metod for yperbolic equations wit application to an aeroacoustic problem, submitted to SIAM Journal on Scientific Computing. [16] C.-W. Su and S. Oser, Efficient implementation of essentially non-oscillatory sock-capturing scemes, Journal of Computational Pysics, 77 (1988), pp [17] J. Yan and C.-W. Su, Local discontinuous Galerkin metods for partial differential equations wit iger order derivatives, Journal of Scientific Computing, 17 (2002), pp

10 304 J. RYAN AND C.-W. SHU : u-u before post-processing : u-u after post-processing : d/dx(u-u ) before post-processing : d/dx(u-u ) after post-processing : d 2 /dx 2 (u-u ) before post-processing : d 2 /dx 2 (u-u ) after post-processing Fig Pointwise errors in logaritmic scale wen an L 2 -projection onto te piecewise polynomials is done. Left: before post-processing. Rigt: after post-processing. Top: for te function; middle: for te first derivative; bottom: for te second derivative.

11 ONE-SIDED POST-PROCESSING FOR DISCONTINUOUS GALERKIN METHODS 305 Domain 1: N 1 =[2N/3] Domain 2: N 2 = N-N Time x Fig Mes structure for solving te linear advection equation. Te left alf of te domain contains approximately two-tirds of te elements; te rigt contains approximately one-tird of te elements : Before Post-Processing 10 1 : After Post-Processing, using one-sided version Fig Pointwise errors in logaritmic scale wen te discontinuous Galerkin metod is used to solve te linear advection equation over a domain wit two different mes sizes as sown in Figure 3.2. Left: before post-processing. Rigt: after post-processing. Te graps are scaled te same.

12 306 J. RYAN AND C.-W. SHU : d/dx(u-u ) before post-processing : d/dx(u-u ) after post-processing : d 2 /dx 2 (u-u ) before post-processing : d 2 /dx 2 (u-u ) after post-processing Fig Pointwise errors in te first and second derivatives in logaritmic scale wen te discontinuous Galerkin metod is used to solve te linear advection equation over a domain wit two different mes sizes as sown in Figure 3.2. Left: before post-processing. Rigt: after post-processing. Top: first derivative; bottom: second derivative. : Before Post-Processing : After Post-Processing, using one-sided version Fig Pointwise errors in logaritmic scale wen te discontinuous Galerkin metod is used to solve te discontinuous coefficient equation wit two stationary socks. Left: before post-processing. Rigt: after post-processing.

13 ONE-SIDED POST-PROCESSING FOR DISCONTINUOUS GALERKIN METHODS 307 : Before Post-Processing : After Post-Processing, using one-sided version Fig Pointwise errors in logaritmic scale wen te discontinuous Galerkin metod is used to solve te discontinuous coefficient equation wit two stationary socks and two moving socks. Left: before post-processing. Rigt: after post-processing.

14 308 J. RYAN AND C.-W. SHU