Метод Монте-Карло і його застосування

Арзамаський державний педагогічний інститут

імені А. П. Гайдара

Кафедра математичного аналізу

Зубанов М. А., студент

3 курсу очного відділення

фізико-математичного

факультету

Курсова робота

Метод Монте-Карло і його застосування

Науковий керівник:

канд. тех. наук, доцент

Потєхін В.А.

Арзамас-2002 р.

Зміст

Вступ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 3

Глава 1. Деякі дані теорії ймовірностей ... ... ... ... .5

§ 1. Математичне сподівання, дисперсія ... ... ... ... ... ... ... ... .. 5

§ 2. Точність оцінки, довірча ймовірність. Довірчий

інтервал ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .6

§ 3. Нормальне розподіл ... ... ... ... ... ... ... ... ... ... ... ... ... .. 6

Глава 2. Метод Монте-Карло ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 8

§ 1. Загальна схема методу Монте-Карло ... ... ... ... ... ... ... ... .... ... .8

§ 2. Оцінка похибки методу Монте-Карло ... ... ... ... ... ... ... 8

Глава 3. Обчислення інтегралів методом Монте-Карло ... ... .12

§ 1. Алгоритми методу Монте-Карло для рішення

інтегральних рівнянь другого роду ... ... ... ... ... ... .... ... 12

§ 2. Спосіб усереднення подинтегральной функції ... ... ... .... ... 13

§ 3. Спосіб істотною вибірки, що використовує

«Допоміжну щільність розподілу» ... ... ... ... ... .16

§ 4. Спосіб, заснований на тлумаченні інтеграла як

площі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... .. 19

§ 5. Спосіб «виділення головної частини» ... ... ... ... ... ... ... ... ... ... 21

§ 6. Програма обчислення визначеного інтеграла методом

Монте-Карло ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 23

§ 7. Обчислення кратних інтегралів методом Монте-Карло. ... 25

Висновок ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 28

Додаток ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. .. 29

Література ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 30

Введення.

Метод Монте-Карло можна визначити як метод моделювання випадкових величин з метою обчислення характеристик їх розподілів.

Виникнення ідеї використання випадкових явищ в області наближених обчислень прийнято відносити до 1878 року, коли з'явилася робота Холла про визначення числа p за допомогою випадкових бросаний голки на розграфлені паралельними лініями папір. Істота справи полягає в тому, щоб експериментально відтворити подія, ймовірність якого виражається через число p, і приблизно оцінити цю ймовірність. Вітчизняні роботи за методом Монте-Карло з'явилися в 1955-1956 роках. З того часу накопичилася велика бібліографія за методом Монте-Карло. Навіть побіжний перегляд назв робіт дозволяє зробити висновок про застосовність методу Монте-Карло для вирішення прикладних завдань з великого числа областей науки і техніки.

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

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

Глава 1. Деякі дані теорії ймовірностей

§ 1. Математичне сподівання, дисперсія.

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

Математичним очікуванням дискретної випадкової величини називають суму творів всіх її можливих значень на їхню ймовірність.

,

де Х - випадкова величина, - Значення, ймовірності яких відповідно рівні .

Математичне сподівання наближено одно (тим точніше, чим більше число випробувань) середньому арифметичному можна побачити значень випадкової величини.

Дисперсією (розсіюванням) випадкової величини називають математичне сподівання квадрата відхилення випадкової величини від її математичного сподівання: .

Середнім квадратичним відхиленням випадкової величини Х називають квадратний корінь з дисперсії: .

§ 2. Точність оцінки, довірча ймовірність. Довірчий інтервал.

Точкової називають оцінку, яка визначається одним числом.

Інтервальної називають оцінку, яка визначається двома числами - кінцями інтервалу. Інтервальні оцінки дозволяють встановити точність і надійність оцінок.

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

Надійністю (довірчою ймовірністю) оцінки по називають ймовірність g, з якою здійснюється нерівність .

Довірчим називають інтервал , Який покриває невідомий параметр із заданою надійністю g.

§ 3. Нормальне розподіл.

