§ 10. Ускорение сходимости метода Монте-Карло

Рассмотрим некоторые приемы повышения практической эффективности метода Монте-Карло.

1. Функция представляется в виде

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

2. Подходящий подбор плотности распределения узлов (см. задачу 3 в § 8) также приводит к уменьшению дисперсии. Мы рассматривали случай, когда все узлы имеют одинаковую функцию распределения . В ряде случаев оказывается целесообразным выбирать узлы интегрирования таким образом, чтобы каждый имел своею функцию распределения .

3. Следующий прием является частным случаем приемов 1 и 2. Исходный интеграл представляется в виде суммы интегралов

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

Конечно, случай, когда исходную область интегрирования удается разбить на части, где подынтегральная функция постоянна, очень редкий. Однако, если все-таки удается разбить ее на части, где функция меняется мало, то можно получить существенное увеличение точности при том же объеме вычислений.

Рис. 5.10.1

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

В случае гладкой подынтегральной функции разбиение области интегрирования на части приводит к увеличению порядка скорости сходимости. Пусть вычисляется интеграл

Положим и разобьем исходную область интегрирования на равные кубы . В каждом кубе выберем случайную точку . Считаем, что ее плотность распределения — постоянная, равная , и случайные точки в любых двух кубах выбираются независимо. Положим

Задача 1. Доказать, что .

Проведем оценку дисперсии в предположении, что функция удовлетворяет условию Липшица с постоянной А по каждой из переменных. Справедливо равенство

Имеем равенство

На основании теоремы о среднем имеем , где поэтому

В то же время

Отсюда следует, что для функций рассматриваемого класса

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

при , и, следовательно,

Всякая случайная величина удовлетворяет неравенству

Следовательно,

С помощью этой оценки заключаем, что правая часть равенства (1) не превосходит величины

Обозначив общее число узлов через , получаем оценку

Отсюда на основании неравенства Чебышева (8.1) заключаем, что с вероятностью выполняется неравенство

Полученная оценка погрешности по порядку лучше, чем оценка погрешности метода Монте-Карло.

Мы получили оценку погрешности по вероятности. Оказывается, что для рассматриваемого метода можно получить и гарантированную оценку погрешности. Умножая (2) на , получаем неравенство

Величина может быть представлена в виде суммы таких слагаемых:

Суммируя оценки для этих слагаемых, получим

Сопоставляя эту оценку с теоремой из § 7, заключаем, что рассматриваемый метод имеет гарантированную оценку погрешности, оптимальную по порядку на рассматриваемом классе функций.

Возникает вопрос, можно ли улучшить на этом классе оценку дисперсии (3). Метод Монте-Карло и другие способы интегрирования, подобные рассматриваемому, где приближенное значение интеграла зависит от некоторых случайных параметров, называют недетерминированными. Пусть — приближенное значение интеграла , получаемое при применении некоторого недетерминированного способа вычисления.

Теорема (без доказательства). Существуют удовлетворяющие следующему соотношению. Для любого способа вычисления интеграла, где информация о подынтегральной функции используется лишь как информация об ее значениях в N точках, найдется функция , для которой

с вероятностью , где — приближенное значение интеграла.

Следствием неравенства (4) является неравенство

которое, в частности, означает, что оценка (3) не может быть улучшена по порядку.

Теорема (без доказательства). Можно указать способы интегрирования, для которых имеет место гарантированная оценка погрешности

и одновременно

для всех .

Мы построили выше такой способ при . Идея построения таких способов состоит в разбиении исходной области интегрирования на малые части и вычислении интеграла по малой части при помощи некоторой «случайной квадратурной формулы».

Задача 2. Пусть случайная точка в кубе (при тех же условиях на распределение и независимость точек , как в задаче 1). Обозначим через точку, симметричную относительно центра куба , и положим

Доказать, что для функции из класса выполнены одновременно оценки (6), (7). (Заметим, что здесь ).