Theory of Adaptive Finite Element Methods: An Introduction

1 Theory of Adaptive Finite Element Methods: An IntroductionRicardo H. Nochetto and Kunibert G. Siebert and Andreas VeeserAbstractThis is a survey on the Theory of Adaptive Finite Element methods (AFEM),which are fundamental in modern computational science and engineering. Wepresent a self-contained and up-to-date discussion of AFEM for linear second orderelliptic partial differential equations (PDEs) and dimensiond>1, with emphasison the differences and advantages of AFEM over standard FEM. The material isorganized in chapters with problems that extend and complement the Theory . Westart with the functional framework, inf-sup Theory , and Petrov-Galerkin method,which are the basis of FEM. We next address four topics of essence in the theoryof AFEM that cannot be found in one single article: mesh refinement by bisection,piecewise polynomial approximation in graded meshes, a posteriori error analysis,and convergence and optimal decay rates of AFEM.

2 The first topic is of geometricand combinatorial nature, and describes bisection as a rather simple and efficienttechnique to create conforming graded meshes with optimal complexity. The sec-ond topic explores the potentials of FEM to compensate singular behavior with localresolution and so reach optimal error decay. This Theory , although insightful, is in-sufficient to deal with PDEs since it relies on knowing the exact solution. The thirdtopic provides the missing link, namely a posteriori error estimators, which hingeexclusively on accessible data: we restrict ourselves to the simplest residual-type es-timators and present a complete discussion of upper and lower bounds, along withthe concept of oscillation and its critical role. The fourth topic refers to the conver-gence of Adaptive loops and its comparison with quasi-uniform refinement. We firstshow, under rather modest assumptions on the problem class and AFEM, conver-gence in the natural norm associated to the variational formulation.

