# A Multilevel Correction Method for Convection-Diffusion Eigenvalue Problems

Authors: Zhonglan Peng; Hai Bi; Hao Li; Yidu Yang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We propose a multilevel correction method for the convection-diffusion eigenvalue problems which is suitable for not only simple but also multiple eigenvalues. And we prove that the accuracy of resulting eigenpair approximations can be improved after each correction step. The scheme is easy to realize with Matlab, and numerical results are satisfactory.


---

## Body

## 1. Introduction

The convection-diffusion eigenvalue problems have important physical background, such as convection-diffusion in fluid mechanics and environmental problems. Thus, finite element methods for solving this problem become an important topic which has attracted the attention of mathematical and physical fields. Research [1] discussed a priori error estimates, [2–7] the adaptive algorithms, [8] an adaptive homotopy approach, [9] two level algorithms, [10] function value recovery algorithms, [11, 12] extrapolation methods, and so forth. This paper turns to discuss finite element multilevel discretization based on Lin-Xie correction [13, 14].Lin and Xie [13, 14] introduced a new type of multilevel correction procedure. Later on, this correction was further developed as well as successfully applied to Steklov eigenvalue problems [15], Helmholtz transmission eigenvalue problems [16], and so forth.In this paper, we apply the method of Lin and Xie to convection-diffusion eigenvalue problems to obtain a multilevel method, which can be described as follows: (1) construct a coarsest finite element space and solve the primal and dual eigenvalue problems in the space; (2) solve two associated boundary value problems in an augmented space by using the previous obtained eigenvalue multiplying the corresponding eigenfunction as the load vector; (3) combine the coarsest finite element space with the obtained eigenfunction approximations in step (2) to obtain a new finite element space and solve the primal and dual eigenvalue problems again on the space. Then return to step (2) for next cycle. And the method is suitable for simple and multiple eigenvalues. What is more, we prove the scheme can reach the optimal order as same as solving the corresponding boundary value problem. Our scheme is easy to realize under the package of iFEM [17] with Matlab, and the numerical results are satisfactory.


## 2. Preliminaries

