Лекции по автоматизации и управлению

Вопрос № 16 .

Понятие модели. Параметры математических моделей

Модель - это материальный или мысленно представляемый объект или процесс,

который в процессе извлечения информации замещает оригинал сохраняя его

основные свойства.

Типы моделей:

 физические

 математические

 имитационные

Физические модели - это материальные объекты, представляющие копию

изучаемого объекта или явления.

Математическая модель - это формализованная схема описания явления,

объекта или процесса, выраженного на математическом языке и отражающая

его основные свойства.

Создание Мат. модели делится на три этапа:

1. Выбор параметров задачи (переменные, неизвестные), выбор которых

однозначно определяет моделируемую задачу.

2. Запись математической модели, т.е. запись условий задачи в виде матем.

Соотношений.

3. Постановка цели на сформулированные модели.

Вопрос №18. Генераторы стандартных псевдослучайных

чисел.

1.1. Датчики БСВ

Б а з о в о й случайной величиной (БСВ) в статистическом

моделировании называют непрерывную случайную величину z,

равномерно распределенную на интервале (0,1). Ее плотность

распределения вероятностей (п.р.в.) имеет вид:

f(t) = 1, 0 < t < 1. (1.1)

Математическое ожидание (м.о.) и дисперсия БСВ составляют

M(z) = 1/2 (1.2)

D(z) = 1/12 (1.3)

соответственно.

П р о г р а м м н ы й датчик БСВ обычно вычисляет значения

z ,z , ... по какой-либо рекуррентной формуле типа

z = f(z ) (1.4)

при заданном стартовом значении z .

Заданное значение z полностью определяет всю последователь-

ность реализаций z ,z , ... , поэтому z часто называют п с е в -

д о с л у ч а й н о й величиной. Но ее статистические свойства

идентичны свойствам "чисто случайной" последовательности, что и

обеспечивает успех статистического моделирования.

Программный датчик БСВ имеет следующие преимущества:

- простота создания датчика,

- простота применения,

- простота тиражирования,

- надежность,

- быстродействие,

- высокая точность достижения необходимых статистических

свойств, сравнимая с точностью представления вещественных чисел,

- компактность,

- повторяемость, когда это нужно, любых последовательностей

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

В дальнейшем мы будем рассматривать только программные датчики

БСВ.

Имея датчик БСВ z, можно промоделировать любые случайные

факторы: непрерывные или дискретные случайные величины (как

простые, так и многомерные), случайные события, случайные процессы

и поля и т.д. Для этого достаточно соответствующим образом

преобразовать последовательность z ,z , ... . Поэтому БСВ z и

называют базовой.

Теоретически в качестве базовой можно было бы взять почти

любую случайную величину (с.в.). Использование с.в. z с

распределением (1.1) обусловлено технологическими соображениями:

простотой и экономичностью датчика, простотой преобразования z в

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

датчика.

1.2. Метод середины квадрата

Метод середины квадрата предложен для получения

псевдослучайных чисел Д. фон Нейманом в 1946 г. Вот один из

вариантов этого метода.

(1) Возьмем произвольное четырехзначное число.

(2) Возведем полученное четырехзначное число в квадрат и, если

необходимо, добавим к результату слева нули до

8-мизначного числа.

(3) Возьмем четыре цифры из середины 8-мизначного в

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

(4) Если нужны еще случайные числа, то перейдем к (2).

Например, если взять в качестве начального числа 1994, то из

него получается следующая последовательность псевдослучайных чисел:

9760 2576 6357 4114 9249 5440 5936 2360

5696 4444 7491 1150 3225 4006 0480 2304

3084 5110 1121 2566 ...

Сам по себе метод середины квадрата не получил широкого

распространения, так как выдает "больше чем нужно малых значений"

[26]. Но открытый в нем принцип используется во многих, если не во

всех, более поздних датчиках БСВ. Этот принцип состоит в вырезании

нескольких цифр из результата какой-либо операции над числами.

1.4. Тестирование равномерности

Обозначим равномерное распределение вероятностей на интервале

(0,1) через R[0,1]. Тогда утверждение, что БСВ z имеет

распределение R[0,1] можно кратко записать в виде z ~ R[0,1].

С помощью статистических тестов проверяют два свойства

датчика, делающих его точной моделью идеальной БСВ - это

р а в н о м е р н о с т ь распределения чисел z , выдаваемых

датчиком на интервале (0,1), и их статистическую н е з а в и с и -

