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

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

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

Иначе говоря, надо найти, при какихусловиях равенствоXtmX9 (mod M)(4.14)справедливо при минимальном значении •s=Af—1.Можно записать [см. (4.11)], что Xt+,^X Xi(modM),место припоэтому (4.14) имеетx'=l(modM)(4.15)(здесь существенно, что Х0 взаимно просто с М).По условию требуется, что наименьший показатель степени s=Pu(A), удовлет­воряющий (4.15) и называемый показателем А по модулю М, был равен. Л/— 1. Длялюбого простого модуля М существует ср (М— 1) значений X (первообразных корней),удовлетворяющих уравнению (4.15) при Рм(Л)=<р(Ж0> где q>{M) —функция Эйлера,определяемая как число натуральных чисел т^М, взаимно простых с М.

Дляпростого модуля М имеем q> (M)=М—\.Таким образом, доказано существование многих А, при которых повторениеэлементов последовательности {х,} наступит на (А/— 1)-м числе д.'л/-ь т. е.L=P=M—\, что и требовалось доказать.Для алгоритмов получения последовательностей чисел {х,} об­щего вида (4.10) экспериментальная проверка является сложной(из-за наличия больших Р и L), а расчетные соотношения в явномвиде не получены.

Поэтому в таких случаях целесообразно провеститеоретическую оценку длины отрезка апериодичности последовате­льности L. Для этого воспользуемся элементарной вероятностноймоделью, рассмотренной в следующем примере [4, 36, 37].Пример 4.6. Пусть имеется конечное множество, содержащее Л' различных чисел.Проведем последовательность независимых опытов, в каждом из которых из этогомножества извлекается и записываетсяодно число.

Вероятность извлечения любогочисла в каждом из опытов равна 1/N, так как выборка чисел проводится с возвратом.Обозначим через L случайную величину номер опыта, в котором впервые будетснова извлечено уже записанное ранее число Можно доказать, что в данной вероят­ностной модели для любого х > 0 имеем128—lim Р{Ь/^Ы<х} = 1-е— x*I2JV-oOТак как математическое ожидание случайной величины с такой функцией рас­пределения равно у/п/2, то при N-»oo получим M[L] = y/nN/2. Такая оценка длиныотрезка апериодичности «груба», но полезна на практике для предварительногоопределения L с целью дальнейшего уточнения экспериментальным путем.Рассмотрим некоторые особенности статистической проверкистохастичности псевдослучайных последовательностей.

Для такойпроверки могут быть использованы различные статистические кри­терии оценки, например критерии Колмогорова, Пирсона и т. д. Нов практике моделирования чаще всего пользуются более простымиприближенными способами проверки [29, 37].Для проверки равномерности базовой последовательности слу­чайных чисел xt, f=l, N, можно воспользоваться такими оценками:(1/N) £ x,= l/2,(l/JV) £ *? = l/3.i=li= lДля проверки таблиц случайных цифр обычно применяют раз­личные тесты, в каждом из которых цифры классифицируются понекоторому признаку и эмпирические частоты сравниваются с ихматематическими ожиданиями с помощью критерия Пирсона [29,46].Для проверки аппаратных генераторов случайных чисел можноиспользовать те же приемы, что и для проверки последователь­ностей псевдослучайных чисел, полученных программным спосо­бом.

Особенностью такой проверки будет то, что проверяются не течисла, которые потом будут необходимы для моделирования систе­мы S. Поэтому кроме проверки качества выдаваемых генераторомслучайных чисел должна еще гарантироваться устойчивая работагенератора на время проведения машинного эксперимента с моде­лью Мм.Улучшение качества последовательностей. В силу рассмотренныхпреимуществ основное применение в практике имитационного мо­делирования систем находят различные программные способы по­лучения чисел. Поэтому рассмотрим возможные методы улучшениякачества последовательностей псевдослучайных чисел.