Consider the convection-diffusion eigenvalue problems as follows:(1)-∇·Dx∇u+b(x)·∇u=λu,inΩ,u=0,on⁡∂Ω,where Ω⊂Rd(d≥2) is a polyhedral bound domain. We denote the complex Sobolev space H1(Ω) and H01(Ω)={v∈H1(Ω),v|∂Ω=0} with norm (2)v1=v02+∇v021/2,where ·0 is a norm in complex space L2(Ω).LetV=H01(Ω), (3)a(u,v)=∫Ω‍D(x)∇u·∇v¯+bx·∇uv¯,b(u,v)=∫Ω‍uv¯.We assumeD(x)∈L∞(Ω) is a bounded and measurable real function on Ω and has a positive lower bound, b(x)∈W1,∞(Ω)d is a vector of real or complex functions on Ω, and there exist two positive constants C1,c1 such that(4)aw,v≤C1w1v1,∀v,w∈V,(5)Rea(v,v)≥c1v12,∀v∈V.The variational form of (1) is given by:Findλ∈C (complex plane), u∈V,u0=1, satisfying(6)a(u,v)=λb(u,v),∀v∈V.Letπh={K} be a mesh of Ω⊂Rd. For each element K∈πh, let hK be the diameter of K and ρK=sup⁡{diam⁡(S); S is a ball contained in K} and h=max⁡{hK:K∈πh}. We further assume that πh is a regular-shape mesh (see Section 17 of Chapter 3 in [18]): there exists a constant σ such that (7)hKρK≤σ∀K∈⋃h‍πh,if the quantity h approaches zero.LetVh⊂V be finite element space over πh consisting of continuous piecewise polynomials of degree less than or equal s. The finite element approximation of (6) is given by:Findλh∈C,  uh∈Vh,uh0=1, such that(8)auh,v=λhbuh,v,∀v∈Vh.It is shown in Section  8 in [1] that (4) and (5) show that there are two linear bounded operators T:L2(Ω)→V and Th:L2(Ω)→Vh satisfying(9)a(Tf,v)=b(f,v),∀v∈V,∀f∈L2(Ω),a(Thf,v)=b(f,v),∀v∈Vh,∀f∈L2(Ω).From [1] we also know T:L2(Ω)→L2(Ω) is a compact operator; then (6) and (8) have the following equivalent operator form (10) and (11), respectively. Consider(10)Tu=λ-1u,(11)Thuh=λh-1uh.The corresponding adjoint problem of (1) is(12)-∇·Dx∇u∗-∇·bx¯u∗=λ∗u∗,inΩ,u∗=0,on⁡∂Ω.The variational form and discrete variational form of (12) are given by:Findλ∗∈C,u∗∈V,u∗0=1, satisfying(13)av,u∗=λ∗¯bv,u∗,∀v∈V.Findλh∗∈C,uh∗∈Vh,uh∗0=1, satisfying(14)a(v,uh∗)=λh∗¯b(v,uh∗),∀v∈Vh.Note that the primal and dual eigenvalues are connected via λ=λ∗¯ and λh=λh∗¯.From [1], for (13) and (14) we know that (4) and (5) imply that there are two linear operators T∗:L2(Ω)→V and Th∗:L2(Ω)→Vh, satisfying(15)av,T∗f=bv,f,∀v∈V,∀f∈L2(Ω),av,Th∗f=bv,f,∀v∈Vh,∀f∈L2(Ω).Equations (13) and (14) have the following equivalent operator form (16) and (17), respectively. Consider(16)T∗u∗=λ∗-1u∗,(17)Th∗uh∗=λh∗-1uh∗.Obviously we can easily prove T∗ is the adjoint operator of T in the sense of inner product b(·,·).In this paper, letλi be an eigenvalue of (6) with the algebraic multiplicity q and the ascent is 1. Let λi,h be the eigenvalue of (8) which converges to λi. Let M(λi) be the space spanned by all eigenfunctions corresponding to the eigenvalue λi of T. Let Mh(λi) be the space spanned by all generalized eigenfunctions corresponding to eigenvalue λi,h of Th that converge to λi.As for the adjoint problems (13) and (14), the definitions of M∗(λi∗) and Mh∗(λi∗) are analogous to M(λi) and Mh(λi).We assume that for anyw∈V(18)limh→0inf⁡v∈Vhw-v1=0.We define that Ph denotes the finite element projection operator of V→Vh by(19)aw-Phw,vh=0,∀w∈V,∀vh∈Vh.And we define Ph∗:V→Vh by(20)avh,w∗-Ph∗w∗=0,∀w∗∈V,∀vh∈Vh.Obviously(21)Phw1≤C2w1,∀w∈V,Ph∗w∗1≤C2∗w∗1,∀w∗∈V.For any w∈V, by (18), we have(22)w-Phw1⟶0,ash⟶0,w∗-Ph∗w∗1⟶0,ash⟶0.Define η(h) and η∗(h) as(23)η(h)=sup⁡f∈L2(Ω),f0=1inf⁡v∈VhTf-v1,(24)η∗(h)=sup⁡f∈L2(Ω),f0=1inf⁡v∈VhT∗f-v1.Lemma 1.
The following estimates hold:(25)η(h)⟶0,ash⟶0,η∗(h)⟶0,ash⟶0,w-Phw0≤C3η∗(h)w-Phw1,∀w∈V,w∗-Ph∗w∗0≤C3∗η(h)w-Ph∗w∗1,∀w∗∈V.Proof.
See [1].WhereC2, C2∗, C3, and C3∗ are some positive constants independent of h.We define(26)δh(λi)=sup⁡w∈M(λi),w0=1inf⁡v∈Vhw-v1,δh∗(λi∗)=sup⁡w∗∈M∗(λi∗),w∗0=1inf⁡v∈Vhw∗-v1.For two linear spacesR and U, we define (27)Θ^(R,U)=sup⁡w∈R,w1=1inf⁡v∈Uw-v1,Φ^(R,U)=sup⁡w∈R,w0=1inf⁡v∈Uw-v0.We define the gaps between M(λi) and Mh(λi) in ·1 as(28)ΘMλi,Mhλi=max⁡Θ^Mλi,Mhλi,Θ^Mhλi,Mλiand in ·0 as(29)ΦMλi,Mhλi=max⁡Φ^Mλi,Mhλi,Φ^Mhλi,Mλi.We can likewise define the gaps betweenM∗(λi∗) and Mh∗(λi∗) in ·1 and in ·0, respectively, as(30)ΘM∗λi∗,Mh∗λi∗=max⁡Θ^M∗λi∗,Mh∗λi∗,Θ^Mh∗λi∗,M∗λi∗,(31)ΦM∗λi∗,Mh∗λi∗=max⁡Φ^M∗λi∗,Mh∗λi∗,Φ^Mh∗λi∗,M∗λi∗.For the eigenpair approximations by the finite element method, there exist the following error estimates (see P.699 in [1]).Lemma 2.
The eigenpair approximations{λj,h,uj,h}j=ii+q-1 and {λj,h∗,uj,h∗}j=ii+q-1 have the following error estimates:(32)ΘMλi,Mhλi≤Ciδhλi,(33)ΦMλi,Mhλi≤Ciη∗hδhλi,(34)ΘM∗λi∗,Mh∗λi∗≤Ciδh∗λi∗,(35)ΦM∗λi∗,Mh∗λi∗≤Ciηhδh∗λi∗,(36)λj,h-λi≤Ciδhλiδh∗λi∗.Here and hereafter Ci are some positive constants depending on λi but independent of the mesh size h.


