The Complexity of Fredholm Equations of the Second Kind: Noisy Information About Everything

摘要

We study the complexity of Fredholm problems of the second kind $u - int_Omega k(cdot,y)u(y),dy = f$. Previous work on the complexity of this problem has assumed that $Omega$ was the unit cube~$I^d$. In this paper, we allow~$Omega$ to be part of the data specifying an instance of the problem, along with~$k$ and~$f$. More precisely, we assume that $Omega$ is the diffeomorphic image of the unit $d$-cube under a $C^{r_1}$ mapping~$ho:I^do I^l$. In addition, we assume that $kin C^{r_2}(I^{2l})$ and $fin W^{r_3,p}(I^l)$ with $r_3>l/p$. Our information about the problem data is contaminated by $delta$-bounded noise. Error is measured in the $L_p$-sense. We find that the $n$th minimal error is bounded from below by $Theta(n^{-mu_1}+delta)$ and from above by $Theta(n^{-mu_2}+delta)$, where $$mu_1 = minleft{rac{r_1}{d}, rac{r_2}{2d}, rac{r_3-(d-l)/p}dight} qquadext{and}qquad mu_2 = minleft{rac{r_1-u}d, rac{r_2}{2d}, rac{r_3-(l-d)/p}dight},$$ with $$u = egin{cases} displaystylerac{d}p & ext{if $r_1ge 2$, $r_2ge2$, and $dle p$}, & 1 & ext{otherwise}. end{cases}$$ In particular, the $n$th minimal error is proportional to $Theta(n^{-mu_1}+delta)$ when $p=infty$. The upper bound is attained by a noisy modified Galerkin method, which can be efficiently implemented using multigrid techniques. We thus find bounds on the $arepsilon$-complexity of the problem, these bounds depending on the cost $mathbf{c}(delta)$ of calculating a $delta$-noisy function value. As an example, if $mathbf{c}(delta)=delta^{-b}$, we find that the $arepsilon$-complexity is between $(1/arepsilon)^{b+1/mu_1}$ and $(1/arepsilon)^{b+1/mu_2}$.