资料课件讲义报告-1

1、Adaptive Mesh Refinement and Superconvergence for Two Dimensional Interface ProblemsHuayi WeiThe School of Mathematics and Computational Science Xiangtan UCoauthor: Yunqing Huang(XTU), Long Chen(UCI), Bin ZhengDecember 08, 2012, Xiangtan OutlineOverview1Adaptive body-fi

2、tted mesh generation method2Linear FE superconvergence for 2D interface problem Linear FE Approximation Based on Body-fitted Mesh Linear FE Superconvergence for 2D Interface Problem34 Numerical tests The Elliptic Interface ModelA typical elliptic interface equation is (x)u(x) = f(x), x ,Wwith prescr

3、ibed jump conditions across the interface :W+GW= u+ u = q0,u= +u + u = q1,unnnand Dirichlet or Neumann boundary condition on . Numerical Methods for Interface ProblemsCartesian-type mesh: 1 Mesh generation is very easy. Modify the FD stencils or FE basis functions on the vertices near the interface.

4、Body-fitted mesh: 2 The grid points fitted to the interface. Standard Finite Element discretization.Therefore a crucial ingredient of the method based on body-fitted mesh is to have a simple, robust and fast mesh generator.1 Z. Li, An overview of the immersed interface method and its applications, e

5、se J. Mathematics, 7:pp. 149, 2003.2 C. Borgers. A triangulation algorithm for fast elliptic solvers based on domainimbedding. SIAM J. Numer. Anal., 27(5):pp. 11871196, 1990. Semi-structured and Body-fitted Triangular MeshHere we are interested in the semi-structured and body-fitted triangular mesh

6、generation methods, and in particular the Borgers algorithm 2.Figure: Semi-structured and body-fitted mesh. What is Borgers Algorithm?Figure: Initial Cartesian grid and the interface curve. What is Borgers Algorithm?Figure: Find the nodes near the interface curve. What is Borgers Algorithm?Figure: P

7、erturb the nodes onto to the interface. What is Borgers Algorithm?Figure: Choose an appropriate diagonal of perturbed quadrilaterals to fit the interface and maintain the mesh quality. View the Borgers Algorithm DifferentlyNode pertubation + Edge swap(a)(b) The Advantage of Borgers AlgorithmThe body

8、-fitted mesh generated by Borgers algorithm is ”not bad”:Shape regular and quasi-uniform. Topologically equivalent to the Cartesian grid. The Disadvantage of Borgers AlgorithmWhen the interface contains fine geometric features, Borgers algorithm requires a very fine mesh to resolve the interface and

9、in turn increase the computationalcost.Figure: The interface with fine geometric details. OutlineOverview1Adaptive body-fitted mesh generation method2Linear FE superconvergence for 2D interface problem Linear FE Approximation Based on Body-fitted Mesh Linear FE Superconvergence for 2D Interface Prob

10、lem34 Numerical tests Adaptive Body-fitted Mesh Generation MethodAdaptive mesh refinement+ESTIMATE MARK REFINE.Borgers algorithm Adaptive Body-fitted Mesh Generation MethodAdaptive mesh refinement+ESTIMATE MARK REFINE.Borgers algorithm The Initial Meshp3p4WW+GWp2p1(a) The initial mesh T0.(b) Uniform

11、ly bisect T0 one time.Figure: The initial mesh and one uniform bisection. The element with gray color is named Interface Element. Estimate Discrete Curvature: Three CasesFigure: (1) All elements containing p are interface elements. Estimate Discrete Curvature: Three CasesFigure: (2) The interface el

12、ements containing p are separated by non-interface elements containing p. Estimate Discrete Curvature: Three CasesFigure: (3) Interface vertices locally form two poly-line approximations of . ExampleFigure: The initial mesh and the interface. ExampleFigure: The finial mesh with minimum angle 25.7137

13、. The Characteristics of Our AlgorithmSimple data structure. Shape regular.The hierarchical structure of the body-fitted mesh is implicitly stored in the ordering of triangles. Based on this hierarchical structure, we use the coarsening algorithm in3 to construct a sequence of nested meshes and then

14、 construct the efficient multigrid solver.Resolve the interface with fine geometric details very well.3 L. Chen and C. Zhang. A coarsening algorithm on adaptive grids by newestvertex bisection and its applications. J. Comput. Math., 28(6):pp. 767789, 2010. OutlineOverview1Adaptive body-fitted mesh g