## 3. One Correction Step with Multigrid Method

Based on [13, 14, 19] we introduce one correction step to improve the accuracy of the given eigenvalue and eigenfunction approximations.Firstly, we define the coarse linear finite element spaceVH on the generated mesh πH with the mesh size H. Then we define a sequence of triangulations πhm of domain Ω determined as follows. Suppose πh1=πH is given and let πhm+1 be obtained from πhm according to regular refinement (produce ξd subelements) such that (37)hm+1≈1ξhm,where ξ is an integer and indicates the refinement index and always is 2 in numerical experiments. Based on this sequence of meshes, we construct the corresponding linear finite element spaces such that(38)VH=Vh1⊂Vh2⊂⋯⊂Vhn.Assume we have obtained the eigenpair approximations(λj,hmc,uj,hmc)∈C×VH,hm,uj,hmc0=1 and (λj,hmc∗,uj,hmc∗)∈C×VH,hm,uj,hmc∗0=1 for j=i,…,i+q-1, where eigenvalues {λj,hmc}j=ii+q-1 are the approximations of eigenvalue λi of (6) and {λj,hmc∗}j=ii+q-1 are the approximations of eigenvalue λi∗ of (13) and {uj,hmc}j=ii+q-1 is a basis of Mhm(λi) and {uj,hmc∗}j=ii+q-1 a basis of Mhm∗(λi∗), and the definition of VH,hm see Algorithm 3.Now we introduce a correction step to improve the accuracy of the current eigenpair approximations{λj,hmc,uj,hmc}j=ii+q-1 and {λj,hmc∗,uj,hmc∗}j=ii+q-1.Algorithm 3.
One correction step.
Step 1. For j=i,…,i+q-1, solve the following equations.
Findu^j,hm+1 and u^j,hm+1∗∈Vhm+1 such that(39)a(u^j,hm+1,v)=λj,hmcb(uj,hmc,v),∀v∈Vhm+1,(40)a(v,u^j,hm+1∗)=λj,hmc∗¯b(v,uj,hmc∗),∀v∈Vhm+1.
Step 2. Define a new finite element space:(41)VH,hm+1=VH⊕span⁡u^i,hm+1,…,u^i+q-1,hm+1,hhhhhhhhhhhhhhhhhu^i,hm+1∗,…,u^i+q-1,hm+1∗,and solve the following eigenvalue problems.
Find(λj,hm+1c,uj,hm+1c)∈C×VH,hm+1 such that(42)auj,hm+1c,v=λj,hm+1cbuj,hm+1c,v,∀v∈VH,hm+1.
Find(λj,hm+1c∗,uj,hm+1c∗)∈C×VH,hm+1 such that(43)av,uj,hm+1c∗=λj,hm+1c∗¯bv,uj,hm+1c∗,∀v∈VH,hm+1.We output {λj,hm+1c}j=ii+q-1 and output a basis {uj,hm+1c}j=ii+q-1 of Mhm+1(λi) with uj,hm+1c0=1 and a basis {uj,hm+1c∗}j=ii+q-1 of Mhm+1∗(λi∗) with uj,hm+1c∗0=1.
We denote the two steps of Algorithm3 by (44)λj,hm+1c,uj,hm+1c,uj,hm+1c∗j=ii+q-1=CorrectionVH,λj,hmc,uj,hmc,uj,hmc∗j=ii+q-1,Vhm+1.Here VH denotes the coarse finite element space, {λj,hmc,uj,hmc,uj,hmc∗}j=ii+q-1 are given eigenpair approximations, and Vhm+1 denotes the computing space.
Note that the primal and dual eigenvalues are connected viaλj,hm+1c=λj,hm+1c∗¯.Remark 4.
The construction ofVH,hm+1 is proposed by Lin and Xie [13, 14], which is significant and crucial for designation of a new multilevel method.We adopt the following assumption.(A0) Suppose that there are{uj,hm}j=ii+q-1⊂Mhm(λi) with uj,hm0=1 and {uk,hm∗}k=ii+q-1⊂Mhm∗(λi∗) with uk,hm∗0=1, and there exists positive constant C′ independent of hm such that b(uj,hmc,uk,hm∗)+b(uj,hm,uk,hmc∗)≤C′(η(H)+η∗(H)), (j,k=i,…,i+q-1,j≠k), and b(uk,hmc,uk,hm∗) and b(uk,hm,uk,hmc∗) have a positive lower bound uniformly with respect to hm, respectively.Whenλ is a simple eigenvalue (q=1), it is clear that (A0) is valid. When q>1, we can also prove that if the distance from ui,hmc to span⁡{uj,hmc,j=k,…,k+q-1,j≠i} (i=k,…,k+q-1) (in ·b) has a positive lower bound uniformly with respect to hm and ui,hmc∗ satisfies the corresponding condition, then (A0) holds.Theorem 5.
Assume the condition (A0) holds, and there exist two numbersεhm(λi),  εhm∗(λi∗) such that the given eigenpairs {λj,hmc,uj,hmc}j=ii+q-1 and {λj,hmc∗,uj,hmc∗}j=ii+q-1 in Algorithm 3 have the following error estimates:(45)ΘMλi,Mhmλi≤C4εhmλi,ΘM∗λi∗,Mhm∗λi∗≤C4εhm∗λi∗,ΦMλi,Mhmλi≤C4η∗Hεhmλi,ΦM∗λi∗,Mhm∗λi∗≤C4ηHεhm∗λi∗,λj,hmc-λi≤C4εhmλiεhm∗λi∗,forj=i,…,i+q-1.Then after correction steps, the resultant eigenpair approximations {λj,hm+1c,uj,hm+1c}j=ii+q-1 and {λj,hm+1c∗,uj,hm+1c∗}j=ii+q-1 have the following error estimates:(46)ΘMλi,Mhm+1λi≤Ciεhm+1λi,(47)ΘM∗λi∗,Mhm+1∗λi∗≤Ciεhm+1∗λi∗,(48)ΦMλi,Mhm+1λi≤Ciη∗Hεhm+1λi,(49)ΦM∗λi∗,Mhm+1∗λi∗≤CiηHεhm+1∗λi∗,(50)λj,hm+1c-λi≤Ciεhm+1λiεhm+1∗λi∗,where εhm+1(λi)≔qC5(C4/c1λiη∗(H)εhm(λi)+C1/c1δhm+1(λi)), εhm+1∗(λi∗)≔qC5∗(C4/c1λi∗η(H)εhm∗(λi∗)+C1/c1δhm+1∗(λi∗))(j=i,…,i+q-1), and C4, C5, C5∗ are positive constants independent of hm; η∗(H) and η(H) are determined by (23) and (24), respectively.Proof.
Since{uj,hmc}j=ii+q-1 is a basis of Mhm(λi) and {uj,hm∗}j=ii+q-1⊂Mhm∗(λi∗), thus, from (45), we know there exist a basis {uj}j=ii+q-1 of M(λi) and {uj∗}j=ii+q-1⊂M∗(λi∗) such that(51)uj-uj,hmc1≤C4εhm(λi),(52)uj-uj,hmc0≤C4η∗(H)εhm(λi),(53)uj∗-uj,hm∗1≤C4εhm∗(λi∗),(54)uj∗-uj,hm∗0≤C4η(H)εhm∗(λi∗).For any w∈M(λi), w0=1, we have(55)w=∑j=ii+q-1‍γjuj,thus (56)bw,uk∗=∑j=ii+q-1‍γjbuj,uk∗.Then from b(uj,hmc,uk,hm∗)≤C′(η(H)+η∗(H))(j≠k), we have(57)γk=1buk,uk∗bw,uk∗-∑j≠k,j=ii+q-1‍γjbuj,uk∗≤1buk,uk∗1+∑j≠k,j=ii+q-1‍γjb(uj-uj,hmc,uk∗)hhhhhhhhhhhhhhhhhhhhhhhh+b(uj,hmc,uk∗-uk,hm∗)hhhhhhhhhhhhhhhhhhhhhhh+b(uj,hmc,uk,hm∗)∑j=k,j=ii+q-1‍≤1buk,uk∗1+∑j≠k,j=ii+q-1‍γjC4η∗Hεhmλihhhhhhhhhhhhhhhhhhhhhhhihh+η(H)εhm∗(λi∗)hhhhhhhhhhhhhhhhhhhhhhhiih+C′ηHhhhhhhhhhhhhhhhhhhhhhhhi+η∗Hη∗Hεhmλi1+∑j≠k,j=ii+q-1‍.Since buk,hmc,uk,hm∗ has a positive lower bound uniformly with respect to hm and (52)–(54) hold, buk,uk∗ has a positive lower bound uniformly with respect to hm; that is, there exists δ>0 such that (58)buk,uk∗≥δ,k=i,i+1,…,i+q-1,which together with (57) yields (59)γk≤1δ1+∑j=ii+q-1‍γj·C4η∗Hεhmλi+ηHεhm∗λi∗+C′ηH+η∗HC4η∗Hεhmλi+ηHεhm∗λi∗1+∑j=ii+q-1‍γj.Thus we get(60)∑k=ii+q-1‍γk≤q1δ1+∑j=ii+q-1‍γjhhhhhhhh·C4η∗Hεhmλi+ηHεhm∗λi∗hhhhhhhh+C′ηH+η∗HC4η∗Hεhmλi+ηHεhm∗λi∗1+∑j=ii+q-1‍γjC4η∗Hεhmλi+ηHεhm∗λi∗1+∑j=ii+q-1‍γj.Equation (60) shows that there exists a constant C5 independent of hm such that(61)γj≤C5,j=i,i+1,…,i+q-1.We set αj≔λi/λj,hmc, for j=i,…,i+q-1. From equalities (6), (19), and (39) and inequalities (5), (51), and (52), for j=i,…,i+q-1, the following estimates hold: (62)αju^j,hm+1-Phm+1uj12≤1c1Reaαju^j,hm+1-Phm+1uj,αju^j,hm+1-Phm+1uj≤1c1aαju^j,hm+1-Phm+1uj,αju^j,hm+1-Phm+1uj=1c1aαju^j,hm+1,αju^j,hm+1-Phm+1ujhhhhhhh-a(uj,αju^j,hm+1-Phm+1uj)=1c1αjλj,hmcbuj,hmc,αju^j,hm+1-Phm+1ujhhhhhhh-λjbuj,αju^j,hm+1-Phm+1uj≤1c1λiuj,hmc-uj0αju^j,hm+1-Phm+1uj1≤C4c1λiη∗(H)εhm(λi)αju^j,hm+1-Phm+1uj1.Then we have(63)αju^j,hm+1-Phm+1uj1≤C4c1λiη∗(H)εhm(λi),for j=i,…,i+q-1. According to (63) and the error estimate of finite element projection(64)uj-Phm+1uj1≤C1c1δhm+1(λi)we have(65)αju^j,hm+1-uj1≤C4c1λiη∗Hεhmλi+C1c1δhm+1λi,for j=i,…,i+q-1.
Now we estimate the error for the eigenpairs{λj,hm+1c,uj,hm+1c}j=ii+q-1 of problem (42). Based on the error estimate theory of finite element method for eigenvalue problems (see, e.g., [1, 14] and Lemma 2), (32), (33), and (65), and the definition of the space VH,hm+1, we deduce that(66)ΘMλi,Mhm+1λi≤Cisup⁡w∈M(λi),w0=1inf⁡vH,hm+1∈VH,hm+1w-vH,hm+11≤Cisup⁡w∈M(λi),w0=1∑j=ii+q-1‍γjuj-∑j=ii+q-1‍γjαju^j,hm+11≤Cisup⁡γj∑j=ii+q-1‍γjuj-αju^j,hm+11≤CiqC5max⁡αiu^i,hm+1-ui1,…,hhhhhhhhhhhhhhαi+q-1u^i+q-1,hm+1-ui+q-11≤CiqC5C4c1λiη∗Hεhmλi+C1c1δhm+1λi,ΦMλi,Mhm+1λi≤Cisup⁡w∈M(λi),w0=1inf⁡vH,hm+1∈VH,hm+1w-vH,hm+10≤Ciη~∗(H)sup⁡w∈Mλi,w0=1inf⁡vH,hm+1∈VH,hm+1w-vH,hm+11≤Ciη~∗(H)εhm+1(λi),where(67)η~∗H=sup⁡f∈W,f0=1inf⁡v∈VH,hm+1T∗f-v1≤η∗H.From (66) and (67), we can obtain (46) and (48).
Similarly, we can deduce that, for anyw∗∈M∗(λi∗), w∗0=1,(68)w∗=∑j=ii+q-1‍γj∗uj∗,and there exists a constant C5∗ independent of hm such that(69)γj∗≤C5∗,j=i,i+1,…,i+q-1.
According to the equalities (13), (20), and (40), inequalities (5), (53), and (54), and the error estimate of finite element projection Phm+1∗, we can likewise have(70)αju^j,hm+1∗-uj∗1≤C4c1λi∗η(H)εhm∗(λi∗)+C1c1δhm+1∗(λi∗).
We can likewise have the following estimates:(71)ΘM∗λi∗,Mhm+1∗λi∗≤CiqC5∗C4c1λi∗ηHεhm∗λi∗+C1c1δhm+1∗λi∗,ΦM∗λi∗,Mhm+1∗λi∗≤Ciη~(H)εhm+1∗(λi∗),where(72)η~(H)=sup⁡f∈W,f0=1inf⁡v∈VH,hm+1Tf-v1≤η(H).
From (71) and (72), we can obtain (47) and (49). The estimate (50) can be derived by (36), (46), and (47), and the proof concludes.


