Соболь И.М. Численные методы Монте-Карло (1973) (1186217), страница 18
Текст из файла (страница 18)
в Оставшийся интеграл по области В выразим через неотрицательную величину бт = — ! (1 — С(г" р ДР = ( 1'р ДР— Сэ!с. в в 104 вычисление интегралов !Гл, з Тогда окажется, что (1 — с) Р2 — РЯ' = (1 — с) (гт + (')'с!' — С /3 с) >О, что и требовалось доказать. Предположим, что задан какой-либо алгоритм расчета точек („г в 6. Тогда трудоемкость алгоритма (!4) равна (Го+1!)РЛ, где Уо — время расчета одной точки (,), а 1,— время расчета одного значения !Я). Рассмотрим оценку (25).
Если никакого более удобпого способа моделирования точек ()' в 6! пет, то можио отбирать точки Я' среди точек (;) (и. 5.2 гл. 2). Эффективность такого отбора э=РЯЕ=О!) =! — с. Поэтому время расчета одной точки Я' в среднем равно (ч.= = ((о+(о)/(1 — с), где (о —.время, затрачиваемое иа отбор (т. е. На проверку условия ()ееб!). Трудоемкость алгоритма (25) в этих условиях равна ((е.=сс) РЛ'. Легко доказать, что если (о < с(г, (27) то трудоемкость алгоритма (25) пе больше, чеы трудоемкость алгоритма (14).
В самом деле, ((о + (г) Рг ~ 1((о+ с(,),((1 — с)+ (у) Рг ~((, + У,) Ю. Условие (27) легко проверяется на практике. Если область В «простая», а функция 1(Р) «сложиая», то, очевидно, 1,))(.. П р и и е р. Требуется вычислить объем фигуры У, ограниченной поверхностью (в сферических координатах) г=а+/си(ср, О), где — 1~и(ср, О) (1 (рнс. Зб).
Обозначим через 1'о и Ус вписанный в У н описанньш около У шары, радиусы которых равны а — й и а+Ь, Объемы Уе, У, будем обозначать теми Рнс. 36. же буквами. Воспользуемся геометрическим методом: выберем случайные точки Щс,...> Сей, равномерно распределенные в Уь и если ч из этих точек попадут внутрь У, то будем считать, что объем У приближенно равен е„=у,( уу). й з1 спосоиы ~ОстРОеиия хОРОших Опииок 105 Выделим теперь объем шара У,. Для этого достаточно выбрать случайные точки О|,...~ |)и, равномерно распределенные в шаровом слое У| — Уа', если т' иэ этих точек прянадлежат У, то объем У приближенно равен огт Уа+ (Уа — Уе) (т /Ьг) г Выссго сравнения дисперсий осредняемых величин сравним в этом примере дисперсии самих оценок.
Тах как и и и' подчиняются бино. миальным распределениям с параметрами р=У/У, и соответственно р'=(!' — Уо)/(У~ — Уо), то Рт=мр(1 — р), Ртг=ыр'(1 — р). Поэтому Рел — — (!/Л) У(Ь', — У), РОм (1/!У) (У вЂ” Уэ) (У, — У). Очевидно, всегда РОвг ч.
РО|т. Если отношение е Ь/а<1, то в оцепке7м мы фактически выделяем главную часть задача, н уменьшение дисперсии Рйм по сравнению с РО|т должяо быть особенно заметным. Действительно, так кан Уэ=(4/3)п(а — Ь)', У| (4/3)п(а+Ь)', то ьюжно записать, что У= (4/3)п(а+иаЛ)', где )иэ) ~1. Тогда нетрудно сосчитать, что величияа У(У, — У) = ((4/3) паз) '3(! — иэ) в+О (в ) пропорциональна е, а величина (У вЂ” Уэ) (!гг — У) = [(4/3) паз)з 9 (1 — но~) ат + О (аз) — второго порядка ыалости. Наконец, пока|кем, что если моделировать точки О в !/' в сферических координатах (и. 2,4.1 гл.
2), то алгоритмы, соответствующие обоим рассьютрениым методам, примерно одинаково сложны: !т!. В самом деле, в обоих случаях для |-го испытания нужны три случайных числа т„т| т;.!(оординаты точек О! н О;вычисляются соответственно по формулам г,.= (а-1-Ь) У у| |р,=2пт,, созе 2у — 1 илн 3 г =('+ Ь) у у|+ Ь(! тг) <рг йпу|, созе| 2у! 1' где Ь=(а — Ь)'/(а+Ь)'. Условие принадлежности точки Фили объемУ У пРовеРЯетса одинаково|гг( а+/и (|РР Ог). Если это Условие выполнено, то к счетчику т (соответственно и') добавляется единица. 3.!.3. И н т е г р и р о в а н и е п о ч а с т и и е р е м е нных (понижение порядка интеграла). Докажем, что если аналитически взять интеграл по некоторым из переменных, а по остальным переменным использовать тот же метод Монте-Карло, то дисперсия уменьшится (!43). Правда, в отличие от случая, рассмотрен- Вычисление пнгвгРАлов 1оа !ГЛ 3 ного в п.
3.1.2, нередко бывает, что после интегрирования по некоторым нз переменных получаются более сложные формулы счета и, несмотря на уменьшение дисперсии, трудоемкость возрастает, Перейдем к точной формулировке задачи. Пусть требуется вычислить интеграл г' = ') дР ),г(Р, Р') р(Р, Р') дР', а а где р(Р, Р') — совместная плотность вероятностей случайных точек Яенб и Я'анб', О р(Р,Р')дРдР'=1. аа Если интеграл этот вычислять простейшим методом, то осредняемая случайная величина с=)(Я, Я'). Предположим, что по переменному Р' мы умеем выполнить интегрирование н можем вычислить плотность точки Я: р,(Р) = ~ р(Р, Р') дР', а также функцию (Р) — ) ~(Р Р)Р(Р Р)дР (о (Р) а' Тогда, очевидно, ) — ) / (Р) Р (Р)дР а и если вычислять простейшим методом этот интеграл, то придется осреднять величину Г=~,Я).
Те ар е м а 2. Если дисперсия РЯ конечна, то РЛ'( ' Од. Д о к а з а т е л ь с т в о. Воспользуемся неравенством (1) на стр. 292. (р,(Р)),(Р))'= ~~) ~ р )'рдР ~ ~ ~~ердР ~ рг(Р. '( а' а а' Отсюда следует, что (1 (Р) р (Р) ~ 1" (Р, Р ) р (Р, Р ) дР . Г 4 з) спОсОБИ постРОшп(я хОРОших О(зг(гок РО? 1 =- ) Д (1!у) (1х (1у где область пптегрировапия В представляет (об*зй треугольник, ограниченный прямыми у = 1, х=2 и у=х (рис. 37).
Интеграл этот лсгко вычисляется; г к ! .=1бх1 у-(Ду =1'1пхбх = ! 1 ! ю Рис. 37. = 2 1п 2 — 1 =- 0,38630. А. ВасдСМ СЛуЧайНуЮ тОЮ(у (3, и), ПЛО(ИОСтЬ КОтсрОй р(Х, у)мв2 в В. Тогда ?=МЛ, где 2= (20) ', а дисперсия 2 к 03 = ) пх ) 2 'у г (1у — Р = (1/2) (? 1п 2 — 1) — 4 1п' 2 = О 0043.
! ! Так как плотпость р, (у) =2(2 — у), то пз уравнения Еч (Ч) = 1 — у "о"Учи!' что (1=2 ) у, Следовательно, оценка интеграла 1 равна У Огг —— (2У) ! ~~~ '(2 — )/ у() ~=! Б. Проинтегрируем аналитически плотность и подыптегральпую функцию по у: к к р,(,т) = ~ 2(1у=-(х — 1), р,(х) )(х)=) (1?у)((у= !пх. ! ! В этом случае функция распредслеиия к равна Е((х) =(х — 1)'. Из уравнения Е((с) =у следует, что 5=1+Ту. Так как осредияемая ве.
личина Л'=)((Б) =2-(Я вЂ” 1)-'!и Ц, то оценка интеграла и 0' =(2А)-! ~~ — Пг!п (1+ !12) (=! Лисперсия в этом ел!чае равна 02' = ~ 2 ((х — 1) ' !пз х((х — Р = 0,15О25 — 0,14923 = 0,0010, ! Проинтегрировав зто иерааепстпо по Р, получим, что ~ )! (Р) Р! (Р) ()Р ~ ~((Р ~ )г(Р Р') Р (Р, Р') ()Р', о о пли, что то Хке, М (Гг) ( М (Лг). Так как М Г=М7=), то тем самым доказано, что )зл'~Ос. П р н и е р.
Рассыотрнм интеграл ЮБ Вычисление иитеглллов ил 3 В. Из первых цифр табл. 4 (стр. 295) образуем десять случайных чисел и вычислим по ним значения Ом и Ойв. Случайные числа: у~ 086515, ув — 090?95, уз=066155, ув=066434, уз=056558, уз=0,12332, уз=094337, уз=057802 уз=069186, у~в=003393. Сосчитанные по пнм значения: О~а=0408.
Оло=0,378. Ошибки этих значений 01в — 1=0,022 и Ойв — 1=0,008 близки к соот- ветствующим вероятным ошибкам Ов=0,014 и гва — — 0,007. 3.2. Метод существенной выборки. До сих пор мы рассматривали интегралы вида (12) и использовали при вычислении их случайные точки с плотностью р(Р). Предположим теперь, что требуется вычислить абсолютно сходящийся интеграл 1о = ) ?' (Р) дР, (28) )7 (Р)?р (Р) прн Р 8= 6+, 0 прн Р с= 6в.
Если Я вЂ” случайная точка, определенная в 6 с плотностью р(Р), то МЯа(Я) = ) 7а(Р) р(Р) йР = ~~(Р) йР = 1,, ибо вне множества 6' функция 1(Р) =О. где область 6 может быть как ограниченной, так и неограниченной, и квадрат функции 1(Р) не обязательно интегрируем. Предполагается только, что )))(Р)(с(Р)0. 3.2.!. Плотность р(Р), определенную в 6, назовем допустимой по отношению н '1(Р), если р(Р))0 в тех точках, в которых 1(Р) 4=0. Если р(Р))0 всюду в 6, то зта плотность допустима по отношению к любым 1(Р). Вообще же допустимая плотность может обращаться в пуль, ио только там, где )(Р) =О. Множество точек, в которых )(Р) =О, назовел1 6о н пусть 6'= 6 — 6о. Выберем произвольную допустил1ую плотность р(Р) и рассмотрим функцию % З! спОсОБы постРОБнпя хОРОшщ!х ОпгпОК юэ Согласно п.
2.1 для приближенного расчета 1ь можно использовать независимые реализации !г!,..., Я. случайной точки Я и оценку Ен = ()1А),'Р 7„(а). Вероятная ошибка этой оценки зависит от дисперсии ь!г',БЯ), которую нетрудно вычислит!н так как Оль = ~ль(Р) Р(Р) дР— 1',, о то О~ = ~('(Р)1Р(Р))дР— 1ь. (29) Величина эта зависит от выбора плотности р(Р) и даже пе обязательно конечна. Естественно поставить вопрос о выборе р(Р) .так, чтобы минимизировать Р7ь.