15、eneration method2Linear FE superconvergence for 2D interface problem Linear FE Approximation Based on Body-fitted Mesh Linear FE Superconvergence for 2D Interface Problem34 Numerical tests Some AssumptionsFor the simplicity of exposition, we assumethe function value jump condition u = 0. the Dirichl

16、et boundary condition u| = 0.the coefficient function (x) is positive and piecewise constant.RemarkThe final results can be extened to general elliptic interface problems without essential difficulty. The Sobolev space and its normWe denote by Wk,p( +) the Sobolev space consisting of function w such

17、 that w| Wk,p() and w|+ Wk,p(+) equipped with norm4()1/pppkwkk,p,+k wkk,p, + kwkk,p,+,=and seminorm()1/p,p+|w|p|w|k,p,+ = |w k,p,|k,p,+with standard modification for p = .4 J. H. Bramble and J. T. King. A finite element method for interface problems in domains with smooth boundaries and interfaces.

18、Adv. Comput. Math.,6(1):pp. 109138, 1996. The Weak Formulation and Its RegularityFind u H 1() such that:0(u, v) = (f, v) hq1, vi,for all v H (1).(1)0The existence and uniqueness of the solution can be easily proved by the Lax-Millegram lemma. For the solution u, we have the following regularity resu

19、lt: u Hr( +)kukr,+ . kfk0, + kq1kr3/2, ,where 0 r 2 5.5 J. Rotberg and Z. Seftel, A theorem on homeomorphisms for elliptic systems and its applications. MATH USSR SB+, 7(3):pp. 439465, 1969. The Triangulation ThFigure: Th and the interface approximation h (red line). Th is shape regular and h splits

20、 into two subdomains: ahnd + whhich arethe approximations of and +, respectively. The Triangulation Th+Each triangle Th is either in h or h, and has at most two vertices on . The triangulation Th can be decomposedintothree parts:T +:= T | +, has at most one vertex on ,hhhT := T | , has at most one v

21、ertex on ,hhhT 0 := T | has two vertices on .hhAssume C2, and for each triangle T0 , let + = +hand = , then we have either | |+. h 3or | | .h .3 The Projection From to Let Eh be an edge of h and nh the unit normal of Eh pointingfrom to +. We can define a projection P0 from Eh to 6:hhP0(x)= x + d(x)n

22、h,for all x Eh,where P0(x) and |d(x)| is the distance between x and along nh. We assume the length of Eh is small enough so thatP0 and its inverse P1 are all well defined.06 J. Bramble and J. King. A finite element method for interface problems in domains with smooth boundaries and interfaces. Adv.

