Finite element methods are not always optimal (Q1096364)

It is a well known fact that the theory of optimal algorithms for elliptic problems is connected with the theory of N-widths of compacts in Sobolev spaces. The author considers a regular elliptic 2n-th order problem \(Lu=f\) with \(f\in H^ r\), \(r>-m\). He shows that the finite element method with piecewise polynomials of degree k is not asymptotically optimal if \(k<2m-1+r\). A special spline algorithm (a generalized Galerkin method) is recommended in this case. In the complexity analysis the author considers the number of unknowns only as a cast of the algorithm. Usually the computational work to solve grid systems with desired accuracy is considered as the key problem.