Главная > Математика > Численные методы Монте-Карло
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.2. Метод существенной выборки.

До сих пор мы рассматривали интегралы вида (12) и использовали при вычислении их случайные точки с плотностью Предположим теперь, что требуется вычислить абсолютно сходящийся интеграл

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

3.2.1. Плотность определенную в G, назовем допустимой по отношению к если в тех точках, в которых

Если всюду в G, то эта плотность допустима по отношению к любым . Вообще же допустимая плотность может обращаться в пуль, но только там, где Множество точек, в которых назовем и пусть

Выберем произвольную допустимую плотность и рассмотрим функцию

Если Q — случайная точка, определенная в G с плотностью , то

ибо вне множества функция .

Согласно п. 2.1 для приближенного расчета можно использовать независимые реализации случайной точки Q и оценку

Вероятная ошибка этой оценки зависит от дисперсии которую нетрудно вычислить: так как

то

Величина эта зависит от выбора плотности и даже не обязательно конечна. Естественно поставить вопрос о выборе так, чтобы минимизировать

Теорема 3. Минимальная дисперсия реализуется в случае, когда плотность пропорциональна и равна

Доказательство. Если плотность пропорциональна она равна

Подставив (31) в (29), получим, что

Осталось доказать, что, какова бы ни была допустимая плотность дисперсия . А это легко доказывается с помощью неравенства (1), стр. 292:

Следствие. Если подынтегральная функция не меняет знака в , то, .

Отметим, что плотность тождественно равна нулю в области в которой Этот результат согласуется с выводом из теоремы 1, что область, в которой выгодно при интегрировании исключить.

В действительности использовать плотность (31) для расчета интеграла (28) нельзя, ибо в (31) входит значение вычисление которого представляет собой задачу, эквивалентную по трудности исходной задаче (в случае знакопостоянной функции — в точности эквивалентную). Однако из теоремы 3 можно сделать вывод, что желательно выбирать плотность по возможности пропорциональной . Такой метод выбора часто приводит к величинам с небольшими дисперсиями. Он был предложен Г. Капом [142] и называется методом существенной выборки (importance sampling), ибо если пропорциональна то в тех частях области G, в которых больше и вклад которых в более существен, будет выбираться больше случайных точек.

Возможна и другая интерпретация целесообразности выбора пропорционально случае знакопостоянной : чем ближе к постоянной, тем меньше дисперсия

Очень сложные плотности использовать не рекомендуется, так как тогда процесс реализации случайных точек Q с плотностью станет очень трудоемким. Заметим, что для вычисления интеграла

не обязательно использовать оценку можно применить какой-нибудь из методов п. 3.1.

Пример. Интеграл

рассмотренный в пп. 2 3 и 3.1.1, можно представить в виде

где . Значения случайной величины с плотностью вычисляются по формуле (метод обратных функций), а оценка равна

В этом примере дисперсия осредняемой величины равна

Это гораздо меньше, чем в п. 2.3, и меньше, чем в п. 3.1.1.

3.2.2. Метод существенной выборки позволяет строить хор яиие оценки для несобственных интегралов (28). Предположим, что область G ограничена, но

В этом случае простейший метод Монте-Карло позволяет записать оценку интеграла (28)

где точки равномерно распределены в G, a — объем G. Однако оценка эта плохая, ибо . В то же время оценка, полученная методом существенной выборки будет иметь конечную дисперсию, если выбрать допустимую плотность так, чтобы интеграл, фигурирующий в выражении (29), сходился. Такие плотности всегда существуют. В частности, этому требованию удовлетворяет плотность (31).

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

Предположим теперь, что функция в (28) особенностей не имеет, но область интегрирования G неограничепа. Чтобы оценить такой интеграл, можно

выбрать ограниченную область так, что

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

3.2.3. Один тип интегралов с особенностью. Обозначим через G шар Во многих разделах физики и механики встречаются интегралы вида

где обе точки принадлежат расстояние между этими точками:

Рассмотрим интеграл такого типа с особенностью

где функция ограничена и Интеграл (33) абсолютно сходится при

А. Для того чтобы вычислить интеграл (33) простейшим методом Монте-Карло, выберем две независимые случайные точки равномерно распределенные в G. Так как плотности их то положим Тогда а дисперсия Z равна

При последний интеграл расходится и

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

Для определения перенесем начало координат в точку Р и выберем сферические координаты с центром в Р (рис. 38). Направление (из точки Р) условимся задавать единичным вектором , а расстояние по этому направлению от точки Р до границы шара G назовем Пусть

где

Нетрудно проверить, что формула (34) действительно определяет условную плотность вероятностей: при любой фиксированной точке Р

Рассмотрим скалярную случайную величину

где . Нетрудно вычислить, что

a дисперсия этой величины равна

Так как функция ограничена, не превосходит диаметра шара G, то последний интеграл сходится, и дисперсия DZ конечна при всех

В. Из-за симметрии задачи интеграл (33) может быть сведен к трехкратному. В расчетной схеме методов Монте-Карло этот факт учитывается «автоматически», если при реализации случайных точек принимать во внимание симметрию. Чтобы показать это выведем расчетные формулы для обоих способов расчета .

Рис. 38.

Сферические координаты точки Q в обоих случаях можно вычислять по формулам (14) гл. 2. Однако из соображений симметрии ясно, что точку Q можно выбрать на оси

Поэтому положим

В способе А точка Q также равномерно распределена в G. Из соображений симметрии ясно, что можно ее выбирать в плоскости и считать, что

где

Получаем следующий алгоритм для расчета методом А:

1) Формулы для испытания

2) Если — значение , полученное в испытании, то

В способе Б случайную точку Q с плотностью (34) можно строить следующим образом: сперва из точки Q надо выбрать случайное направление (п. 2.4.2 гл. 2); затем на луче выбрать случайное расстояние с функцией распределения (где ); тогда

В самом деле, условная плотность точки Q (при условии в сферических координатах о центром в Р равна

Рис. 39.

Первый сомножитель равен плотности случайного направления (в сферических координатах), а второй — это условная плотность случайного расстояния на луче при условии, что со уже выбрано.

Те же соображения симметрии, что в случае А, позволяют выбирать направление в плоскости Оно определяется одним параметром . Вычислив расстояние получим следующий алгоритм для расчета I методом Б:

1) Формулы для испытания

2) Если значения , полученные в испытании. то

В обоих алгоритмах — (35) и (36) — на каждое испытание затрачивается всего три случайных числа, так что фактически вычисляется

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

Г. Рассмотрим численный пример: интеграл (33) в случае

где единичный шар Некоторые значения этого интеграла:

Запишем оценки (35) и (36) для

Нетрудно заметить, что в этом случае оценка зависит лишь от двух случайных чисел.

Вычислим дисперсии соответствующих этим методам величин приведены в пунктах А и Б):

откуда следует, что . Для оценок типа Б

Пусть , так что . Тогда

откуда следует, что . Интересно отмстить, что Этот пример показывает, что неудачное использование существенной выборки приводит к увеличению дисперсии.

Таблица 1

В табл. 1 приведены результаты расчета всех четырех оценок при с использованием случайных чисел, указанных на стр. 108. Здесь же указаны ошибки расчета и вероятные ошибки

<< Предыдущий параграф Следующий параграф >>
Оглавление