Соболь И.М. Численные методы Монте-Карло (1973) (1186217), страница 42
Текст из файла (страница 42)
(1О) Р (Я (6),'Л!! - -(те. Сравнение этой формулы с (10) снова показывает, что точки равномерно распределенной последовательности являются аналогами независимых реализаций случайной точки Г. Мы уже отмсчалп, что не все г равномерно распределенные последовательности одинаково хорошо распределены. Оценить «равномерность> распределения можно прн по.
мощи величины, называемой отклонением. Чтобы определить ее, выберем в К" произвольную точку Р и обозначим через П„ параллелепипед с диагональю ОР и со сторонами, параллельнымп координатным осям (рпс. В>8). Отклонением группы точек Рь ..., Р, называется ве- личина > е, (1!) ОА =- енр )ЗА (П>) — й>(тг> .« Ее в Отсюда видно, что при больших !Ч количество точек, принадлежащих 6, среди точек Рь ..., Р„„приблизительно пропорционально объему )т«.
Рассмотрим случайную точку Г, равномерно распределенную в К", и й! ее независимых реалпзапий Гь ..., Г;. Так как вероятность Р(ГЕ:-6) = Р,, то сходимость частоты попадания этих реализапий в 6 к вероятности попадания означает, что 1ГЛ 7 НЕСЛУЧАЙНЫЕ ТОЧКИ В АЛГОРИТА1АХ Следующая теорема легко вытекает из работ Г. Вейля: Теорема. Для того чтобы последовательность тп пчс 'Рь ..., Р...ь бьгла равномерно распределенной в К", необходимо и достаточно, чтобы [нп (Рмгйг) = О.
Н-е ч Очевидно, чем быстрее убывает отношение Р,(К, тсы более равномерно распределена последовательность ч). Можно доказать, что ([2(Рм(Л(, но неясно, каков наилучший порядок роста Р„прн И -оо. В настояпнс время известны лишь два класса последовательностей точек в К", для которых при всех Л1 РХ=О((п.Л)). ((2) Это последовательности Холтона п ЛП,-последовательности.
Примеры таких последовательностей — Р; и (гг— приведены ниже в п. 2.4. Существуют ли последовательности, для которых Рл=о((п"Лг) при всех Л[ неизвестно. Однако для точек К, ..., ()и при Лг=2ч отклонение равно Рм=О(!и -%). В книге [82! изучается лругая количественная характеристика расположения гругпы точек Рь ..., Рн,называемая неравномерностью гр = ф (Рь ..,, Рн). Для нее справедлива теорема, аналогичная предыдущей: длл того чтобы последовательность точек Рь ..., Рн была равномерно распределенной в К", необходимо и достаточно, чтобы 1)ю (гр 1Л)=0.
Н.ее Л)ажно доказать, что 1(ф <)у. Поэтому наиболее равномерно распределенными следует считать такие последовательности, неравномерности которых пря всех )У ограничены. Среди известных в настоящее ьрсыя последовательностей точек в Калишь ЛП -посл:- довательност и обладают этям свойством: гр (Ог, ..., ян) < 0(п,т). Для последовательностей Холтона получена только более слабая оценка: <Р О ()пчЛГ) ') В литературе час~о отклонением называют отношение Пн (М, так как это есть верхняя грань отклонений эмпирической функции распределения Ян(ПР)/)у точек Рь..., Р,ч от теоретической функции распределения случайной точки Г, которая и точке Р равна 1'и .
Ср. Таклге упражвение 8 гл, 1, п МЕРНЫЕ ПСЕВДОСЛУЧАННЫЕ ТОЧКИ рбз $2! 2.3. Ускорение сходимости. Формула (9) справедлива для всех интегрируемых по Римаиу функций Ф(уь, у.). Если рассмотреть более узкие классы фуикций, то возможиы оцеики погрешности этой формулы. Например, неравенство ) Ф(Р)дР— —. ~УФ(Рг) ~ (Ф) — ',У (14) л г=! где с(Ф) пи от йг, пи от точек Р, пе зависит, справедливо для л!обых Рь ..., Р и для всех функций Ф(уь °, у,), ко!орые Непрерывны и ограничены в К„вместе со своимп частными производными, содержащими пе более одпого дифференцирования по каждой переменной. (Все этп производные можно записать формулой д" Ф/дул ...
дусм Гдс 1 ='/! С;/2(... (/А(и П й МО>КЕт ПрИПИК!атЬ ЗиаЧЕ- иия 1, 2, ..., п. Старшая среди этих производных, д"Ф/ду! ... ду„). В олечке л= ! докктктелы"пго и рякенстпк (!4) кнклогпчно локктательс1еу. теоремы 5 гл 3. В гамом деле, пусть х(Ф! =— 1 !Ф'(х) !ггх. Тогда, полагая н (46) гч!к 228 /=Ф, получим, что као копы бы нн бьлк точки хь..., хл, пх п~ гг!пгнле (О,!) ! ~ю! ОФ)!э, ! Ф г)х — у Ъ~ Ф(х; ! ~ ы — т — кпр !5л (л! — Лх! = 'е Однако алгоритмы Монте-Карло весьма часто приводят к разрывным функциям Ф.
Поэтому важно отметить, что оцепка (!4) справедлива для гораздо более широких классов функций (3. Хлавка 11381, И. М. Соболь 1821). Например, если все разрывы функции Ф(уь ..., у„) расположены на конечном чвсле гиперплоскостсй вида ук=сопз( (т. е. параллельных координатиым гиперплоскостям), а в остальных точках куба К" фупкция Ф и все вышеупомянутые производные непрерывны и ограничены, то перавеиство (14) выполиепо. Интересно, что разрывы, возппкагощие при моделировании дискретных случайных величии и при использовании метода гуперпозпцпи (гл. 2, и. 3,3) как раз такого типа. Напротив, при использоваиип метода Неймаиа 2Б1 НЕСЛУЧАЙНЫЕ ТОЧКИ Н АЛГОРИТМАХ !Гл т (гл. 2, п. 5.3) возникают разрывы, которые пе обязаны располагаться в гипсрплоскостях, параллельных координатным. П р и и е р Снова прыположпм, что вычисляется интеграл (В), а случайная величина $ молелирустся методом суперпозииии: к = ол (21~1), если сз + ...
+ сл 1: тп> ( с, + ... + сл (6 (у) — обратная функш1я ио отношсншо к гл(л)). В этом случае л Л-1 л Ф=)(6л(у,)) при ~"„с, гс у,<~~~', ср 1=! 1=1 так по Ф(уи уз), вообше говоря, имеет разрывы при у=си у=с,+ +сь... В этом же случае метод Неймана (см, пример п. Н2) приводит н фтнкиии Н>=)(У(Уи У~, ...)), котоРаЯ РазРыпна пРи сУА ——— =р(о+(ь.. ) ул1, л=), 2. Если в (14) подставить Р,=Р; илн Р,=Я;, то в соответствии с (!2) правая часть окажется порядка 0(?>1 ')п")з'). Так как при всех достаточно больших У справедливо неравенство 1п"й(()уе (при любых фиксированных л)1 и в)0), то можно сказать, что погрешность (14) убывает бенстрее, чем ))1 " " с любы>н в)0.
Напомним, что порядок погрешности формулы (7) с «настоящил1и» случайными точками равен )т' ' з, т. е. заметно хуже. Численный пример, сосчитанный с помощью точек 0;, имеется в гл. 5, п. 4.4.!. См, также 1!За]. Заметим, что порядок сходимости формулы (9) пе но>кот быть о(?з)-') даже на весьма узких классах функпий (см. упражнение 5 на стр. 2?8).
2.4. «Хорошие» псевдослучайные точки. 24! П о еледов а тельность Хо л т он а Р;. Для построения этой последовательности необходимо определить числовые последовательности р„(1). Фиксируе~ натуральное число г)2. 0 п р с д е л е и и е. Если в т-ичной системе счисления 1= — а,,а„,, ... азаь то снова в г-ичной системе р,(1) =О, а,а, ... а,аги Злсск ясс и — полые г-ичиые ш|фры, т. е.
равны одному из Значений О, 1, 2,..., г — 1. В дссшичиой системе последние две 285 и мерные псввлослучлпныв точки $2! формулы выглядят таи; 5= ! Первые 1О значений Рз((1 о~ р,(ь)= ~' о,! ь=! .5 — 1 Я ириведены в табл. !. Таблица 1 (о 10 0,01 0,1 11 0,11 100 10! 0,001 О, ЮИ ! троичи. 21 0,12 22 0,21 0,2 0,02 и оа р,(!) троичи. р,(!) !727 !0727 8,'9 4!9 779 273 2/О ! ('3 Пусть гь..., г„— попарно взаимно простые числа.
Последовательностью Холтона называется последовательность точек в К" с декартовыми координатами (р,,(!), ..., р„„(!)), 1=1, 2, ... 2.4.2. ЛПспоследовательность Ю;. Свойства ЛП;последовательностей подробно изучаются в [821, Здесь мы укажем лишь алгоритм для расчета точек ((( = (0(, !..., (7(, о), ! = 1, 2, ..., образующих ЛП;последовательность Программа расче- та на ЭВМ БЭСМ-4 имеется в [861. О и р е д е л е н и е. Если в двоичной системе счисления !'=ее,ео, ! ... еле(, (15) то для всех 1=1, 2, ..., и (И (2) (ы! д! ! = е!)г! * ев)г! °... ° еи, )г,. (16) Здесь еь ..., е„— двоичные цифры, каждая пз ко- торых равна 0 плп 1.
В десяти пюй системе (=2'о 'еь,+2ь' 'еь (+... 2езв е!. 18 !.(. М. с ~воль Эти последовательности были построены Дж. Холтопоа! [131), получившим для них оценку (12). Все такие последовательности равномерно распределены в К". На практике обычно в качестве гь ..., г„выбирают первые и простых чисел: г,=2, ге=3, г,=5, ... и используют л-мерные точки Р! — — (ре(!), ра(!), ..., рг (!)), !'=1, 2, ... 266 неслучхнгчые точки в АЛГОРитмлх 1ГЛ т Числа )7!з! можно найти по табл. б (стр.
297), которая позволяет вычислить более 2 !О' точек ф в кубе К" размерности и = 13. Звездочкой (') обозначена операпия поразрядного сложения по модулю два в двоичной системе. Более полробно, чтобы вычисл!пь «сумму» анЬ, надо оба слагаемых записать в двоичной системе а=о, а,а,,ах! Ь=О, Ь,Ь«...Ь,и', тогла в двоичной системе в » Ь = — О, сгс« ° ° ' «зг где са —— (па+ Ьа) (пюд 2) плп, лР)п!мп словами, с = 1, если аа ~ Ьа н са — — О, сели аь — — Ьа. В системе команд любой ЭВМ имеется специальная команда, осуществляющая операцию в, Обычно ее называют командой срав- нения. Она относится к числу логических кочанл и выполняется быстрее, чем арифметические команды.
Вообще, для расчета по фор!"! л!уле (!6) нужны лишь логические команды (произведение «х)г(И либо равно 1г(аз~ если е» = 1, либо раааа нулю, если «а= О). ! Пример. Вычислить первые 1О точек О; в трехмерном к!бе. По табл, 6 (стр. 297) находим нужные значения 1 !'1. Они написаны 1 в табл. 2. Вьщисления по формуле (16) спелсиы и табл 3.
Результаты в десяти ищй сне!сне: ОЗ! =-(1,'2, 1,2, 1 2), Г)„=- (3,'8, 3 8, 5'Я), !7г =(1!4 3!4 1741 Ог =178 7'8 1!8) ()з = (3/4 !!4 ч!4) С)в = (1116 15716 11)16) !7 =(!(8, 5)8, 7)8), !7 =(87!6, 7П6, 3)!6), !7з = (5!8, 1)8, 3/8), !7!в —— (5,'!6 ЗП6 !ог)!6). На рис. 67, а изображены точка !7з, ..., !7!а в квадрате, в па рис 67, б — !6 «настоящих» случайных точек. Замечание.
Хотя табл. б па стр. 297 рассчитана на к. р, (13, ее можно иногда испбльзовать при любых К, Р., ДажЕ К.Р.=оо. В КаЧЕСтВЕ ЗНаЧЕНИй ПЕДОСтаЮГППХ координат псевдослучайных точек можно выбирать обычные псевдослучайные числа 7, так что, например, «! — (г)г,! ° !)г,!з 15 ° ° *')г! ° ° ) и МГРНЫГ ПСЕВДОСЛУг(А>тиЫЕ ТОЧКИ 267 ЦелесообРаано вычислЯть по ()о! наиболее СУптественные переменные в Ф(у(, ..., р, ...), а по Т( — все осталь<и ные. Если в действительности существе((ных координат печного, то такой способ расчета может ускорить сходимость (по сравнению с расчетом по формуле (7)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
