# Analysis of Two-Grid Characteristic Finite Element Methods for Convection-Diffusion Equations

Authors: Keyan Wang; Boxia Hu
Journal: Journal of Mathematics
 (2023)

---

## Abstract

In this paper, two efficient two-grid algorithms for the convection-diffusion problem with a modified characteristic finite element method are studied. We present an optimal error estimate inLp-norm for the characteristic finite element method unconditionally, while all previous works require certain time-step restrictions. To linearize the characteristic method equations, two-grid algorithms based on the Newton iteration approach and the correction method are applied. The error estimate and the convergence result of the two-grid method are derived in detail. It is shown that the coarse space can be extremely coarse and achieve asymptotically optimal approximations as long as the mesh sizes H=Oh1/3 in the first algorithm and H=Oh1/4 in the second algorithm, respectively. Finally, two numerical examples are presented to demonstrate the theoretical analysis.


---

## Body

## 1. Introduction

In this paper, we consider the following convection-diffusion equations:(1)ut+b⋅∇u−∇⋅ax∇u=fu,x,t∈Ω×J,(2)ux,t=0,x,t∈∂Ω×J,(3)ux,0=u0,x∈Ω,where Ω is a bounded polygonal domain in ℝ2 with boundary ∂Ω, J=0,T, T>0 is some final time, x=x1,x2T, ut=∂u/∂t, f⋅ is a twice continuously differentiable function with bounded derivatives through the third order, u0 is a given function, ax is the diffusion coefficient, and b is the convection field. To state some results about the convergence of the present method, we assume the following conditions:(i)
The functionfu satisfies the Lipschitz continuous condition about u.(ii)
We assume that the coefficientax is bounded above and below by positive constants:(4)a∗≤ax≤a∗.(iii)
We also assume that the coefficientb=bx=b1x,b2xT is bounded, and we obtain(5)b=b12+b22≤K1,bx+∂bx∂xi≤K2,whereK1 and K2 are the positive constants.Convection-diffusion problems have been investigated extensively due to their wide applications in various fields of sciences and technologies, such as solutes in moving fluids and transport problems of heat [1–12]. In these areas, numerical solutions of problems (1)–(3) play a key role. A number of numerical methods have been developed for the simulation of convection-diffusion equations, including finite element methods [3, 4], finite volume methods [5], characteristic methods [6–8], multilevel adaptive particle methods [9], variational multiscale method [10], and discontinuous Galerkin method [11]. One of the most popular methods is the characteristic finite element method (CFEM) [6]. The characteristic method is a combination of a characteristic approximation to handle the convection part in time and a finite element spatial approximation to deal with the diffusion part. Compared with the standard finite element method, the CFEM has a much smaller time truncation error, because the solution of the above method changes more slowly in the characteristic τ direction than in the t direction. Thus, this method will allow one to use a large time step in practical computations. In the past several decades, many authors have contributed to developing, analyzing, and applying CFEM (see [13–16]).As we know, the two-grid method is a highly efficient and accurate method, which was first formulated for nonsymmetric linear and nonlinear elliptic problems by Xu [17, 18]. Due to the better practical performance, the two-grid method was applied and investigated for other types of problems by many authors (see [12, 19–25]). Among them, Bi and Ginting [19] have given the two-grid discontinuous Galerkin method for a quasi-linear elliptic problem, Li and Tan [20] have used the two-grid method for nonlinear hyperbolic equations, Dawson and Wheeler [21] have used two-grid mixed finite element methods for nonlinear parabolic equations, and Chen et al. [22, 23] have considered the two-grid method for nonlinear reaction-diffusion equations by the expanded mixed finite element method. In particular, Qin and Ma [12] have constructed and analysed a two-step algorithm by using a two-grid idea for the characteristic finite element solution of nonlinear convection-diffusion equations. Recently, we have proposed the two-grid algorithms based on the mixed finite element approximation for nonlinear hyperbolic equations [24] and studied the unconditional error estimates of two-gird finite element methods for parabolic integrodifferential equations [25]. In the abovementioned works, the theoretical study and numerical experiments show that the two-grid technique is computationally more efficient than the original method.In this paper, we propose two efficient algorithms of the two-grid method for the approximation of semilinear convection-diffusion equations (1)–(3) by using CFEM and present a new analysis to obtain unconditionally optimal error estimates. The analysis is based on a temporal-spatial error splitting technique [26], with which the error function is split into two parts (temporal error and spatial error) by introducing a new characteristic time-discrete system. The previous analyses required certain time-step conditions to obtain optimal error estimates. For example, a two-scale product approximation for the semilinear parabolic problem with the mixed finite element method was analysed, and optimal error estimates were obtained under the condition Δt=Oh [27]. The restriction Δt=Oh2 was also required for the Galerkin alternating-direction method for a kind of three-dimensional nonlinear hyperbolic problem [28]. However, the certain restriction conditions between spatial mesh size and temporal step size are not necessary and can be removed. Our results show clearly that the characteristic temporal discrete scheme is effective, and the time-step conditions in previous analyses were required mainly due to the error estimate of quadratic terms arising from linearization by using the inverse inequality. Moreover, compared with [12], the feature of our algorithms mainly lies in step 3 where a further coarse/fine grid correction is performed. It is of great theoretical interest that a further coarse/fine grid correction after the fine grid correction can actually improve the accuracy. A remarkable fact about this simple approach is, as shown in [17, 18], that the coarse mesh can be quite coarse and still maintain a good accuracy approximation.The paper is organized as follows: In Section2, we introduce some notations and approximation results that are used throughout the paper and construct the CFEM for (1)–(3). In Section 3, by using the splitting technique, we analyze the temporal and spatial errors, respectively, and prove the optimal error estimate of CFEM in Lp-norm unconditionally. In Section 4, we present the two-grid algorithms and analyze their error estimates. In Section 5, the numerical results are given to confirm our theoretical analysis. Finally, some conclusions and further works are presented in the last section.


