Моделирование систем




НазваниеМоделирование систем
Дата конвертации30.01.2013
Размер445 b.
ТипЛекция


ГОУ ВПО Уральский государственный технический университет – УПИ


Кафедра «Автоматика и управление в технических системах» направление 220200 – Автоматизация и управление специальность 220201 – Управление и информатика в технических системах

  • МОДЕЛИРОВАНИЕ СИСТЕМ

  • Лекция 16

  • Генерация базовой последовательности.

  • Проверка и улучшение качества последовательностей псевдослучайных чисел.

  • Преподаватель: Трофимова Ольга Геннадиевна, доц., к.т.н.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Цель изучения материала:

  • изучить методы генерации базовой последовательности случайных чисел,

  • изучить требования к генератору случайных чисел,

  • научиться проверять качество последовательностей псевдослучайных чисел,

  • изучить характеристики качества генераторов.

  • Компетенций, формирующиеся в процессе знакомства с материалом:

  • приобретать новые знания, используя современные образовательные и информационные технологии;

  • разрабатывать модели информационных систем, включая модели систем управления;

  • использовать современные технологии моделирования систем.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Содержание лекции 16

  • Раздел 4. Статистическое моделирование систем на ЭВМ.

  • Псевдослучайные последовательности и процедуры их машинной генерации.

  • Генерация базовой последовательности.

  • Требования к генератору случайных чисел.

  • Проверка и улучшение качества последовательностей псевдослучайных чисел.

  • Проверка качества последовательностей.

  • Характеристики качества генераторов



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Генерация базовой последовательности

  • При моделировании систем на ЭВМ программная имитация случайных воздействий любой сложности сводится к генерированию стандартных (базовых) процессов и к их последующему функциональному преобразованию.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Генерация базовой последовательности

  • При дискретном моделировании базовым процессом является последовательность чисел {xi} = x0, x1, …, xN, представляющих собой реализации независимых, равномерно распределенных на интервале (0, 1) случайных величин {ξi} = ξ0, ξ1, …, ξN или в статистических терминах – повторную выборку из равномерно распределенной на (0, 1) генеральной совокупности значений величины .



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Генерация базовой последовательности

  • Непрерывная случайная величина  имеет равномерное распределение в интервале (a, b), если ее функции распределения (рис. 4.9, a) и плотности (рис. 4.9, б) соответственно примут вид



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Генерация базовой последовательности

  • Рис.4.9. Равномерное распределение случайной величины



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Генерация базовой последовательности

  • Числовые характеристики случайной величины , принимающей значения x, – математическое ожидание, дисперсия и среднее квадратичное отклонение соответственно:

  • M[] = xf(x) dx = xdx/(b a) = (a + b)/2; (4.7)

  • D[] = (x M[])2f(x) dx = (b a)2/12;

  •  = + = (b a)/(2/ ).



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Генерация базовой последовательности

  • При моделировании систем на ЭВМ применяется частный случай равномерного распределения, когда случайные числа находятся на интервале (0, 1), т.е. границы интервала a = 0 и b = 1. Функции плотности и распределения соответственно имеют вид:

  • Такое распределение имеет математическое ожидание M[] = 1/2 и дисперсию D[] = 1/12.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Генерация базовой последовательности

  • Получить такое распределение на цифровой ЭВМ невозможно, так как машина оперирует с n-разрядными числами. Поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала (0, 1) используют дискретную последовательность 2n случайных чисел того же интервала. Закон распределения такой дискретной последовательности называют квазиравномерным распределением.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Генерация базовой последовательности

  • Случайная величина , имеющая квазиравномерное распределение в интервале (0, 1), принимает значения xi = i/(2n – l) с вероятностями рi = 1/2n, i= .

  • Математическое ожидание квазиравномерной случайной величины :



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Генерация базовой последовательности

  • Дисперсия квазиравномерной случайной величины



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Генерация базовой последовательности

  • Таким образом, математическое ожидание квазиравномерной случайной величины совпадает с математическим ожиданием равномерной случайной последовательности интервала (0, 1), дисперсия отличается только множителем (2n + 1)/(2n – 1), который при достаточно больших n близок к единице.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Требования к генератору случайных чисел

  • Полученные с помощью идеального генератора псевдослучайные последовательности чисел должны: - состоять из квазиравномерно распределенных чисел; - содержать статистически независимые числа; - быть воспроизводимыми; - иметь неповторяющиеся числа; - получаться с минимальными затратами машинного времени; - занимать минимальный объем машинной памяти.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Требования к генератору случайных чисел

  • Обычно для генерации последовательностей псевдослучайных чисел при моделировании на ЭВМ применяются алгоритмы вида

  • х i – 1 = Ф(хi), (4.9)

  • представляющие собой рекуррентные соотношения первого порядка, для которых начальное число х0 и постоянные параметры заданы.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Требования к генератору случайных чисел

  • Рассмотрим две процедуры получения последовательностей псевдослучайных квазиравномерно распределенных чисел при статистическом моделировании систем на ЭВМ.

  • Первая процедура получения псевдослучайных чисел процедура – метод серединных квадратов

  • Вторая – конгруэнтная процедура генерации псевдослучайных последовательностей



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Требования к генератору случайных чисел

  • 1. Метод серединных квадратов.

  • Пусть имеется 2n-разрядное число, меньше 1: хi = 0,а1а2…а2n. Возведем его в квадрат: хi0,b1b2…b4n, затем отберем средние 2n разрядов хi+1 = 0,bn+1bn+2…b3n, которые будут являться очередным числом псевдослучайной последовательности.

  • Например, если начальное число х0,2152, то (х0)2 = 0,04631104, т.е. х1 = 0,6311, затем (х1)2 =  0,39828721, т.е. х2 = 0,8287, и т.д.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Требования к генератору случайных чисел

  • 1. Метод серединных квадратов.

  • Недостаток этого метода – наличие корреляции между периодами последовательности, а в ряде случаев случайность вообще может отсутствовать. Например, если х0,4500, то (х0)2 = 0,20250000, х0,2500, (х1)2 = 0,06250000, х2 = 0,2500, (х2)2 = 0,06250000, х3 = 0,2500 и т.д.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Требования к генератору случайных чисел

  • 2. Конгруэнтная процедура

  • Используя арифметические операции, на базе понятия – конгруэнтности процедура заключается в следующем. Два целых числа α и β конгруэнтны (сравнимы) по модулю m, где m – целое число, тогда и только тогда, когда существует такое целое число k, что α – β = km, т.е. если разность α – β делится на m и если числа α и β дают одинаковые остатки от деления на абсолютную величину числа m. Например, 1984 ≡ 4 (mod 10), 5008 ≡ 8 (mod 103) и т.д.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Требования к генератору случайных чисел

  • 2. Конгруэнтная процедура

  • Раскроем рекуррентное соотношение (4.10):

  • Х1 = λХ0 + μ(mod M);

  • Х2 = λХ1 + μ = λ2Х0 + (λ + 1)μ(mod M);

  • Х3 = λХ2 + μ = λ3Х0 + (λ2 + λ + 1)μ = λ3Х0 + (λ3 – 1)μ/(λ – 1)(mod M);

  • …………….

  • Хi = λiХ0 + (λi – 1)μ/(λ – 1)(mod M). (4.11)



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Требования к генератору случайных чисел

  • 2. Конгруэнтная процедура

  • Если заданы начальное значение Х0, множитель λ и аддитивная константа μ, то (4.11) однозначно определяет последовательность целых чисел {Хi}, составленную из остатков от деления на М членов последовательности {λ0 + (λi – 1)/(λ – 1)}. Таким образом, для любого i  1 справедливо неравенство Хi<M. По целым числам последовательности {Хi} можно построить последовательность {xi} = {Хi/M} рациональных чисел из единичного интервала (0, 1).



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации.

  • Требования к генератору случайных чисел

  • 2. Конгруэнтная процедура

  • В настоящее время почти все пакеты прикладных программ универсальных ЭВМ для вычисления последовательностей равномерно распределённых случайных чисел основаны на конгруэнтной процедуре.



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Результаты моделирования системы S, полученные методом статистического моделирования на ЭВМ, существенно зависят от качества используемых псевдослучайных квазиравномерных последовательностей чисел. Поэтому все применяемые генераторы случайных чисел должны пройти предварительное тестирование – комплекс проверок по различным стохастическим критериям, включая в качестве основных проверки (тесты) на равномерность, стохастичность и независимость.



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Проверка равномерности последовательностей псевдослучайных квазиравномерно распределённых чисел {xi} может быть выполнена по гистограмме с присваиванием косвенных признаков. Суть проверки по гистограмме сводится к следующему. Выдвигается гипотеза о равномерности распределения чисел (0, 1). Затем интервал (0, 1) разбивается на m равных частей, тогда при генерации последовательности {xi} каждое из чисел xi c вероятностью pj = 1/m, j = , попадет в один из подынтервалов.



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Всего в каждый j-й подынтервал попадает Ni чисел последовательности {xi}, i = , причём N = . Относительная частота попадания случайных чисел из последовательности {xi} в каждый из подынтервалов будет равна Nj/N. Очевидно, что если числа xi принадлежат псевдослучайной квазиравномерно распределённой последовательности, то при достаточно больших N экспериментальная гистограмма (ломаная линия на рис. 4.10, а) приближается к теоретической прямой 1/m.



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Рис. 4.10. Проверка равномерности последовательности



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Оценка степени приближения, т.е. равномерности последовательности {xi}, может быть проведена с использованием критериев согласия. На практике принимается m = 20 50, N = (102103)m.

  • Суть проверки равномерности по косвенным признакам сводится к следующему. Генерируемая последовательность {xi} разбивается на две последовательности:

  • х1, х3, х5, x2i-1;

  • х2, х4, х6, x2i, i = .



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Геометрически условие (4.12) означает, что точка (x2i-1, x2i), i = , находится внутри круга радиусом r = 1, что иллюстрирует рис. 4.11, б. В общем случае точка (x2i-1, x2i) всегда попадает внутрь квадрата. Тогда теоретическая возможность попадания этой точки в четверть круга:

  • pk = S 1/4круга/Sквадрата = (r2/4)/(11) = /4.

  • Если числа последовательности {xi} равномерны, то в силу закона больших чисел теории вероятностей при больших N относительная частота 2k/N  /4.



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Проверка стохастичности последовательности псевдослучайных чисел {xi} наиболее часто проводится методами комбинаций и серий. Сущность метода сводится к определению закона распределения длин участков между единицами (нулями) или закона распределения (появления) числа единиц (нулей) в n-разрядном двоичном числе Хi.



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Теоретически закон появления j единиц в l разрядах двоичного числа Хi описывается, исходя из независимости отдельных разрядов, биномиальным законом распределения:

  • P(j, l) = Cljpj(1)[1 – p(1)]l-j = Cljpl(1),

  • где P(j, l) – вероятность появления j единиц в l разрядах числа Xi; p(1) = p(0) = 0,5 – вероятность появления единицы и нуля в любом разряде числа Xi; Clj = l! / [j! / (l – j)!].



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Тогда при фиксированной точке выборки N теоретически ожидаемое число появления случайных чисел Xi с j единицами в проверяемых l разрядах будет равно nj = NCljpl(1).

  • После нахождения теоретических и экспериментальных вероятностей P(j, l) или чисел nj при различных значениях ln гипотеза о стохастичности проверяется с использованием критериев согласия.



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • При анализе стохастичности последовательности чисел {xi} методом серий последовательность разбивается на элементы первого и второго рода (a и b), т.е.

  • где 0 < p < 1.



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Серией называется отрезок последовательности {xi}, состоящий из идущих друг за другом элементов одного и того же рода. Причём число элементов в отрезке (a или b) называется длиной серии.

  • После разбиения последовательности {xi} на серии первого и второго рода будем иметь, например, серию вида

  • .....aabbbbaaabbbaabbab.... .



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Так как случайные числа a и b в данной последовательности независимы и принадлежат последовательности {xi}, равномерно распределённой на интервале (0, 1), то теоретическая вероятность появления серии длиной j в N опытах (под опытом здесь понимается генерация числа xi и проверка условия xi < p) определится формулой Бернулли:

  • P(j, l) = Cljp(1 – p)l-j , j = , l = .



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • В случае экспериментальной проверки оцениваются частоты появления серий длиной j. В результате получаются экспериментальная и теоретическая зависимости P(j, l), сходимость которых проверяется по известным критериям, причём проверку целесообразно проводить при разных значениях р, 0 < р < 1 и l.



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Проверка независимости элементов последовательности псевдослучайных квазиравномерно распределённых чисел {xi} производится на основе корреляционного момента.

  • Случайные величины  и  называются независимыми, если закон распределения каждой из них не зависит от того, какое значение приняла другая. Таким образом, независимость элементов последовательности {xi} может быть проверена путём введения в рассмотрение последовательности {yj}={xi+}, где  – величина сдвига последовательностей.



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • В общем случае корреляционный момент дискретных случайных величин  и  с возможными значениями yj и xi определяется по формуле

  • где pij – вероятность того, что (, ) примет значение (xi, yj).



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • Корреляционный момент характеризует рассеивание случайных величин  и  и их зависимость. Если случайные числа независимы, то K = 0. Коэффициент корреляции

  • ,

  • где x и y – среднеквадратические отклонения величин  и .



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • При проведении оценок коэффициента корреляции на ЭВМ удобно для вычисления использовать следующее выражение:



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • где

  • При вычислениях сначала рационально определить суммы:



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Проверка качества последовательностей

  • При любом   0 для достаточно больших N с доверительной вероятностью  справедливо соотношение

  • .

  • Если найденное эмпирическое значение () находится в указанных пределах, то с вероятностью  можно утверждать, что полученная последовательность чисел {хi} удовлетворяет гипотезе корреляционной независимости



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Характеристики качества генераторов

  • При статистическом моделировании системы S с использованием программных генераторов псевдослучайных квазиравномерных последовательностей важными характеристиками качества генератора является - длина периода Р, - длина отрезка апериодичности L.



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Характеристики качества генераторов

  • Длина отрезка апериодичности L псевдослучайной последовательности {xi}, заданной уравнением

  • Xi+1 = λХi + μ(mod M), xi = Xi/M,

  • есть наибольшее целое число, такое, что при 0<j<i<L событие Р{xi=xj} не имеет места, т.е. все числа х в пределах отрезка апериодичности не повторяются.



