Rob Stevenson on the Adaptive Finite Element Method
Fast Moving Front Commentary, January 2011
|
Article: Optimality of a standard adaptive finite element method
Authors: Stevenson, R |
Rob Stevenson shares his thoughts on this month's Fast-Moving Front paper in Mathematics.
The finite element method is the most popular method for the numerical approximation of the solution of an elliptic boundary value problem. In its simplest form for two-dimensional problems, the underlying domain is subdivided into triangles, and the best approximation is computed that is continuous and piecewise linear with respect to this subdivision.
The quality of the approximation depends on the diameter of the triangles and the smoothness of the solution. For many problems, the solution is much less smooth near non-smooth parts of the boundary (corners in two-dimensions) than in the interior of the domain, and it is therefore much more efficient to employ locally strongly refined subdivisions. An optimal, or near optimal distribution of the sizes of the triangles over the domain is, however, difficult or impossible to determine a priori.
Figure 1:
A locally refined partition created by an adaptive
finite element method.
View larger image in the tab below.
For this reason the adaptive finite element method (AFEM) was developed. The idea is to start with a subdivision into a few triangles, to compute the corresponding finite element approximation, and then to compute a posteriori error estimators associated to the individual triangles. Then, in the next step, those triangles are refined that carry the largest estimators, and the process is repeated until a target tolerance is met. An example of adaptively created subdivision is given in Figure 1.
For many problems, the AFEM is much more efficient than its non-adaptive counterpart, and therefore it is widely used by engineers since its introduction in the 1970s by Babuska and co-workers. It was, however, not before 1996 that, in two and more dimensions, the method was proven to produce a sequence of approximations that actually converges to the solution. This result was derived by Dörfler, and later in an improved version by Morin, Nochetto, and Siebert.
Although an important step forward in the mathematical foundation of AFEM, this result was not satisfactory in the sense that no convergence rates were demonstrated, and in this sense, it did not show any benefit of AFEM compared to the non-adaptive method.
The content of my paper is the proof that AFEM converges with the best possible rate, i.e., the rate that one would obtain knowing the optimal distribution of the sizes of the triangles over the domain, in moreover optimal computational complexity, i.e., the computational work scales linearly with the number of triangles. This work was inspired by an earlier paper of Binev, Dahmen, and DeVore from 2004 in which a similar result was proven for a modified AFEM extended with a so-called coarsening routine. Although mathematically satisfactory, practical experience showed that computationally this routine is very demanding.
The proof from my paper applies to the simplest case of Poisson's equation with linear finite elements. Since then, several authors have used the technique to extend the result in various directions, including nonconforming finite elements, mixed finite elements, variable coefficients, nonsymmetric problems, goal-oriented finite elements, Stokes equations, eigenvalue problems, and nonlinear equations.
Adaptive approximation is the key to solving complicated problems that one
encounters in practical situations. My current work is mainly devoted to a
further development of adaptive wavelet methods. Particularly
interesting seems their application to evolution equations formulated as
simultaneous space-time variational problems. Optimal rates can be
demonstrated which seems hard to be realizable with the traditional
time-stepping methods.
Prof. dr. Rob Stevenson
Korteweg-de Vries Institute (KdVI) for Mathematics
University of Amsterdam
Amsterdam, The Netherlands
KEYWORDS: ADAPTIVE FINITE ELEMENT METHOD; OPTIMAL COMPUTATIONAL COMPLEXITY; A POSTERIORI ERROR ESTIMATOR; NONLINEAR APPROXIMATION, BOUNDARY-VALUE-PROBLEMS; BESOV REGULARITY; CONVERGENCE.