23、Computat. Mathe.,6(1):109138, 1996. The Projection From to W+GP0(x)nht+xtEhWtFigure: The projection P0. In this figure, + = + and = , and | |+. h . 3 The Linear Finite Element approximationFind u h V h H (1 ) such that:0(huh, vh) = (f, vh) hq1, vhi ,for all vh Vh H 1(),0hwhere q1(x) = q1(P0(x), for

24、all x h and h| = +, for all + and h| = , for all .hhL -norm and H -norm estimatesTheorem (Theorem 2.2 in 6 )1/2ku uhk0, . h |log h|(kf k0, + kq1k2,),ku uhk0, . h2 |log h| (kf k0, + kq1k2,).6 Z. Chen and J. Zou. Finite element methods and their convergence for ellipticand parabolic interface problems

25、. Numer. Math., 79(2):pp. 175202, 1998. The error of replacing with LemmaLet u W 1,( +) , then we have3/2|(u, vh) ( hu, v )h|. hkuk+ |v |.h1, 1,Proof.Given T 0, let = supp( h) . Then | . h 3. Andhby the fact that vh is constant on , we can prove this lemma. Obviously, the constant in .is dependent o

26、n the difference ofand +. The Error of Data transmission From to The following lemma is slightly different with Lemma 2.2 in 6. Here we use the extension q1= q1(P0(x) to replace the linear interpolation of q1 on h in 6.LemmaAssume q1 W 0,() and C2. Then we have|hq1, vhi hq1 ,vh i | . h3/k2q1kkvhk,fo

27、r all vh Vh,0,1,hwhere q1(x) = q1(P0(x), for all x h. O(h2) Irregular Body-fitted TriangulationDefinitionLet E = E1 E2 denote the set of interior edge of Th. The triangulation Th is O(h2) irregular, for some 0, if for eachE E1, E is not an edge of h and E forms an O(h2)approximate parallelogram, whi

28、leEE |E| = O(h2).27 R. E. Bank and J. Xu. Asymptotically exact a posteriori error estimators, part I: Grids with superconvergence. SIAM J. Numer. Anal., 41(6):pp. 22942312, 2003.8 J. Xu. Error estimates of the finite element method for the 2nd order ellipticequations with discontinuous coefficients.

29、 J. Xiangtan University, 1:pp. 15, 1982. The Main Superconvergence ResultTheoremSuppose the body-fitted triangulation Th is O(h2) irregular. Let u be the solution, uh the linear element solution and uI the linear interpolation of u in Vh. If u H1() H3( +) W 2,( +) and is of class C2, then for all vh

30、 Vh, we have(h(u uI), vh).h1+min 1,(kuk3,+ + kuk2,+ ) |vh|1,+ h3/2 kuk+ |vh|,2, 1,and)1/2.h1+min 1,(kuk3,+ + kuk2,+ )3/2(u uhIh0,+ h(kuk+ kq k).12, +0, The Maximal Norm Error EstimateHere let hmin be the mimimal edge length of the element with the maxmal diameter in mesh Th. By the discrete embeddin

31、g resultkvhk0, .|log hmin|1/2 |vh|1, ,for all vh Vh H 1(),0we have the following corollary immediately: CorollaryAssume the same hypothesis in above theorem. We havekuh uIk0,.|log hmin|1/2h1+min1,(kuk3,+ +kuk2, + )3/2+ kq k) .+ h(kuk12, +0, OutlineOverview1Adaptive body-fitted mesh generation method

32、2Linear FE superconvergence for 2D interface problem Linear FE Approximation Based on Body-fitted Mesh Linear FE Superconvergence for 2D Interface Problem34 Numerical tests Numerical TestsMachine: A machine with 2.8 GHz Intel Xeon processor. Package: Matlab package iFEM 9.Solver: Multigrid V-cycle a

33、s a preconditioner in the preconditioned conjugate gradient method (MGCG).To test the rate of convergence, we first generate a body-fitted triangular mesh by our algorithm and then uniformly refine it to get a sequence of meshes. The new vertices on the interface edges introduced in each refinement

34、will be projected onto the interface.9 L. Chen. iFEM: An Integrated Finite Element Methods Package in MATLAB. Technical Report, University of California at Irvine, 2009 Tested Errors20,20,+ku u k := ( u uh+h)1/2,+ u + uh020,I20,|u uh | := ( (u u)+ )1/2, + (u + u )+1hhkuh uIk := max( u u , u + u+),hh

35、I0,h0,h1/2(uh u I)h022+ 1/2 (u+ u:= ( 1/2(u u )1/2,)+hhhhhI0,0,+hhwhere u and u+ are the linear finite element approximations ofhhu and u+, respectively. Numerical Example 1The domain is (1, 1)2 and the interface is a circle defined by the zero level set of the function(x, y) := x2 + y2 0.64.The ana

36、lytic solution is given byu+ = sin(x) sin(y) 1, and u = cos(x) cos(y) 1,where + = 10000, = 1. Numerical Example 0.600.80.51211.4001.8Y0.511X(a) The initial body-fitted mesh with minimum angle 29.0972.(b) The solution on the body-fitted meshFigure: The mesh and solution

37、 of Example 1.Z Numerical Example 1010110110210210310310441010log (Dof)log (Dof)1010(a) The errors of ku uhk0 and |u uh|1.(b) The errors of |uI uh|1 andkuI uhk.Figure: The errors of Example 1.log (err)10log (err)10 |u u |I h 1Dof 0.92165 |u u |I h Dof 0.81551 |uu |h 0Dof 1.0068|uu |h 1Dof 0.50365 Nu

38、merical Example 1Table: Example 1, the iterations and computing time of the V-cycle preconditioned conjugate gradient method for = 1 and diffrent +.+ = 10+ = 100+ = 1000+ = 10000Dofs#IterTime(s)#IterTime(s)#IterTime(s)#IterTime(s)1,089100.021110.023100.021100.0214,225100.031100.033100.032100.03216,6

39、41100.092100.099100.093100.166,049100.36100.37100.37100.37 Numerical Example 2The domain is (1, 1)2 and the interface is defined by(t) = t+ sin(4t),r(t) = 0.60125 + 0.24012 cos(4t + /2),X(t) = r(t)cos(t),Y (t) = r(t) sin(t),where 0 t 2. The analytic solution is given byu = cos(y) sin(x), u+ = 1 x2 y2,with = 4 + sin(x + y) and + = 10000 + x2 + y2. Numerical Example 2(a) The initial body-fitted mesh with minimum angle 26.2797.(b) The solution on the body-fitted mesh.Figure: The mesh and