Раздел 4. Статистическое моделирование систем на ЭВМ. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Характеристики качества генераторов

  • Если длина последовательности чисел {xi} больше отрезка апериодичности L, то повторение испытаний происходит в тех же условиях, что и раньше, т.е. увеличение числа реализации не дает новых статистических результатов.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Выводы и заключение по лекции:

  • изучили методы генерации базовой последовательности случайных чисел,

  • изучили требования к генератору случайных чисел,

  • научились проверять качество последовательностей псевдослучайных чисел,

  • изучили характеристики качества генераторов.



Раздел 4. Статистическое моделирование систем на ЭВМ. Псевдослучайные последовательности и процедуры их машинной генерации. Проверка и улучшение качества последовательностей псевдослучайных чисел

  • Перечень источников:

  • 1. Советов Б.Я., Яковлев С.А. Моделирование систем: Учеб. для вузов. 3-е изд., перераб. и доп. М.: Высш. шк., 2001. 343 с.: ил.

  • 2. Тарасик В.П. Математическое моделирование технических систем: Учебник для вузов. М.: Наука, 1997. 600 с.

  • Список дополнительной литературы по теме:

  • 3. Ивченко Г.И., Медведев Ю.И. Математическая статистика: Учебное пособие для втузов. М.: Высш. шк., 1984. 248 с.: ил.

  • 4. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. М.: Наука. 1988. 480 с.

  • 5. Ликеш И., Ляга Й. Основные таблицы математической статистики/ Пер. с чешск., Предисл. Ю.Н. Тюрина, Д.С Шмерлинга. М.: Финансы и статистика, 1985. 356 с.: ил.



