Введение

Численная техника

В математике, интегрирование Монте-Карло – это метод численного интегрирования с использованием случайных чисел. Это конкретный метод Монте-Карло, который численно вычисляет определенный интеграл. В то время как другие алгоритмы обычно вычисляют подынтегральную функцию в регулярной сетке, метод Монте-Карло случайным образом выбирает точки, в которых вычисляется подынтегральная функция. Этот метод особенно полезен для многомерных интегралов. При заданных N равномерных выборках,

I может быть приближенно вычислен как

Это связано с тем, что закон больших чисел гарантирует, что

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

Пока последовательность

ограничена, эта дисперсия асимптотически стремится к нулю как 1/N. Таким образом, оценка ошибки QN выглядит следующим образом:

которая уменьшается как Это стандартная ошибка среднего, умноженная на Этот результат не зависит от числа измерений интеграла, что является ключевым преимуществом интегрирования Монте-Карло перед большинством детерминированных методов, которые экспоненциально зависят от размерности. Важно отметить, что, в отличие от детерминированных методов, оценка ошибки не является строгим ограничением; случайная выборка может не выявить все важные особенности подынтегральной функции, что может привести к занижению оценки ошибки. В то время как наивный метод Монте-Карло работает для простых примеров, улучшение по сравнению с детерминированными алгоритмами возможно только с использованием алгоритмов, которые применяют распределения выборки, специфичные для решаемой задачи. Используя подходящее распределение выборки, можно использовать тот факт, что почти все многомерные подынтегральные функции сильно локализованы, и только небольшое подпространство существенно вносит вклад в интеграл. Большая часть литературы по методу Монте-Карло посвящена разработке стратегий для улучшения оценок ошибок. В частности, стратифицированная выборка – разделение области на подобласти – и важностная выборка – выборка из неравномерных распределений – являются двумя примерами таких методов.

Рекурсивный стратифицированный отбор проб

Рекурсивное стратифицированное семплирование является обобщением одномерных адаптивных квадратур на многомерные интегралы. На каждом шаге рекурсии интеграл и ошибка оцениваются с использованием обычного алгоритма Монте-Карло. Если оценка ошибки превышает требуемую точность, область интегрирования разделяется на подинтервалы, и процедура рекурсивно применяется к этим подинтервалам. Обычная стратегия "деления пополам" неэффективна в многомерном случае, поскольку число подинтервалов растет слишком быстро для отслеживания. Вместо этого оценивается, по какому измерению разбиение принесет наибольшую выгоду, и разбиение выполняется только вдоль этого измерения. Алгоритм стратифицированного семплирования концентрирует точки семплирования в областях с наибольшей дисперсией функции, тем самым уменьшая общую дисперсию и повышая эффективность семплирования, как показано на иллюстрации. Популярная процедура MISER реализует аналогичный алгоритм.