м о с т ь. При этом числа z рассматривают как реализации

некоторой с.в., то есть как статистическую выборку.

Достаточно простым методом проверки равномерности

распределения является частотный тест. Он основан на законе больших

чисел и выполняется по следующему алгоритму.

(1) Разобьем интервал (0,1) на K равных отрезков

(например, K = 10).

(2) Сгенерируем n чисел z , ... ,z с помощью

тестируемого датчика БСВ (например, n = 100).

(3) Подсчитаем, сколько чисел попало в каждый из K

отрезков, т.е. найдем числа попаданий n , ... ,n .

(4) Рассчитаем относительные частоты попаданий в отрезки:

p' = n /n, ... , p' = n /n.

(5) Построим гистограмму частот p' , ... ,p' на K

отрезках интервала (0,1).

(6) Повторим действия (2) - (5) для большего значения n

(напрмер, для n = 10 000).

(7) Оценим по полученным гистограммам сходимость каждой

частоты p' к вероятности p = 1/K того, что БСВ

попадет в i-ый отрезок. Согласно закону больших чисел

должно быть

p' -> 1/K, n -> . (1.6)

Это значит, что высоты столбиков во второй гистограмме

должны в целом быть ближе к уровню 1/K, чем в первой.

Тестирование датчика на равномерность можно совместить с

оцениванием м.о. и дисперсии с.в. Оценки M' и D' для м.о. и

дисперсии рассчитываются соответственно по формулам:

(1.7)

(1.8)

С ростом n оценки M' и D' должны сходиться по вероятности к

точным значениям M(z) = 1/2, D(z) = 1/12 = 0.08333... .

В табл. 1.2 приводится пример тестирования одного из

распространенных датчиков БСВ. На рис. 1.1 и 1.2 показаны

соответствующие гистограммы. Судя по этим результатам,

протестированный здесь датчик отвечает требованию равномерности.

Пример испытания датчика Табл. 1.2

----------------------------------------------------------

Рассчитываемые оценки | Длина выборки n

|-------------------------------

| n = 1000 | n = 100 000

--------------------------|------------------|------------

Оценки для м.о. | M' | 0.4928 | 0.4992

| | |

и дисперсии | D' | 0.0841 | 0.0832

--------------------|-----|------------------|------------

| | |

| p' | 0.114 | 0.10136

| | |

| p' | 0.097 | 0.09974

| | |

| p' | 0.100 | 0.09868

| | |

| p' | 0.108 | 0.10130

| | |

Частоты | p' | 0.094 | 0.10155

| | |

| p' | 0.096 | 0.09896

| | |

| p' | 0.096 | 0.09928

| | |

| p' | 0.102 | 0.10015

| | |

| p' | 0.104 | 0.10085

| | |

| p' | 0.089 | 0.09813

--------------------------|------------------|------------

Сумма частот | 1.000 | 1.000

----------------------------------------------------------

1.5. Тестирование независисмости

Простейшую проверку статистической независимости реализаций

z ,z , ... можно осуществить, оценивая корреляцию между числами

z и z , отстоящими друг от друга на шаг s > 1.

Для вывода формулы, по которой можно рассчитать коэффициент

корреляции чисел z и z, расссмотрим две произвольные с.в.

x, y. Коэффициент корреляции определяется для них формулой:

M(xy) - M(x)M(y)

R(x,y) = ---------------- . (1.9)

D(x)D(y)

Если известно, что x,y ~ R[0,1], то M(x) = M(y) = 1/2

и D(x) = D(y) = 1/12, то есть формула (1.9) принимает вид:

R(x,y) = 12 M(xy) - 3. (1.10)

Условимся рассматривать пару чисел (z ,z ) как

реализацию пары с.в. (x,y). Тогда в выборке z , ... ,z имеем

всего n-s реализаций этой пары:

(z ,z ), (z ,z ), ... ,(z ,z ).

По ним можно рассчитать оценку R' коэффициента корреляции R(x,y),

заменяя в (1.10) м.о. M(xy) соответствующим средним

арифметическим:

1

R' = 12 ----- ( z z ) - 3 . (1.11)

n-s

С ростом n оценка R' должна приближаться к нулю, в противном

случае датчик БСВ не отвечает требованию независисмости.

Конечно, если R' сходятся к нулю, то это еще не гарантирует

наличие независимости, но все же один из тестов оказывается успешно

выдержанным. При желании всегда можно продолжить испытания датчика

другими методами.