Похожие:

Моделирование систем iconМоделирование технических систем. Системы массового обслуживания Моделирование технических систем

Моделирование систем iconМоделирование динамики твердых тел и систем связанных тел с механическими соударениями

Моделирование систем iconМоделирование систем
Кафедра «Автоматика и управление в технических системах» направление 220200 Автоматизация и управление
Моделирование систем iconМоделирование систем
Кафедра «Автоматика и управление в технических системах» направление 220200 Автоматизация и управление
Моделирование систем iconМатематическое моделирование информационных процессов Содержание: Информационные технологии и моделирование

Моделирование систем iconМоделирование в среде графического редактора Моделирование геометрических фигур
Цели моделирования нарисовать стандартную фигуру (квадрат), собрать рисунок из данных деталей
Моделирование систем iconМоделирование систем
Кафедра «Автоматика и управление в технических системах» направление 220200 Автоматизация и управление специальность 220201 Управление...
Моделирование систем iconМоделирование процессов потребления. Моделирование процессов потребления
Повседневная жизнь человека связана с решением целого ряда задач, в которых необходимо принимать решения о выборе поведения
Моделирование систем iconМоделирование как метод познания Моделирование – это метод познания, состоящий в создании и исследовании моделей
Свойства объекта, которые должна отражать модель, определяются поставленной целью его изучения
Моделирование систем icon1 Цель. 1 Цель. Моделирование как метод познания
Моделирование это метод познания, состоящий в создании и исследовании моделей
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница