Соболь И.М. Численные методы Монте-Карло (1973) (1186217), страница 2
Текст из файла (страница 2)
Поэтому теория методов Монте-Карло должна дать ответы на два вопроса: 1) как выбрать удобную величину $ для расчета той нли иной задачи? 2) как находить значения $ь $э, ... произвольной случайной величины $р Изучение этих вопросов и должно составить основное содержание практического курса методов МонтеКарло. Почти все методы, рассмотренные в настоящей книге, основаны на расчете математических ожиданий. За рамками книги остались упомянутые выше методы случайного поиска (кроэте простейшего) и стохастических приближений.
Среди методов Монте-Карло можно выделить методы, в которых полностью воспроизводится модель рассчитываемого процесса. Такие методы иногда называют «физическнми», хотя автору представляется более удачным другое название этих методов — имитационные. Имитация естественных процессов широко используется в самых различных областях науки, техники, экономики. Однако приемы имитации в каждой области свои, и подробно излагать пх более целесообразно в специальных руководствах, а не в общем курсе методов Монте-Карло.
Нет оснований считать, что имитация естественного процесса— это лучший способ для расчета этого процесса; скорее — наоборот. В самом деле, при имитации вычисляется вся информация о течении процесса; однако в реальных задачах, как правило, ие аужна вся информация о всех величинах; поэтому естественно огкидать, что существуют методы, в которых скорость расчета нужных величин понышается благодаря отказу от информации о ненужных величинах. Слово «численные» включено в заглавие книги, чтобы подчеркнуть, что здесь рассматриваются главным образом не имитационные методы, ГЛАВА 1 ПОЛУЧЕНИЕ СЛУЧАЙНЫХ ВЕЛИЧИН НА ЭВМ В алгоритмах Монте-Карло фигурируют значения случайных величин с различными законами распределения.
Как будет доказано в гл. 2, для того чтобы вычислять значения любых таких величин, достаточно уметь находить значения какой-нибудь одной случайной величины, ибо всегда можно подоорать такую функцию от этой случайной величины, которая имеет требуемый закон распределения. 11оэтому'мы сначала рассмотрим вопрос о том, как получать на ЭВМ значения одной, «стандартной», случайной величины. $ 1. Три способа получения случайных величин 1.1. Случайные числа и случайные цифры. Как правило, в качестве стандартной выбирают непрерывную случайную величину Т, равномерно распределенную в интервале (О,!).
Напомним основные характеристики этой величины: при 0(х(! плотность рт(х) =1, а функция распределения г (х) =х; математическое ожидание йй1=1/2, дисперсия Р1=1/12. Заметно реже в качестве стандартной используют дискретную случайную величину е, которая с одинаковой вероятностью может принимать 10 значений О, 1, 2,..., 9. Распределение е задается таблицей ( о,! о,! о,! ... о,! ) Мы будем называть величину Т случайным числом, а величину е случайной цифрой Иногда е называют де- тРН спОсОБА пОлучения случАиных величин !1 сятичной случайной цифрой, чтобы отличить ее от двоичной случайной цифры — величины а с распределением 0,5 0,5 Чтобы установить связь между т н е, разло>кпм чпс. ло ц в бесконечную десятичную дробь: '1=0, Е>Е ...
Ее ... (1),' Последняя запись означает, что 7=~ ее)О А. О=> Теорем а 1. Леслгичнь>е цифрьс сь..., с„,... случайного числа ц г>редставлл>от собой незавеесимые случайные цифры. Обри>т>о, если еь..., е,,...— независимые случайные цифры, го формула (1) определяет случайное число. Д о к а з а т е л ь с т Б о.
Если величина Т равномерно распрсдегена в (О, 1), то е,=) тогда и только тогда, ко~да О, е, ...еь й~(у(0, е> ...Б>, >1+0, 0...01, (2),' причем еь ..., е,, в (2) могут принимать любые значения О, 1, ..., 9. Так как длина каждого пз интервалов (2) равна 1О " и интервалы этн попарно не пересекаюгся, то Р(ел=1)= ~~' 1О "=1О" '.10 '=0,1; е„...иь >=О сумма берется по всем интервалам, так что сь ..., с, > независимо пробегают значения О, 1, ..., 9. Пусть теперь 1(з()г. Рассмотрим вероятность одновременного выполнения равенств Р (ее=(, Б,=Д. Очевидно, оба эти равенства будут выполнены тогда н только тогда, когда выполнено неравенство (2), и в то же время е,=у. Следовательно, 9 Р(се =с', е,=)')= Х 10-'=0,01 ° е„..., е >, ее+И..., е>, >=О 12 получение случлпных Величиннл эвм )гл т Точно так же Р(е»,=!1...,,Е» =1,)=10-' и, таким образом, Р (е», = 1„ ..., е», = !',) = Р (е», = з,) ...
Р (е», = !з), а это означает независимость е»„..., е»,. Перейдем к доказательству обратного утверждения. Произвольное число х из интервала (О, 1) запишем в форме бесконечной десятичной дроби х=О, а! аз ...а, ... (3) Если т(х, то в разложении (1) либо е1(а1, либо е1= =а! и ез(аз, либо е! — — а1, ее=аз и ез(аз, и т. Д, Поэтому Р(у(х) = 2; Р (е, = а„..., е» ! = а» 1, е» < а»). »=1 Так как по условию теоремы все еь..., Е„независимы, то СО Р(у < х) = ~ Р(е, =-а!) . Р(е»-1 =- а» -1) Р(е»<'а»).
» =-1 Легко видеть, что Р(е»<а») =а» !0-1, нбо значениями е, в этом случае могут быть О, !... ໠— !. Значит, Р(у<" х) = ~ а»10 ' 10 " "= ~~ а»10 '= х, »:=1 » =1 и теорема доказана. 1.2. О приближенных случайных числах. В вычислениях всегда используют числа с конечным количеством десятичных знаков, поэтому вместо случайных чисел т употребляют конечные десятичные дроби т=О, е1... е„. Никаких специальных исследований по этому поводу мы проводить не будем: мы считаем, что здесь имеет место ошибка округления такая же, как при любых приближенных вычислениях.
Отме!ин одно простое свойство чисел у, которое теряегся прп такоч приближении '). *) В книге использованы следующие обозначения: с((к) — целая часть числа к (т. е. наибольшее целое число, не превосходящее .1), )1(к) — дробная часть числа к (т. е. Д (к) =л — 4(х)). трн спосопл получения случлиных Величин )3 Т е о р е м а 2. Пусть у — произвольное целое положительное число.
Случайная величина т!=П(уу) равномерно распределена е интервале (О, 1), принадле1кят ~~~~р~~~у (О В ность я — 1 р (ц < х) = ~я~~ (з (й <,, < й + „) а=а в — 1 к — 1 = 2; р (йу-' м у < (й+,),-~) л=в а=а что н требовалось доказать Ясно, что приближенная случайная величина у=о, в, , е„ не обладает таким свойством, так как при е=р2 ", где р — пелое, Д(д» =О ИПОГДа аЫЧиСЛ1ПЕЛЯ ПЫГаЮтСЯ ИСПОЛЬЗОВаГЬ ЦИФРЫ Ен ..., Ев числа у для одной цели, а цифры ее+1,..., с„— для другой.
Теоретически такой прием вполне обоснован: пз теоремы ! вытекает, что одно случайное число у эквивалентно бесконечной последовательности случайных величин у: О, ет ... еп, О, е„+! ... вз„, О, вал+1 ... ез„, ° Тем не менее его не всегда можно рекомендовать на практике: как мы увидим ниже, «качество» слу шйных чпсеч, используемых в расчетах, проверяется с помошью специальных тестов; и исрелко главные разряды — вг, ея ез чисел у оказываются гораздо лучше проверенными, чем более далекие разряды, !.3. Таблицы случайных цифр. Предположим, что мы осуществили )у' независимых опытов, в результате которых получили )ч' случайных цифр вь ..., е . Записав эти цифры (а порядке появления) в таблицу, получим то, что называется таблицей случайньгх цифр (см.
стр. 295, где цифры объединены в группы только ради удобства чтения). Способ употребления такой таблицы весьма прост. Если в ходе расчета некоторой задачи нам потребуется случайная цифра е, то мы можем взять любую цифру е, из этой таблицы. Если нам понадобится случайное число Т, то мы можем взять из таблицы и очередных цифр и считать, что Т=О, е, е,+1... з.+ -1. Выбирать цифры из такой таблицы в случайном порядке не обязательно. Их можно выбирать подряд. Но, конечно, можно начинать с любого места, читать в любом направлении, использовать любой заранее заданный алгоритм 14 ПОЛУт!СИИЕ СЛУк!ЛПИЫХ ВЕЛИЧИИ ИЛ ЭВМ !ГЛ ! выбора, не зависящий от конкретных значений цифр таблицы в). Все сказанное выше относится к «идеальной» таблице случайных цифр и не вызывает никаких сомнений.
Мы не будем подробно останавливаться на трудностях, возникающих прн переходе к «реальным» таблицам, но отметим некоторые из них. Во-первых, изготовление хорошей таблицы — весьма сложное дело, ибо в любом реальном опыте всегда возможны ошибки. Например, для изготовления таблицы (166], содержащей миллион случайных цифр, была построена и тщательно отлажена специальная «рулетка» (с использованием злектроники). Тем не менее после некоторого периода хорошей работы оиа стала выдавать, как показала проверка, не равновероятные цифры. Таким образом, проверка «качества» таблицы абсолютно необходима.
Никакие априорные соображения о тщательности постановки опыта не гарантируют нас от ошибок. Тесты для проверки таблиц случайных цифр рассмотрены ниже в 9 3. Здесь только поясним, что проверяется частота каждой из десяти цифр, частота различных соседних пар и т. п. Вторая трудность связана с «незаконностью» многократного использования одной и той же таблицы. Вычислителей этот вопрос не очень беспокоит, так как интуитивно ясно, что таблицу можно повторно использовать прп решении независимых задач (впрочем, что такое «независимые» задачи — не очень ясно). Возможность использования одних н тех же случайных величин для решения целых классов задач доказана ниже в гл.
3, $ 4. Наконец, отметим еще известный парадокс: в большой таблице найдутся плохие участки. (Например, в таблице, содержащей 10!вз цифр, вполне вероятно найти ') Таблицы случайных пнфр очень удобны для осупссствлеиия случайной выборки. Пусть, например, требуется из 55 предматов отобрать случайно 6 предметов. Зануисрусм исходное мнозкество предметов и воспользусцся таблицей со стр.
295. Рассмотрим пары цифр нз таблипы: 85, 5!, 59, 07, 95, 55, !5, 55, 54, ... и отберем предметы с номерами, оказавшимися в этой послсдовзтсльиостн: 5!, 07, 15, 34, 23, 32. 1 !1 тРи спосоеА полу'!ш!ия слу~!Апных Величин 1В 100 пулей подряд.) Очевидно, самостоятельное использование таких участков недопус!Иыо. В настоящее время таблицы случайных цифр (нли более разнообразные таблицы случайных величин) используют главным образом прн расчетах вручную; для расчетов на ЭВМ ими практически не пользуются.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