3 We next restrictthe problem class to coercive symmetric bilinear forms, and show that AFEM isa contraction for a suitable error notion involving the induced energy norm. Thisproperty is then instrumental to prove optimal cardinality of AFEM for a class ofsingular functions, for which the standard FEM is H. NochettoDepartment of Mathematics and Institute of Physical Science and Technology, University of Mary-land, College Park, MD 20742, e-mail: Partially supported by NSF G. SiebertFachbereich Mathematik, Universit at Duisburg-Essen, Forsthausweg 2, D-47057 Duisburg, Ger-many, e-mail: VeeserDipartimento di Matematica, Universit`a degli Studi di Milano, Via C. Saldini 50, I-20133 Milano,Italy, e-mail: H. Nochetto, K. G. Siebert, and A. Veeser1 IntroductionAdaptive Finite Element methods are a fundamental numerical instrument in sci-ence and engineering to approximate partial differential equations. In the 1980s and1990s a great deal of effort was devoted to the design of a posteriori error estima-tors, following the pioneering work of Babu ska.

4 These are computable quantities,depending on the discrete solution(s) and data, that can be used to assess the approx-imation quality and improve it adaptively. Despite their practical success, adaptiveprocesses have been shown to converge, and to exhibit optimal complexity, onlyrecently and for linear elliptic survey presents an up-to-date discussion of Adaptive Finite Element methodsencompassing its design and basic properties, convergence, and Classical vs Adaptive Approximation in 1dWe start with a simple motivation in 1d for the use of Adaptive procedures, due toDeVore [28]. Given =(0,1), a partitionTN={xi}Nn=0of 0=x0<x1< <xn< <xN=1and a continuous functionu: R, we consider the problem ofinterpolating uby apiecewise constantfunctionUNoverTN. To quantify the difference betweenuandUNwe resort to themaximum normand study two cases depending on theregularity 1:W1 -Regularity. Suppose thatuis Lipschitz in[0,1]. We consider the ap-proximationUN(x):=u(xn 1)for allxn 1 x< |u(x) UN(x)|=|u(x) u(xn 1)|= xxn 1u (t)dt hn u L (xn 1,xn)we conclude that u UN L ( ) 1N u L ( ),(1)provided the local mesh-sizehnis about constant (quasi-uniformmesh), and so pro-portional toN 1(the reciprocal of the number of degrees of freedom).

5 Note thatthe same integrability is used on both sides of (1). A natural question arises:Is itpossible to achieve the same asymptotic decay rate N 1with weaker regularity de-mands?Case 2:W11-Regularity. To answer this question, we suppose u L1( )=1 andconsider the non-decreasing functionTheory of Adaptive Finite elements methods : An Introduction3 (x):= x0|u (t)|dtwhich satisfies (0)=0 and (1)=1. LetTN={xi}Nn=0be the partition given by xnxn 1|u (t)|dt= (xn) (xn 1)= , forx [xn 1,xn],|u(x) u(xn 1)|= xxn 1u (t)dt xxn 1|u (t)|dt xnxn 1|u (t)|dt=1N,whence u UN L ( ) 1N u L1( ).(2)We thus conclude that we could achieve the same rate of convergenceN 1forrougher functions with just u L1( )< . The following comments are in orderfor Case 1(Equidistribution).The optimal meshTNequidistributesthe mesh is graded instead of uniform but, in contrast to a uniform mesh, such apartition may not be adequate for another function with the same basic regularity asu.

6 It is instructive to consider the singular functionu(x)=x with = and errortolerance 10 2to quantify the above computations: ifN1andN2are the number ofdegrees of freedom with uniform and graded partitions, we obtainN1/N2= 2(Nonlinear Approximation).The regularity ofuin (2) is measured inW11( )instead ofW1 ( )and, consequently, the fractional regularity measured inL ( )increases to one full derivative when expressed inL1( ). This exchange ofintegrability between left and right-hand side of (2), and gain of differentiability, isat the heart of the matter and the very reason why suitably graded meshes achieveoptimal asymptotic error decay for singular functions. By those we mean functionswhich are not in the usual linear Sobolev scale, sayW1 ( )in this example, butrather in a nonlinear scale [28]. We will get back to this issue in Chap. OutlineThe functionUNmay be the result of a minimization process. If we wish to minimizethe norm u v L2( )within the spaceVNof piecewise constant functions overTN,then it is easy to see that the solutionUNsatisfies the orthogonality relationUN VN: u UN,v =0 for allv VN(3)and is given by the explicit local expression4R.

7 H. Nochetto, K. G. Siebert, and A. VeeserUN(x)=1hn xnxn 1ufor allxn 1<x< previous comments apply to thisUNas well even thoughUNcoincides withuat an unknown point in each interval[xn 1,xn].The latter example is closer than the former to the type of approximation issuesdiscussed in this survey. A brief summary along with an outline of this survey fol-lows:PDE:The functionuis not directly accessible but rather it is the solution of anelliptic PDE. Its approximation properties are intimately related to its regular-ity. In Chap. 2 we review briefly Sobolev spaces and the variational formulationof elliptic PDE, a present a full discussion of the inf-sup Theory . We show theconnection between approximability and regularity in Chap. 5, when we assessconstructive approximation and use this later in Chap. 9 to derive rates of :To approximateuwe need a numerical method which is sufficiently flex-ible to handle both geometry and accuracy (local mesh refinement); the methodof choice for elliptic PDEs is the Finite Element method.

8 We present its basictheory in Chap. 3, with emphasis on piecewise linear elements . We discuss therefinement of simplicial meshes in any dimension by bisection in Chap. 4, andaddress its complexity. This allows us to shed light on the geometric aspects ofFEM that make them so flexible and useful in practice. The complexity analysisof bisection turns out to be crucial to construct optimal approximations in gradedmeshes in Chap. 5 and to derive convergence rates in Chap. 9 for :We briefly recall polynomial interpolation Theory in Chap. 5 aswell as the principle of error equidistribution. The latter is a concept that leadsto optimal graded meshes and suggests that FEM might be able to approximatesingular functions with optimal rate. We conclude Chap. 5 with the constructionof optimal meshes via bisection for functions in a certain regularity class relevantto elliptic PDE. We emphasize the energy Posteriori Error Estimation:To extract the local errors incurred by FEM, andthus be able to equidistribute them, we present residual-type a posteriori error es-timators in Chap.

9 6. These are computable quantities in terms of the discretesolution and data which encode the correct information about the error distribu-tion. They are the simplest but not the most accurate ones. Therefore, we alsopresent alternative estimators, which are equivalent to the residual discussion of Chap. 6 includes the appearence of an oscillation term and aproof that it cannot be avoided for the estimator to be practical. We show bothupper and lower bounds between the energy error and the residual estimator. Theformer is essential for convergence and the latter for :This refers to the use and study of loops to the formSOLVE ESTIMATE MARK REFINE(4) Theory of Adaptive Finite elements methods : An Introduction5to iteratively improve the approximation of the solution of a PDE while keepingan optimal distribution of computational resources (degrees of freedom). The de-sign of each module, along with some key properties, is discussed in Chap.

10 7 and8. We emphasize the standard AFEM employed in practice which employs theestimator exclusively to make refinement decisions and never uses :This issue has been largely open until recently. In Chap. 7 wepresent a basic convergence Theory for most linear elliptic PDEs, including sad-dle point problems, under rather modest assumptions and valid for all existingmarking strategies. The final result is rather general but does not, and cannot,provide a convergence :We restrict ourselves to a model problem, which is symmetric andcoercive, to investigate the convergence rate of AFEM. In Chap. 8 we derive acontraction property of AFEM for the so-called quasi-error, which is a scaledsum of the energy error and the estimator. In Chap. 9 we prove that AFEM con-verges with optimal rate as dictated by approximation Theory even though theadaptive loop (4) does not use any regularity information but just the analysis leads to approximation classes adequate for FEM, and so to thegeometric restrictions caused by conforming grids, which are not the usual onesin nonlinear approximation H.