Нормальним називають розподіл ймовірностей неперервної

випадкової величини, яке описується диференціальної функцією

.

а - математичне сподівання, s - середнє квадратичне відхилення нормального розподілу.

Глава 2. Метод Монте-Карло

§ 1. Загальна схема методу Монте-Карло.

Суть методу Монте-Карло полягає в наступному: потрібно знайти значення а деякою досліджуваної величини. Для цього вибирають таку випадкову величину Х, математичне очікування якої одно а: М (Х) = а.

Практично ж надходять так: виробляють n випробувань, у результаті яких отримують n можливих значень Х; обчислюють їх середнє арифметичне і приймають x в якості оцінки (наближеного значення) a ^* шуканого числа a:

.

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

§ 2. Оцінка похибки методу Монте-Карло.

Нехай для отримання оцінки a ^* математичного сподівання а випадкової величини Х було вироблено n незалежних випробувань (розіграно n можливих значень Х) і з них було знайдено вибіркова середня , Яка прийнята в якості шуканої оцінки: . Ясно, що якщо повторити досвід, то будуть отримані інші можливі значення Х, отже, інша середня, а значить, і інша оцінка a ^*. Вже звідси випливає, що отримати точну оцінку математичного очікування неможливо. Природно виникає питання про величину допустимої помилки. Обмежимося відшуканням лише верхньої межі d допустимої помилки із заданою вірогідністю (надійністю) g: .

Цікавить нас верхня грань помилки d є не що інше, як «точність оцінки» математичного очікування по вибіркової середньої за допомогою довірчих інтервалів. Розглянемо наступні три випадки.

1. Випадкова величина Х розподілена нормально і її середнє

квадратичне відхилення d відомо.

У цьому випадку з надійністю g верхня межа помилки

, (*)

де n число випробувань (розіграних значень Х); t - значення аргументу функції Лапласа, при якому , S - відоме середнє квадратичне відхилення Х.

2. Випадкова величина Х розподілена нормально, причому її середнє квадратичне відхилення s невідомо.

У цьому випадку з надійністю g верхня межа помилки

, (**)

де n - число випробувань; s - «виправлене» середнє квадратичне відхилення, знаходять за таблицею додатка 3.

3. Випадкова величина Х розподілена за законом, відмінному від нормального.

У цьому випадку при досить великому числі випробувань (n> 30) з надійністю, наближено дорівнює g, верхня межа помилки може бути обчислена за формулою (*), якщо середнє квадратичне відхилення s випадкової величини Х відомо, коли ж s невідомо, то можна підставити у формулу (*) його оцінку s - «виправлене» середнє квадратичне відхилення або скористатися формулою (**). Зауважимо, що чим більше n, тим менше розходження між результатами, які дають обидві формули. Це пояснюється тим, що при розподіл Стьюдента прагне до нормального.

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

Серед інших обчислювальних методів, метод Монте-Карло виділяється своєю простотою і спільністю. Повільна збіжність є істотним недоліком методу, однак, можуть бути зазначені його модифікації, які забезпечують високий порядок збіжності при певних припущеннях. Правда, обчислювальна процедура при цьому ускладнюється і наближається за своєю складністю до інших процедур обчислювальної математики. Збіжність методу Монте-Карло є збіжністю по ймовірності. Ця обставина навряд чи слід відносити до числа його недоліків, бо імовірнісні методи в достатній мірі виправдовують себе в практичних застосуваннях. Що ж до завдань, що мають імовірнісний опис, то збіжністю по імовірності є навіть якоюсь мірою природною при їх дослідженні.

Глава 3. Обчислення інтегралів методом Монте-Карло.

§ 1. Алгоритми методу Монте-Карло для рішення інтегральних рівнянь другого роду.

