4 Метод статистичних випробувань Метод статистичних випробувань

Скачати 2.04 Mb.

Назва	4 Метод статистичних випробувань Метод статистичних випробувань
Сторінка	2/31
Дата	08.04.2013
Розмір	2.04 Mb.
Тип	Лекция

bibl.com.ua > Інформатика > Лекция

1 2 3 4 5 6 7 8 9 ... 31

Табличний метод. У 1955 році корпорація «Ренд» опублікувала таблиці випадкових чисел, які мали мільйон значень. Для заповнення цих таблиць застосовувались апаратні методи. Дані цих таблиць можна використовувати під час моделювання систем за допомогою методу статистичних випробувань. У сучасних комп'ютерах ці таблиці можна зберігати на зовнішніх носіях або навіть в основній пам'яті. Головним недоліком табличного методу є те, що під час його використання витрачаються значні об'єми основної пам'яті комп'ютера.

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

Загалом же програмні генератори повинні задовольняти таким вимогам:

генерувати статистично незалежні випадкові числа, рівномірно розподілені в інтервалі [0, 1];
мати можливість відтворювати задані послідовності випадкових чисел;
затрати ресурсів процесора на роботу генератора повинні бути мінімальними;
легко створювати незалежні послідовності випадкових чисел (потоки).

Слід звернути увагу на те, що більшість програмних генераторів виробляють випадкові числа, рівномірно розподілені в інтервалі [0, 1]. Необхідність моделювання таких чисел обумовлена тим, що на їх основі можна отримати випадкові числа практично будь-яких розподілів. Потрібно також мати на увазі, що випадкові числа, які виробляють програмні генератори, є квазірівномірно розподіленими. Причина в тому, що вони створюються комп'ютером, кількість двійкових розрядів якого обмежена, і за його допомогою можна зобразити тільки дискретні (а не неперервні) значення з діапазону від 0 до 1.

Якість роботи генераторів визначається статистичними властивостями послідовностей випадкових чисел, які він виробляє, – незалежністю і випадковістю. Властивості послідовностей перевіряються за статистичними критеріями, детально описаними нижче.

Здатність відтворювання послідовності випадкових чисел полягає в тому, що за однакових початкових умов і параметрів генератор повинен відтворювати одні й ті ж послідовності псевдовипадкових чисел. Ідентичні послідовності випадкових чисел рекомендується використовувати у випадку, коли потрібно порівняти альтернативні варіанти систем, що моделюються, і налагодити програми. Однак можливість відтворення не завжди бажана під час моделювання систем і в комп'ютерних іграх. Для усунення такого недоліку початкові значення величин, необхідних для запуску програмного генератора, рекомендується брати з таймера комп'ютера.

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

У більшості генераторів псевдовипадкових чисел х_i використовується рекурентна процедура

. Найпростішим та найдавнішим серед таких генераторів є генератор фон Неймана та Метрополіса, робота якого базувалась на методі середин квадратів. Пояснімо суть цього методу.

Зобразимо умовно довільне чотирирозрядне десяткове число як х х х х. Піднесемо це число до квадрату і в отриманому результаті відкинемо по дві цифри зліва і справа:

Чотири цифри, які залишились, і є новим випадковим числом. Якщо результатом множення є число з кількістю цифр менше восьми, зліва дописуються додаткові нулі. Реалізувати програмно цей генератор дуже просто, але він має ряд вад:

якщо початкове число парне, то може відбутися виродження послідовності, тобто починаючи з деякого значення всі наступні дорівнюватимуть нулю (спробуйте взяти як початкове число 4500);
числа, які виробляє генератор, є сильно корельованими.

4.2.2. Лінійні конгруентні генератори

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

Наприклад, щоб знайти число, конгруентне з числом 134 за модулем 10, необхідно знайти цілочислову остачу від ділення 134 на 10, яка дорівнює 4.

Наведемо кілька прикладів обчислення конгруентних значень для різних m:

