1986 Reports

Probabilistic setting of information-based complexity

Wozniakowski, Henryk

We study the probabilistic (E, b)-complexity for linear problems equipped with Gaussian measures. The probabilistic (E, S)-complexity, comp@“˜(e, 6), is understood as the minimal cost required to compute approximations with error at most e on a set of measure at least 1 - 6. We find estimates of comp@(e, 6) in terms of eigenvalues of the correlation operator of the Gaussian measure over elements which we want to approximate. In particular, we study the approximation and integration problems. The approximation problem is studied for functions of d variables which are continuous after r times differentiation with respect to each variable. For the Wiener measure placed on rth derivatives, the probabilistic comp@(e, S) is estimated by ,((~/,)“(r+~)(ln(~/~))(d-“˜“r+““r‘+~‘), where a = 1 for the lower bound and a = 0.5 for the upper bound. The integration problem is studied for the same class of functions with d = 1. In this case, compPmb(e,6 ) = @((m/E)“@““˜).