Советов Б.Я., Яковлев С.А. Моделирование систем (3-е изд., 2001) (1186218), страница 29

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Кроме того, для получениязначений х случайной величины £ используются формулы (алгорит­мы). Поэтому такие последовательности, являющиеся по своей сутидетерминированными, называются псевдослучайными [4, 29].Требования к генератору случайных чисел. Прежде чем перейтик описанию конкретных алгоритмов получения на ЭВМ последова­тельностей псевдослучайных чисел, сформулируем набор требова­ний, которым должен удовлетворять идеальный генератор.

Полу­ченные с помощью идеального генератора псевдослучайные после­довательности чисел должны состоять из квазиравномерно рас­пределенных чисел, содержать статистически независимые числа,быть воспроизводимыми, иметь неповторяющиеся числа, получать­ся с минимальными затратами машинного времени, занимать ми­нимальный объем машинной памяти.Наибольшее применение в практике моделирования на ЭВМ длягенерации последовательностей псевдослучайных чисел находят ал­горитмы вида*+! = *(*.),(4-9)представляющие собой рекуррентные соотношения первого поряд­ка, для которых начальное число х0 и постоянные параметрызаданы [36, 37].119Определим качественно требования к виду функции Ф. Напри­мер, легко показать, что функция вида (4.9), изображенная на рис.4.10, а, не может породить хорошую последовательность псевдо­случайных чисел х1г хг, ...