12  5 (mod 7); 35  5 (mod 10); 125  5 (mod 10).

Серед методів генерування випадкових чисел найбільш поширеним є лінійний мультиплікативний конгруентний метод:

(4.1)

де і = 1, 2, ...; а, с і m — цілі константи.

Щоб отримати нове число, необхідно взяти псевдовипадкове число х_i (або задати вихідне х₀), помножити його на коефіцієнт а, додати константу с і взяти модуль отриманого числа за m, тобто розділити на m, і отримати остачу. Ця остача і буде наступним псевдовипадковим числом х_i₊₁. У разі правильного підбору параметрів цей генератор повертає випадкові числа від 0 до m – 1.

Отримані за формулою (4.1) значення х_i₊₁ належать до діапазону

і мають рівномірний дискретний розподіл. Для того щоб отримати випадкове значення r_і₊₁ з інтервалу [0, 1], необхідно число х_i₊₁ розділити на m. У цьому разі всі значення m, с, a, x₀ повинні бути додатними й задовольняти умовам:

Отримана за формулою (4.1) послідовність називається лінійною конгруентною послідовністю.

Однією із вад лінійних конгруентних генераторів є те, що отримані випадкові числа х_і₊₁ суттєво залежать від значень m, с, a, x₀ і обчислюються за однією й тією ж формулою (4.1), тобто не є абсолютно випадковими. Але незважаючи на те що алгоритм їх отримання є детермінованим, за умови відповідного вибору констант m, с, a послідовність чисел х_і₊₁, на основі яких отримують значення r_і₊₁, повністю задовольнятиме більшості статистичних критеріїв.

Ще одна вада цих генераторів стосується того, що випадкові числа r_і₊₁, отримані за допомогою генератора, можуть приймати тільки дробово-раціональні значення —

. Більше того, числа r_і₊₁ можуть приймати лише деякі з указаних значень залежно від вибраних параметрів m, с, a, x₀, а також від того, як реалізується операція ділення чисел з плаваючою комою на число m у комп'ютері, тобто залежно від типу комп'ютера і системи програмування. Наприклад, якщо m = 10, x₀ = а = с = 7, то отримаємо послідовність 7; 6; 9; 0; 7; 6; 9; 0,..., яка не є випадковою. Це свідчить про важливість правильного вибору значень констант m, с, a, x₀. Правильно підібрані значення іноді називають магічними числами.

Наведений приклад ілюструє й те, що конгруентна послідовність завжди є циклічною, тобто вона починає повторюватися через певну кількість випадкових чисел. Кількість значень, після яких випадкові числа починають повторюватися, називається повним періодом генератора і є основним його параметром. Значення повного періоду залежать від розрядності комп'ютера, а також від значень m, с, a, x₀. Існує теорема, яка визначає умови існування повного періоду генератора, а саме:

числа с і m повинні бути взаємно простими, тобто мати взаємний дільник 1;
значення b = а – 1 має бути кратним q для кожного простого q, бути дільником m;
значення b має бути кратним 4, якщо m кратне 4.

Достатність цих умов уперше було доведено Халлом і Добеллом. Повне доведення теореми можна знайти в літературі [23].

Якщо с > 0, то генератор називається мішаним, а якщо с = 0 — мультиплікативним.

Розглянемо, як потрібно вибирати параметри лінійного конгруентного генератора, щоб отримати послідовність з повним періодом. Для отримання такої послідовності необхідно вибирати значення m = 2^g – 1, де g — довжина розрядної сітки комп'ютера. Для 32-розрядного комп'ютера m — найбільше ціле число, яке може бути відтворене в ньому, дане число дорівнює 2³¹ – 1 = 2147483647 (один розряд відводиться під знак числа). У цьому разі ділення х_і₊₁/m виконувати не обов'язково. Якщо в результаті роботи генератора буде отримане число х_і₊₁, яке більше ніж те, що може бути відтворене в комп'ютері, виникне переповнення розрядної сітки. Це призведе до втрати крайніх лівих двійкових знаків цілого числа, які перевищили допустимий розмір. Однак розряди, що залишились, саме і є значеннями х_і₊₁ (mod 2^g). Таким чином, під час генерування замість операції ділення можна скористатись переповненням розрядної сітки.