В табл. 1.3 показан пример тестирования датчика БСВ. Как видно

из таблицы, оценки коэффициентов корреляции для s = 1,2,3

постепенно сходятся к нулю. На рис. 1.3 изображены соответствующие

графики.

Табл. 1.3

-------------------------------------

| | Оценка R'для s = 1,2,3 |

| n |------------------------|

| | s = 1 s = 2 s = 3 |

|----------|------------------------|

| | |

| 1000 | 0.175 0.142 0.232 |

| 2000 | 0.071 0.059 0.111 |

| 3000 | 0.007 0.021 0.043 |

| 4000 | 0.017 0.040 0.043 |

| 5000 | 0.019 0.045 0.042 |

| 6000 | 0.009 0.031 0.039 |

| 7000 | -0.003 0.019 0.027 |

| 8000 | -0.003 0.021 0.028 |

| | |

-------------------------------------

1.6. Другие методы тестирования

1.6.3. Специальные тесты

Еще более сильные тесты разработаны специально для проверки

равномерного распределения. К их числу относятся:

- тест "гиперкубов" на равномерное заполнение N-мерных кубов

точками с координатами (z , ... ,z ), (z , ... ,z ), ... ,

описанный в [5,30];

- тест "серий" на длину подпоследовательностей (например, на

длину серий чисел z , которые начинаются одной и той же цифрой)

[5,15];

- тест "максимумов и минимумов" [15].

1.6.4. Проверка практикой

Любое тестирование датчиков БСВ все-же остается частичным.

Поэтому Ермаков и Михайлов в [5] отмечают, что кроме специального

статистического тестирования "... чрезвычайно важна проверка с

помощью решения типовых задач, допускающих независимую оценку

результатов аналитическими или численными методами. Можно сказать,

что представление о надежности псевдослучайных чисел создается в

процессе их использования с тщательной проверкой результатов

всегда, когда это возможно".

1.6.5. Точные методы

Точные методы применяются наряду со статистическими для

д о к а з а т е л ь с т в а тех или иных частных свойств датчиков

БСВ.

В ряде точных исследований вероятностные характеристики

датчиков рассчитывают п о в с е м у периоду z , ... ,z ,

что, очевидно, равносильно статистическому тестированию датчика по

выборке бесконечного объема: z , ... ,z . Этот подход используется

у Кнута [15], а также у Кавью и Макферсона [31].

1.6.6. Тестирование апериодичности

К точным методам следует отнести также методы тестирования

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

z ,z , ... требуется, вообще говоря, сравнивать каждое новое

число z со всеми предыдущими. Однако непосредственное сравнение

z с каждым из чисел z , ... ,z привело бы к чересчур

большим затратам машинного времени, возрастающим на каждом шаге i.

Более эффективный алгоритм тестирования апериодичности опубликован

Ю.Г.Полляком в [21].

1.6.7. Методы теории чисел

Длину периода и некоторые другие важные характеристики

датчиков можно определять также точными методами теории чисел [2].

Результаты подобных алгебраических исследований можно найти в [30].

Для примера приведем следующую интересную теорему.

Т е о р е м а . Пусть в (1.5) m - простое число. Максимально

возможное значение периода T = m-1 достигается, если k не кратно

m и величины

также не кратны m,

где p , ... ,p - простые числа, входящие в каноническое

разложение числа m-1 на сомножители: m-1 =

1.7. Другие алгоритмы генерации БСВ

1.7.1. Не все то золото, что блестит

Прежде, чем дать информацию о некоторых других методах

построения БСВ, сделаем одно важное замечание.

Уже более двадцати лет назад была опубликована библиография

[35], которая содержит 491 ссылку на литературу по датчикам

случайных чисел. Двумя годами позднее Дж. Клейнен в [12] приходит,

однако, к выводу, что "все еще нет высококачественного генератора

псевдослучайных чисел". Одновременно с ним Льюис [33] и Марсалья

[34] указывают: "Многие широко распространенные генераторы

фактически непригодны". Предостережение о распространенности плохих

генераторов делает также И.М.Соболь в [26].

Дж. Клейнен в [12] отмечает, что "Наилучший в настоящее время,

по-видимому, мультипликативный генератор, однако он требует

тщательного выбора сомножителя".

1.7.2. Датчики с большой длиной периода

В [32] рекомендуются следующие шесть вариантов множителя k

для датчика (1.5) с m = 2 -1 :

1078318381, 1203248318, 397204094,2027812808, 1323257245, 764261123.

