1983 Reports

Complexity of Indefinite Elliptic Problems

Werschulz, Arthur G.

We study the complexity of 2mth order definite elliptic problems Lu = f (with homogeneous Dirichlet boundary conditions) over a d-dimensional do- main Ω, error being measured in the Hm(Ω)-norm. The problem elements f belong to the unit ball of Wr,p(Ω), where p ∈ [2,∞] andr > d/p. Informa- tion consists of (possibly-adaptive) noisy evaluations of f or the coefficients of L. The absolute error in each noisy evaluation is at most δ. We find that the nth minimal radius for this problem is proportional to n−r/d + δ,and that a noisy finite element method with quadrature (FEMQ), which uses only function values, and not derivatives, is a minimal error algorithm. This noisy FEMQ can be efficiently implemented using multigrid techniques. Using these results, we find tight bounds onthe ε-complexity (minimal cost of calculating anε-approximation) for this problem, said bounds depending on the cost c(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ- noisy evaluation isc(δ) = δ−s (for s > 0), then the complexity is proportional to (1/ε)d/r+s.