## 4. Multilevel Scheme for the Eigenvalue Problem

In this part, we will give the multilevel scheme based on Algorithm3. This type of multilevel method can achieve the optimal accuracy which is almost the same to solving the eigenvalue problem directly in the finest finite element space.Firstly, the sequence of finite element spacesVH=Vh1⊂Vh2⊂⋯⊂Vhn which are defined in Section 3 have the following relations:(73)δhm+1λi≈1ξδhmλi,δhmλi≤C6ξδhm+1λi,(74)δhm+1∗λi∗≈1ξδhm∗λi∗,δhm∗λi∗≤C6∗ξδhm+1∗λi∗,for m=1,…,n-1, where C6 and C6∗ are two positive constants independent of m and n.Remark 6.
The relations (73) and (74) are obviously reasonable, because we can choose δhm(λi)≈hm,δhm∗(λi∗)≈hm(m=1,…,n). Invariably the upper bound of the estimates δhm(λi)≤C7hm,δhm∗(λi∗)≤C7∗hm(m=1,…,n) holds. We also can obtain the lower bound δhm(λi)≥c7hm,δhm∗(λi∗)≥c7∗hm(m=1,…,n) (see [20]); c7,C7,c7∗,C7∗ are some positive constants independent of hm.Algorithm 7 (multilevel scheme).
Implement the following.
Step 1. Construct a sequence of nested finite element spaces Vh1,Vh2,…,Vhn such that (38), (73), and (74) hold.
Step 2. Solve the following eigenvalue problems.
Find(λj,h1,uj,h1)∈C×Vh1 such that uj,h10=1 and(75)auj,h1,vh1=λj,h1buj,h1,vh1,∀vh1∈Vh1.
Find(λj,h1∗,uj,h1∗)∈C×Vh1 such that uj,h1∗0=1 and(76)avh1,uj,h1∗=λj,h1∗¯bvh1,uj,h1∗,∀vh1∈Vh1.
Step 3. For m=1,…,n-1, compute new eigenpair approximations {λj,hm+1c,uj,hm+1c}j=ii+q-1∈C×VH,hm+1,{λj,hm+1c∗,uj,hm+1c∗}j=ii+q-1∈C×VH,hm+1 by Algorithm 3: (77)λj,hm+1c,uj,hm+1c,uj,hm+1c∗j=ii+q-1=CorrectionVH,λj,hmc,uj,hmc,uj,hmc∗j=ii+q-1,Vhm+1.
Finally, we obtainq eigenpair approximations {λj,hnc,uj,hnc}j=ii+q-1∈C×VH,hn, {λj,hnc∗,uj,hnc∗}j=ii+q-1∈C×VH,hn, and λj,hnc=λj,hnc∗¯.Theorem 8.
After implementing Algorithm7, if the mesh size H is small enough such that qC5Ci/c1λiC6ξη∗(H)≤1, qC5∗Ci/c1λi∗C6∗ξη(H)≤1 and the condition (A0) holds. Then the resultant eigenpair approximations {λj,hnc,uj,hnc}j=ii+q-1 and {λj,hnc∗,uj,hnc∗}j=ii+q-1 have the following error estimates:(78)ΘMλi,Mhnλi≤CiC8δhnλi,(79)ΦMλi,Mhnλi≤CiC8η∗Hδhnλi,(80)ΘM∗λi∗,Mhn∗λi∗≤CiC8∗δhn∗λi∗,(81)ΦM∗λi∗,Mhn∗λi∗≤CiC8∗ηHδhn∗λi∗,(82)λj,hnc-λi≤CiC8C8∗δhnλiδhn∗λi∗,where C8∶=C1/c1{1+qC5/1-qC5C6ξ|λi|η∗(H)Ci/c1} and C8∗∶=C1/c1{1+qC5∗/1-qC5∗C6∗ξ|λi∗|η(H)Ci/c1}.Proof.
At first, by Lemma2, we have(83)ΘMλi,Mh1λi≤Ciδh1(λi),(84)ΦMλi,Mh1λi≤Ciη∗h1δh1λi≤Ciη∗Hδh1λi,(85)ΘM∗λi∗,Mh1∗λi∗≤Ciδh1∗λi∗,(86)ΦM∗λi∗,Mh1∗λi∗≤Ciηh1δh1∗λi∗≤CiηHδh1∗λi∗,(87)λj,h1c-λi≤Ciδh1λiδh1∗λi∗.Let εh1(λi)≔δh1(λi) and εh1∗(λi∗)≔δh1∗(λi∗). From (83)–(86) and Theorem 5 with C4=Ci, for m=1,…,n-1, we have(88)εhm+1(λi)≤qC5Cic1λiη∗Hεhmλi+C1c1δhm+1λi,(89)εhm+1∗(λi∗)≤qC5∗Cic1λi∗ηHεhm∗λi∗+C1c1δhm+1∗λi∗.Then by recursive relation and based on the proof in Theorem 5, (73), (88), and qC5Ci/c1λiC6ξη∗(H)≤1, we have(90)εhnλi≤qC5Cic1λiη∗Hεhn-1λi+C1c1δhnλi≤qC5Cic1λiη∗H2εhn-2(λi)+qC52Cic1λiC1c1η∗Hδhn-1λi+qC5C1c1δhnλi≤C1c1qC5Cic1λiη∗Hn-1δh1(λi)hhhhhh+qC5∑m=2n‍qC5Cic1λiη∗Hn-mδhmλi≤C1c1qC5Cic1C6ξλiη∗Hn-1δhnλihhhihhh+qC5∑m=1n‍qC5Cic1C6ξλiη∗Hn-mhhhhhhhhhhhh·δhn(λi)qC5Cic1C6ξλiη∗Hn-m≤C1c11+qC51-qC5C6ξλiη∗(H)Ci/c1δhn(λi)≤C8δhnλi,(91)ΘMλi,Mhnλi≤Ciεhn(λi).The estimate (78) can be obtained by combining (90) and (91). And we can likewise obtain (80). From the proof of Theorem 5 and (78) and (80) we can obtain the desired results (79), (81), and (82).Remark 9.
We can likewise estimate the computational work of Algorithm7 similar to Section 5 of [14] and can prove that solving the eigenvalue problem needs nearly the same work as solving the corresponding boundary value problem for Algorithm 7.


