The Complexity of Definite Elliptic Problems with Noisy Data

We study the complexity of 2mth order definite elliptic problemsLu=f(with homogeneous Dirichlet boundary conditions) over ad-dimensional domain Ω, error being measured in theH^m(Ω)-norm. The problem elementsfbelong to the unit ball ofW^r,p(Ω), wherep∈ 2, ∞] andr>d/p. Information consists of (possibly adaptive) noisy evaluations offor the coefficients ofL. The absolute error in each noisy evaluation is at most δ. We find that thenth minimal radius for this problem is proportional ton^−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 costc(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation isc(δ) = δ^−s(fors> 0), then the complexity is proportional to (1/ϵ)^d/r+s.