геометрический алгоритм Монте-Карло интегрирования

Когда говорят о интегрировании методом Монте-Карло, обычно подразумевают метод, при котором область интегрирования [a, b] делится случайным образом на участки шириной (a — b)/N, где N — количество случайных точек, и затем площадь получившихся столбиков суммируется. Формула для вычисления интеграла этим методом выглядит так:

Однако есть еще иной геометрический метод Монте-Карло, удивительный по своей простоте и эффективности.

Для этого метода нужно взять область интегрирования [a, b], ограничить ее прямоугольником с площадью Spar и набросать в этот прямоугольник случайным образом точек. Затем требуется посчитать количество точек K попавших в область под графиком функции и вычислить интеграл (площадь под кривой S) по формуле:

При этом, чем больше будет значение N, тем точнее окажется аппроксимация.

Для примера попробую посчитать этим методом интеграл функции f(x) = sin(x) / 2 на отрезке [0, 2]. При этом значение интеграла должно получиться приблизительно равным 0.708074.

Ограничиваю область интегрирования прямоугольником размером 2 x 1.5:

и вбрасываю сотню точек со случайными координатами. Повторяю этот эксперимент 20 раз. На изображении здесь и ниже показан один из 20 результатов:

При таком малом количестве точек значение предсказуемо бессовестно скачет от 0.51 до 0.99, со средним 0.735 и такой же медианой.

Увеличиваю количество точек в сто раз до 10000:

Разброс значений теперь становится значительно меньше: между 0.6849 и 0.732, со средним 0.705825 и медианой 0.7077.

Увеличиваю количество точек еще в сто раз до миллиона:

Миллион точек на изображении превращается в сплошную заливку прямоугольника. Разброс значений оказывается между 0.705135 и 0.709499, со средним 0.70764705 и медианой 0.7075275.

Последняя череда экспериментов со ста миллионами точек:

Точность результатов повышается, диапазон значений оказывается между 0.70788846 и 0.70843821. Среднее значение 0.708100675 и медиана 0.70808943.

Как видно из результатов этого простого эксперимента, этот метод можно использовать для вычисления интеграла. Более или менее приемлемая точность для искомых шести знаков после запятой появляется только в эксперименте со ста миллионами точек. При этом оказалось, что в моём случае наиболее близко к искомому значению оказалось значение медианы двадцати экспериментов.

Для того, чтобы повысить точность, нужно увеличивать количество точек. Однако это становится вычислительно затратно. Уже для ста миллионов точек каждый эксперимент на ноутбуке середины 2015 года с процессором core i7 считается около трёх минут. Для сравнения при помощи scipy.integrate этот же интеграл вычисляется за несколько сотен наносекунд.

Еще точность можно повысить уменьшением ограничивающей площади, максимально приблизив ее к самой функции.

Конечно, никто в здравом уме для таких простых интегралов этот алгоритм использовать не будет, однако существуют такие ситуации, при которых обычные детерменированные методы становится сложно или невозможно использовать. Тогда на помощь приходит Монте-Карло. Пример из википедии: “когда функция задана неявно, а необходимо определить область, заданную в виде сложных неравенств, стохастический метод может оказаться более предпочтительным.”

https://ru.wikipedia.org/wiki/Метод_Монте-Карло
https://www.integral-calculator.com