Complexity of Integral Equations and Relations to S-Numbers

The complexity of computing a functional of the solution of a Fredholm integral equation is studied. We show that the estimate of the information complexity is equivalent to that of Gelfand numbers of a certain mapping. Upper and lower estimates as well as open problems are discussed. 1 Introduction In this paper we study a certain problem concerning the complexity of approximate solution of integral equations. The analysis is carried out within the framework of information-based complexity theory [TWW88]. We consider Fredholm integral equations of the second kind with smooth data, and we set the task of computing not the full solution of the problem, but only the value of a certain linear functional of the solution. We assume that linear functionals of the data can be exploited for the computational process. In [Hei93] an algorithm was constructed which showed that approximations to functional values can be computed much faster than approximations to the full solution. The question o..