## 2. CFEM for the Convection-Diffusion Equations

LetWm,pΩ be the standard Sobolev space (see [29] for details). The norm of ϕ∈Wm,pΩ is denoted by ϕm,pp=∑κ≤mDκϕLpΩp, for 1≤p<∞ and ϕm,∞=maxκ≤messsupDκϕ, for p=∞. We set HmΩ=Wm,2Ω with norm ⋅m=⋅m,2 (the notation ⋅=⋅0,2) and ⋅∞=⋅L∞. In addition, let C denote a generic positive constant that does not depend on the spatial mesh and temporal discretization parameters.LetTh be a quasi-uniform family of finite element partitions of Ω, where h is the maximal element diameter. Let Vh be the piecewise continuous finite element spaces and Vh0=v∈Vh,v|∂Ω=0.Let(6)ψx=1+bx2,and let the characteristic direction associated with the operator ∂u/∂t+b⋅∇u be denoted by τ=τx, where(7)∂∂τ=1ψx∂∂t+bx⋅∇.Then, problem (1)–(3) can be written in the equivalent form as follows:(8)ψx∂u∂τ−∇⋅ax∇u=fu,x,t∈Ω×J,(9)ux,t=0,x,t∈∂Ω×J,(10)ux,0=u0,x∈Ω.Lettnn=0N be a uniform partition in the time direction with the time step Δt=T/N. For a sequence of functions unn=0N, we denote(11)∂tun=un−un−1Δt.The characteristic derivative is approximated in the following way att=tn:(12)ψx∂un∂τ≈ψxux,tn−ux¯,tn−1x−x¯2+Δt2=ux,tn−ux¯,tn−1Δt.That is, a backtracking algorithm is used to approximate the characteristic derivative.x¯=x−bxΔt is the foot (at level tn−1) of the characteristic corresponding to x at the head (at level tn) (see Figure 1).Figure 1
The direction of characteristics.The fully discrete CFEM for (1)–(3) is defined. For n=1,2,…,N, we seek uhn∈Vh0 such that(13)uhn−u¯hn−1Δt,vh+ax∇uhn,∇vh=fuhn,vh,∀vh∈Vh0,uh0=Ihu0,where un=ux,tn, u¯n−1=ux¯,tn−1=ux−bxΔt,tn−1, and Ih is the Lagrange interpolation operator over Vh0. Hence, it can be seen in [30, 31] that if u∈H3Ω, there holds(14)∇u−Ihu,∇v≤Ch2u3∇v,∀v∈Vh0.In this paper, we assume that the initial boundary value problem (1)–(3) admits a unique solution as follows:(15)u02+uL∞J;H2Ω∩W2,4Ω+utL∞J;H2Ω+uttL∞J;L2Ω≤C.LetRh≔H01Ω⟶Vh0 denote the Ritz projection that satisfies(16)∇u−Rhu,∇v=0,∀v∈Vh0.Then, the following estimates hold [32] for 2≤p<∞ and ∀u∈W2,pΩ:(17)u−Rhu0,p+hu−Rhu1,p≤Ch2u2,p,(18)u−Rhut0,p+hu−Rhut1,p≤Ch2ut2,p.The discrete Gronwall’s lemma [33] is recalled.Lemma 1.
Assume thatkn is a non-negative sequence and that the sequence ψ¯n satisfies(19)ψ¯0≤g0,ψ¯n≤g0+∑s=0n−1Ps+∑s=0n−1ksψ¯s,n≥1.Then,ψ¯n also satisfies(20)ψ¯1≤g01+k0+p0,ψ¯n≤g0+∏s=0n−11+ks+∑s=0n−2ps∏r=s+1n−11+kr+pn−1,n≥2.Moreover, ifg0≥0 and pn≥0 for n≥0, it follows that(21)ψ¯n≤g0+∑s=0n−1Psexp∑s=0n−1ks,n≥1.


