2010 Reports

Tractability of the Fredholm problem of the second kind

Werschulz, Arthur G.; Wozniakowski, Henryk

We study the tractability of computing ε-approximations of the Fredholm problem of the second kind: given f ∈ Fd and q ∈ Q2d, find u ∈ L2(Id) satisfying
u(x)− q(x,y)u(y)dy=f(x) ∀x∈Id =[0,1]d. Id
Here, Fd and Q2d are spaces of d-variate right hand functions and 2d-variate kernels that are continuously embedded in L2(Id) and L2(I2d), respectively. We consider the worst case setting, measuring the approximation error for the solution u in the L2 (I d )-sense. We say that a problem is tractable if the minimal number of information operations of f and q needed to obtain an ε- approximation is sub-exponential in ε−1 and d. One information operation corresponds to the evaluation of one linear functional or one function value. The lack of sub-exponential behavior may be defined in various ways, and so we have various kinds of tractability. In particular, the problem is strongly polynomially tractable if the minimal number of information operations is bounded by a polynomial in ε−1 for all d. We show that tractability (of any kind whatsoever) for the Fredholm problem is equivalent to tractability of the L2-approximation problems over the spaces of right-hand sides and kernel functions. So (for example) if both these approximation problems are strongly polynomially tractable, so is the Fredholm problem. In general, the upper bound provided by this proof is essentially non-constructive, since it involves an interpolator algorithm that exactly solves the Fredholm problem (albeit for finite-rank approximations of f and q). However, if linear functionals are permissible and that Fd and Q2d are tensor product spaces, we are able to surmount this obstacle; that is, we provide a fully-constructive algorithm that provides an approximation with nearly-optimal cost, i.e., one whose cost is within a factor ln ε−1 of being optimal.