Нехай необхідно обчислити лінійний функціонал , Де , Причому для інтегрального оператора K з ядром виконується умова, що забезпечує відповідність низки Неймана: . Ланцюг Маркова визначається початковій щільністю і перехідною щільністю ; Ймовірність обриву ланцюга в точці дорівнює . N - випадковий номер останнього стану. Далі визначається функціонал від траєкторії ланцюга, математичне сподівання якого дорівнює . Найчастіше використовується так звана оцінка за зіткнень , Де , . Якщо при , І при , То при деякому додатковому умови . Важливість досягнення малої дисперсії в знакопостоянном випадку показує наступне твердження: якщо і , Де , То , А . Моделюючи підходящу ланцюг Маркова на ЕОМ, отримують статистичну оцінку лінійних функціоналів від рішення інтегрального рівняння другого роду. Це дає можливість і локальної оцінки рішення на основі подання: , Де . Методом Монте-Карло оцінка першого власного значення інтегрального оператора здійснюється інтераціональним методом на основі співвідношення . Усі розглянуті результати майже автоматично поширюються на системи лінійних алгебраїчних рівнянь виду . Рішення диференційних рівнянь здійснюється методом Монте-Карло на базі відповідних інтегральних співвідношень.

§ 2. Спосіб усереднення подинтегральной функції.

В якості оцінки певного інтеграла приймають

,

де n - число випробувань; - Можливі значення випадкової величини X, розподіленої рівномірно в інтервалі інтегрування , Їх розігрують за формулою , Де - Випадкове число.

Дисперсія усредняемого функції дорівнює

,

де , . Якщо точне значення дисперсії обчислити важко або неможливо, то знаходять вибіркову дисперсію (при n> 30) , Або виправлену дисперсію (при n <30) , Де .

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

В якості оцінки інтеграла , Де область інтегрування D належить одиничному квадрату , , Приймають

, (*)

де S - площа області інтегрування; N - число випадкових точок , Що належать області інтегрування.

Якщо обчислити площу S важко, то в якості її оцінки можна прийняти ; В цьому випадку формула (*) має вигляд

,

де n - число випробувань.

В якості оцінки інтеграла , Де область інтегрування V належить одиничному кубу , , , Приймають , Де V - обсяг області інтегрування, N - число випадкових точок , Що належать області інтегрування.

Якщо обчислити об'єм важко, то як його оцінки можна прийняти , В цьому випадку формула (**) має вигляд , Де n - число випробувань.

Завдання: знайти оцінку певного інтеграла .

Рішення. Використовуємо формулу . За умовою, a = 1, b = 3, . Приймемо для простоти число випробувань n = 10.Тогда оцінка , Де можливі значення розігрується за формулою .

Результати десяти випробувань наведені в таблиці 1.

Випадкові числа взяті з таблиці додатка.

Таблиця 1.

З таблиці 1 знаходимо . Шукана оцінка

§ 3. Спосіб істотною вибірки, що використовує «допоміжну щільність розподілу».

В якості оцінки інтеграла приймають , Де n - число випробувань; f (x) - щільність розподілу «допоміжної» випадкової величини X, причому ; - Можливі значення X, які розігрують за формулою .

Функцію f (x) бажано вибирати так, щоб відношення при різних значеннях x змінювалося незначно. Зокрема, якщо , То отримаємо оцінку .

Завдання. Знайти оцінку інтеграла .

Рішення. Так як , То в якості щільності розподілу «допоміжної» випадкової величини X приймемо функцію . З умови знайдемо . Отже, .

Запишемо шуканий інтеграл так:

.

Таким чином, інтеграл I представлений у вигляді математичного сподівання функції . Як шуканої оцінки приймемо вибіркову середню (для простоти обмежимося десятьма випробуваннями):

,

де - Можливі значення X, які треба розіграти за відомою щільності . За правилом (для того, щоб розіграти можливе значення безперервної випадкової величини X, знаючи її щільність ймовірності f (x), треба вибрати випадкове число і вирішити щодо рівняння

, Або рівняння ,

де a - найменше звичайно можливе значення X), маємо . Звідси знаходимо явну формулу для розігрування можливих значень X:

.

У таблиці 2 наведені результати 10 випробувань.

Склавши числа останнього рядка таблиці 2, отримаємо . Шукана оцінка дорівнює .

Таблиця 2.

§ 4. Спосіб, заснований на тлумаченні інтеграла як площі.

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

