Соболь И.М. Численные методы Монте-Карло (1973) (1186217), страница 17
Текст из файла (страница 17)
2.4. Сравнение трудоемкости алгоритмов Моите-Карло. Из результатов предыдущего пункта напрашивается вывод, что простейший метод !"!опте-!(арло всегда выгоднее геометрического. Однако такой вывод был оы слишком поспешным: хотя вероятная ошибка оценки Ол и лтецьше вероятной ошибки О» при одинаковых Ж, ио время, затрачиваемое па расчет 9, может оказаться гораздо больше времени, затрачиваемого иа расчет Он. 7 И Ы, Соболь 98 в!!'и!слс!и>г иит!>ГР>лов !гл !1 тогда опенка 8«окажется ирак>ичеа<и более эффек>нвиой, чем О,.
Обычно говорят, что «построен метод Моите-Карл»» для расчета интеграла 7 тогда, когда определена опенка вида (1), приближающая!: прп этом обычно предполагается, что !»19=!. Условимся говорить, что «построен алгоритм Монте-Карло>, соответствующий данному методу, если указаны также формулы для моделирования используемых в этол! л>етоде случайных величин. Например, оценка (14) и формула х'=) Я) определяют метод Монте-Карло; чтоГ>ы получить алгоритм Моите-Карло, надо указать еще формулы для расчета точки Я по стандартным случайным числам. Как мы видели в гл. 2, это можно делать различными способами, так что одпп и тот >ко метод Монте-Карло может быть реализован в виде различных алгоритмов. Рассмотрим два алгоритма Моите-Карло (безразлпч. ио соответствуют ли опи разным методам илп одному) для вычисления интеграла Л Пусть в одном алгоритме осредияются значения случайной величины =$'(7!,..., 7.
), а во втоРом $"=$" (уь..., 7„), так что соответствующие оценки интеграла равны й х йк = (1/Лг) ~~ $; и й,е = (17Л>) У $;. (22) Обозначим дисперсии осредпяемых величин через 0'= =ь>й' и 0"=Р$", и пусть 1' и !" — время, затрачиваемое па расчет одного значения $' и соответственно ь". Естественно считать более эффективным тот алгоритм, который требует меньшего времени счета для достижеиия заданной вероятной ошиГ>ки. Для того чтобы вероятная ошибка для первого из сравниваемых алгоритмов равнялась г„,=е, количество Л" осредняемых значений й', согласно (5), должно равняться Л>'= 0'(0,6745/е)з. сп простсишин метод монти карло й 21 Бремя счета при этом окажется равным ('Ьч = КР' (0,6745/е ) '.
'(ля второго алгоритма время счета, необходимое для достижения той же вероятной ошибки е, равно (пЛ("=("Р" (0,5745)е) 2. Назовем тррдоел!костью алгоритма Лйонте-Карло про нзведенне Ж$ дисперсии осредняемой случайной величин й на в!рема ( расчета одного значения $. Тогда время счета, необходимое для достижения заданной вероятной ошибки, ока!кетов пропорциональным трудоемкости алгоритма. Ясно, что пз двух алгоритмов более эффективен менее трудоемюш. Так как трудоемкость используется обычно для сравнения алгоритмов, то вычислять ее можно в любых единицах, в частности, ( можно выражать в секундах, а 5!он!но — в количествах элементарных операций.
Конечно, надо предполагать, что сравниваемые алгоритмы реализуются с помошью одних и тех же вычислительных средств. Кстати, не исключена возможность того, что при переходе к другим средствам вычисления менее тру доемкпй алгоритм станет более трудоемким. П р и ч е р. Вычпсд1пь интеграл 7= ) т'хг(к= —. а 5 Мо:кио считать, что под интегралом стоит также плотиог!г, р(х) = — 1 случайной величины у, Тогда простейший метод приводят к опенке 7 м (1рц) ~! ГI ! .. ! =' 1 Дисперсия осредияемой саучаггиой велпчииы х=(у) равна 15 5 ' 5 ! -= 2'"-(-) =--' о Так как О«' х1)5~~1, то можно воспольэовагься также геометрически! методом: М 7 = (1(У) ~; Ег, где 7, =-1, если у; < (уг) и 21=0 в противном случае.
дисперсиго ° 15 гч Выт!ИГЛЕНИЕ ИНТЕГРАЛОВ юо 1Гл. 3 осредняемой величины ле1 ко вычислить по формуле (20): 6 16) Зб' Таким образом, в полном согласии с (2!), Р2(РУ, Оненим количество операций, затрашваемых на расчет одного значения 31 или 21. Для расчета 21 надо найти одно случайное число у; — три операции — н вычнслнгь(тг) .
На ЭВМ вычисление х 15 15 ос)ществляется путем логарифмирования с помощью стандартных програмлг 1и л и ехр х. Общее колачсство пспольз»емых в таком рас. чете элементарных операций !як 70. Для расчета 2!надо на(1тн два случайных числа тг и уг — шесть операций — и вместо неравенства у; < (у,) проверить равносильное 115 неравенство (т;) < уг. Общее количество элементарных операций '15 в таком расчете (як !О. Значит, ! 02ж!,4, !Рй=!,4 в второй алгоритм оказывается не более трудоемким, чем первый, несмотря на то, что дисперсия Р2 в семь раз больше, чем Р2. Однако тот иге простейший мегод можно реагшзовать с ноьющью другого алгоритма (см. п.
4.! гл. 2). 7 ш (1/й() '~, шах г(!г,; т,; т,; у,; у!Е) ! 1=1 тогда ( 20 и ! Р2ж0,40, гак что трудоемкость этого алгоритма оказывается заметно меньшей. й 3. Важнейшие способы построения хороших оценок (способы уменьшения дисперсии) Из формулы (б) видно, что вероятная ошибка оценки (1) пропорциональна )гР~/Ф. Скорость убывания этой ошноки с ростом Ж невелика. Поэтому очень важно научиться выбирать для расчета интегралов такие вычислительные схемы или, другими словами, такие случайные величины $, для которых дисперсия Р$ по возможности мала.
Часто способы построения таких схем называют способами уменьшения дисперсии, имея ввиду, что для этих способов дисперсия должна быть меньше, чем дисперсия простейшего метода Монте-Карло (п. 2.!). 3.1. Частичное аналитическое интегрирование. Если часть задачи можно решить аналитически, то, используя это частичное решение, обычно удается построить метод спосовы постэовния хогоших оценок 1О1 Монте-Карло для решения всей задачи с дисперсией, меньшей, чем (19). Правда, вообще говоря, построен- ные таким путем методы могут оказаться более трудо- емкими и в конечном счете невыгодными.
Мы будем говорить об аналитическом интегрирова- нии, хотя в некоторых случаях такую же роль может сыграть численное интегрирование, если точность этого интегрирования значительно выше, чем точность метода Монте-Карло. 31.1. Выделение главной части. Это весьма очевидный и весьма общий принцип, относящийся ко всем методам Монте-Карло: если главную часть задачи можно вычислить аналитически, то, как правило, выгод- но считать методом Монте-Карло не всю задачу, а толь- ко «поправку» — разницу между всей задачей и главной частью. Уменьшение дисперсии при этом может оказать- ся очень значительным. Пусть, например, требуется вычислить интеграл (12) 1 = ( ~ (Р) р(Р) 6Р, а где [(Р)~12(6; р), и имеется функция й(Р)енйз(б; р), «близкая» к 1(Р), такая, что значение интеграла ) й(Р) р(Р) дР = С известно. Тогда вместо оценки (14) можно использовать оценку Е„' - С + (Ьу) ~ У Оу,) й (О,)[, (2З) ! ! пбо математическое ожидание осредняемой величины Л'= С+) (Я) — й Я) равно МИ=С+1 — С=В Дисперсия «.' в этом случае равна 02' = )[~ (Р) — й (Р)[«р (Р) ЙР— (1 — С)'.
о Если й(Р) настолько близка к [(Р), что ) [)' (Р) — й (Р)[» р (Р) ~(Р ( с, то, очевидно, и РЛ'е~е. !гч з 102 вычисление интегралов П р и м е р. Вычислить интеграл ! 7= [е !(.т, О рассмотренный в п. 2.3. Так как е =1+х+..., то выберем В(х) =х (постоянное слагаемое на лисперсию не влияет). бог,!асио (23) получим расчетную формулу и 0 = (172)+ (1)!У) У (ет! — т!). ~=-! Дисперсия осрелняемоа величины Д'=1)2-,' ет — у равна 1 (>2' = [ (е" — х)т ч(х — (! — 172)' = (е — 1) (5 — е))2— Π— 237!2 — 0,0137 и значительно меньше, чем 02 и (>2 в п. 2.3.
Общие правила выделения главной части указать трудно: в различных задачах это делается по-разному. Например, при расчете больших сцинтилляционных детекторов необходимо учитывать многократно рассеянные нейтроны (их вклад в световыход составляет до !Оо(О). В. Г. Золотухину с сотрудниками [37[ удалось добиться значительного увеличения точности метода Монте-Карло путем аналитического учета вклада нерассеянных и однократно рассеянных нейтронов. В ряде областей физики используют теорию возмущений, которая позволяет оцепить решение сложной задачи по известному решению «близкой» простой задачи. Если рассчитывать методом Моите-Карло пе всю сложную задачу, а только интегралы теории возмущений, то можно значительно повысить точность результатов [57!.
312, Интегрирование по ча стн области. Допустим, что мы умеем (аналнтиг>ески) вычислить интегралы по некоторой части В области Сц [7(Р) р(Р) г(Р=- С, [Р(Р)г(Р= с, где О«"с~!. Докажем, что, как правило, всегда вы~одно представить интеграл (!2) в виде суммы ! =- ['! (Р) Р(Р) г(Р -'; С (24) с, ! з! СПОСОБЫ ПОСТРОЕПИЯ ХОРОШНХ ОЦЕ!ЮК !Оз н вычислять простейшим методом только интеграл по области 6~=6 — В. (Если С близко к l, то можно считать, что мы выделяем главную часть; по данный прием у выгоден и тогда, когда область В заметно меньше, чем 6 в (рпс.
Зб); правда, и понижение дисперсии в этом случае Ю будет заметно меньше.) В области 61 определим плотность р1(Р) = р (Р) /(1 — г) и рассмотрим случайную величину Рнс, 35. 2'= С+ (1 — с) ! (О'), где Я' — случайная точка с плотностью р~(Р) в 6ь Легко видеть, что МЛ'=Е Поэтому для расчета т' можно использовать оценку бв = С+ (1уй!) (1 — с) ~' ((4) (25) ;=-1 где Яь ° Яч — независимые реализации точки 6'. Чтобы сравнить эту оценку с оценкой (14), сравшьм дисперсии 07' и 07, где 2=1(Я). Т е о р е м а 1. Егли существует дисперсия 02, то 02' = (1 — с)02. (26) Д о к а з а т е л ь с т в о. Согласно определению дис~персии 02 = ~~ар ДР— )с = ~ (эр ДР + а) гсср ДР— Тх, в в,' 02' = (1 — с)' ) !'Р,ДР— ((! — с) ~(р,дР~ = с, в, = (1 г) ! !2рДР И!РДР1 . и, Умножив 02 на 1 — с и вычти 02', получим, что (1 — с) 02 — 0Т = (! — с) ~ )ср ДР— (1 — с) (э + (1 — С)'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
