Главная » Просмотр файлов » 1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b

1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (844202), страница 22

Файл №844202 1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (Войтишек - Лекции по численным методам Монте-Карло) 22 страница1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (844202) страница 222021-07-16СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 22)

также формулы (9.10),(9.11) и (9.13)).Особо отметим, что последовательности вида (9.4) являются характерными примерами циклических групп вида (9.3) (см., например, [30]).Конкретные значения для параметров K и Q обусловлены широким применением алгоритма (9.4) с достаточно большими значениямистепеней m и 2p + 1 для реализации датчиков псевдослучайных чисел,используемых в алгоритмах метода Монте-Карло (см., например, [9, 13],а также подразделы 2.4, 9.3, 9.5 данного пособия).Мультипликативный метод вычетов (9.4) по модулю K = 2m длявыбранного множителя Q = 52p+1 обладает минимальной (для различных Q) мерой управляемости, равной µ = 1/2m−2 (см. далее подраз136дел 9.5), что обуславливает целесообразность использования этого алгоритма в качестве численной модели случайной величины α, равномернораспределенной в интервале (0, 1).9.2. Двоичное представление случайной величины α ∈ U (0, 1).Использование стандартных случайных чисел {αi }, представляющихсобой выборочные значения случайной величины α, равномерно распределенной в интервале (0, 1), является по сути единственным инструментом «воспроизведения случайности» на ЭВМ с целью применениячисленных алгоритмов метода Монте-Карло для решения методическихи прикладных задач.Случайная величина α ∈ U (0, 1) имеет функцию распределения 0 для x ∈ (−∞, 0];x для x ∈ (0, 1);Fα (x) = P{α < x} =(9.5)1 для x ∈ [1, +∞)(см.

также формулу (2.12) и рис. 2.2) и характеристики Eα = 1/2,Dα = 1/12 (см. формулы (2.13)). Важным свойством этой случайнойвеличины, которое активно используется при обосновании алгоритмовметода Монте-Карло, является то, чтоP{α ∈ (c, d) ⊆ (0, 1)} = d − c,(9.6)см. также формулу (2.14) и рис. 2.3.Значения {αi } получаются на ЭВМ с помощью специальной программы или устройства, которое называется генератором стандартныхслучайных (псевдослучайных) чисел.Важным для практического построения генераторов стандартныхслучайных чисел является следующее рассуждение (см., например,[9, 13]). Учтем первым делом то обстоятельство, что числа в компьютереимеют двоичное представление.Поскольку α ∈ (0, 1), то двоичное представление каждого выборочного значения этой случайной величины имеет видα = 0, α(1) .

. . α(k) . . . =∞Xα(k) 2−k ,(9.7)k=1причем каждый разряд α(k) мантиссы числа (9.7) равен нулю или единице.УТВЕРЖДЕНИЕ 9.2 (см., например, [9]). Для того чтобы случайная величина α была равномерно распределенной в интервале (0, 1),137необходимо и достаточно, чтобы двоичные цифры α(1) , . . . , α(k) , . . . изсоотношения (9.7) представляли собой последовательность независимых бернуллиевских случайных величин с вероятностью успеха 1/2: 1P α(k) = 1 = P α(k) = 0 = .2ДОКАЗАТЕЛЬСТВО.

Необходимость. Поскольку случайная величина (9.7) равномерно распределена в (0, 1), то α(k) = 0 при0, α(1) . . . α(k−1) 0 ≤ α < 0, α(1) . . . α(k−1) 1,(9.8)причем α(1) , . . . , α(k−1) в (9.8) могут принимать значения 0 и 1. Длина интервала (9.8) равна 2−k , и интервалы (9.8) для разных наборовα(1) , . . . , α(k−1) не пересекаются, поэтому, используя соотношение (9.6),получаем1XP α(k) = 0 =2−k = 2k−1 × 2−k =α(1) ,...,α(k−1) =01.2(9.9)Тогда P α(k) = 1 = 1 − P α(k) = 0 = 1/2.(s)(k)Докажем теперь независимость (k) α и α(s) , где1 ≤ s < k. Для этогорассмотрим вероятность P α = i ∩ α = j .

