1997 Reports

The complexity of indefinite elliptic problems with noisy data

Werschulz, Arthur G.

We study the complexity of second-order indefinite elliptic problems - div (a 𝛁 u) + bu=ƒ (with homogeneous Dirichlet boundary conditions) over a d-dimensional domain Ω, the error being measured in the H^1 (Ω)-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 ƒ, a, or b (or their derivatives). 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}.