Соболь И.М. Численные методы Монте-Карло (1973) (1186217), страница 44
Текст из файла (страница 44)
..., хь ..., припадле'каших интервалу (О, !), называется вполне равнол!арно распределенной, если при каждом натуральном и последовательность точек (хг,..., х„), (х,..., х„г!), (хз,..., х„.!.7), ... (21) равномерно распределена в К". Из этого определения и п. 2.! следует, что если Ф(уь ..., у.) ннтегрируема по Риману в К", то, каково бы ни было натуральное а, А — ! !Ип — ~ Ф(хг-с1, °,хг+ ) = ) Ф(Р)г(Р. (22) Может показаться, что расчет по формуле (22) выгоднее, чем расчет по формуле (20), так как при этом затрачивается примерно в л раз меньше чисел хь Несомненно однако, чтс вычислители, инстинктивно стремясь к «независимости» псевдослучайных точек, отдадут предпочтение точкам (!9) и формуле (20).
Вполне вероятно, что они правы: может оказаться, что для точек (21) отклонение Р (при любом п?) растет быстрее, чем для точек (!9). Вопрос этот пе исследован. ') таким свойс!вом обладают почти все а)1, $ 31 УНИВЕРСАЛЬНЫЕ ПСЕВДОСЛУЧАЙНЫЕ ЧИСЛА 973 3.3. Асимптотически вполне равномерно распределенные последовательности чисел. Рассмотрим семейство последовательностей х>, ..., х„..., зависящее от нату. ральпого параметра д(д= 1, 2,...): х>(у), х,(д)...,, х,(д)..., (23)' Семейство (23) естественно назвать асимптотически вполне равномерно распределенным, если для любой функции Ф(уь ..., у„), интегрируемой по Рнману В К", при любом натуральном и справедливо равенство 1 д н †! 1пп Ип! — ~'. Ф (х>и, (д),..., х;„;, (д)) = ) Ф (Р) дР, Иех,а >О ю' 'и >св (24) илн равенство А — ! 1!!и 1пп — „, ~, Ф(х>,(у),...,.к>+в(у)) =-) Ф(Р) дР. (25) и н- ~ !о кп Термин этот введен И.
Франклином в !963 г. 1126). Ев!у же принадлежит второе утверждение следующей теоремы, первое утверждение которой доказано в 133). Т е о р е м а. Существует бесконечно многа чисел а, 0(а~1, таких, что семейство последовательностей х,(д) =Д(ад'), 1=1, 2, ... ву асимптотически вполне равномерно распределено как в смысле (24), так и в смысле (25)*). Интересно отметить, что при каждом фиксированном д последовательность х,=Д(ай') может быть равномерно распределенной в К!, но точки (хв>-ь хм) не могут быть равномерно распрел ! х ! деленными в Кв. В самом деле, Рис 69. точки (хь хт), (хм хи) ... можно записать в виде (х>, Д(дх!)), (хм Д(дхв)), Отсюда видно, что все они расположены на линии у=Д(ух), которая состоит из д отрезков прямых у=ух — й при * Таким свойством обладают сочти все и ив интервала (О, 1), 2?4 ' !ГЛ 7 НЕСЛУЧАИНЫЕ ТОЧКИ В АЛГОРИТМАХ й 4.
Проверка псевдослучайных чисел с детерминистической точки зрения 4.1. Интерпретация простейших критериев. В гл 1, 4 3 чы рассмотрели некоторые тесты, используемые лля проверки псевдослучайных чисел, и отметили, что все такие тссты только необходимы, ио не достаточны: они могут опровсргнуть гипотезу о том, чзо у„..., ул! — независимые значения случайной величины у, но ие могут доказать ее. Сузим теперь постановку вопроса: вместо «можно ли числа у„ ..., узг считать независимыми значениями у?» мададнм вопрос; можно ли числа у!, ° ° °, уз! использовать вмесго независимых значений у в формуле ! и ! Ф(х) !(х — ~ы Ф(у,) 'о 7=! (26) пра любых Ф(х) из достаточно широкого класса? При такой постановке вопроса рассмотренные в гл, 1 критерии оказываются и необходимыми н достаточными — каждый на своеи классе функций Ф(х).
Впервые такая интерпретация была изложена автором в 1968 г. 4.1.1. Критерий ы'. Из формулы (48) стр. 129 вытекает, что ! А' зпр ~ ) Ф (х) с(х — — 7, Ф(у.)! = й шее' !ц ! а 2 (2?) Следовательно, малость величины ыш нсобходпзза и достаточна лля 2 того, чтобы ошибка приближения (26) была мала для всех ф)акций класса (Р2 (1.). 4Л.2. Критерий Хе. Разобьем интервал (О, 1) на г интервалов А',+... + л, = (О, !), клипы которых равны рп ., ., р, так, что Р!+. ° .
+ Рг = ! и все р. )О. Обозначим черсз т. колнче. у ? а=6„„, Аг — ! (рис. 69). Тем более последовательность х, пе может быть вполне равномерно распределенной. Сформулированная теорема в какой-то мере объясняет, почему метод сравнений (п. 2.2.2 гл. !) позволяет строить «хорошие» псевдослучайные числа и почему приходится выбирать большие йч из (7) гл. ! вытекаст, что у!=Д(усу*). Однако никаких выводов о том, как выбирать «хорошие» Аг, М, то отсюда сделать нельзя. Как доказал С. М. Е!рмаков !'ЗЗ),скорость сходимости в формуле (24) (но не в (25)!) связана с у!ОФ(!")?Л?.
й 41 провеикл псевдослтчлиных чисел 275 ство значений у, прп 1(!<Ь', принадлежащих ХХ Критерий хз основан на асимптотвческом распределении величины !'=! l (28) которое не зависит от Хь ...,Х, а только от числа степеней свог' боды г — !. Введем множество функций А,(Е), постоянных на каждом из Х1, т, е, фуакций вида Ф(х) = =с. при х с Х, 1 < ! < г, l' п таких, что Г рс ! ! !'=! (чр) Ф(х)шА!(ь), то г г 1(егрздпо вычпсшпь, что если ! ~Фг(х — '~', Ф(у!) = Ят', Е й(гг 1! Используя известное неравенство(2!! л.)з < 'и!2о, получим оценку ч !! !' у.л! причем оценка зта гочная, так как прп последнее нсравсисзво обращается в равенство. )!таге, и зо р ~ ( Ф (х) г(х — — х~л Ф (у.) = й 1 св жгс1 'о !У,—.! Л~ (30) Отсюда видно, что малость величины 2мд необходима н достаточна для того, чтооы ошибка приближения (26) была мала для всех функций нласса А!(Ь), Мы.
знаем, олнако, что к формуле (26) сводятся лишь такие ал!орит!гы Моитс-Карло, у которых к.р.=!. Стало быть, расспотренныс критерии (как и критерий Колмогорова, см. упражнение 8 НЕСЛУЧА!ЧНЫЕ ТОЧКИ В АЛГОРИТМАХ 27Б !Гл т гл 1 и упражнение 6 гл 71 гарантируют применимость проверенных псездослучаииых чисел у!,..., Ум только для расчетов по алто. ритмам с к. Р.=!. 4.2. Миогомериые критерии.
Если мы хотим использовать зтч же числа для расчета Во алгоритмам с к. р.=л, то необходимо проверить вх с помощью кзкого-либо л.мерного теста. Например, разобьем куб К" иа г областей Х!+... + Х„=-К", объемы которых равны р!, ... р, так что рг+...+Р =1 и все р )О. Из чисел ! уь ° ° ° ум образуем А!„=-П(АГ7п) точек с координатами "' Тл)' (Уп+!' "" 12л)' '"' (Уп!мл — !Н.!' ' ' Улмп)' и пусть т — количество таких точек, принадлежащих Х . ! Тот же крвтерий 7!з с (г — 1)-й степенью спободй позволяет проверить распределение зтих точек вКп с помощью величины Обозначим через Ал!ь) множество функций Ф(х, ..., хп), постоянных на кап!дом Х7, т.
е. функций вида Ф(х,,...,х)мс прп (то...,х)цХ, 1<)(г, и таких, что выполнено условие (29). Повторяя вычисления п. 4.!.2, получиы, что Лп — ! зпР,~ Ф(Р) г1Р— А! л, Ф (Уж+2, ..., У, ) = й')гг:м Фщил!С! Ап (31) Такпч обРазом, малость Ух действительно гаРантиРУет пРиыенн. .2 л!ость чисел уь..., Ум лля расчета по некоторым алгоритмам с к. р.=л. Конечно, класс алгоритмов, которым отвечают функшш Ф (х„..., х ) из А„(ь) весьма узок. Однако если г велвко и все Х.
малы, то многие функции допускают хорошее приближение кусочно постояннымн функциями из А (Е). И тогда псевдослучайл пые числа, пригодные для интегрирования функций из А„1ь) окажутся пригодными для интсгрпровгиия гораздо более разнообраз. ных функппй. 4.3. О системах тестов. С точки зрения изложенного в пп. 4.1 и 4.2, система тестов, рекомендованная в гл. 1, представляется логичной, но довольно слабой.
В самом деле, она включает простейшие проверки одномерного и двумерного распределения у и заодно распределения некоторых попутно вычисляемых второстепенных величин. Лишь проверка серий моуксы рассматриваться как тест, упплжнкния к Гл. т Упражнения к главе 7 1. Рассмотрим пример п 1.2, где значения $ вычисляются ме.
тодом Неймана. Ограничим число проб величиной ! и условимся полагать Э=О, если су!)р!а~), ..., суг> р(а!). Для такого алго итма к. р.=2!. оказать, что для того, чтобы погрешность такого приближения не превосходила вероятной ошибки метода гм — 0,675Р')»/!4)//»' должно выполняться неравенство ! > 1п (г,//) 1п ' (1 — з). 2. Выберем в кубе /т" равпомсрну!о кубическую сетку, состоя- и ую нз !У вЂ” 31® точен с кооРлинатами — 1/2 ) л М [ !» — 1/2 где 1ь..., 1 =1, 2,..., 34.
/!оказать, что отклонение этой сетки равно 0„=05л/~ '" (при л=1 величпнабн 05 минималь. па, но прп больших л отношение Рм/й/ убывает крайне медленно) 3. Вычислить точку!3!з в 4-мерном кубе, Ответ: !/!з — — !!!Пб, 13/16, !3/16, 15/!6). 4. Используя равенства 1'1!' — — 2 ' при з= 1, 2, ..., доказать, что пеРвые кооРдинаты 4! ! точек !е! совпадают с числами Р»Я. рассчитанный на алгоритмы с к.р, еь, правда, алгоритмы весьма спепиального вила Если бы речь шла только об использовании алгоритмов с любыми к.
р.<л, то можяо было бы предложить очень хороший тест— расчет отклонения/)м или, другими словами, л-ыерный критерий Колмогорова !см. упра>кнсние 8 гл. 1 и упражнение 6 гл. 7). Правда, вычисление /тм при больших /У очень трудоемко. Обеспечить же знпирической проверкой «универсальность» псевдослучайных чисел, по-видимому, крайне трудно, Например, без теоретических результатов, подобных результатам 4 3, пришлось бы проверять л-мерное распределение не один раз, а л раз, так как (Уы ...,7„), (Ул)!, ..., У „)... хорошо рас. пределены, не следует, что точки(у/,...,7;+„) (у;+„+1, ..., у;+ „),... при 1<!<и также хороши.
Это видно пз следуюшего простого примера: в последовательности 11110000!11!0000 ... пары 11, 11, 00, 00. 11, 11, 00, 00 распределены неравномерно (так как комбинапнй О! и !О совсем нет); отбросив первую единицу последовательности, получим пары !1, 1О, 00, 01, 11, 10, 00, 01, ..., где каждая пз возможных комбинаппй встречается одинаково часто. Результаты этого параграфа содержатся в статье [34). 2ТЕ НИОЛУИАЙИЫН ТОЧКИ Н АЛГОРИТМАХ [ГЛ. т б.
Какова бы пи была последовательность чисел кь..., хг ... нз интервала (О, 1), равенство 1 ) 1' (х) г(х — — У„) (х.) = о ~ —,~ о — — (А~ длп 1 х и ) хз одновременно невозможно. (И. Н Ченпов). 6. Обозначим (Р', ((.) множество непрерывных функций 1'(х1, определенных при 0<к~! и пмг;гщпх нусочно нспрсрывные производные )'(х) такие, что 1 ) ()'(л)) ало Доказать, что лля любых чисел уь..., Тх 11 зпр ~~Ф(х) г(х — ~~ Ф(у.)~ = (.
ФаЗР (А) О й! " ФА)' где Км — — У)У(з — величина, Фигурирующая в критерии Колмогоро- ва (упражнение 8 гл 1) (И. б!. Соболь [84)). ГЛАВА 8 НЕКОТОРЫЕ ДРУ1'ИЕ ЗАДАЧИ 9 1. Интерполирование функций от большого числа переменных Рнс Уо В книге уже встречались задачи, в которых методы Монте-Карло оказываются эффективнее классических методов при большом числе переменных (см.упражнение 9 гл.
3 и п. 5.6 гл. 5). Здесь П,1/ изложена одна задача такого типа, рассмотренная впервые Д ж. Х з м м е р с л и 1134) . 1.1. Постановка задачи. Рассмотрим функцию )(хь - гх,„гА х„), значения которой -------+--- известны лишь в вершинах единичного и-мерного куба К". Требуется ироннтерполи- 4Ф ЙИ ровать значение втой функции в точке (хь ..., х„), расположенной внутри К" (рис. 70). Интерполяция линейная по каждому из переменных. В случае а= ! интерполяцпонная форзгула всем хоро. шо знакома: !(х1) = (1 — х1)!(О)+хи(1). !1етрудно проверить, что при а=2 получается аналогичная формула: )(хь лг) = (1 — х,) (1 — х,)!(О, О)+х,(! — хз))(1,0)+ +(1 — хДхз1(0, 1)+х1хз~(1, 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
