Where does smoothness count the most for Fredholm equations of the second kind with noisy information?
We study the complexity of Fredholm problems (I - T-k)u =f of the second kind on I-d = [0,1](d), where T-k is an integral operator with kernel k. Previous work on the complexity of this problem has assumed either that we had complete information about k or that k and f had the same smoothness. In addition, most of this work has assumed that the information about k and f was exact. In this paper, we assume that k and f have different smoothness; more precisely, we assume that f is an element of W-r,W-p (I-d) with r > d/p and that k is an element of W-s,W-infinity (I-2d) with s>0. In addition, we assume that our information about k and f is contaminated by noise. We find that the nth minimal error is Theta(n(-mu) + delta), where mu = min{r/d(1)s/(2d)} and delta is a bound on the noise. We prove that a noisy modified finite element method has nearly minimal error. This algorithm can be efficiently implemented using multigrid techniques. We thus find tight bounds on the epsilon-complexity for this problem. These bounds depend on the cost c(delta) of calculating a delta-noisy information value. As an example, if the cost of a delta-noisy evaluation is proportional to delta(-t), then the epsilon-complexity is roughly (1/epsilon)(t+1/mu) (C) 2003 Elsevier Science (USA). All rights reserved.
fredholm equation complexity optimal algorithms multigrid methods