1996 Reports

The complexity of definite elliptic problems with noisy data

Werschulz, Arthur G.

We study the complexity of 2mth order definite elliptic problems Lu=ƒ (with homogeneous Dirichlet boundary conditions) over a d-dimensional domain Ω, error being measured in the H^m(Ω)-norm. The problem elements ƒ belong to the unit ball of W^{r,p}(Ω), where p ∈ [2, ∞] and r > d/p. Information consists of (possibly-adaptive) noisy evaluations of ƒ 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 on the ε-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 is c(δ)=δ^{-s} (for s > 0), then the complexity is proportional to (1/ε)^{d/r+s}.