Stochastic numerical algorithm

A numerical algorithm that includes operations with random numbers, with the result that the outcome of the calculation is random. Stochastic algorithms include algorithms of statistical modelling used in the numerical research into random processes and phenomena, and algorithms of the Monte-Carlo method for solving deterministic problems: the calculation of integrals, the solution of integral equations, boundary value problems, etc.

Randomized numerical procedures of interpolation and quadrature formulas with random nodes constitute a particular class of stochastic numerical algorithms. The randomization is usually carried out in such a way that the mathematical expectation of the result of the calculation is equal to the required value. The final estimate is obtained by averaging the results of various realizations of stochastic numerical algorithms (for the error and amount of calculation in these estimates, see Monte-Carlo method). For problems of large dimensions, randomization can make a considerable saving in computer memory time (see [1]–[4]). This is shown in particular by estimates of the amount of calculation in a randomized method of finite sums for solving integral equations of the second kind (see [4]). Particularly effective are those stochastic numerical algorithms that allow a number of realizations of the algorithm to be made simultaneously when a multi-processor calculating system is used.

Special stochastic numerical algorithms have been constructed for the realization of a random search for a global extremum of a function in several variables (see [5]). These algorithms are relatively effective if the value of the function is defined with a random error.

References

[1]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[2]	S.M. Ermakov, "Die Monte-Carlo Methode und verwandte Fragen" , Deutsch. Verlag Wissenschaft. (1975) (Translated from Russian)
[3]	I.M. Sobol', "Numerical Monte-Carlo methods" , Moscow (1973) (In Russian)
[4]	G.A. Mikhailov, "Some questions in the theory of Monte-Carlo methods" , Novosibirsk (1971) (In Russian)
[5]	L.A. Rastrigin, "Statistical search methods" , Moscow (1968) (In Russian)

Comments

One can distinguish between problems which are stochastic by nature and problems which are not. For numerical algorithms with respect to the first class of problems, see e.g. [a1], [a2] and Stochastic approximation. Random search for the global extremum of a function has attracted a lot of attention; it belongs to the second class. See [a3]–[a5].

Random methods can be very effective for the classical equations of mathematical physics, partly because of the connections between potential theory and stochastics, cf. [a6], [a7].

References

[a1]	L. Ljung, T. Söderström, "Theory and practice of recursive identification" , M.I.T. (1983)
[a2]	H. Robbins, S. Monro, "A stochastic approximation method" Ann. Math. Studies , 22 (1951) pp. 400–407
[a3]	P.J.M. van Laarhoven, "Theoretical and computational aspect of simulated annealing" , CWI Tracts , 51 , CWI , Amsterdam (1988)
[a4]	A.A. [A.A. Zhiglyavskii] Zhigljavsky, "Theory of global random search" , Kluwer (1991) (Translated from Russian)
[a5]	P.J.M. van Laarhoven, E.H. Aarts, "Simulated annealing: theory and practice" , Reidel (1987)
[a6]	R.M. Blumenthal, R.K. Getoor, "Markov processes and potential theory" , Acad. Press (1968)
[a7]	V.V. Nekrutin, "Random processes for the classical equations for mathematical physics" , Kluwer (1989) (Translated from Russian)