Optimality of a standard adaptive finite element method

In this paper an adaptive finite element method is constructed for solving elliptic equations that has optimal computational complexity. Whenever, for some s > 0, the solution can be approximated within a tolerance epsilon > 0 in energy norm by a continuous piecewise linear function on some partition with O(epsilon(-1/s)) triangles, and one knows how to approximate the right-hand side in the dual norm with the same rate with piecewise constants, then the adaptive method produces approximations that converge with this rate, taking a number of operations that is of the order of the number of triangles in the output partition. The method is similar in spirit to that from [SINUM, 38 (2000), pp. 466-488] by Morin, Nochetto, and Siebert, and so in particular it does not rely on a recurrent coarsening of the partitions. Although the Poisson equation in two dimensions with piecewise linear approximation is considered, the results generalize in several respects.