Мультиплікативний конгруентний метод(метод лишків)

Випадкове число РВП [0, 1] дістаємо перетворенням цілих чисел , що визначаються з допомогою рекурентного виразу

(2)

де a і m -- невід'ємні цілі числа.

Згідно з (2) для знаходження наступного випадкового числа достатньо виконати такі дії:

1) взяти останнє випадкове число ;

2) помножити його на коефіцієнт a ;

3) добуток поділити на модуль m;

4) остачу від ділення вважати шуканим випадковим числом ; це буде одне з цілих чисел 0, 1, 2, 3, . . . , m - 1.

Для генерування послідовності випадкових чисел потрібно мати початкове число, множник a і модуль m. При виборі a і m потрібно виявити певну обережність. Коли a = 1, то = при будь-якому і . Коли = 0, то = 0 при довільному і . Очевидно, що будь-який генератор псевдовипадкових чисел може дати лише скінченну множину цілих випадкових чисел; після чого послідовність повторюватиметься.

Період (довжина) послідовності залежить від розрядності ЕОМ та вибраного модуля, а статистичні властивості -- від вибору початкового числа та множника. Отже, вибирати потрібно так, щоб забезпечити максимальний період і мінімальну кореляцію (автокореляцію).

Мультиплікативний конгруентний метод пояснимо, розглянувши процес генерування десяткових дробів з десятьма знаками після коми. Перепишемо формулу (2), узявши -- довільне непарне число, що не ділиться на 5:

Нехай x0 = 123456789, тоді

і т.д.

У системах ЕОМ типу IBM широко застосовується метод Хатчинсона. Двійкові числа в цих машинах подаються 32 розрядами: 31 розряд містить значущі цифри, крайній зліва розряд показує знак числа. За модуль беруть множник Максимальна довжина послідовності випадкових чисел дорівнює m - 1; 0,46566113. Запишемо програму цього датчика випадкових чисел мовою фортран.

SUBROUTINE RAND (N1, N, R)

1. N = 1220703125 N1

2. IF (N)3,4,4

3. N = N + 2147483647 + 1

4. NI = N

5. R = N

6. R = R 0.4656613E - 9

7. RETURN

8. END

У програмі -- ціле число між 1 і -- випадкове число з плаваючою крапкою (оператори 5 і 6 дають результати з плаваючою крапкою). Від'ємне число N може виникнути після команди 1 у результаті відкидання старших розрядів, тому оператор 3 змінює його значення.

Щоб дістати кілька послідовностей випадкових чисел РВП [0, 1], необхідно ввести різні значення початкових чисел: , а щоб повторити початковий відрізок будь-якої послідовності, достатньо всередині основної програми присвоїти відповідній змінній N1 її початкове значення і повторити весь цикл звертань до генератора.

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

Мішані конгруентні методи

Побудова мішаних когруентних методів грунтується на залежності

xi+1 (axi + c) (mod m),

де с -- деяка константа.

Адитивний конгруентний метод

В основу цього методу покладено рекурентне співвідношення

Існують і складніші адитивні методи.

Переваги програмного методу:

1) місця в оперативній пам'яті займає мало (близько десяти машинних команд);

2) можна повторити спроби;

3) забезпечується одноразова перевірка якості випадкових чисел;

4) не потрібні зовнішні пристрої.

Недоліки програмного методу:

1) відносно невелика швидкість утворення випадкових чисел;

2) запас чисел обмежений.

Порівнюючи переваги та недоліки трьох методів генерування РВП [0, 1], доходимо висновку, що програмний спосіб породження псевдовипадкових чисел найприйнятніший для застосування в імітаційному моделюванні.

2. Моделювання випадкових величин

Алгоритмічне (імітаційне) моделювання -- це числовий метод дослідження систем і процесів за допомогою моделюючого алгоритму.