## 3. Unconditional Error Estimate for the CFEM Solution

In this section, we provide a primary error estimate for the CFEM (13) unconditionally by the Li–Sun error splitting technique [26]. For n=1,…,N, we introduce a characteristic time-discrete system as follows:(22)Un−U¯n−1Δt−∇⋅ax∇Un=fUn,inΩ,(23)Un=0,on∂Ω,(24)U0=u0,inΩ.For convenience, we split the error into the following manner:(25)un−uhn=un−Un+Un−RhUn+RhUn−uhn≔=en+αn+βn.Now, we start to prove the regularity and error estimation of the solution of the above time-discrete system.Theorem 1.
Suppose that the time-discrete system (22)–(24) has a unique solution Un. Then, for 2≤n≤N and 2≤p<∞, we have(26)Un2+Δt∑n=1ℓ∂tUn22≤C,en1+Δt1/2∑n=1ℓen2+∂ten≤CΔt.Proof.
On levelt=tn, we rewrite (8) as(27)un−u¯n−1Δt−∇⋅ax∇un=fun+un−u¯n−1Δt−ψ∂un∂τ.
From (8) and (22), we observe that the error function en satisfies the following equation:(28)∂ten−∇⋅ax∇en=fun−fUn+un−u¯n−1Δt−ψ∂un∂τ+en−1−e¯n−1Δt.
We multiply both sides of (28) by ∂ten to get(29)∂ten,∂ten+ax∇en,∇∂ten=fun−fUn,∂ten+un−u¯n−1Δt−ψ∂un∂τ,∂ten+en−1−e¯n−1Δt,∂ten≔=∑i=13Li.
Obviously, we have the following equality:(30)ax∇en,∇∂ten≥a∗2Δt∇en2−∇en−12+∇en−∇en−12.
First, we estimate the left-hand side of (29), and it is easy to derive that(31)∂ten,∂ten+ax∇en,∇∂ten≥∂ten2+a∗2Δt∇en2−∇en−12.
Now, we estimate the right-hand side terms of (29). For L1, using the Cauchy–Schwarz inequality and ϵ-Cauchy inequality, we obtain(32)L1=fun−fUn,∂ten≤Cen⋅∂ten≤Cen12+ϵ∂ten2,for any small constant ϵ>0. For L2, with the result in [6], we have(33)un−u¯n−1Δt−ψ∂un∂τ2≤CΔt∫tn−1tn∫Ω∂2u∂τ22dxdt≤CΔt∂2u∂τ2L2tn−1,tn;L2Ω2,and therefore,(34)L2=un−u¯n−1Δt−ψ∂un∂τ,∂ten≤CΔt∂2u∂τ2L2tn−1,tn;L2Ω2+ϵ∂ten2.
In the inequality, by using the result by Russell (see Theorem1 in [13]), L3 can be bounded by(35)L3=en−1−e¯n−1Δt,∂ten≤C∇en−1⋅∂ten≤Cen−112+ϵ∂ten2.
Choosing properϵ and using the equivalence of ⋅1 and ⋅, inequalities (31)–(34) can be combined with (29) to get(36)∂ten2+a∗2Δten12−en−112≤Cen−112+en12+Δt∂2u∂τ2L2tn−1,tn;L2Ω.
Note thate0=0. If we multiply (36) by 2Δt, sum for n=1,2,…,ℓ1≤ℓ≤N, and apply the discrete Gronwall’s lemma, it follows that(37)eℓ12+Δt∑n=1ℓ∂ten2≤CΔt2.
On the other hand, we multiply (28) by −∇⋅ax∇en to get(38)∇∂ten,ax∇en+∇⋅ax∇en2=fun−fUn,−∇⋅ax∇en+un−u¯n−1Δt−ψ∂un∂τ,−∇⋅ax∇en+en−1−e¯n−1Δt,−∇⋅ax∇en.
Similarly to the proof of (36), we see that(39)a∗2Δten12−en−112+∇⋅ax∇en2≤Cen12+en−112+Δt∂2u∂τ2L2tn−1,tn;L2Ω.
Multiplying (39) by 2Δt, summing for n=1,2,…,ℓ1≤ℓ≤N, noting that e0=0, and applying the discrete Gronwall’s lemma, we get(40)eℓ12+Δt∑n=1ℓen22≤CΔt2,where we have used the result en2≤CΔen (see [34, 35]). It follows from (37) and (40) that(41)eℓ12+Δt∑n=1ℓen22+∂ten2≤CΔt2.
In particular, by (15) and (41), we further derive that(42)Un2≤en2+un2≤CΔt1/2+un2≤C,Δt∑n=1ℓ∂tUn22≤CΔt∑n=1ℓ∂ten22+Δt∑n=1ℓ∂tun22≤C1Δt∑n=1ℓen22+Δt∑n=1ℓ1Δt∫tn−1tnutnds22≤C.
The proof of Theorem1 is complete.Remark 1.
Based on the result of Theorem1, we use the Sobolev embedding inequality to get(43)en0,p≤Cen1≤CΔt,where 1≤p<∞.
In the following, the unconditional convergence result is deduced through the analysis of the spatial error.Theorem 2.
LetUn be the solution of (22) and uhn be the fully discrete solution of (13). Then, for 1≤n≤N and 2≤p<∞, we have(44)Un−uhn0,p≤Ch2.Proof.
We rewrite the time-discrete system (22)–(24) in a weak form by(45)Un−U¯n−1Δt,vh+ax∇Un,∇vh=fUn,vh,∀vh∈Vh0.
From (13) and (45), we see that the error function βn satisfies the equation as follows:(46)∂tβn,vh+ax∇βn,∇vh=fUn−fuhn,vh−∂tαn,vh−αn−1−α¯n−1Δt,vh−βn−1−β¯n−1Δt,vh≔=∑i=14Ki,for vh∈Vh0. Substituting vh=∂tβn into (46), the following estimate holds for the left-hand terms of (46):(47)∂tβn,∂tβn+ax∇βn,∇∂tβn≥∂tβn2+a∗2Δtβn12−βn−112.
The terms of the right-hand side of (46) are estimated by(48)K1≤Cαn+βn∂tβn≤Cαn2+Cβn2+2ϵ∂tβn2,K2≤C1Δt∫tn−1tnutdt⋅∂tβn≤C1ΔtutL2tn−1,tn;L2Ω2+ϵ∂tβn2,K3≤C∇αn−1⋅∂tβn≤C∇αn−12+ϵ∂tβn2,K4≤C∇βn−1⋅∂tβn≤C∇βn−12+ϵ∂tβn2.
Combining the estimates above, we can bound (46) as(49)∂tβn2+a∗2Δtβn12−βn−112≤Cαn2+βn2+1ΔtutL2tn−1,tn;L2Ω2+∇αn−12+∇βn−12+5ϵ∂tβn2.
Multiplying both sides of the above equation by2Δt and summing for n from 1 to ℓ, for 1≤ℓ≤N, since β01≤Ch, we see that(50)βℓ12+Δt∑n=1ℓ∂tβn2≤Ch2+CΔt∑n=1ℓβn12+utL20,T;L2Ω2≤Ch2+CΔt∑n=1ℓβn12.Here, ϵ is sufficiently small, and we have used (17) and (18). It follows the discrete Gronwall’s lemma that(51)βn1≤Ch.
If2≤p<∞, by (51), and similar to the proof of Theorem 3.4 in [18], we can obtain(52)βn1,p≤Ch.
We define the elliptic operatorℒ as(53)ℒ=∇⋅ax∇uhn.
Obviously,ℒ≔H01Ω⟶H−1Ω is isomorphism. Corresponding to ℒ, we define a bilinear form, for uh,vh∈H01Ω, as(54)Auhn,vh=∫Ωax∇uhn⋅∇vhdx.
To prove (44), we use a duality argument by considering the auxiliary problem. We find ϖ∈H01Ω so that(55)Av,ϖ=φ,v,v∈H01Ω.
Given2≤p<∞, let q=p/p−1∈1,2. It is uniquely solvable for ϖ∈LqΩ and has the following regularity (Grisvard [36]):(56)ϖ2,q≤φ0,q,for φ∈LqΩ. If s>2p/p+2, it follows from the Sobolev embedding theorem that(57)Rhϖ1,s/s−1≤Cϖ1,s/s−1≤Cϖ2,q≤Cφ0,q.
Therefore, withs>2p/p+2, by Lemma 3.1 of Xu [18], we obtain(58)RhUn−uhn,φ=ARhUn−uhn,ϖ=ARhUn−uhn,ϖ−Rhϖ+ARhUn−uhn,Rhϖ=ARhUn−uhn,ϖ−Rhϖ+ARhUn−uhn,Rhϖ≤CRhUn−uhn1,pϖ−Rhϖ1,q+RhUn−uhn1,2s2Rhϖ1,s/s−1≤ChRhUn−uhn1,p+RhUn−uhn1,2s2φ0,q.
Consequently, we obtain(59)RhUn−uhn0,p≤ChRhUn−uhn1,p+RhUn−uhn1,2s2.
Forp=2, if Un∈H2Ω, then(60)RhUn−uhn≤ChRhUn−uhn1,2+RhUn−uhn1,2+ϵ2≤Ch2.
For2<p<∞, note that 4p/p+2<p, and we deduce that(61)RhUn−uhn0,p≤ChRhUn−uhn1,p+RhUn−uhn1,p2≤Ch2.
The desired result (44) can be derived by using the triangle inequality, (17), (60), and (61).
Therefore, we combine (17) with the results in Remark 1 and Theorem 2 to obtain the following theorem.Theorem 3.
Suppose that (15) holds. Let un and uhn be the solutions of (1)–(3) and (13) at t=tn, respectively. Then, for 1≤n≤N and 2≤p<∞, we have(62)un−uhn0,p≤Ch2+Δt.


