Соболь И.М. Численные методы Монте-Карло (1973) (1186217), страница 41
Текст из файла (страница 41)
2 — 6 книги, сохраняют свою силу независимо от того, какие псевдослучайные числа предполагается использовать. Твк что говорить о гибели методов Моите. Карло вряд ли стоит. Можно не сомневаться, что и для других методов Монте-Карло (например, связанных с расчетом средних по одной зргодпчной траектории) будут найдены достаточно удобные квазпслучайиые числа. З ц кОнстРуктиВнАя РАзмеРнОсть АлгоРитмоВ 255 Таким образом, формулы (1) и (2) определяют лишь методы Монте-Карло для расчета величин (ь)ь, Кьц) н р . А соответствующие им алгоритмы будут заданы только тогда, когда будут записаны формулы для моделирования всех входящих в определение 0,[111 и и величин прн помощи случайных чисел Т.
1.1. Алгоритмы с конечной конструктивной размерностью. О и р е деле н и е. Если функция Ф зависит от и арг) ментов Ф.= Ф (Т' ", ..., Т1 "ь), то мы ска кем, что конструктивная разльерность (к. р.) алгоритма (4) — (5) равна и. В эгом случае для реализации ььго «испытания» достаточно выбрать и случайных чисел 7)н 7)" н вычислить по ним случайное значение ,1 ьТЗ (упь, уьнь). Конечно, может случиться, что при каких-то конкретных значениях аргументов функция Ф зависит не от всех Тнь...,, ти'ь. Так что конструктивная размерность и— это максимальное количество случайных чисел, которое может понадобиться для реализации одного испытания.
Так как каждая из независимых величин Тн',..., Ть"ь равномерно распределена в интервале (О, 1),то функция Ф (уь,..., у„) определена в единичном и-мерном кубе К"=(0(уь(1,..., 0«'у. !), и случайная точка Г= — (тн',..., 1'"') равномерно распределена в К": плотность ее рг(уь..., у„)= — 1 при (ун..., у„)~К'*. Следовательно, искомая величина может быть записана в форме и-мерного интеграла по К": 1 1 а= Д11=)У)йь(Г) = ( ... 1 Ф (у„..., у„) г(уь ... г(у,. (6) й О Мы приходим к следующей общей интерпретации алгоритмов Монте-Карло: если конструктивная размерность алгоритма равна и (к. р.=п), то этот алгоритм представляет собой приближенный метод вьщпслення 256 ' НЕСЛУЧАННЫЕ ТОЧКИ В АЛГОРИТМАХ 1ГЛ. 7 л-мерного интеграла (6) по случайным точкам Г,=' =(Тп!! °, 21")) равномерно распределенным в Ка )" Ф(Р) ) = — > Ф(Г,).
(?) а Г;ы, к Здесь и ниже для краткосп! используется запись 1 1 ) Ф(Р) Г(Р.=- ) ... ) Ф(У„... Уа) с(У1... Г)ца. .а о о Формула (?) равносильна формулам (4) и (5). П р и м е р. Вычисляется однократный интеграл ь у = У у (х) р (х) Лх, (8) а где р(х) — плотность вероятностей некоторой случайной величины 5, определенной в интервале а(х(Ь, с помощью простейшего ме.
тода Монте-Карло л ) — У ~~/Дг). 1.= 1 Если случайную вел пчв н у $ моделировать методом обратных функций (п. 1.4 гл. 2), то $ = 6 (у) . Функция 6 ( у) это обратная функ ци я по отношению к у = Е (х ), где Е (х) = ) р ( ! ) 17! . Замена у = Е (х) а преобразует интеграл (8) к пилу 1 ) =) ?(6(у))г)у.
о Очевидно, в этом случае Ф=)(6(у)) и к р равна 1. Однако, вообще говоря, для моделирования 5 мо!кно использо. вать какую-нибудь формулу вида 5=8(уо ...,Т„) (4 4 гл. 2). Согласно (25) гл. 2 (ср. сноску на стр. 52) в этом случае 1 1 Р(х) =) ... ( 6(х — У(У,, ..., Уа)) дУ1 ... !(Уа. о о Подставив это равенство в (8) и поменяв порядок интегрврований — сперва по х, а потом по уь ..., у„ — получим, что 1 1 — " ) У(й(У1 " ! У,!)) "Ут" "Ул. о Таким образом, в этом случае Ф=((Ы(у! ° ° у„)) н к р. Рав ва л, % Ц констРУктивнля РлзмгРность АлГОРитмов 287 1.2.
Алгоритм с бесконечной конструктивной размерностью. Такие алгоритмы встречаются довольно часто прн моделировании физических задач. Например, в задаче о поглощении нейтронов (гл. 6, и. 1.!) траектория нейтрона может (теоретнческп) состоять из сколь угол- по большого числа звеньев, так что нельзя указать заранее, сколько значений тгн,..., Т'"',... понадобится пам для реализации такой траектории. Алгоритмы с к. р., равной оо, получаются также при моделировании случайных величии методами отбора (гл. 2, $ 5), когда количество значений у, используемых для реализации одного значения т), случайно и (теоретически) может оказаться сколь угодно большим. П р и м е р, Рассмотрим снова вычисление янтеграла (8).
Предположив, что р(х) (с и значения в вычисляются методом Нет>чапа (гл. 2, п. б 3): 8=а+ (Ь вЂ” а) Т, если су'(р(а+(Ь вЂ” а) у); если последнее неравенство нс выполнено, то пара случайных чисел (у, у') отбрасывается п выбирается новая пара. Нетрудно проверить, что в этом случае ( и> Гп' ХЮ РП тле фунипия д (рю д>, ..., у>,, ра, ...) определяется следуюшимп условиями: если су> > р (8>), ..., су„ , > р (ла >), но суе < Р (Ага), то а = аа, где (для кратности) мы обоэначилн да величину а+(Ь вЂ” а) ра! Ь=), 2, ... (Конечно, прп желании можно ввести единую нумера. пию переменных).
Н в этом случае Ф=Г(я), таи что я. р.=се, Запишем (формально; строгое определение имеется в (82)) пн теграл по бссиоисчномерному единичному кубу, в котором все о( уа< ), О<де'< !. 1 ! ( ... ~ .../(.) ху>иу ... (Ь,ру» о 'е йбз НЕСЛУЧАИИЫЕ ТОЧКИ В АЛГОРИТМАХ (гл 7 н докажем, что 1 =!. Для этого прелставнм ! в виде бесконечной суммы интегралов по областям, в которых у= ул) э(л) э(л) 1 « ! 1 ,1 « ! = ( ! / (Р!) ((УЛ((У, , ( (' ((У)()У, ( ( ! (Уа)((У«()У 0 0 О э(гл) О О с 1 1 1 ! ' ' + 1 $ ((УЛ((У! 1 ~ ((У«((Уз О л(е,) О э(л,) ал 1 1 с " Г 3' г!УЛ-АУЛ-1 ~ ~ у(УЛ) УУЛЛУЛ'+ ...
ОРЫ(, 1 О с Здесь каждый из интегралов вида э (ч),) 1 с 1 1 у(уа) ((уз ду; — ~ ! (и + (Ь вЂ” а) уь) — р (а + (Ь вЂ” а) уа) Нуе О О О легко вычисляется с по!)ощыо заз)епы х=а+(Ь вЂ” а) уз и равен ) ! (х) р (л)()х = — э1, с (Ь вЂ” а) . где з — эффективность ме!ода 11еймапа А каждый из «наружных» интегралов равен 1 1 )г Г ~ .,..;г-~Р-'.(.— — л).;)]",= —.. О Э(Э„) О с Следовательно, 1„= ~~(1 — э) э! .= !.
Л=-1 Реализация алгоритмов Монте-Карло с к, р.=со на практике затруднений не вызывает, если предполагать, что в расчете используются «настоян(не» случайные числа (. Иногда каждое испытание доводят до конца, и количество использованных случайных чисел оказывается конечным (хотя и случайным). Иногда расчет испытания прекрашают после выполнения некоторого условия. На. пример, при решении интегрального уравнения можно и МЕРИНГ ПСЕППОГЛУЧЧ1ЧНЫР ТО'1КИ чм ограничиться конечным (фиксированным) числов! членов ряда 1-!еймана, а при использовании алгоритма п. З.З гл.
6 учесть условие обрыва ток(е. В втой ситуации мы по существу аппраксимируем алгоритм с к. р.=-оо алгоритмом с к. р.=п,. Величина пв зависит от допустимой погрешности расчета и может зависеть от общего количества испытаний йг или даже от конкретных значений т, использованных во время расчета. Поэтому оценка по иногда весьма затруднительна. Значение к.
р. играет важную роль, когда мы в ка:1сстве случашгых значений 7 хотил1 использовать неслучайные (детерминированные) числа. В атом случаеалгоритм с различными к. р. приходятся рассматривать отдельно. 5 2. и-мерные псевдослучайные точки 2Н. Равномерно распределенные последовательности. Рассмотрим произвольньш алгоритм Моите-Карло с к.
р.=п и соответствующую ему функцию .Ф(д1, ..., у.). !(ак мы видели в п. 1.1, этот алгоритм сводит решаемую задачу к вычислению интеграла (7). Естественно поставить вопрос: нельзя ли указать неслучайную последовательность точек Рь..., Рь... нз К" такую, что 1 ) Ф (Р) др =- 1пп —; ~. Ф (Р,) (9) К и для всех функций Ф пз достаточно широкого класса? О п р е д е л е н н е.
Последовательность точек Рь ... ..., Рь ... называется равномерно распределенной в К", если соотношение (9) справедливо для любой функции ер(91, ..., у„), интегрируемой в К" по Риману а). Понятие это было введено в 19!6 г. Г. Вейлем [182), который построил та!Оке примеры равномерно распределенных последовательностей. ") Напомним, ч~о интеграл Римана определяется только для ограниченнык функций. Однако автор книги недавно доказал, что если выбрюь Рг = (1г (см. и. 24,2), то формула (9) справедлива также для фупкич!!1 ф(Н) с любыми степенными особенностями вида д~ Р' .. ° р...
где Р,(1, ..., Р„(! (см. Дока. ЛН СССР 2!а, Ы 2, Р973 г., 278 — 281). 260 игслучлиные то'И<и В ллгоР!!тмлх )гл. 7 Сопоставление формул (9) и (7) показывает, что для реализации алгоритмов Монте-(харло с к. р.=п можно попытатьсн вместо случайных точек Г, использовать точки равномерно распределенной последовательности Р,. Для этого надо при реализации 7хго «испытания» вместо случайных чисел у!.'!, ..., у!л! использовать декартовы координаты уь7, ..., у, „ точки Рь Соотношение (9) гарантирует сходимость такого способа вычислений для большинства встречающихся на практике алгоритмов.
Легко заметить, что равенство (9) не нарушается, если изменить в последовательности Рь ..., Рь ... любое конечное число точек. Однако сходимость средних к пределу может при этом очень замедлиться. Г!оэтому далеко пе каждую равномерно распределенную последовательность разумно использовать на практике в качестве псевдослучайных точек. Среди всех равномерно распределенных последовательностей следует отобрать в некотором смысле (см. ниже п.
2.2) «хорошие». Отыскание таких последовательностей обычно наталкивается на серьезные трудности. Например, еще Г. Вейль доказал, что любые последовательности точек с декартовыми координатаыи Р; = (Д (!О!), ..., Д(!0„)), ! = 1,2, где О<,..., ΄— алгебранчески независимые ирраппональные чпс« / аад /;,,' !7 / а/ Ш д/ й Рпс. 67. ла, равномерно распределены в К" . Но ни одного «хорошего» набора О!,..., О„при л)2 до спх пор не известно.
(На рпс. 67, а изображены точки Рь..., Рм в квадрате, полученные при О! Р 2 /2, Оа= )'3 /2.) % 21 2б! «.А>ЕРНЫЕ ПСЕВДОСЛУЧАННЫЕ ТОЧКИ 2.2. Геометрическая характеристика равномерно распределенных последовательностей. Обозначим через 6 произвольную и-мерную область, принадлежащую К", а через (т,— ее обтем (и-мерный). Обозначим через 5в(6) — количество точек с номерами 1(!(й> прпнадле>кащих 6. Теорем а (Г, Вейль). Для того чтооы последовательность точек Р, Рь ... была РаенолеРно РаспРеделенной е К", необходи«но и достаточно, чтобы для л>обой области 6 1!гп (Вл (6))й>! = ('а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
