Обычный алгоритм Монте-Карло интегрирования
Предположим, требуется вычислить определённый интеграл . Рассмотрим случайную величину , равномерно распределённую на отрезке интегрирования . Тогда также будет случайной величиной, причём её математическое ожидание выражается как
,
где — плотность распределения случайной величины , равная на участке .
Таким образом, искомый интеграл выражается как
.
Но матожидание случайной величины можно легко оценить, смоделировав эту случайную величину и посчитав выборочное среднее.
Итак, бросаем точек, равномерно распределённых на , для каждой точки вычисляем . Затем вычисляем выборочное среднее:
.
В итоге получаем оценку интеграла:
Точность оценки зависит только от количества точек .
Этот метод имеет и геометрическую интерпретацию. Он очень похож на описанный выше детерминистический метод, с той разницей, что вместо равномерного разделения области интегрирования на маленькие интервалы и суммирования площадей получившихся «столбиков» мы забрасываем область интегрирования случайными точками, на каждой из которых строим такой же «столбик», определяя его ширину как , и суммируем их площади.
Рис. 3. Численное интегрирование функции методом Монте-Карло
Для определения площади под графиком функции можно использовать следующий стохастический алгоритм:
v ограничим функцию прямоугольником (n-мерным параллелепипедом в случае многих измерений), площадь которого можно легко вычислить;
v «набросаем» в этот прямоугольник (параллелепипед) некоторое количество точек ( штук), координаты которых будем выбирать случайным образом;
v определим число точек ( штук), которые попадут под график функции;
v площадь области, ограниченной функцией и осями координат, даётся выражением .
Для малого числа измерений интегрируемой функции производительность Монте-Карло интегрирования гораздо ниже, чем производительность детерминированных методов. Тем не менее, в некоторых случаях, когда функция задана неявно, а необходимо определить область, заданную в виде сложных неравенств, стохастический метод может оказаться более предпочтительным.
При том же количестве случайных точек, точность вычислений можно увеличить, приблизив область, ограничивающую искомую функцию, к самой функции. Для этого необходимо использовать случайные величины с распределением, форма которого максимально близка к форме интегрируемой функции. На этом основан один из методов улучшения сходимости в вычислениях методом Монте-Карло: выборка по значимости.