Monte Carlo complexity of global solution of integral equations (Q1271167)

This paper is devoted to the theoretical complexity analysis of randomized solutions of the global problem of the Fredholm integral equation \[ u(s)- \int_G k(s,t) u(t)dt= f(s). \] The framework for this analysis is provided by information-based complexity theory. The present work complements previous research on the deterministic complexity of the local and the global problem and on the Monte Carlo complexity of the local problem. The result shows that randomized methods are superior to deterministic ones for the global problem. However, the difference between the optimal stochastic and deterministic convergence rate in the global case is smaller than in the local case.