Действительно, если построить точкис координатами (xt, x2), (х3, xj по случайным числам, полученным,например, из таблицы случайных чисел (табл. 4.2), то они будутравномерно распределены в единичном квадрате 0 < х ( ^ 1 ,0<JC ( + I< 1. Соответствующие же точки, построенные по числам (xt,Ф(*2))» (хз> Ф(.х*))> —. располагаются в площади, ограниченнойкривой хп i = Ф (*,).Хорошую последовательность случайных чисел может породитьтолько такая функция х,+1 =Ф (*,), график которой достаточно плот­но заполняет единичный квадрат.

Примером такой функции можетслужить xi+i=/J(Ax!) при больших целых положительных А, гдеД(и)=и—Ц(и) — дробная часть числа и; Ц(и) — целая часть числаи, т. е. наибольшее целое число, не превосходящее и. Пусть дляпримера А = 10, тогда функция х1+1=Ф(х1) будет иметь вид, пока­занный на рис. 4.10, б. Приведенные условия являются тольконеобходимыми, но не достаточными для того, чтобы соотношение(4.9) порождало хорошие последовательности псевдослучайных чи­сел.Рассмотрим некоторые процедуры получения последовательно­стей псевдослучайных квазиравномерно распределенных чисел, ко­торые нашли применение в практике статистического моделирова­ния систем на ЭВМ.Одной из исторически первых процедур получения псевдослучай­ных чисел была процедура, получившая название метода середин­ных квадратов.

Пусть имеется 2л-разрядное2число, меньшее 1: х,=0,at а2 —а-ъ,. Возведем его в квадрат: дс, =0, bl Ьг ... Ь4п, а затемотберем средние 2л разрядов xt+l=0, fc„+I Ья+2 — Ь3„, которые и будутявляться очередным числом псевдослучайной последовательности.Например, если начальное2 число лсо=0,2152, то (х0)2=0,04631104,т. е. *!=0,6311, затем (xj) =0,39828721, т. е. х2=0,8287, и т. д.Недостаток этого метода — наличие корреляции между числа­ми последовательности, а в ряде случаев случайность вообщеможет отсутствовать. Напри­мер, если х0=0,4500, то(JC0)2 = 0,20250000, x 1 = 0,2500,(JCJ)2 = 0,06250000, JC2 = 0,2500,(JC2)2 = 0,06250000,x 3 = 0,2500и т.

д. Кроме того, при некото­рых г* вообще может наблю­даться вырождение последова­тельности, т. е. х,=0 при/>/*. Это существенно ограниРис. 4.10. Вид функции Ф120чиваетвозможностииспользованияметодасерединныхквадратов.Конгруэнтные процедуры генерации. Широкое применение примоделировании систем на ЭВМ получили конгруэнтные процедурыгенерации псевдослучайных последовательностей, представляющиесобой арифметические операции, в основе которых лежит фунда­ментальное понятие конгруэнтности.

Два целых числа а. к В конгру­энтны (сравнимы) по модулю т, где т — целое число, тогда и толь­ко тогда, когда существует такое целое число к, что а—В=кт, т. е.если разность а.—В делится на т и если числа а и В дают одинаковыеостатки от деления на абсолютнуювеличину числа т.

Например,1984=4 (mod 10), 5008 = 8 (mod 103) и т. д.Таблица 4.2щ865156918641686865227258794377916415380712311144807913025731459041997615218731892870917932945900874991682876537942985444857390255574364216565005518788418991610739976184659079503393421634717193000578021886700607903165096190410375257560104925492866444838238666862256143448128049808866186394534432652905167969366211244913326920752141212798765066155425028518188059896885245276773048258711384754454201628770492078248957131276762086425470177284842914275162591576798191641846375957581305298353279566785888983669465509664349922438967893427841642499975268213484778576167775766181102747604442903707957657557598035691632565877974969511449687408377615432764588463580154313872252377585970660655655888955331816724827589333462725680317458633813275593732442397432373595983307153163266232130262786645175929716021368019303014150910906955823472390720549830649221489101612332537587266409082995288393566447751202452064294514356187014783053125677496929584819173017381314663146679636308903866603675078766651541675227001680951512865456010250324Конгруэнтные процедуры являются чисто детерминированны­ми, так как описываются в виде рекуррентного соотношения, когдафункция (4.9) имеет вид121Х1+1 =ХХ,+ц (mod АО,(4.10)где X,, Л, ц, М — неотрицательные целые числа.Раскроем рекуррентное соотношение (4.10):Xt = ХХ0+ц (mod M);Х2=ХХХ+/i=Х*Х0+(Л+ IMmod M)\^з=ЛAr 2 +^i=Л 3 ^ 0 +a 2 +Я^-l)^i=A 3 Z o +(A 3 -l)^i/(;.-l)(modA0;*j=Х%+(A'- l)/i/(A- l)(mod Af).(4.11)Если заданы начальное значение Х0, множитель Л и аддитивнаяконстанта ц, то (4.11) однозначно определяет последовательностьцелых чисел {X,}, составленную из остатков от деления на М членовпоследовательности {ХХ0+ц(Л— 1)/(А— 1)}.

Таким образом, длялюбого !>1 справедливо неравенство Xt<M. По целым числампоследовательности {Л^} можно построить последовательность{*,} = {XJM} рациональных чисел из единичного интервала (0, 1).Конгруэнтная процедура получения последовательностей псев­дослучайных квазиравномерно распределенных чисел может бытьреализована мультипликативным либо сметанным методом.Мультипликативный метод. Задает последовательность неотри­цательных целых чисел {А",}, не превосходящих М, по формулеXi+l=XX,(modM),(4.12)т. е. это частный случай соотношения (4.10) при ц=0.В силу детерминированности метода получаются воспроизводи­мые последовательности. Требуемый объем машинной памяти приэтом минимален, а с вычислительной точки зрения необходимпоследовательный подсчет произведения двух целых чисел, т.

е.выполнение операции, которая быстро реализуется современнымиЭВМ.Для машинной реализации наиболее удобна версия М=р', гдер — число цифр в системе счисления, принятой в ЭВМ (р=2 длядвоичной и р= 10 для десятичной машины); g — число битов в ма­шинном слове. Тогда вычисление остатка от деления на М сводитсяк выделению g младших разрядов делимого, а преобразованиецелого числа Х( в рациональную дробь из интервала х,е(0, 1)осуществляется подстановкой слева от X, двоичной или десятичнойзапятой.Алгоритм построения последовательности для двоичной маши­ны М=2в сводится к выполнению таких операций [31, 36, 46]:1221.

Выбрать в качестве Х0 произвольное нечетное число.2. Вычислить коэффициент X=8* ±3, где / — любое целое поло­жительное число.3. Найти произведение ХХ0, содержащее не более lg значащихразрядов.4. Взять g младших разрядов в качестве первого члена последо­вательности Хи а остальные отбросить.5. Определить дробь JCJ =XJ2g из интервала (0, 1).6.

Присвоить X0=Xt.7. Вернуться к п. 3.Пример 4.4. Необходимо получить числа последовательности для случая g=4,используя приведенный алгоритм мультипликативного метода. Для этого выполня­ем следующие действия: 1. Выбираем Дою=7 (в десятичной системе счисления) илиЯГ0=ОШ (в двоичной системе счисления). 2. Найдем (=1, тогда Лю —И или 5; пустьЛ 1 0 -5, Я=0101.

3. Рассчитываем произведение ХХ0, берем я младших разрядов,вычисляем Xt и присваиваем Х0=ХХ, т. е. выполняем п. 3 — 7 алгоритма:а)б)в)г);Х,-(0101)(ОШ)>=00100011, ЛГ. =0011, х,—3/16-0,1875;АА^ =(0101)(0011)=00001111, Г 2 =1111, х,-15/16-0,9375;ЛДГ,«.(0101)(1111)=01001011, ДГ3 = 1011,*,-11/16-0,6875;ЯЯГ3=(0101)(1011)=00110111, Л^-0111, х 4 -7/16-0,4375.Смешанный метод.

Позволяет вычислить последовательностьнеотрицательных целых чисел {X,}, не превосходящих М, поформулеX,+l=XXi+n (mod M),т. е. в отличие от мультипликативного метода цФЪ.С вычислитель­ной точки зрения смешанный метод генерации сложнее мультип­ликативного на одну операцию сложения, но при этом возможностьвыбора дополнительного параметра позволяет уменьшить возмож­ную корреляцию получаемых чисел.Качество конкретной версии такого генератора можно оценитьтолько с помощью соответствующего машинного эксперимента.В настоящее время почти все пакеты прикладных программуниверсальных ЭВМ для вычисления последовательностей равно­мерно распределенных случайных чисел основаны на конгруэнтнойпроцедуре [17, 38, 40].4.3. ПРОВЕРКА И УЛУЧШЕНИЕ КАЧЕСТВА ПОСЛЕДОВАТЕЛЬНОСТЕЙПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛЭффективность статистического моделирования систем на ЭВМи достоверность получаемых результатов существенным образомзависят от качества исходных (базовых) последовательностей псев­дослучайных чисел, которые являются основой для получения сто­хастических воздействий на элементы моделируемой системы.

По­этому, прежде чем приступать к реализации моделирующих ал­горитмов на ЭВМ, необходимо убедиться в том, что исходная123последовательность псевдослучайных чисел удовлетворяет предъяв­ляемым к ней требованиям, так как в противном случае даже приналичии абсолютно правильного алгоритма моделирования процес­са функционирования системы S по результатам моделированиянельзя достоверно судить о характеристиках системы [29, 37].Проверка качества последовательностей. Результаты анализа си­стемы S, полученные методом статистического моделирования наЭВМ, существенно зависят от качества используемых псевдослучай­ных квазиравномерных последовательностей чисел.

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

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