Стосовно константи с теорема стверджує, що для отримання послідовності з повним періодом генератора значення с повинне бути непарним, і, крім того, а – 1 має ділитися на 4. Для такого генератора початкове значення х₀ може бути довільним і лежати в діапазоні від 0 до m – 1. Якщо с = 0, то отримуємо мультиплікативний конгруентний метод, який передбачає використання таких рекурентних виразів:

(4.2)

Цей метод більш швидкодіючий, ніж попередній, але він не дає послідовності з повним періодом. Дійсно, з виразу (4.2) видно, що значення х_і₊₁ = 0 може з'явитись тільки в тому випадку, якщо послідовність вироджується в нуль. Взагалі, якщо d — будь-який дільник m і х_і кратне d, всі наступні елементи мультиплікативної послідовності х_і₊₁, х_і₊₂, ... будуть кратними d. Таким чином, якщо с = 0, потрібно, щоб х_і і m були взаємно простими числами з m і знаходились між 0 і m.

Що стосується вибору а, то у випадку, коли m = 2^g, де g  4, викладені в праці [23] умови приводять до єдиної вимоги стосовно значення а:

а = 3 (mod 8) або а = 5 (mod 8).

У цьому випадку четверта частина всіх можливих значень множників дає довжину періоду, що дорівнює m/4, яка й буде максимальним періодом генератора.

Наведемо одну з найкращих програм генерування послідовностей рівномірно розподілених випадкових чисел.

/* Програма мовою С для ТТ800: версія від 8 липня 1996 р. */

/* М. Matsumoto, email: [email protected] */

/* genrand() генерує одне псевдовипадкове число */

/* з подвійною точністю */

/* рівномірно розподілене в інтервалі [0, 1] */

/* для кожного запиту. Можна вибирати будь-які */

/* 25 початкових значень */

/* окрім всіх нулів. */

/* Див.: ACM Transactions on Modelling and Computer Simulation. */ /* Vol. 4. No. 3. 1994. pages 254-266. */

#include

#define N 25

#defіne M 7

double

genrand()

{

unsigned long y:

static int k = 0;

static unsigned long x[N]={/* Початкові 25 значень за бажанням */

0x95f24dab. 0х0b685215. 0хе76ссае7. 0xaf3ec239. 0x715fad23.

0x24a590ad. 0x69e4b5ef. 0xbf456141. 0x96bc1b7b. 0xa7bdf825.

0xclde75b7. 0x8858a9c9. 0x2da87693. 0xb657f9dd. 0xffdc8a9f.

0x8121da71. 0x8b823ecb. 0x885d05f5. 0x4e20cd47. 0x5a9ad5d9.

0x512c0c03. 0xea857ccd. 0x4cc1d30f. 0x8891a8a1. 0xa6b7aadb.

};

static unsigned long mag01[2]={

0x0. 0x8ebfd028 /* Це чарівний вектор 'а', що не змінюється*/

};

if (k==N) { /* Генерування N слів одночасно */

int kk;

for (kk=0:kk> 1) ^ mag01[x[kk] % 2];

}

for (: kk> 1) ^ mag01[x[kk] % 2];

}

k=0;

}

у = x[k];

У ^= (у << 7) & 0х2b5b2500; /* s і b. чарівні вектори*/

у ^= (у << 15) & 0xdb8b0000: /* t і с. чарівні вектори */

у &= 0xffffffff: /* вилучіть цей рядок, якщо довжина слова = 32 */

/* Наступний рядок був доданий для зменшення кореляції. */

у ^= (у >> 16); /* Додати для версії 1994 р. */

k++;

return( (double) у / (unsigned long) 0xffffffff);

}

/* main() виводить перші 50 згенерованих чисел */

main()

