## Rob Stevenson on the Adaptive Finite Element Method

#### Fast Moving Front Commentary, January 2011

Article: Optimality of a standard adaptive finite element method
Authors: |

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.