Geodesic
On numerical methods for functions depending on a very large number of variables
Matematičeskoe modelirovanie, Tome 29 (2017) no. 2, pp. 135-138 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The question under discussion is why do optimal algorithms on classes of functions sometimes become useless in practice. As an example let's 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 that case the probable error of estimation is proportional $1/\sqrt{N}$, where $N$ is the number of values of the integrand. If we use a quasi-Monte Carlo method instead of Monte Carlo one, then the error does not depend on the dimension $d$, numerous examples show that it depends on the average dimension $\hat{d}$ of the integrand. For small $\hat{d}$ the order of the error is close to $1/N$.
Mots-clés : optimal algorithm
Keywords: Lipschitz condition, Monte Carlo method, quasi-Monte Carlo method, the average dimension. 
@article{MM_2017_29_2_a10,
     author = {I. M. Sobol},
     title = {On numerical methods for functions depending on a very large number of variables},
     journal = {Matemati\v{c}eskoe modelirovanie},
     pages = {135--138},
     year = {2017},
     volume = {29},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MM_2017_29_2_a10/}
}
TY  - JOUR
AU  - I. M. Sobol
TI  - On numerical methods for functions depending on a very large number of variables
JO  - Matematičeskoe modelirovanie
PY  - 2017
SP  - 135
EP  - 138
VL  - 29
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MM_2017_29_2_a10/
LA  - ru
ID  - MM_2017_29_2_a10
ER  - 
%0 Journal Article
%A I. M. Sobol
%T On numerical methods for functions depending on a very large number of variables
%J Matematičeskoe modelirovanie
%D 2017
%P 135-138
%V 29
%N 2
%U http://geodesic.mathdoc.fr/item/MM_2017_29_2_a10/
%G ru
%F MM_2017_29_2_a10
I. M. Sobol. On numerical methods for functions depending on a very large number of variables. Matematičeskoe modelirovanie, Tome 29 (2017) no. 2, pp. 135-138. http://geodesic.mathdoc.fr/item/MM_2017_29_2_a10/

[1] Dzh. Traub, Kh. Vozhniakovskii, Obshchaia teoriia optimalnykh algoritmov, Mir, M., 1983

[2] S. M. Nikolskii, Kvadraturnye formuly, Fizmatgiz, M., 1958

[3] I. M. Sobol, “Determination of the extremal values of a function of several variables Satisfying a generalized Lipschitz condition”, USSR Computational Mathematics and Mathematical Physics, 28:2 (1988), 112–118 | DOI | Zbl

[4] I. M. Sobol, “Quadrature formulae for functions of several variables satisfying a general Lipschitz condition”, USSR Computational Math. and Mathematical Physics, 29:3 (1989), 201–206 | DOI | MR | Zbl

[5] I. M. Sobol', D. Asotsky, A. Kreinin, S. Kucherenko, “Construction and comparison of high-dimensional Sobol' generators”, Wilmott Mag., 2011:56 (2011), 64–79 | DOI

[6] R. Liu, A. B. Owen, “Estimating mean dimensionality of analysis of variance decompositions”, J. Amer. Statist. Assoc., 101:474 (2006), 712–721 | DOI | MR | Zbl

[7] D. Asotsky, E. Myshetskaya, I. M. Sobol', “The average dimension of a multidimensional function for quasi-Monte Carlo estimates of an integral”, Comp. Math. Math. Phys., 46:12 (2006), 2061–2067 | DOI | MR

[8] A. B. Owen, Variance components and generalized Sobol' indices, Technical report, Stanford University, 2012 | MR

[9] I. M. Sobol', B. V. Shukhman, “Quasi-Monte Carlo: A high-dimensional experiment”, Monte Carlo Methods Appl., 20:3 (2014), 167–171 | DOI | MR | Zbl

[10] B. V. Shukhman, I. M. Sobol', “A limit theorem for average dimensions”, Monte Carlo Methods Appl., 21:2 (2015), 175–178 | DOI | MR | Zbl