The Complexity of Indefinite Elliptic Problems with Noisy Data

✍ Scribed by Arthur G. Werschulz

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 194 KB
• Volume: 13
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1006/jcom.1997.0456

✦ Synopsis

We study the complexity of second-order indefinite elliptic problems -div(a∇u) + bu = f (with homogeneous Dirichlet boundary conditions) over a d-dimensional domain , the error being measured in the H 1 ( )-norm. The problem elements f belong to the unit ball of W r, p ( ), where p ∈ [2, ∞] and r > d/p. Information consists of (possibly adaptive) noisy evaluations of f, 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 .