## 4. Two-Grid Algorithms and Error Estimates

In this section, we propose two two-grid algorithms for (1)–(3) based on two finite element spaces. The basic ingredient in our approach is another finite element space VH0⊂Vh0⊂H01Ω defined on a coarser quasi-uniform triangulation (with mesh size h<H<1) of Ω. Let us now present our first two-grid algorithm.Algorithm 1: Correction on the coarse grid.
Step 1: On the coarse gridTH, for n=1,…,N, we find uHn∈VH0 and solve the following nonlinear system: uHn−u¯Hn−1/Δt,vH+ax∇uHn,∇vH=fuHn,vH,∀vH∈VH0,uH0=IHu0.Step 2: On the fine gridTh, for n=1,2,…,N, given uHn, we find Uhn∈Vh0 to satisfy the following linear system: Uhn−U¯hn−1/Δt,vh+ax∇Uhn,∇vh=fuHn+f′uHnUhn−uHn,vh,∀vh∈Vh0,Uh0=Ihu0.Step 3: On the coarse gridTH, for n=1,2,…,N, given uHn and Uhn, we find Uhn=Uhn+dHn∈Vh0 to satisfy the following linear system: dHn−d¯Hn−1/Δt,vH+ax∇dHn,∇vH=f′uHndHn+1/2f′′uHnUhn−uHn2,vH,∀vH∈VH0,Uh0=Ihu0.In the following analysis, we first introduce the following lemma [6].Lemma 2.
Letω∈L2Ω, ω¯=ωx−gxΔt, and g and g′ be bounded functions on Ω¯. If the time step Δt is sufficiently small, then there exists a positive integer K such that(63)ω−ω¯−1≤KωΔt,where K is only dependent on gL∞ and g′L∞, and the norm of ⋅−1 is defined as follows:(64)ϕ−1=supv∈H1Ω/0ϕ,vv1.Next, we need to proveun−Uhn0,p.Lemma 3.
Ifun be the solution of (27) and uhn be the solution of Algorithm 1, then(65)un−Uhn0,p≤Ch2+H4+Δt,for 1≤n≤N and 2≤p<∞.Proof.
We setun−Uhn=un−Rhun+Rhun−Uhn≔=γn+δn. From (27) and Algorithm 1, it is easy to derive the following equation:(66)∂tδn,vh+ax∇δn,∇vh=un−u¯n−1Δt−ψ∂un∂τ,vh−γn−γ¯n−1Δt,vh+δ¯n−1−δn−1Δt,vh+f′uHnun−Uhn,vh+12f′′θun−uHn2,vh≔∑j=15Aj,∀vh∈Vh0,where we employ the Taylor expansion fun=fuHn+f′uHnun−uHn+1/2f′′θ1un−uHn2, f′′θ1 means that f′′u is evaluated at a point θ1 between un and uHn. By taking vh=∂tδn in (66), then the left-hand side of (66) becomes(67)∂tδn,∂tδn+ax∇δn,∇∂tδn≥a∗2Δt∇δn2−∇δn−12+∂tδn2.
In the inequality, the estimates ofA1–A3 can be obtained similarly as in the proof of Theorem 2:(68)A1≤CΔt2+C∂tδn2,A2≤C∇γn−1⋅∂tβn≤Ch2+C∂tδn2,A3≤C∇δn−1⋅∂tδn≤C∇δn−12+C∂tδn2.
By (17), we estimate for A4 as follows:(69)A4≤Cγn+δn∂tδn≤Ch4+δn2+∂tδn2.
With the estimate (62) for un−uHn0,4, we have(70)A5≤Cun−uHn0,42∂tδn≤CH8+Δt4+∂tδn2.
It follows from (66)–(70) that(71)a∗2Δt∇δn2−∇δn−12+∂tδn2≤Ch2+H8+Δt2+∇δn−12+δn2+∂tδn2.
Noting thatδ01=Rhu0−Ihu01≤Rhu0−u01+u0−Ihu01≤Ch. Multiplying (71) by 2Δt and summing for n=1,2,…,ℓ1≤ℓ≤N, we see that(72)δℓ12+Δt∑n=1ℓ∂tδn2≤Ch2+H8+Δt2+CΔt∑n=0ℓ∂tδn2.
Applying the discrete Gronwall’s lemma, we get(73)δn12≤Ch2+H8+Δt2.
Similarly, as in Theorem2, we have(74)δn0,p≤Ch2+H4+Δt,for 2≤p<∞. Thus, (65) follows from (17) and (74), and the inequality is obtained as follows:(75)un−Uhn0,p≤un−Rhun0,p+Rhun−Uhn0,p≤Ch2+H4+Δt.
Now, we give the error estimate for two-grid Algorithm1.Theorem 4.
AssumeUhn∈Vh0 is obtained by Algorithm 1, and then, for 1≤n≤N, we have(76)un−Uhn≤Ch2+H6+Δt.Proof.
Letun−Uhn=un−Rhun+Rhun−Uhn≔=γn+ζn. From (27), Algorithm 1, and (16), we see that(77)∂tζn,vh+ax∇ζn,∇vh=un−u¯n−1Δt−ψ∂un∂τ,vh−γn−γ¯n−1Δt,vh+ζ¯n−1−ζn−1Δt,vh+F1,vh,∀vh∈Vh0,where F1=fun−fuHn−f′uHnUhn−uHn−1/2f′′uHnUhn−uHn2. For the last term of the right-hand side of (77), a Taylor expansion of fun about uHn yields(78)fun=fuHn+f′uHnun−uHn+12f′′uHnun−uHn2+16f′′′θ2un−uHn3,for some function θ2 between un and uHn. Then,(79)F1=f′uHnun−Uhn−12f′′uHnun−Uhnun−uHn+Uhn−uHn+16f′′′θ2un−uHn3.
We rewrite (77) as follows:(80)∂tζn,vh+ax∇ζn,∇vh=un−u¯n−1Δt−ψ∂un∂τ,vh−γn−γ¯n−1Δt,vh+ζ¯n−1−ζn−1Δt,vh+f′uHnun−Uhn,vh+12f′′uHnun−Uhnun−uHn+Uhn−uHn,vh+16f′′′u∗un−uHn3,vh≔∑j=16Tj,for vh∈Vh0. Choosing vh=ζn, it is not difficult to get(81)∂tζn,ζn+ax∇ζn,∇ζn≥12Δtζn2−ζn−12+a∗∇ζn2.
Now, we estimate the terms of the right-hand side in (80), respectively. For T1, we have(82)T1≤CΔt2+ζn2.
ForT2 and T3, by Lemma 2 and (17), we get(83)T2≤Cγn−γ¯n−1Δt−1ζn1≤Cγn−12+ζn12≤Ch4+ζn12,T3≤Cζ¯n−1−ζn−1Δt−1ζn1≤Cζn−12+ζn12.
ForT4–T6, using (17), (62), and (65), we derive that(84)T4=f′uHnun−Rhun+Rhun−Uhn,ζn≤Ch4+ζn2,T5≤Cun−Uhn0,4un−uHn0,4+Uhn−uHn0,4ζn≤CΔt2+h4+H12+ζn2,T6≤Cun−uHn0,63ζn≤CH12+ζn2.
Then, substituting (81)–(84) into (80) yields(85)12Δtζn2−ζn−12+a∗ζn12≤Ch4+H12+Δt2+ζn−12+ζn2+ζn12.
Multiplying2Δt and summing for n from 1 to ℓ1≤ℓ≤N at both sides of (85), since ζ0=Rhu0−Ihu0≤Rhu0−u0+u0−Ihu0≤Ch2, it follows from the discrete Gronwall’s lemma that(86)ζℓ2+Δt∑i=1ℓζn12≤Ch4+H12+Δt2.
By (17) and (86), we deduce that(87)un−Uhn≤un−Rhun+Rhun−Uhn≤Ch2+H6+Δt.
Thus, the estimate (76) is proved.
We notice that Algorithm1 involves only one Newton iteration on the fine grid. Furthermore, we construct the following three-step algorithm. In this algorithm, a more dramatic result can be derived if one more Newton iteration is performed on the fine grid.Theorem 5.
LetUhn be the solution obtained by Algorithm 2. For 1≤n≤N, we have(88)un−Uhn≤Ch2+H8+Δt.Algorithm 2: Correction on the fine grid.
Steps 1 and 2: The same as in Algorithm1.Step 3: On the fine gridTh, for n=1,2,…,N, given Uhn, we find Uhn∈Vh0 to satisfy the following linear system: Uhn−U¯hn−1/Δt,vh+ax∇Uhn,∇vh=fUhn+f′UhnUhn−Uhn,vh,∀vh∈Vh0,Uh0=Ihu0.Proof.
A Taylor expansion offun about Uhn yields(89)fun=fUhn+f′Uhnun−Uhn+12f′′θ3un−Uhn2,where θ3 is some value between un and Uhn. Let un−Uhn=un−Rhun+Rhun−Uhn≔=γn+ξn. By (27), Algorithm 2, and (89), we get the error equation as follows:(90)∂tξn,vh+ax∇ξn,∇vh=un−u¯n−1Δt−ψ∂un∂τ,vh−γn−γ¯n−1Δt,vh+ξ¯n−1−ξn−1Δt,vh+f′Uhnun−Uhn,vh+12f′′θ3un−Uhn2,vh≔∑j=15Bj,for vh∈Vh0. Taking vh=ξn in (90), similar to the estimates of (81)–(84), we have(91)∂tξn,ξn+ax∇ξn,∇ξn≥12Δtξn2−ξn−12+a∗∇ξn2,B1≤CΔt2+ξn2,B2≤Cγn−γ¯n−1Δt−1ξn1≤Cγn−12+ξn12≤Ch4+ξn12,B3≤Cξ¯n−1−ξn−1Δt−1ξn1≤Cξn−12+ξn12,B4=f′Uhnun−Rhun+Rhun−Uhn,ξn≤Ch4+ξn2,B5≤Cun−Uhn0,42ξn≤Ch4+H16+Δt2+ξn2.
Combining these estimates with (90), we get(92)12Δtξn2−ξn−12+a∗ξn12≤Ch4+H16+Δt2+ξn−12+ξn2+ξn12.
Noting thatξ0≤Ch2, multiplying 2Δt on both sides of (92), summing for n=1,2,…,ℓ1≤ℓ≤N, and using the discrete Gronwall’s lemma, we derive that(93)ξℓ2+Δt∑i=1ℓξn12≤Ch4+H16+Δt2.
Consequently, the theorem can be derived with (17) and (93) and the triangle inequality.


