Complexity of differential and integral equations (Q1085950)

The author considers the intrinsic difficulties (or complexity) of computing an approximate solution of the linear operator equation \(Lu=f\). Practical examples of such problems include when L is a known partial differential or integral operator. Of particular interest is the determination of conditions which are necessary and sufficient for the finite element method to be optimal. The author describes such conditions for elliptic partial differential equations involving an inequality involving the order of the problem and the degree of the finite element subspace. The situation when this condition is violated is also discussed and it is shown that the nonoptimality of the method is due to the way any available information is used. The situation when information required by the finite element method is not available. In particular when the only information available about f consists of evaluations of f, it is shown that in the case of Fredholm equations of the second kind this information is optimal; moreover, a finite element method in which the inner products are approximated by quadrature rules is an optimal algorithm.