Кожного разу, коли на хід модельованого процесу впливає випадковий чинник, його вплив імітується за допомогою спеціально організованого розіграшу (жеребкування). Таким способом будується випадкова реалізація модельованого явища, яка є одним із результатів дослідження. За результатами окремого досліду, звичайно, не можна робити висновок щодо закономірностей досліджуваного процесу. Але за великої кількості реалізацій середні характеристики (математичне сподівання, мода, медіана), що їх виробляє (генерує) модель, набувають стійких властивостей, котрі посилюються зі зростанням кількості реалізацій (прогонів). Звісно, залишається певний ризик, який характеризується тим, що модель є гомогенною, існує неповнота даних тощо.

Кидання жеребка можна здійснити вручну (вибором із таблиці випадкових чисел), але зручніше це робити за допомогою спеціальних програм, що входять до складу програмного забезпечення комп'ютера. Такі програми називають датчиками чи генераторами випадкових чисел.

У складі трансляторів майже всіх алгоритмічних мов є стандартні процедури (чи функції), котрі генерують випадкові (точніше, псевдовипадкові) числа, що є реалізаціями послідовності випадкових чисел із рівномірним законом розподілу.

Наприклад, у складі транслятора мови Visual Basic -- стандартна функція RND, що видає випадкові дійсні числа одинарної точності в інтервалі (0; 1). Звернення до цієї функції може мати вигляд x = RND, де x -- можливе значення (реалізація) випадкової величини, яка рівномірно розподілена на інтервалі (0; 1).

Моделювання випадкових подій:

1. Моделювання простої події

Нехай має місце подія А, імовірність настання котрої дорівнює Р(А). Потрібно обрати правило, у багаторазовому використанні якого частота появи події прямувала б до її ймовірності. Оберемо за допомогою датчика випадкових чисел, що мають рівномірний закон розподілу на інтервалі (0;1), деяке число x і визначимо ймовірність того, що x < Р(А). Для випадкового числа x, котре є реалізацією випадкової величини з рівномірним законом розподілу на інтервалі (0; 1), справедливою буде така залежність:

Отже, імовірність потрапляння випадкової величини в інтервал (0; Р(А)) дорівнює величині Р(А). Тому, якщо під час розіграшу число потрапило в цей інтервал, то слід вважати, що відбулася подія А. Протилежна подія () відбудеться з імовірністю (1 - Р(А)) у тому разі, коли x ? Р(А).

Процедура моделювання простої події в імітаційній моделі описується алгоритмом, схема якого подана на рис. 2.1 (ДВЧ(x) -- датчик випадкових чисел x, що відповідають рівномірному закону розподілу на інтервалі (0; 1).)

Рис. 2.1.. Моделювання простої події

Оператор 1 звертається до датчика випадкових чисел, який генерує випадкове число x.

Оператор 2 здійснює перевірку умови x < Р(А). Якщо вона виконується, вважається, що відбулася подія А. У протилежному випадку вважається, що відбулася протилежна подія (А).

2. Моделювання повної групи несумісних подій

Нехай наявна повна група випадкових несумісних подій (ПГНП) А1, А2, …, Аk з імовірностями p1, p2, …, pk. При цьому виконується умова:

Поділимо інтервал (0; 1) на k відрізків, довжини яких відповідно дорівнюють p1, p2, …, pk.

Рис. 2.2.. Моделювання повної групи несумісних подій

Якщо випадкова величина x, яка генерується датчиком випадкових чисел, що відповідають рівномірному закону розподілу на інтервалі (0; 1), припадає, наприклад, на відрізок pk-1, то це повинно означати, що відбулася подія Аk-1.

Справді, якщо позначити то виявиться справедливим вираз

Процедура моделювання повної групи несумісних подій описується алгоритмом, схема якого наведена на рис. 2.2.

Рис. 2.3.Схема алгоритму моделювання повної групи несумісних подій

Оператор 1 звертається до генератора випадкових чисел, що відповідають рівномірному закону розподілу на інтервалі (0; 1). Оператор 2 перевіряє умову потрапляння випадкової величини x в інтервал (0; L1). Якщо ця умова виконується, то вважається, що відбулася подія А1. Якщо ця умова не виконується, то алгоритм передбачає перевірку умов потрапляння випадкової величини в інші інтервали.

3. Моделювання дискретної випадкової величини

Розподіл дискретної випадкової величини може бути поданий у вигляді таблиці

Тут pj -- імовірність того, що випадкова величина х набуває значення хj, j = 1, …, n.

Накладається також умова:

Поділимо інтервал (0; 1) на n відрізків, довжини котрих дорівнюють заданим імовірностям. Якщо випадкове число x, що формується генератором випадкових чисел, котрі відповідають рівномірному закону розподілу на інтервалі (0; 1), потрапляє до інтервалу pk, то випадкова величина х набуває значення хk. Отже, під час моделювання дискретної випадкової величини фактично використовується та сама процедура, що й за моделювання повної групи несумісних подій.

3. Програмне генерація РВП(0; 1)

3.1 Генератори випадкових чисел

Технічно термін "генератор випадкових чисел" - це абсурд; числа само по собі не є випадковими. Наприклад, 100 - це випадкове число? А 25? Що насправді означає цей термін, так це те, що створюється послідовність чисел, що з'являються випадковим чином. Це породжує складніше питання: що таке послідовність випадкових чисел? Єдино правильна відповідь: послідовність випадкових чисел - це послідовність, в якій всі елементи є незв'язаними. Це визначення наводить до такого парадоксу, що будь-яка послідовність може бути як випадковою, так і невипадковою залежно від того, як ця послідовність отримана. Наприклад, наступний рядок чисел 1 2 3 4 5 6 7 8 9 0 був отриманий друкуванням верхнього рядка клавіатури по порядку, таким чином послідовність звичайно не може розглядатися як що згенерувала випадковим чином. Але як бути, якщо ви отримаєте ту ж саму послідовність, виймаючи пронумерований тенісні кулі з боченка. В даному випадку це вже випадковим чином послідовність, що згенерувала. Даний приклад показує, що випадковість послідовності залежить від того, як вона була отримана, а не від неї самої. Пам'ятаєте, що послідовність чисел, що згенерувала комп'ютером, є детермінованою: кожне число, окрім першого, залежить від попередніх чисел. Технічно це означає, що комп'ютером може згенерувати лише квазівипадкова послідовність чисел. Проте, це вистачає для більшості завдань і в даній курсовій роботі такі послідовності для простоти називатимуться випадковими. У загальному випадку вважається добре, коли числа в послідовності випадкових чисел розподілені рівномірно (не плутайте це з нормальним розподілом або колоколообразной кривою). При рівномірному розподілі всі події рівноімовірні так, що діаграма рівномірного розподілу прагне до прямої горизонтальної лінії, а не до кривої.

До широкого поширення комп'ютерів всякий раз, коли необхідні були випадкові числа, вони виходили або киданням гральних кісток, або вийманням пронумерованих куль з ящика. У 1955 році фірма RAND опублікувала таблицю з 1 мільйона випадкових чисел, отриманих за допомогою обчислювальної машини. На ранній стадії розвитку обчислювальної техніки було розроблено багато методів генерації випадкових чисел, але більшість з них не знайшла вживання. Один дуже цікавий метод був розроблений Джоном фон Нейманом; його часто називають середньоквадратичним. У даному методі попереднє випадкове число зводиться в квадрат, а потім з результату виділяються середні цифри. Наприклад, якщо ви створюєте числа з трьох цифр, а попереднє число було 121, то зведення в квадрат дає результат 14641. Виділення трьох середніх цифр дає наступне випадкове число 464. Недоліком даного методу є те, що він має дуже короткий період повторення, званий циклом. З даної причини даний метод сьогодні не використовується.

Страницы: 1, 2, 3