Where does smoothness count the most for Fredholm equations of the second kind with noisy information? |
| |
Authors: | Arthur G Werschulz |
| |
Institution: | a Department of Computer and Information Sciences, Fordham University, New York, NY 10023, USA;b Department of Computer Science, Columbia University, 1214 Amsterdam Avenue, MC0401, New York, NY 10027, USA |
| |
Abstract: | We study the complexity of Fredholm problems (I−Tk)u=f of the second kind on Id=0,1]d, where Tk 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 fWr,p(Id) with r>d/p and that kWs,∞(I2d) 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 Θ(n−μ+δ), where μ=min{r/d,s/(2d)} and δ 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 -complexity for this problem. These bounds depend on the cost c(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation is proportional to δ−t, then the -complexity is roughly (1/)t+1/μ. |
| |
Keywords: | Fredholm equation Complexity Optimal algorithms Multigrid methods |
本文献已被 ScienceDirect 等数据库收录! |
|