Соболь И.М. Численные методы Монте-Карло (1973) (1186217), страница 43
Текст из файла (страница 43)
(Двумерные точки, у которых одна координата случайная, а вторая детерминированная попользовались в [181.) Таблица 2 В двоичной системе В десигичиой гост ие ,>,о(хи О,ИИ О,1011 О,ОО! 0,101 О,И1 О,ГИ О,И 0,01 1 0,1 2 0,1 3 0,1 1,(4 3)4 1)'4 173 ггг'3 7(8 1>'2 1 (2 1г'2 15/1Г 117181 Таблица 3 (дв чг,з оиг 0,1 )г((> !г! 2) > р ((> е <г(2> 0,1 1 1 2 10 0,1! О,О! О,Г)! 3 И )г(ие ):(З) ,<2> 1,<З> > 1 3 101 О Ип 7 1И 0,00:)1 0,1'И! 0,10 И 8 1000 9 (00! 0,1 О,ИИ= =О,ОИ1 О,И О,ИИ= =О,ООИ 0,1 0,(>001= =О, 1001 0,0(-0,0001= :-О,О>0! 0,1 0,10И= =0,00(1 0,0! 0,10И= =0,1И1 10~!010 <г(2)4 <г(4> > 18* <г(!) е>г(2>э > у<з> <г(4) > >г(пе И(4) 0,1*0,01= =О,И О,ОО! 0,1 О.ОО! = =О,(и! 0,0! 0,0(>! = =О,ОИ 0,1 О,О! 0,00(=О,И1 0,1" О,И= =О, 01 0,10! 0,1 О,!О!.= =О,ОО! О,И 0,10(= =О,О(! 0,1.0,И 0,101=0,1 !1 0,1.0,0!— =О,>! 0,1(! 0,1.О,И !— =0,0! ! 0,0! 0,1((= =0,101 0,1 0,0(.
-О,1!1=0,00! 268 НЕСЛУЧАИНЫЕ ТОЧКИ Я АЛГОРИТМАХ ггл т — ((К 1,())А< — К 1,())а' ) выписьиы в табл. 4. Ридом приведены игроптные ошибки гм — — 0675)ПО<(А. где дисперсии 061=57,3. Очев<шно, 5А1 заиетно меньше, чем г<с Не следует думать, что если дисперсия не определяет ошибку, то все приемы гл. 3, 4, направленные на уменьшение дисперсии, теряют смысл.
Во-первых, ал- А, ч <к«, !и 8,3510 8,3381 8,2746 8,2840 8,2837 8,2770 8,2723 0,32 0,22 0,16 О,!1 0,08 0,06 0,0! 0.079 0.066 0,002 0,0!2 0,011 0,005 21 и пч 2<! 211 111 211 горитмам с меньшеи дисперсией отвечают функции ф с меньшим изменением, кото.
рые, вообще говоря, интегрпр)ются лучше. 2.4.3. Общие треб о в а н и и. Если подходить к вопросу более строго, то от хороших псевдослучайных точек естественно потребовать, чтобы: 1' асимптотика 0м или <у была наилучшей (или хотя бы бл<гь ког< к наилучшей); 2' константы в (!2) или в (13) были наилучшими (илп хотя бы достаточно малыми); 3' значения Г),чу<у пли <Г /Л были небольшими уже прп небольших А<; 4' алгоритм расчета этих точек ца ЭВМ был логтато иш простым.
К со<калению, проверить все эти требовании в настопшгс премя невозможно, так как наилучшие значении констант (13) неизвестны (а длп Г)А( неизвестен даже нанлучшай порилок роста). Оливки первому требованию в какой-то мере удовлетвори<от точки Р; и вполне — точки О< ° При нсбольших л второму и третьечу требованию удовлетворяют точки Я; ° Наконец, время расчета точек О; того же воридка, что время расчета стандартных псевдослучайных точек Г< (если только имеется готовая таблица 1'' ).
. (Ч< Дли расчета точек Р; нужны лишь и простых чисел, но по сравис<цпо со временем расчета()1 время расчета Р; примерно в и раз больше. 2.5. Замечание о роли дисперсии. В расчетах, выполненных по точкам Я;, фактическая ошибка часто оказывается на порядок меньше вероятной. Пример. Рассмотрнч значения (К'1, Р) м прп А(=2м, приведенные в табл. 1 гл. 5 (стр. 192). Условнмси считать последнее значение, соответствующее А( = 2", точным. Фактические ошибки бл —— . таблица 4 й 2! «.МЕРНЫЕ ПСЕВДОСЛУЧЛПНЫЕ ТОЧКИ 289 Простейший результат в зточ направлении для случая л=! можно получить с помощью формулы (48) гл. 3, стр.
129. В самом ДЕЛЕ, дпя ЛЮбОй фуНКцнн Ф(у) КЛаССа )г'2 (! ), ! ! л ~)Ф(у)' — .у Х Ф(т) - '1''"'," (") в !=.1 где можно сюпать, что 1 б'=-)'!Ф (рП ли. а !йак доказано в (78), еслнФ(д) ейгз(Ц, то дисперсия случайной величины Ф(у) удовлетворяет неравенству 0Ф(у) (аз!из. (18) Фиксируем числа у„..., ун. Пз (17) видно, что для тех функций, для которых б меньше, погрешность интегрирования будет меньше Но таким функциям, согласно (!8), соответствуют также меньшие значения дисперсии. Во-вторых, алгоритмам с меньшей дисперсией часто отвечают более гладкие функции Ф, удовлетворяющие оценке (14).
Например, при расчете задачи о поглощении нейтронов методом п. !.1 гл. 6, осредняемая функция может принимать лишь два значения: 0 и !. Нетрудно убедиться в том, что ее разрывы не параллельны координатным гнперплоскостям *). А при расчете той же задачи методом п. 3.3 (гл. 6), осредняемая функция непрерывна и даже диффсренцпруема. Вооб!це говоря, можно ожидать больи!его ускорения сходил!ости за счет использования детгрлеинированнь!х псевдослучайных чисел тогда, когда используются более совершеннь!е алгоритмы,негода Монте-Карло. ') если область йе — шар гз с)72, то пз формулы ге+! — — ге+ в!Я! следует условие вылета ,2 2 1 2е (г (1) ! еь2~рз Поэтому одва из поверхностей разрыва оспедняемой функции опре. деляется уравнением $~! + 2$! (гг, ()г) + гз — )72 = О, В случае изотропного рассеяния (гп Я!) =!г,1(2у — 1), длина пробега Ц = — (1/ь) 1п у', гак чтв уравнение зто связывает у с у'.
!ГЛ 1 НЕСЛУЧАИНЫЕ ТОЧКИ В АЛГОРИТМАХ 3 3. Поиски «универсальных» псевдослучайных чисел В предыдущем параграфе были указаны дсзсрмннированные точки, координаты которых можно использовать в качестве псевдослучайных чисел при реализации алгоритмов Монте-Карло с конечными к. р. Однако весьма часто встречаются также алгоритмы с к. р.= ОО. Рассмотрим некоторые попытки построить детерминированные псевдослучайные числа, пригодные для расчета задач с любыми к.р. Мы говорим о попытках, так как нельзя считать, что эти поиски уже закопчены: до сих пор нет последовательностей, удовлетворяющих требованиям практики (типа описанных в п.
2.4.3), да и сами этп требования не вполне четко сформулированы. 3.1. Использование бесконечномерных точек. Тако!! подход к проблеме был предложен Н. Н. Чепцовым в 1961 г. [97). На этом пути удалось указать весьма широкие классы функций Ф(у1, ..., у„, ...), зависящих от бесконечного числа переменных у1,..., у„,... (0«у„(1) и такие классы последовательностей Р„..., Рь..., состоящих из точек бесконечномерного единичного куба Р,= (у» 1, ..., у!, „, ...), что для казкдой ф)пинии класса А! 1 1 Ю 1пп ~ ~~~ Ф(Р,) =) ) ...
Ф(р„, „1!,„...) П г(дм Ю»ю 1=! 0 0 »=1 и порядок сходимости лучше, чем 1/Л!! ' с любым е)0. В частности, этим классам функций принадлежат любые достаточно гладкие функции Ф(уь..., у„), завися!цпе от любого конечного числа переменных и. Поэтому прн реализации всех упомянутых в 5 1 алгоритмов с к. р.= ОО можно пытаться вместо псевдослучайных чисел исполь зовать координаты точек Р,. Пока известны лишь две конкретные бесконечномерные последовательности с более или менее «хорошпмп» свойствами. Одна из них — обобп(еннал Л77ь последовательность — вычисляется по формулам (15), (16), где 1«=!<ОО. К сожалению, достаточно простых формул для расчета всех элементов у!г~ нет. $ 31 «уннвеРЕАльиые псевлослучАинне числА 271 Вторая последовательность, впервые рассмотренная в !77), называется обобщенной паеледовательностша Холтона. Точки этой последовательности Р;, 1= 1, 2,..., имеют координаты Р*"=(р,(!) р.(/) ",рл(/) ".) где г>(гг( ° (г.~...
— последовательность всех простых чисел. Для расчета точек Р; на практике можно задать достаточно большую таблицу простых чисел и (или) запрограммировать какой-нибудь алгоритм их нахождения (например, метод решета). Первые две точки этой последовательности: * /! 1 1 1 ! ~2' 3' 3' 7'''" «„''''/' Если мы хотим использовать точки Р; для расчета задачи о поглощении нейтронов (гл. 6, п. 1.1), то для построения первой траектории надо вместо случайных чисел использовать значения !/2, 1/3, !/5,..., для второй — !/4, 2/3, 2/5,..., и т. д.
Пример такого расчета имеется в [80). 3.2. Вполне равномерно распределенные последовательности чисел. О п р е д е л е и и е. Последовательность чисел хь ... ..., хь ..., принадле>каших интервалу (О, 1), называется вполне равно>нерпа раепрег7еленной, если при каждом натуральном и последователыюсть точек (х>,..., х„), (х„«ь ° ., хг.), (хг +ь ° ° ., хг ),... (19) равномерно распределена в К".
Понятие это было введено Н. М. Коробовыы в 1949 г. (41). Из п. 2.1 вытекает, что если функция Ф(рь ..., 9«) ннтегрируема по Риману в К", то н-! !Ип — э гТ>(хь, >,..., хг„.!.„) =* ) Ф (Р) йР, (2(1) н соотношение это справедливо для любого натурального и или, другими словамн, для функций Ф от Любого ко- 272 НССЛЮ!АЙНЫЕ ТО'!КИ В АЛГОРИТМАХ !ГЛ 7 печного числа аргументов. Следовательно, вполне равномерно распределенные последовательности чисел мозкно (в принципе) использовать для практической реализации алгоритмов Монте-Карло с любыми конечными к.р., а в некоторых случаях и с к. р.
= оо !991. К сожалению, до сих пор неизвестно ни одной вполне равномерно распределенной последовательности, которая в какой-то степени удовлетворяла бы требованиям п. 2.4.3 при различных и. П р и и е р [12Г! Известно, что с!шествуют бесконечно много таких чисел а)1, что последовательность дробных далей х; = д (сс!), ! =- 1, 2, ..., вполне равномерно распределена *!.
Легко доказать, что такие а обязаны быть транснендентнымп числами. Но до сиз пор ни одного конкретного значения а не найдено. Можно доказать, что вышеприведенное определение вполне равномерно распределенных последовательностей эквивалентно следующему. О п р е д е л е и и е. Последовательность чисел хг,...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
