On numerical methods for functions depending on a very large number of variables

Аннотация

The question under discussion is why optimal algorithms on classes of functions sometimes become useless in practice. As an example let us consider the class of functions which satisfy a general Lipschitz condition. The methods of integral evaluation over a unit cube of d dimensions, where d is significantly large, are discussed. It is assumed that the integrand is square integrable. A crude Monte Carlo estimation can be used. In this case the probable error of estimation is proportional to 1/√N, where N is the number of values of the integrand. If we use the quasi-Monte Carlo method instead of the Monte Carlo method, then the error does not depend on the dimension d, and according to numerous examples, it depends on the average dimension d̂ of the integrand. For small d̂, the order of error is close to 1/N.