Одним изнаиболее употребительных методов такого улучшения являетсяупотребление вместо формул вида (4.9), представляющих собойрекуррентные формулы первого порядка, рекуррентных формулпорядка г, т. е.где начальные значения х0, xlt ..., xr_t заданы. В этом случае длинаотрезка апериодичности L у такой последовательности при г>\129гораздо больше, чем при г= 1. Однако при этом возрастает слож­ность метода, что приводит к увеличению затрат машинного време­ни на получение чисел и ограничивает возможности его примененияна практике.Для получения последовательности псевдослучайных чисел с бо­льшой длиной отрезка апериодичности L можно воспользоватьсяметодом возмущений [29, 37]. В основу этого метода полученияпоследовательности чисел положена формула вида(Ф(х,), если i=0 (mod M),'* {Ч(р:д, если i=0(modA0,Х1где функции Ф(и) и Y(u) различны.В этом случае в основном используется формула х1+1=Ф(хд,и только когда / кратно М, последовательность «возмущается»,т.

е. реализуется переход к формуле хш=44x1). Целое число М на­зывается периодом возмущения.Все рассмотренные критерии проверки последовательностей псе­вдослучайных чисел являются необходимыми при постановке ими­тационных экспериментов на ЭВМ с моделью Л/ы, но об их до­статочности можно говорить лишь при рассмотрении задачи моде­лирования конкретной системы S.4.4. МОДЕЛИРОВАНИЕ СЛУЧАЙНЫХ ВОЗДЕЙСТВИЙНА СИСТЕМЫПри моделировании системы S методом имитационного моде­лирования, в частности методом статистического моделирования наЭВМ, существенное внимание уделяется учету случайных факторови воздействий на систему. Для их формализации используютсяслучайные события, дискретные и непрерывные величины, векторы,процессы.

Формирование на ЭВМ реализаций случайных объектовлюбой природы из перечисленных сводится к генерации и преоб­разованию последовательностей случайных чисел. Вопросы генера­ции базовых последовательностей псевдослучайных чисел {х;}, име­ющих равномерное распределение в интервале (0, 1), были рассмот­рены в § 4.2, поэтому остановимся на вопросах преобразованияпоследовательностей случайных чисел {*,} в последовательность{>>(} для имитации воздействий на моделируемую систему S.Эти задачи очень важны в практике имитационного моделирова­ния систем на ЭВМ, так как существенное количество операций,а значит, и временных ресурсов ЭВМ расходуется на действия сослучайными числами. Таким образом, наличие эффективных мето­дов, алгоритмов и программ формирования, необходимых длямоделирования конкретных систем последовательностей случайныхчисел {у,}, во многом определяет возможности практического ис130пользования машинной имитации для исследования и проектирова­ния систем [37, 46].Моделирование случайных событии.

Простейшими случайнымиобъектами при статистическом моделировании систем являютсяслучайные события. Рассмотрим особенности их моделирования [4].Пусть имеются случайные числа xh т. е. возможные значенияслучайной величины £,, равномерно распределенной в интервале (О,1). Необходимо реализовать случайное событие А, наступающеес заданной вероятностью р. Определим А как событие, состоящеев том, что выбранное значение х, случайной величины £ удовлет­воряет неравенствух^р.(4.16)рТогда вероятность события А будет Р{А)=\ dx=p. Противопо_о_ложное событие А состоит в том, что xt>p. Тогда Р(А)= 1 — р.Процедура моделирования в этом случае состоит в выборезначений х, и сравнении их с р. При этом, если условие (4.16)выполняется, исходом испытания является событие А.Таким же образом можно рассмотреть группу событий.

ПустьАи А2, ..., Aj — полная группа событий, наступающих с вероят­ностями ри р2, ..., р, соответственно. Определим Ат как событие,состоящее в том, что выбранное значение х, случайной величины£ удовлетворяет неравенству4,-1 <**</«,(4-17)Ггде 1Т— £ р,.

ТогдаlmP(Am)= J dx=pm.Im-lПроцедура моделирования испытаний в этом случае состоитв последовательном сравнении случайных чисел xt со значениями4. Исходом испытания оказывается событие Ат, если выпол­няется условие (4.17). Эту процедуру называют определением ис­хода испытания по жребию в соответствии с вероятностями р1гРг> •••» А -Эти процедуры моделирования были рассмотрены в предполо­жении, что для испытаний применяются случайные числа х„ име­ющие равномерное распределение в интервале (0, 1). При модели­ровании на ЭВМ используются псевдослучайные числа с квазирав­номерным распределением, что приводит к некоторой ошибке. Оце­ним ее.131Пример 4.7. Пусть имеются л-раэрядвые случайные числа с возможными значе­ниями Jtf-f/(2 - 1 ) , i=0,2 —1.

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

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