Back to Search
Start Over
Where does smoothness count the most for Fredholm equations of the second kind with noisy information?
- Source :
-
Journal of Complexity . Dec2003, Vol. 19 Issue 6, p758. 41p. - Publication Year :
- 2003
-
Abstract
- 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]
- Subjects :
- *FREDHOLM equations
*COMPUTATIONAL complexity
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 0885064X
- Volume :
- 19
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- Journal of Complexity
- Publication Type :
- Academic Journal
- Accession number :
- 11425439
- Full Text :
- https://doi.org/10.1016/S0885-064X(03)00030-X