Во всех этих случаях длина периода T = m-1. Поэтому в качестве

стартового значения можно брать любое целое число от 1 до m-1.

1.7.3. Линейная смешанная формула

Эта формула является обобщением (1.5):

A = (k A + ... + k A + C) mod m, (1.12)

z = a /m, i = 1,2, ... ,

где - порядок,

A , A , ... , A - стартовые значения,

k , ... , k - множители.

Здесь длина периода T < m .

1.7.4. Квадратичный конгруэнтный метод

Это еще один вариант обобщения (1.5). В нем используется

формула:

A = (k A + k A + C) mod m, (1.13)

z = a /m, i = 1,2, ... .

1.7.5. Метод Макларена - Марсальи

Для повышения точности моделирования БСВ Макларен и Марсалья

предложили комбинировать два простейших датчика БСВ, если их

точность моделирования недостаточно высока.

Пусть x ,y , i = 0,1,2, ... - две псевдослучайные

последовательности, порождаемые независимыми датчиками Д1 и Д2

сответственно; V = { V(0), ... , V(K-1) } - вспомогательная таблица

целых чисел. Вначале таблица V заполняется первыми K членами

последовательности x :

V(j) = x , j = 0,1, ... , K-1.

Через z будем обозначать псевдослучайную последовательность

метода Макларена-Марсальи. Число z определяется путем выполнения

следующей последовательности операций:

j = | y K |,

z = V(j),

V(j) = x , i = 0,1,2, ... ,

где операция | y K | означает целую часть y K.

Мы видим, что Д2 используется здесь для случайного выбора

элемента из таблицы V, а Д1 заменяет этот элемент новым случайным

значением.

Этот метод позволяет ослабить зависимость между числами z и

получать длину периода до T T , где T ,T - периоды

датчиков Д1 и Д2 соответственно. Например, при T = T = 2 - 2

(см. п. 1.7.2) и K = 9 мы можем получить T 2,2 10 , то есть

больше гугола (больше 10 ). Это, очевидно, перекрывает любые

практические потребности и даже возможности исчерпания периода.

Обратим внимание также на то, что быстродействие метода - то

есть количество операций, выполняемых на каждом шаге - практически

не зависист от размера K вспомогательной таблицы.

1.7.6. О датчике системы GPSS

Т.Дж. Шрайбер в [29] описал датчик БСВ, встроенный в язык GPSS

(в версииях для IBM 360/370). В этом датчике комбинируются

следующие идеи, отличающие его от датчика (1.5).

Произведение двух больших чисел представляется в д е с я -

т и ч н о й форме. Получается 20 - разрядное число, из которого 6

средних цифр берутся в качестве очередного целого псевдослучайного

числа A .

Из произведения выбирается еще одно псевдослучайное число -

правая половина 60 - разрядного д в о и ч н о г о представления

произведения. Она используется на следующем шаге i+1 вместо A

для формирования нового десятичного произведения с k.

В качестве множителя k на каждом таком шаге используется один

из восьми коэффициентов, выбираемый случайно с помощью третьего

псевдослучайного числа, составляемого из цифр "другой средней части

произведения".

Точное описание алгоритма и данные тестирования этого датчика

в [29] не приводятся, как и в фирменной документации [6,24]. Наше

доверие к датчику может питаться авторитетом фирмы IBM и, в

особенности, широким апробированием языка GPSS в прикладных

исследованиях и в учебных курсах моделирования.

Хорошим подтверждением высокого качества датчика можно считать

также работу [4], где на GPSS моделируются системы массового

обслуживания и результаты сравниваются с точными аналитическими

решениями. По этому поводу см. п.1.6.4.

1.7.7. О проблемах программирования

В известной нам литературе параметры датчиков сильно зависят

от длины машинного слова. Дело в том, что в алгоритмах вычисления

БСВ используются большие целые числа. А так как непосредственное

программирование операций над ними может привести к переполнению

разрядной сетки ЭВМ, то ряд операций приходится разбивать на

промежуточные шаги, в которых учитываются тонкости машинной

арифметики. В результате текст программы оказывается существенно

зависимым от модели ЭВМ и от используемого языка программирования.

Или же он содержит операции настройки на длину слова и на

особенности обработки переполнений в ЭВМ, как, например, в прил.1 в

[30].

Работа на границе диапазона представимых целых чисел - это

специфическая трудность при программировании датчиков БСВ._

Лекции по автоматизации и управлению

Подождите немного. Документ загружается.