В якості оцінки інтеграла приймають , Де n - загальне число випадкових точок , Що належать D; - Число випадкових точок, які розташовані під кривою .

Завдання. Знайти оцінку інтеграла .

Рішення. Використовуємо формулу .

В інтервалі (0,2) підінтегральна функція неотрицательна і обмежена, причому , Отже, можна прийняти c = 4.

Введемо в розгляд двовимірну випадкову величину (X, Y), розподілену рівномірно в прямокутнику D з основою і висотою з = 4, щільність ймовірності якої .

Розігруємо n = 10 випадкових точок , Що належать прямокутнику D. Враховуючи, що складова X в інтервалі (0,2) розподілена рівномірно з щільністю і складова Y в інтервалі (0,4) розподілена рівномірно з щільністю , Розіграємо координати випадкової точки , Що належить прямокутнику D, по парі незалежних випадкових чисел : , . Звідси , .

Якщо виявиться, що , То точка лежить під кривою і в «лічильник »Треба додати одиницю.

Результати десяти випробувань наведені в таблиці 3.

З таблиці 3 знаходимо . Шукана оцінка інтеграла

§ 5. Спосіб «виділення головної частини».

В якості оцінки інтеграла приймають

,

де - Можливі значення випадкової величини X, розподіленої рівномірно в інтервалі інтегрування , Які розігрують за формулою ; Функція , Причому інтеграл можна обчислити звичайними методами.

Завдання. Знайти оцінку інтеграла .

Рішення. Так як , То приймемо . Тоді, вважаючи число випробувань n = 10, маємо оцінку

.

Виконавши елементарні перетворення, одержимо

.

Враховуючи, що a = 0, b = 1, можливі значення розіграємо за формулою . Результати обчислень наведені в таблиці 4.

Склавши числа останнього стовпця таблиці 4, знайдемо суму 19,597, підставивши яку в співвідношення , Отримаємо шукану оцінку інтеграла

.

Зауважимо, що точне значення I = 1,147.

§ 6. Програма обчислення визначеного інтеграла методом Монте-Карло.

Обчислити визначений інтеграл за методом "Монте-Карло" за формулою

,

де n - число випробувань; g (x) - щільність розподілу "допоміжної" випадкової величини X, причому , У програмі g (x) = 1 / (b - a)

Програма написана на мові TURBO PASCAL 7.0

Program pmk;

Uses crt;

Var k, p, s, g, x, Integral: real;

n, i, a, b: integer;

BEGIN

writeln ('Введіть проміжок інтегрування (a; b ):');

readln (a);

readln (b);

writeln ('Введіть кількість випадкових значень (число випробувань ):');

readln (n);

k: = b - a; {Змінної "k" привласнимо значення довжини проміжку інтегрування}

writeln ('k =', k);

for i: = 1 to n do begin {проведемо n випробувань}

g: = random; {g - мінлива дійсного типу, випадкова величина з проміжку [0; 1]}

x: = a + g * (b - a); {За цією формулою виходить довільна величина з [a; b]}

s: = s + (1 + x); {s: = s + (x * x)} {Взагалі можна підставити будь-яку функцію}

delay (1000); {затримка, щоб довільні значення не повторювалися}

end; {кінець випробувань}

writeln ('s =', s); {Сума функції для n довільних значень}

Integral: = (1 / n) * k * s;

writeln ('Інтеграл =', Integral);

readln;

END.

Потрібно ввести проміжок інтегрування і кількість випробувань, інтегрована функція вже задана в програмі (але її можна поміняти).

; .

§ 7. Обчислення кратних інтегралів методом Монте-Карло.

Нехай функція неперервна в обмеженій замкнутій області S і потрібно обчислити m-кратний інтеграл

. (1)

Геометрично число I є (m +1)-мірний об'єм прямого ціліндроіда в просторі , Побудованого на підставі S і обмеженого зверху даної поверхнею , Де .

Перетворимо інтеграл (1) так, щоб нова область інтегрування цілком містилася всередині одиничного m-мірного куба. Нехай область S розташована в m-мірному паралелепіпеді

