1996 Reports

# The complexity of definite elliptic problems with noisy data

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

## Subjects

## Files

- cucs-035-96.pdf application/pdf 288 KB Download File

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

## More About This Work

- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-035-96
- Published Here
- April 25, 2011