Это число, очевидно, можно рассматривать как условную вероятность того, что выполнено соотношение типа (9.8) при условии, что α(s) фиксировано. Тогдапо аналогии c равенством (9.9) имеем1XP α(k) = i ∩ α(s) = j =2−k =α(1) ,...,α(s−1) ,α(s+1) ,...,α(k−1) =0= 2k−2 × 2−k =1= P α(k) = i × P α(s) = j .4АналогичноP α(k1 ) = i1 ∩..∩ α(kq ) = iq } = 2−q = P α(k1 ) = i1 ×..×P α(kq ) = iq ,а это и означает независимость случайных цифр числа (9.7).Достаточность. Очевидно, что дробь из правой части соотношения(9.7) принадлежит интервалу (0, 1), поэтому(∞)(∞)XXPα(k) 2−k < x = 0 при x ≤ 0 и Pα(k) 2−k < x = 1k=1k=1138при x ≥ 1.Возьмем произвольноеx = 0, a1 a2 . .

. ak . . . из интервала (0, 1) и поP∞(k) −kα2< x = x.кажем, что Pk=1P∞(k) −kЕсли k=1 α 2 < x , то либо α(1) < a1 , либо α(1) = a1 и α(2) < a2 ,либо α(1) = a1 , α(2) = a2 и α(3) < a3 и т. д. Таким образом,(∞)∞XX(k) −kPα 2 <x =P α(1) = a1 ∩ .. ∩ α(k−1) = ak−1 ∩k=1∩ α(k) < akk=1=∞XP α(1) = a1 ×..×P α(k−1) = ak−1 ×P α(k) < ak ;k=1здесь использована независимостьцифр α(1) , . . . , α(k) .

(k) случайныхЛегко проверить, что P α < ak = ak /2. Поэтому(∞)∞∞XX X(k) −kPα 2 <x =2−(k−1) × ak 2−1 =ak 2−k = x.k=1k=1k=1Таким образом, функция распределения случайной дроби из правойчасти соотношения (9.7) совпадает с функцией (9.5). Утверждение 9.2доказано.9.3. Два типа генераторов стандартных случайных чисел.С одной стороны, доказанное утверждение 9.2 может повергнуть исследователя в некоторое уныние, так как оно говорит о том, что «настоящее» стандартное случайное число (9.7) имеет бесконечную мантиссу,воспроизвести которую на ЭВМ невозможно.С другой стороны, можно отметить, что в вычислительной математике машинные ошибки, связанные с конечностью мантиссы, часто неучитываются (в качестве примера можно указать использование форматов вещественных чисел на ЭВМ).

Для используемых на практикегенераторов случайных чисел эффекты, связанные с конечностью мантиссы, как правило, незначительны.Утверждение 9.2 обосновывает принцип работы так называемых физических датчиков случайных чисел. Это технические устройства(чаще всего «шумящие» электронные приборы), которые вырабатывают случайную последовательность двоичных цифр (условно: лампочкагорит или не горит с вероятностью 1/2; если вероятность не равна 1/2,то целесообразно брать пары событий «да – нет» и «нет – да», а события«да – да», «нет – нет» отбрасывать).139К преимуществам такого способа получения случайных чисел относят быстроту реализации и неограниченность запаса случайных чисел.Недостатком физических датчиков случайных чисел является то,что периодически требуется статистическая проверка вырабатываемыхслучайных чисел (поскольку даже сверхнадежное техническое устройство дает сбои).

Кроме того, нет возможности воспроизвести расчеты.Следует тем не менее заметить, что существует немало вычислителей,которые предпочитают именно физические датчики случайных чисел,и работы по конструированию таких устройств продолжаются.Большинство расчетов по методу Монте-Карло произведено и производится с помощью генераторов псевдослучайных чисел, представляющих собой некоторые вычислительные подпрограммы (чаще всеготакие подпрограммы называются RAN D или RAN DOM ).Аргументами в пользу применения псевдослучайных чисел являются возможность воспроизводить расчеты, быстрота получения чисел,отсутствие внешних устройств и необходимости многократной проверки качества получаемых чисел, малая загруженность памяти ЭВМ.Большинство известных алгоритмов реализации псевдослучайныхчисел представляет собой детерминированную дискретную последовательность и имеет видαn+1 = ψ(αn )(9.10)(это аналог формулы (9.1)), где начальное число α0 задано. Областьюзначений функции ψ(x) должен являться интервал (0, 1).Одно из соображений о том, каким образом следует выбирать функцию ψ(x) из соотношения (9.10), состоит в следующем.