## 5. Numerical Experiments

In this section, we will present two numerical examples of the multilevel scheme by using linear finite elements on uniform triangle meshes. We use MATLAB 2012b under the package of iFEM [17] to solve Examples 10 and 11 on Ω=(0,1)2andΩ=(-1,1)2∖[0,1]2, respectively. In the numerical examples we give the following notational explainations:λi,h: the ith finite element eigenvalue by solving the eigenvalue problem directly.λi,hc: the ith finite element eigenvalue by multilevel correction method solving the eigenvalue problem.Example 10.
Consider the convection-diffusion equation(92)-Δu+b·∇u=λu,inΩ,u=0,on⁡∂Ω,where Ω=(0,1)2 and b=bx=(b1,b2)T.
The eigenvalues of (92) are(93)λi,j=b12+b224+π2i2+j2,where i,j∈N+. The corresponding adjoint eigenvalue problem has eigenvalues λi,j∗=λi,j (see [10]). We obtain that λ1=b12+b22/4+2π2 and λ2=λ3=b12+b22/4+5π2, so the multiplicity of λ2 is 2. For (92) with b=(1,0)T, b=(3,0)T, and b=(10,0)T, the numerical results are shown in Tables 1, 2, and 3, respectively, and we give Figure 1 to present the intuitive trend of the approximations. From them, we can see that the accuracy of λi,hc and λi,h is nearly the same.Table 1
Ω
=
(
0,1
)
2, b = (1,0)T.
h
Dof
λ
1
,
h
c
λ
2
,
h
c
λ
1
,
h
λ
2
,
h
2
/
32
961
20.034801
49.798457
20.034800
49.798418
2
/
64
3969
20.000601
49.648112
20.000601
49.648109
2
/
128
16129
19.992056
49.610543
19.992056
49.610543
2
/
256
65025
19.989921
49.601152
19.989921
49.601152
2
/
512
261121
19.989387
49.598805
19.989387
49.598805Table 2
Ω
=
(
0,1
)
2, b=(3,0)T.
h
Dof
λ
1
,
h
c
λ
2
,
h
c
λ
1
,
h
λ
2
,
h
2
/
32
961
22.019219
51.765675
22.019218
51.765637
2
/
64
3969
21.996691
51.639857
21.996691
51.639853
2
/
128
16129
21.991078
51.608476
21.991078
51.608475
2
/
256
65025
21.989676
51.600635
21.989676
51.600635
2
/
512
261121
21.989326
51.598675
21.989326
51.598675Table 3
Ω
=
(
0,1
)
2, b=(10,0)T.
h
Dof
λ
1
,
h
c
λ
2
,
h
c
λ
1
,
h
λ
2
,
h
2
/
32
961
44.637275
74.100045
44.637249
74.097049
2
/
64
3969
44.713643
74.284384
44.713642
74.284210
2
/
128
16129
44.732812
74.332012
44.732812
74.332001
2
/
256
65025
44.737609
74.344013
44.737609
74.344013
2
/
512
261121
44.738809
74.347019
44.738809
74.347019Figure 1
Ω
=
(
0,1
)
×
(
0,1
), error curves for the 1st (a) and 2nd (b) eigenvalues.
(a)
(b)Example 11.
Consider the convection-diffusion equation (92) where Ω=(-1,1)2∖[0,1]2. A reference value for the first eigenvalue of (92) is b12+b22/4+9.639724 and the sixth eigenvalue is b12+b22/4+41.47451 (see [3]). From Tables 4–6 and Figure 2, we can get the same accurate approximations as those computed directly when the degrees of freedom are the same, but our running time is decreased. We also see that they are not perfect especially when b=(10,0)T; the numerical first eigenvalue doesn’t perform well in approximating process, which is the consequence of the performance of linear algebra routine on this convection dominated problem.Table 4
Ω
=
(
-
1,1
)
2
∖
[
0,1
]
2, b=(1,0)T.
h
Dof
λ
1
,
h
c
λ
6
,
h
c
λ
1
,
h
λ
6
,
h
2
/
32
2945
9.921856
41.931339
9.921856
41.931223
2
/
64
12033
9.900929
41.782028
9.900929
41.782007
2
/
128
48641
9.893785
41.741203
9.893785
41.741199
2
/
256
195585
9.891239
41.729602
9.891239
41.729601
2
/
512
784385
9.890301
41.726147
—
—Table 5
Ω
=
(
-
1,1
)
2
∖
[
0,1
]
2, b=(3,0)T.
h
Dof
λ
1
,
h
c
λ
6
,
h
c
λ
1
,
h
λ
6
,
h
2
/
32
2945
11.913459
43.897920
11.913459
43.897831
2
/
64
12033
11.898825
43.773604
11.898825
43.773591
2
/
128
48641
11.893259
43.739093
11.893259
43.739091
2
/
256
195585
11.891108
43.729074
11.891108
43.729074
2
/
512
784385
11.890268
43.726016
—
—Table 6
Ω
=
(
-
1,1
)
2
∖
[
0,1
]
2, b=(10,0)T.
h
Dof
λ
1
,
h
c
λ
6
,
h
c
λ
1
,
h
λ
6
,
h
2
/
32
2945
34.613575
66.310273
34.613578
66.311082
2
/
64
12033
34.636342
66.439222
34.636341
66.439144
2
/
128
48641
34.640137
66.467962
34.640137
66.467962
2
/
256
195585
34.640327
66.473790
34.640327
66.473790
2
/
512
784385
34.640073
66.474694
—
—Figure 2
Ω
=
(
-
1,1
)
2
∖
[
0,1
]
2, error curves for the 1st (a) and 6th (b) eigenvalues.
(a)
(b)


## 6. Concluding Remarks

Based on [13, 14, 19], in this paper we discuss a multilevel method for the convection-diffusion eigenvalue problems. Theoretical analysis and experimental results show that the approach is easy to carry out and can be used to solve the eigenvalue problems efficiently.We can replace (39)-(40) in Algorithm 3 by other types of efficient iteration schemes such as local and parallel finite element algorithms based on two-grid discretizations, which was first introduced by Xu and Zhou [21] and it has been applied successfully to eigenvalue problems (see, e.g., [22–24]). The multilevel method discussed here can also be extended to the general nonsymmetric elliptic eigenvalue problems (including Helmholtz transmission eigenvalue problems). These will be investigated in our future work.



---

*Source: 904347-2015-04-29.xml*