The Monte Carlo complexity of Fredholm integral equations

A complexity study of Monte Carlo methods for Fredholm integral equations is carried out. We analyze the problem of computing a functional μ(y), where y is the solution of a Fredholm integral equation y(s) = ∫Im k(s,t)y(t)dt + f(s), s element-of Im, on the m-dimensional unit cube Im, where the kernal k and right-hand side f are given r times differentiable functions. We permit stochastic numerical methods which can make use of function evaluations of k and f only. All Monte Carlo methods known to the authors for solving the above problem are of the order n-1/2, while the optimal deterministic methods yield rate n-r/(2m), thus taking into account the given smoothness of the data. Here, n denotes the (average) number of function evaluations performed. The optimal algorithm we present combines deterministic and stochastic methods in an optimal way. It can be seen that both rates - the standard Monte Carlo rate for general continuous data and the deterministic rate for r-smooth data - multiply. This provides the smallest error that stochastic methods of given computational cost can achieve. 20 refs