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

3.1.2. Интегрирование по части области.

Допустим, что мы умеем (аналитически) вычислить интегралы по некоторой части В области G:

где . Докажем, что, как правило, всегда выгодно представить интеграл (12) в виде суммы

и вычислять простейшим методом только интеграл по области . (Если С близко к то можно считать, что мы выделяем главную часть; по данный прием выгоден и тогда, когда область В заметно меньше, чем G (рис. 35); правда, и понижение дисперсии в этом случае будет заметно меньше.)

Рис. 35.

В области определим плотность и рассмотрим случайную величину

где Q — случайная точка с плотностью . Легко видеть, что Поэтому для расчета можно использовать оценку

где - независимые реализации точки Q. Чтобы сравнить эту оценку с оценкой (14), сравним дисперсии , где

Теорема 1. Если существует дисперсия , то

Доказательство. Согласно определению дисперсии

Умножив на и вычтя , получим, что

Оставшийся интеграл по области В выразим через неотрицательную величину

Тогда окажется, что

что и требовалось доказать.

Предположим, что задан какой-либо алгоритм расчета точек Q в G. Тогда трудоемкость алгоритма (14) равна где время расчета одной точки Q, а время расчета одного значения .

Рассмотрим оценку (25). Если никакого более удобного способа моделирования точек Q в пет, то можно отбирать точки Q среди точек Q (п. 5.2 гл. 2). Эффективность такого отбора . Поэтому время расчета одной точки Q в среднем равно , где - время, затрачиваемое на отбор (т. е. на проверку условия ). Трудоемкость алгоритма (25) в этих условиях равна

Легко доказать, что если

то трудоемкость алгоритма не больше, чем трудоемкость алгоритма (14). В самом деле,

Условие (27) легко проверяется на практике. Если область В «простая», а функция «сложная», то, очевидно,

Рис. 36.

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

где

Обозначим через вписанный в V и описанный около V шары, радиусы которых равны Объемы будем обозначать темп же буквами. Воспользуемся геометрическим методом: выберем случайные точки равномерно распределенные в и если v из этих точек попадут внутрь V, то будем считать, что объем V приближенно равен

Выделим теперь объем шара . Для этого достаточно выбрать случайные точки равномерно распределенные в шаровом слое ; если v из этих точек принадлежат V, то объем V приближенно равен

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

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

пропорциональна , а величина

второго порядка малости.

Наконец, покажем, что если моделировать точки в сферических координатах (п. 2.4.1 гл. 2), то алгоритмы, соответствующие обоим рассмотренным методам, примерно одинаково сложны:

В самом деле, в обоих случаях для испытания нужны три случайных числа Координаты точек и вычисляются соответственно по формулам

или

где . Условие принадлежности точки объему V проверяется одинаково: это условие выполнено, то к счетчику v (соответственно v) добавляется единица.

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