Academic Commons


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}.



  • thumnail for demo title for ac:110294 demo title for ac:110294 application/octet-stream 114 KB Download File

More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-035-96
Published Here
April 25, 2011
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.