Імітаційне моделювання
Машинна імітація випадкових параметрів
Методичні вказівки
щодо виконання лабораторної роботи
Зміст роботи
Методи генерування послідовності рівномірно розподілених випадкових чисел
Завдання
Перевірка якості псевдовипадкових чисел
Завдання
Приклади використання методу Монте Карло в імітаційному моделюванні
Обчислення числа
Обчислення визначеного інтегралу методом Монте-Карло
Для построения последовательности равномерно распределенных случайных чисел используются следующие методы.
Мультипликативно-конгруэнтный метод, или метод степенных вычетов:
xi=axi-1 (mod m), i=l,2,...
x0=b.(1)
где a, m - неотрицательные целые числа.
Согласно (1) необходимо взять последнее случайное число, умножить его на a и взять модуль полученного числа по т (т.е. разделить на т и взять остаток в качестве следующего xi). Последовательность равномерно распределенных на отрезке [О, 1] псевдослучайных чисел получается при делении остатка на т.
В качестве модуля обычно выбирают 2Ь или 10d.
На основе конгруэнтной формулы было создано множество генераторов.
Смешанные генераторы Томпсона основываются на следующей формуле
xi+1=axi + C (mod m)
Аддитивный конгруэнтный метод (Грин, Смит, Клем) использует рекуррентную формулу
xi+1=(xi + xi-1)C (mod m)
Примеры построения последовательности псевдослучайных равномерно распределенных на отрезке [0; 1] чисел с помощью приведенных алгоритмов.
Пусть а=111, т=256, b=10.
Тогда с помощью мультипликативно-конгруэнтного метода получается
x0=b = 10, r0= = x0/m = 10/256=0,039.
Далее получается
x1=ax0(mod m) = 111*10 (mod 256) = 1110 mod 256 = 86,
r1=x1/m=86/256=0,336
При тех же параметрах а, m и параметре С=347 с помощью смешанного генератора Томпсона получаем:
x1=ax0+C(mod m) = 111*10 +347 (mod 256) = 1457 mod 256 = 177,
r1=x1/m=177/256=0,691.
Наконец, аддитивно-когруэнтным методом при х0=100, x1=183 получаем
х2 =x0+xl(modm) = (100 + 183) (mod 256) = 283 mod 256 = 27,
r2=x2/m=27/256= 0,105.
В табл. 1 приведены результаты расчетов для первых 10 псевдослучайных чисел, полученных всеми перечисленными способами.
Переваги програмного методу:
- займає мало місця в оперативній пам"яті (близько десяти команд);
- можна поворити спроби;
- забезпечується одноразова первірка якості випадкових чисел;
- не потрібні зовнішні пристрої.
Недоліки програмного методу:
- швідкість утворення випадкових чисел відносно невелика;
- обмежений запас чисел.
Таблица 1
Последовательности псевдослучайных чисел
| i | Мультипликативно-конгруэнтный метод | Смешанный генератор Томпсона | Аддитивно - конгруэнтный метод | |||
| xi | ri | xi | ri | xi | ri | |
| 0 | 10 | 0,039 | 10 | 0,039 | 100 | 0,391 |
| 1 | 86 | 0,336 | 177 | 0,691 | 183 | 0,715 |
| 2 | 74 | 0,289 | 26 | 0,102 | 27 | 0,105 |
| 3 | 22 | 0,086 | 161 | 0,629 | 16 | 0,063 |
| 4 | 138 | 0,539 | 42 | 0,164 | 75 | 0,293 |
| 5 | 214 | 0,836 | 145 | 0,566 | 224 | 0,875 |
| 6 | 202 | 0,789 | 58 | 0,227 | 123 | 0,480 |
| 7 | 150 | 0,586 | 129 | 0,504 | 176 | 0,688 |
| 8 | 10 | 0,039 | 74 | 0,289 | 171 | 0,668 |
| 9 | 86 | 0,336 | 113 | 0,441 | 128 | 0,500 |
| 10 | 74 | 0,289 | 90 | 0,352 | 219 | 0,855 |
Построить последовательности псевдослучайных чисел, используя табличный процессор MS Excel. Получить таблицу, аналогичную таблице 1.
Для вычисления остатка от деления рекомендуется использовать функцию ОСТАТ.
Выполнить форматирование.
Описание функции ОСТАТ
Назначение: Возвращает остаток от деления аргумента число на делитель. Результат имеет такой же знак, как и делитель.
Синтаксис
ОСТАТ(число;делитель)
Число - это число, остаток от деления которого определяется.
Делитель - это число, на которое нужно разделить (делитель). Если делитель равен 0, то функция ОСТАТ возвращает значение ошибки #ДЕЛ/0!
Замечания
Функция ОСТАТ может быть выражена через функцию ЦЕЛОЕ:
ОСТАТ(n; d) = n - d*ЦЕЛОЕ(n/d)
Застосовувати псевдовипадкові числа, утворювані з допомогою програмних генераторів РВП [0, 1], правомірно в тому разі, коли статистичні характеристики їх збігаються з властивостями чисел, породжених деяким ідеальним генератором, що вибирає значення на відрізку [0, 1] рівноймовірно і незалежно одне від одного згідно із законом
| 0 | при x<0 | |
| f(x)= | 1 | при 0 <= x<= 1 |
| 0 | при x>1 |
Тому успішне застосування методу Монте-Карло можливе лише тоді, коли створювані генератором числа будуть випадковими, рівномірно розподіленими на відрізку [0, 1] і незалежними. Зрозуміло, що за своїми конструктивними особливостями програмні датчики не можуть відтворювати випадкові числа, які повністю задовольняють перелічені вимоги. Проте для практичних цілей буває достатньо, щоб послідовність РВП [0, 1] приблизно відповідала вимогам ідеального генератора. Таке припущення перевіряється з допомогою спеціальних статистичних тестів. При цьому виконуються дві передумови.
1.Генератор псевдовипадкових чисел вважається придатним для використання, якщо він витримує набір наперед установлених тестів.
2.Якість випадкових чисел перевіряється лише один раз на попередньому етапі побудови імітаційної моделі.
Розроблено чимало тестів, котрі дають змогу оцінювати якість випадкових чисел. Серед них є загальновідомі статистичні методи перевірки гіпотез (перевірка відповідності розподілів за критеріями Пірсона або Колмогорова, виявлення кореляційної залежності між серіями випадкових чисел — автокореляції ), а також і спеціально розроблені для методу Монте-Карло критерії.
Розглянемо кілька спеціальних тестів перевірки якості випадкових чисел. Особливість їх застосування полягає в тому, що генератор РВП [0,1] вважають за можливе використовувати лише в тому разі, коли він одночасно відповідає всім вибраним тестам (перевірка датчика припиняється, тільки-но він не відповідає черговому тесту). При цьому багато рішень щодо відповідності датчика тому чи іншому тесту експериментатор приймає на інтуїтивному рівні, спираючись на власний досвід таких досліджень.
Перевірка за моментами розподілу
Для ідеального генератора рівномерно розподілених випадкових чисел математичне сподівання їх дорівнює Ѕ, а дисперсія дорівнює 1/12.
Перевірка на рівномірність за гистограмою
Розіб"ємо відрізок [0,1] на n рівних частин. Кожне з чисел xi потрапить на один з таких відрізків. Нехай m1 – кількість випадкових чисел, що потрапили на перший відрізок, m1 – на другий і т.д. При цьому
m1 +m2 +... +mn = N/
Обчислимо відносні частоти потрапляння випадкових чисел на кожний із відрізків
p1=m1/N; p2=m2/N; … pn=mn/N,
а далі для перевірки рівномірності псевдовппадкових чисел будується гістограма.
Якщо випадкові числа рівномірні, то для достатньо великих N гістограма (ламана лінія) має наближатися до теоретичної прямої у = 1/n.
Число розбиттів n має бути не дуже малим, щоб можна було перевірити локальну рівномірність. Водночас і дуже велике n нас не задовольняє, оскільки потрібно буде багато випадкових чисел (N на два — три порядки більше за n). На практиці n беруть таким, що задовольняє нерівність 20 <= n <= 50.
Перевірка зa посередніми ознаками
Дивись [1, с. 55].
Перевірка на періодичність
Якщо серед множини програмне утворюваних випадкових чисел x0,x1,x2, ....xl-1 немає однакових, а xl збігається з одним зі створених раніше чисел, то L називається відрізкомаперіодичності. Очевидно, що L<=2k. При дослідженні генератора випадкових чисел необхідно установити довжину відрізка аперіодичності. Якщо число необхідних для експериментів випадкових чисел менше за довжину відрізка аперіодичності L, то датчик можна використовувати. У противному разі довжину відрізка аперіодичності слід збільшити, застосувавши різні штучні прийоми, зокрема змінивши початкове число x0 або використавши інший генератор.
Перевірка на випадковість
Дивись [1, с. 57].
Перевірка генератора в "роботі"
Досить надійним методом установлення якості випадкових чисел е перевірка генератора РВП [0,1] в «роботі». Згідно з цим методом складають імітаційну модель, результат роботи якої може бути передбачений теоретично. Порівнюючи експеріментальний, здобутий за допомогою ЕОМ, і теоретичний результати, можна зробити висновки щодо придатності генератора випадкових чисел.
Для ілюстрації такого підходу перевірки якості випадкових чисел розглянемо описану далі гру. Стрілець стріляє по мішені. Якшо він у неї влучить, то отримає виграш 9 грн., а якщо промахнеться — заплатить штраф у розмірі 1 грн. Імовірність влучити в мішень становить 0,05.
Величина виграшу с випадковою величиною з таким розподілом:
| Виграш | 9 | - 1 |
| Імовірність | 0,05 | 0,95 |
Математичне сподівання виграшу за один постріл подається у вигляді