Where does smoothness count the most for Fredholm equations of the second kind with noisy information?

We study the complexity of Fredholm problems <f>(I−Tk)u=f</f> of the second kind on <f>Id=[0,1]d</f>, where <f>Tk</f> is an integral operator with kernel <f>k</f>. Previous work on the complexity of this problem has assumed either that we had complete information about <f>k</f> or that <f>k</f> and <f>f</f> had the same smoothness. In addition, most of this work has assumed that the information about <f>k</f> and <f>f</f> was exact. In this paper, we assume that <f>k</f> and <f>f</f> have different smoothness; more precisely, we assume that <f>f∈Wr,p(Id)</f> with <f>r>d/p</f> and that <f>k∈Ws,∞(I2d)</f> with <f>s>0</f>. In addition, we assume that our information about <f>k</f> and <f>f</f> is contaminated by noise. We find that the <f>n</f>th minimal error is <f>Θ(n−μ+δ)</f>, where <f>μ=min{r/d,s/(2d)}</f> and <f>δ</f> 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 <f>&epsiv;</f>-complexity for this problem. These bounds depend on the cost <f>c(δ)</f> of calculating a <f>δ</f>-noisy information value. As an example, if the cost of a <f>δ</f>-noisy evaluation is proportional to <f>δ−t</f>, then the <f>&epsiv;</f>-complexity is roughly <f>(1/&epsiv;)t+1/μ</f>. [Copyright &y& Elsevier]