THE COMPLEXITY OF FREDHOLM EQUATIONSOF THE SECOND KIND:NOISY INFORMATION ABOUT EVERYTHING

摘要

We study the complexity of Fredholm prob-lems of the second kind u — ∫_Ωk(x,y)u(dy = f.Previouswork on the complexity of this problem has assumed that Ωwas the unit cube Id. In this paper, we allow fl to be part ofthe data specifying an instance of the problem, along with kand f. More precisely, we assume that Ω is the diffeomorphicimage of the unit d-cube under a C~r_1mapping ρ: I~d In addition, we assume that k E C~r_2(I~(2l))andf∈C~3(I~l).Using a change of variables, we can reduce this problem to anintegral equation over I~d. Our information about the prob-lem data consists of function evaluations, contaminated by5-bounded noise. Error is measured by the max norm. Weshow that the problem is unsolvable if r_1 = 1 andd < l.Hence we assume that either r_1 2 ord = lin what follows.We find that the nth minimal error is bounded from below bye(n~-μ_1+δ)and from above by Θ(n~—μ_2+ δ), where 1 r_2r_3μ_1= min{r_1/d, r_2/d, r_3/d}and μ_2= min {r_1-1/d The upper bound is attained by a noisy modified Galerkinmethod, which can be efficiently implemented by a two-gridalgorithm. We thus find bounds on the e-complexity ofthe problem, these bounds depending on the cost c(δ) ofcalculating a δ-noisy function value. As an example, if c(δ) = δ-b,b+1/μ_2we find that the ε-complexity is between (1/ε)~(b+1)/μ_1and