Советов Б.Я., Яковлев С.А. Моделирование систем (2001) (1186219), страница 30
Текст из файла (страница 30)
д. Кроме того, при некоторых г* вообще может наблюдаться вырождение последовательности, т. е. х,=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, полученные методом статистического моделирования наЭВМ, существенно зависят от качества используемых псевдослучайных квазиравномерных последовательностей чисел. Поэтому всеприменяемые генераторы случайных чисел должны перед моделированием системы пройти тщательное предварительное тестирование,которое представляет собой комплекс проверок по различным статистическим критериям, включая в качестве основных проверки(тесты) на равномерность, стохастичность и независимость. Рассмотрим возможные методы проведения таких проверок, наиболеечасто используемые в практике статистического моделированиясистем.Проверка равномерности последовательностей псевдослучайных квазиравномерно распределенных чисел {*,-} может быть выполнена по гистограмме с использованием косвенных признаков [4, 26].
Суть проверки по гистограмме сводится к следующему. Выдвигается гипотеза о равномерности распределения чисел в интервале (О,1). Затем интервал (0, 1) разбивается на т равных частей, тогда при генерациипоследовательности {х,} каждое из чисел х с вероятностью pj= l/m,j= 1, т, попадаетв один из подынтервалов. Всего в каждый J-й подынтервал попадает Nj чиселЯ1последовательности {х(}, «=1, N, причем N— £ Nj. Относительная частота попадания случайных чисел последовательности {*/} в каждый из подынтервалов будетравна Nj/N. Вид соответствующей гистограммы для примера показан на рис.
4.11, а,где пунктирная линия соответствует теоретическому значению pj, а сплошная —экспериментальному Nj/N. Очевидно, что если числа х, принадлежат псевдослучайной квазиравномерно распределенной последовательности, то при достаточно больших N экспериментальная гистограмма (ломаная линия на рис. 4.11, а) приблизитсяк теоретической прямой 11т.Оценка степени приближения, т. е. равномерности последовательности {xt},может быть проведена с использованием критериев согласия. На практике обычнопринимается л?=20-^50, N=(\02 + \03)m.Суть проверки равномерности по косвенным признакам сводится к следующему.Генерируемая последовательность чисел {х,} разбивается на две последовательности:а)1/тРис. 4.11.
Проверка равномерности последовательности124xl>*Ji -fji —ix2i-l>•** **. x6, .... x2l; / - 1 , N.Затем проводится следующий эксперимент. Бели выполняется условиех1_у+xl<l, i-TTN,(4.13)то фиксируется наступление некоторого события и в счетчик событий добавляетсяединица. После Я/2 опытов, когда генерировано N число, в счетчике будет некотороечисло k^N/2.Геометрически условие (4.13) означает, что точка (ха-ь хгд> '""1. ^> находитсявнутри четверти круга радиусом г = 1 , что иллюстрируется рис.
4.11, б. В общемслучае точка ( х а - ь ха) всегда попадает внутрь единичного квадрата. Тогда теоретически вероятность попадания этой точки в четверть кругаРх ="Si / 4 хруп/Здмщраи=(я^/4)/(1 • 1)=Я/4.Если числа последовательности {*/} равномерны, то в силу закона большихчисел теории вероятностей при больших N относительная частота 2kjN-ni/4.Проверка стохастичности последовательностей псевдослучайных чисел {*/} наиболее часто проводится методами комбинаций и серий [7,11, 25]. Сущность методакомбинаций сводится к определению закона распределения длин участков междуединицами (нулями) или закона распределения (появления) числа единиц (нулей) в празрядном двоичном числе Xt.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
