1983 Reports

# Complexity of Indefinite Elliptic Problems

We study the complexity of 2mth order definite elliptic problems Lu = f (with homogeneous Dirichlet boundary conditions) over a d-dimensional do- main Ω, error being measured in the Hm(Ω)-norm. The problem elements f belong to the unit ball of Wr,p(Ω), where p ∈ [2,∞] andr > d/p. Informa- tion consists of (possibly-adaptive) noisy evaluations of f 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 onthe ε-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 isc(δ) = δ−s (for s > 0), then the complexity is proportional to (1/ε)d/r+s.

## Subjects

## Files

- cucs-084-83.pdf application/pdf 1.16 MB 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-084-83
- Published Here
- October 26, 2011