## 5. Numerical Experiments

In this section, we present some numerical experiments to illustrate the theoretical results discussed in the previous sections and to show the effectiveness of the two-grid method.LetH and h be the space steps of the coarse grid and the fine grid, respectively. The rates of convergence with respect to the mesh size h are computed as(94)logEi/Ei+1loghi/hi+1,where Ei and Ei+1 are the errors corresponding to hi and hi+1, respectivelyAll experiments were performed on Windows 7 (64 bit) PC-Intel (R) Core (TM) i5-7500k CPU 3.40 GHz, 8 GB of RAM using MATLAB R2012b.Example 1.
We consider the following convection-diffusion equations:(95)ut+b⋅∇u−∇⋅ax∇u=−3u2+gx,t,x,t∈Ω×J,ux,t=0,x,t∈∂Ω×J,ux,0=u0,x∈Ω,where x=x1,x2T, Ω=0,12, J=0,1, b=1,1T, and ax=0.01, the initial condition u0, and gx,t are chosen according to the exact solution ux,t=4e−2tsin2πx1sin2πx2.
The domainΩ is uniformly divided into two families TH and Th of triangular elements. To confirm our theoretical analysis, we choose τ=1/50. The numerical results of Algorithm 1 and CFEM are listed in Table 1 at t=1, from which we can see clearly that the two methods have the same accuracy, but the two-grid method can save more time than the CFEM. This phenomenon shows that the two-grid algorithm is a very effective algorithm when it comes to dealing with nonlinear problems. We also see that the convergence rates for un−uhn and un−Uhn in the L2-norm can reach the second-order, which are in agreement with our theoretical results presented in Sections 3 and 4. Moreover, the numerical results of two-steptwo-grid method Algorithm 1and CFEM are shown in Table 2. Clearly, we see that the three-step method was more efficient than the two-step method, as the scale of nonlinear equations of the three-step format is much smaller. For the time parameter t=1, we show the graphs of the exact solution u and the numerical solution Uh based on the two-grid characteristic finite element algorithm with H,h=1/4,1/64, as shown in Figure 2. We see that the two-grid solution is almost the same as the exact solution.Table 1
Numerical results of Algorithm1 and CFEM.
Algorithm1CFEMH,hun−UhnComputing time (s)hun−uhnComputing time (s)1/2,1/81.9518e − 31.281/81.7156e − 31.591/4,1/642.9224e − 525.161/642.6173e − 594.211/6,1/2162.6236e − 6118.351/2162.3352e − 6645.66Rate2Rate2Table 2
Numerical results of two-steptwo-grid method Algorithm1 and CFEM.
Two-steptwo-grid method Algorithm1CFEMH,hun−UhnComputing time (s)hun−uhnComputing time (s)1/2,1/46.9703e − 30.851/46.8595e − 30.701/4,1/164.4452e − 42.681/164.3657e − 44.531/8,1/642.8049e − 533.471/642.6173e − 594.211/16,1/2561.8001e − 6252.491/2561.6499e − 6896.04Rate2Rate2Figure 2
(a) The exact solutionu. (b) The numerical solution Uh by Algorithm 1.
(a)(b)Example 2.
We consider the following convection-diffusion problem:(96)ut+b⋅∇u−∇⋅ax∇u=u3−u,x,t∈Ω×J,ux,t=0,x,t∈∂Ω×J,ux,0=u0,x∈Ω.
In this example, the exact solution is unknown.U∗ is the reference solution. In order to show the convergence order, we choose(97)H,h=12,116,14,132,14,164,14,1256.
For simplicity, we setΩ=0,12, J=0,1, b=0.1,0.1T, and ax=1. The numerical results of Algorithm 2 and CFEM are shown in Table 3. As seen from Table 3, the numerical results show the second-order accuracy of Algorithm 2 and CFEM as proved in Theorem 5 and Theorem 3. In addition, we can find that the two methods have the same accuracy, but the two-grid method has much less cost time than the CFEM, since we just have to solve small-scale nonlinear systems.Table 3
Numerical results of Algorithm2 and CFEM.
Algorithm2CFEMH,hU∗n−UhnComputing time (s)hU∗n−uhnComputing time (s)1/2,1/162.4247e − 41.611/162.3566e − 43.171/4,1/326.2186e − 54.831/326.0079e − 515.081/4,1/641.6094e − 527.421/641.5195e − 590.761/4,1/2564.1397e − 6122.541/2563.8730e − 6584.91Rate2Rate2


## 6. Conclusions

In this paper, we have established unconditionally optimal error estimates of the two-grid CFEM for convection-diffusion equations in a two-dimensional space. Our algorithms involve the following three steps: (1) solving a small fully discrete nonlinear problem to obtain a rough solution on the coarse grid, (2) solving a linearized problem based on the rough solution to produce a corrected solution on the fine grid, and (3) performing a further coarse/fine grid correction. It is shown theoretically and numerically that coarse space can be extremely coarse and preserve asymptotically optimal estimates for the CFEM discretization error as long as the mesh size satisfiesH=Oh1/3 in Algorithm 1 and H=Oh1/4 in Algorithm 2, respectively. As a result, we can save a lot of computational cost for calculating nonlinear convection-diffusion equations. In future work, we shall extend the proposed efficient two-grid methods for nonlinear convection-diffusion equations to solve other complicated problems, such as variable-order nonlinear convection-diffusion equations [37]. Furthermore, inspired by [26, 38, 39], it is interesting to use the parallel algorithm and the linearization method to solve convection-diffusion equations.



---

*Source: 6322303-2023-01-18.xml*