Пары точекα1 , α2 = ψ(α1 ) , α3 , α4 = ψ(α3 ) , α5 , α6 = ψ(α5 ) , . . . ,с одной стороны, должны располагаться на кривой y = ψ(x), а с другой– эти же точки должны (по свойствам «настоящих» стандартных случайных чисел) быть равномерно распределены в квадрате∆(2) = {(x, y) : 0 < x < 1, 0 < y < 1}. Поэтому график функцииψ(x) должен достаточно плотно заполнять этот квадрат.Примером такой функции ψ(x) может служитьψ(x) = {Q x}(9.11)для большого целого положительного множителя Q; здесь {A} обозначает дробную часть числа A (рис. 9.1).140Рис. 9.1.

График функции ψ(x) = {Q x}Алгоритм (9.10) с функцией (9.11) (и с конечными мантиссами чисел{αn } из последовательности (9.10)) называется мультипликативным методом вычетов и является одним из наиболее часто употребляемых алгоритмов при моделировании псевдослучайных чисел.9.4. Два полезных свойства преобразования методавычетов. Отметим следующее свойство преобразования (9.11).УТВЕРЖДЕНИЕ 9.3 (см., например, [9, 13]).

Случайная величинаβ = {Qα} равномерно распределена в интервале (0, 1) для любого целогоположительного числа Q.ДОКАЗАТЕЛЬСТВО.ИсследуемфункциюраспределенияFβ (x) = P(β < x). Согласно определению дробной части числа, имеем β ∈ [0, 1), и поэтому Fβ (x) = 0 при x < 0 и Fβ (x) = 1 при x ≥ 1.Если x ∈ [0, 1) (см. рис. 9.2), то, используя соотношение (9.6), получаем() Q−1Q−1Q−1XXX xk+xkFβ (x) =P{k ≤ Q α < k+x} =P≤α<= x.=QQQk=0k=0k=0Сравнивая функции Fβ (x) и (9.5), делаем вывод о том, что случайная величина β равномерно распределена в интервале (0, 1). Утвержде141Рис. 9.2. Иллюстрация к доказательству утверждения 9.3ние 9.3 доказано.Таким образом, преобразование метода вычетов (9.11) сохраняет равномерное распределение в интервале (0, 1).Одним из существенных сомнений, связанных с использованием мультипликативного метода вычетов (9.10), (9.11) является то обстоятельство, что даже для «настоящих» («теоретических») стандартных случайных величин вида (9.7) члены последовательностиβ(s + 1) = {Qβ(s)} = Qs+1 β(0) ; β(0) = α(9.12)являются зависимыми случайными величинами.

Поэтому весьма важным является следующее свойство преобразования (9.11).УТВЕРЖДЕНИЕ 9.4 (см., например, [9]). Коэффициент корреляции defα − Eα  β̃ − Eβ̃ qr α, β̃ = r α, β(s) = E  √DαDβ̃равен11r α, β̃ = s = ,QQ̃где β̃ = β(s), Q̃ = Qs , для любых целых положительных чисел Q и s.ДОКАЗАТЕЛЬСТВО. Индукцией по s, используяутверждение 9.3, несложно показать, что случайная величина β̃ = Q̃α = Qs α является также стандартной. При этом Eα = Eβ̃ = 1/2, Dα = Dβ̃ = 1/12(см. соотношения (2.13)), и коэффициент корреляции равен"!!#"!!#α − 1/2β̃ − 1/2Q̃α − Q̃/2β̃ − 1/2ppppr α, β̃ = E=E=1/121/12Q̃ 1/121/12142" !!#Q̃α + Q̃α − Q̃/2 − 1/2 − 1/2β̃ − 1/2pp=E=1/12Q̃ 1/12!#"!!#"!γ − Q̃/2 − 1/2β̃ − 1/2β̃ − 1/2β̃ − 1/2pppp+E,=E1/121/12Q̃ 1/12Q̃ 1/12 где γ = Q̃α (это целая часть числа Q̃α). Случайная величина γ, принимающая значения 0, 1, .

Характеристики

Тип файла
PDF-файл
Размер
2,55 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6710
Авторов
на СтудИзбе
287
Средний доход
с одного платного файла
Обучение Подробнее