{ int j;

for (j=0; j<50; j++) {

printf("%5f ". genrand());

if (j%8==7) printf("\n");

}

print("\n");

}

Існують й інші конгруентні методи генерування випадкових чисел, серед яких слід відзначити адитивний.

Найпростіший генератор, послідовність якого х_і₊₁ залежить більше ніж від одного з попередніх значень, — це генератор, що використовує числа Фібоначчі:

Цей генератор широко використовувався в 50-ті роки XX століття, але, як показали подальші дослідження, статистичні властивості його досить низькі. Більш складні методи генерування випадкових чисел можна знайти в праці [23].

Розглянуті в цьому розділі методи генерування випадкових чисел не стосуються дослідників, які використовують мови або пакети моделювання. Ці засоби містять вбудовані генератори випадкових чисел, якість яких залежить від розробників цих програмних засобів. На жаль, є ще багато пакетів моделювання, в яких застосовуються генератори досить низької якості [18]. Що стосується мов програмування загального призначення, то засоби генерування випадкових чисел, вбудовані в них, взагалі не задовольняють будь-яким статистичним критеріям. Тому їх не слід використовувати під час проведення відповідальних досліджень.

4.3. Перевірка послідовностей випадкових чисел

Статистичні властивості всіх послідовностей випадкових чисел, які будуть використовуватись під час проведення досліджень, потрібно ретельно перевіряти. Для цього застосовують емпіричні та теоретичні критерії.

1 2 3 4 5 6 7 8 9 ... 31

Схожі:

Тема: Предмет, структура, завдання й методи досліджень в юридичній психології Юридична психологія, метод спостереження (інтроспекція), метод бесіди, метод експерименту (законодавчий, природний, лабораторний,...	Урок розвитку мовлення в 11 класі Підготовка до написання твору роздуму... Методи: метод випереджального навчання, метод наукового дослідження, метод дискусії, активний метод навчання — робота в малих групах,...
Список абітурієнтів, які подали ОРИГІНАЛИ ДОКУМЕНТІВ на напрям 050502 Сума балів вступних випробувань, творчих конкурсів, та вступних випробувань з фізичної підготовки	«УЗАГАЛЬНЕНИЙ МЕТОД НАЙМЕНШИХ КВАДРАТІВ (метод ЕЙТКЕНА)» Узагальнений метод найменших квадратів (метод Ейткена) оцінка параметрів лінійної економетричної моделі з гетероскедастиними заліками....
МетодичнІ матеріали до ВСТУПНИХ ВИПРОБУВАНЬ Методичні матеріали до вступних випробувань на навчання для осіб, які здобули освітньо-кваліфікаційний рівень молодшого спеціаліста...	УРОК 58 Тема уроку: Розв'язування логарифмічних рівнянь Мета уроку: формування умінь учнів розв'язувати логарифмічні рівняння різними методами: зведення логарифмічного рівняння до алгебраїчного;...
ЗМІСТ Вступ 3 Змістовна програма вступних випробувань 3 Критерії оцінювання 7 Література 9 Вступ Методичні матеріали до вступних випробувань з Історії України на навчання до Дніпропетровського університету імені Альфреда Нобеля...	ЗМІСТ Вступ 3 Змістовна програма вступних випробувань 3 Критерії оцінювання 7 Література 9 Вступ Методичні матеріали до вступних випробувань з Історії України на навчання до Дніпропетровського університету імені Альфреда Нобеля...
ЗМІСТ Вступ 3 Змістовна програма вступних випробувань 3 Критерії оцінювання 7 Література 9 Вступ Методичні матеріали до вступних випробувань з Історії України на навчання до Дніпропетровського університету імені Альфреда Нобеля...	Тема: Введення в хімію високомолекулярних сполук Опишіть методики визначення молекулярних мас полімерів (кріоскопія, ебуліоскопія, осмометрія, метод кінцевих груп, ультрацентрифугування,...

Додайте кнопку на своєму сайті:
Портал навчання