. (2)

Зробимо заміну змінних . (3)

Тоді, очевидно, m-мірний паралелепіпед (2) перетворюється на m-мірний одиничний куб (4)

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

Обчислюючи якобіан перетворення, будемо мати:

. Таким чином, , (5)

де . Ввівши позначення і , Запишемо інтеграл (5) коротше в наступному вигляді: . (5 ^/)

Зазначимо спосіб обчислення інтеграла (5 ^/) методом випадкових випробувань.

Вибираємо m рівномірно розподілених на відрізку [0, 1] послідовностей випадкових чисел:

Точки можна розглядати як випадкові. Вибравши досить велика N число точок , Перевіряємо, які з них належать області σ (перша категорія) і які не належать їй (друга категорія). Нехай

1. при i = 1, 2, ..., n (6)

2. при i = n +1, n +2, ..., N (6 ^/)

(Для зручності ми тут змінюємо нумерацію точок).

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

Взявши досить велике число n точок , Приблизно можна покласти: , Звідси шуканий інтеграл виражається формулою , Де під σ розуміється m-мірний об'єм області інтегрування σ. Якщо обчислення обсягу σ скрутно, то можна прийняти: , Звідси . В окремому випадку, коли σ є одиничний куб, перевірка стає зайвою, тобто n = N і ми маємо просто .

Висновок.

Метод Монте-Карло використовується дуже часто, часом некритично і неефективним чином. Він має деякі очевидні переваги:

а) Він не вимагає ніяких пропозицій про регулярність, за винятком квадратичної інтегрованості. Це може бути корисним, так як часто дуже складна функція, чиї властивості регулярності важко встановити.

б) Він приводить до здійсненним процедурі навіть у багатовимірному випадку, коли чисельне інтегрування не застосовується, наприклад, при числі вимірів, більшим 10.

в) Його легко застосовувати при малих обмеженнях або без попереднього аналізу завдання.

Він має, проте, деякі недоліки, а саме:

а) Межі помилки не визначені точно, але включають якусь випадковість. Це, однак, більш психологічна, ніж реальна, труднощі.

б) Статична похибка зменшується повільно.

в) Необхідність мати випадкові числа.

Додаток.

Рівномірно розподілені випадкові числа

10 09 73 25 33 76 52 01 35 86 34 67 35 48 76 80 95 90 9117

37 54 20 48 05 64 89 47 42 96 24 80 52 40 37 20 63 61 04 02

08 42 26 89 53 19 64 50 93 03 23 20 90 25 60 15 95 33 47 64

99 01 90 25 29 09 37 67 07 15 38 31 13 11 65 88 67 67 43 97

12 80 79 99 70 80 15 73 61 47 64 03 23 66 53 98 95 11 68 77

66 06 57 47 17 34 07 27 68 50 36 69 73 61 70 65 81 33 98 85

31 06 01 08 05 45 57 18 24 06 35 30 34 26 14 86 79 90 74 39

85 26 97 76 02 02 05 16 56 92 68 66 57 48 18 73 05 38 52 47

63 57 33 21 35 05 32 54 70 48 90 55 35 75 48 28 46 82 87 09

73 79 64 57 53 03 52 96 47 78 35 80 83 42 82 60 93 52 03 44

Література.

1. Гмурман В.Є. Керівництво вирішення завдань з теорії ймовірностей і математичної статистики: Учеб. посібник для студентів втузів. - 3-е изд., Перераб. І доп. - М.: Вища. школа, 1979р.

2. Єрмаков С. М. Методи Монте-Карло та суміжні питання. М.: Наука, 1971.

3. Севастьянов Б. А. Курс теорії ймовірностей і математичної статистики. - М.: Наука, 1982.

4. Математика. Великий енциклопедичний словник / Гол. ред. Ю. В. Прохоров. - М.: Велика Російська енциклопедія, 1999р.

5. Гмурман В. Є. Теорія ймовірностей і математична статистика. Учеб. посібник для втузів. Изд. 5-е, перероб. і доп. М., «Вища. школа », 1977.