Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Вступ
Метод Монте-Карло можна визначити як метод моделювання випадкових величин з метою обчислення характеристик їх розподілів.
Виникнення ідеї використання випадкових явищ в області наближених обчислень прийнято відносити до 1878 року, коли з'явилася робота Холла про визначення числа p за допомогою випадкових бросаний голки на розграфлені паралельними лініями папір. Істота справи полягає в тому, щоб експериментально відтворити подія, ймовірність якого виражається через число p, і приблизно оцінити цю ймовірність. Вітчизняні роботи за методом Монте-Карло з'явилися в 1955-1956 роках. З того часу накопичилася велика бібліографія за методом Монте-Карло. Навіть побіжний перегляд назв робіт дозволяє зробити висновок про застосовність методу Монте-Карло для вирішення прикладних завдань з великого числа областей науки і техніки.
Спочатку метод Монте-Карло використовувався головним чином для вирішення завдань нейтронної фізики, де традиційні чисельні методи виявилися мало придатними. Далі його вплив поширився на широкий клас задач статистичної фізики, дуже різних за своїм змістом.
Метод Монте-Карло зробив і продовжує робити істотний вплив на розвиток методів обчислювальної математики (наприклад, розвиток методів чисельного інтегрування) і при вирішенні багатьох задач успішно поєднується з іншими обчислювальними методами і доповнює їх. Його застосування виправдане в першу чергу в тих завданнях, які допускають теоретико-імовірнісний опис. Це пояснюється як природністю отримання відповіді з деякою заданою вірогідністю в задачах з імовірнісним змістом, так і суттєвим спрощенням процедури вирішення.
Загальна схема методу Монте-Карло.
Суть методу Монте-Карло полягає в наступному: потрібно знайти значення а деякою досліджуваної величини. Для цього вибирають таку випадкову величину Х, математичне сподівання якої дорівнює а:
М (Х) = а.
Практично ж надходять так: виробляють n випробувань, в результаті яких отримують n можливих значень Х; обчислюють їх середнє арифметичне і приймають x в якості оцінки (наближеного значення) a *шуканого числа a:
.
Оскільки метод Монте-Карло вимагає проведення великого числа випробувань, його часто називають методом статистичних випробувань. Теорія цього методу вказує, як найбільш доцільно вибрати випадкову величину Х, як знайти її можливі значення. Зокрема, розробляються способи зменшення дисперсії використовуваних випадкових величин, в результаті чого зменшується помилка, що допускається при заміні шуканого математичного сподівання а його оцінкою а*.
Оцінка похибки методу Монте-Карло.
Нехай для отримання оцінки 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, тим менше різниця між результатами, які дають обидві формули. Це пояснюється тим, що при розподіл Стьюдента прагне до нормального.
З викладеного випливає, що метод Монте-Карло тісно пов'язаний із завданнями теорії ймовірностей, математичної статистики і обчислювальної математики. У зв'язку із завданням моделювання випадкових величин (особливо рівномірно розподілених) істотну роль відіграють також методи теорії чисел.
Серед інших обчислювальних методів, метод Монте-Карло виділяється своєю простотою і спільністю. Повільна збіжність є істотним недоліком методу, однак, можуть бути зазначені його модифікації, які забезпечують високий порядок збіжності при певних припущеннях. Правда, обчислювальна процедура при цьому ускладнюється і наближається по своїй складності до інших процедур обчислювальної математики.
Збіжність методу Монте-Карло є збіжністю за ймовірністю. Ця обставина навряд чи слід відносити до числа його недоліків, бо імовірнісні методи в достатній мірі виправдовують себе в практичних додатках. Що ж стосується завдань, що мають імовірнісний опис, то збіжністю за ймовірністю є навіть у якійсь мірі природної при їх дослідженні.
Обчислення інтегралів методом Монте-Карло.
1Спосіб усереднення підінтегральної функції.
В якості оцінки певного інтеграла приймають
,
де n - число випробувань;
- можливі значення випадкової величини X, розподіленої рівномірно в інтервалі інтегрування , їх розігрують за формулою ,
де - випадкове число;
Дисперсія усереднює функції дорівнює:
,
де , .
Якщо точне значення дисперсії обчислити важко або неможливо, то знаходять вибіркову дисперсію (при n> 30)
, або виправлену дисперсію (при n <30)
,
де .
Ці формули для обчислення дисперсії застосовують і при інших способах інтегрування, коли усереднюється функція не збігається з подинтегральной функцією.
В якості оцінки інтеграла , Де область інтегрування D належить одиничному квадрату , , беруть:
, (*)
де S - площа області інтегрування;
N - кількість випадкових точок , що належать області інтегрування.
Якщо обчислити площу S важко, то в якості її оцінки можна прийняти В цьому випадку формула (*) має вигляд:
,
де n - число випробувань.
В якості оцінки інтеграла ,
де область інтегрування V належить одиничному кубу , , ,
беруть: ,
де V - обсяг області інтегрування;
N - число випадкових точок , що належать області інтегрування.
Якщо обчислити об'єм важко, то як його оцінки можна прийняти ,
В цьому випадку формула (**) має вигляд ,
де n - число випробувань.
ПРИКЛАД
Завдання: знайти оцінку певного інтеграла .
Рішення
Використовуємо формулу .
За умовою, a = 1, b = 3, , приймемо для простоти число випробувань n = 10.
Тоді оцінка , де можливі значення розігрується за формулою .
Результати десяти випробувань наведені в таблиці 1.
Випадкові числа взяті з таблиці додатку.
Таблиця1.
|
Номер i |
|||
|
1 |
0,100 |
1,200 |
2,200 |
З таблиці 1 знаходимо .
Шукана оцінка
Спосіб істотної вибірки, що використовує «допоміжну щільність розподілу».
В якості оцінки інтеграла приймають ,
де n - число випробувань;
f (x) - щільність розподілу «допоміжної» випадкової величини X, причому ;
- Можливі значення X, які розігрують за формулою.
Функцію f (x) бажано вибирати так, щоб відношення при різних значеннях x змінювалося незначно.
ПРИКЛАД
Завдання. Знайти оцінку інтеграла
Рішення. Так як , То в якості щільності розподілу «допоміжної» випадкової величини X приймемо функцію .
З умови знайдемо . Отже,, запишемо шуканий інтеграл так:
.
Таким чином, інтеграл I представлений у вигляді математичного сподівання функції . Як шуканої оцінки приймемо вибіркову середню (для простоти обмежимося десятьма випробуваннями):
,
де - Можливі значення X, які треба розіграти за відомою щільності .
За правилом (для того, щоб розіграти можливе значення неперервної випадкової величини X, знаючи її щільність ймовірності f (x), треба вибрати випадкове число і вирішити щодо рівняння , або рівняння ,
де a - найменше звичайно можливе значення X), маємо .
Звідси знаходимо явну формулу для розігрування можливих значень X:
.
У таблиці 2 наведено результати 10 випробувань.
Склавши числа останнього рядка таблиці 2, отримаємо . Шукана оцінка дорівнює .
Таблиця 2.
|
Номер i |
|||||
|
1 |
0,100 |
0,140 |
1,150 |
1,140 |
1,009 |
Спосіб, заснований на тлумаченні інтеграла як площі.
Нехай підінтегральна функція ненегативна і обмежена: , А двовимірна випадкова величина розподілена рівномірно у прямокутнику D з підставою і висотою с.
Тоді двовимірна густина ймовірності для точок, що належать D;
поза D.
В якості оцінки інтеграла приймають ,
де n - загальне число випадкових точок , що належать D;
- число випадкових точок, які розташовані під кривою .
Завдання. Знайти оцінку інтеграла .
Рішення. Використовуємо формулу .
В інтервалі (0,2) підінтегральна функція ненегативна і обмежена, причому ; Отже, можна прийняти c = 4.
Введемо в розгляд двовимірну випадкову величину (X, Y), розподілену рівномірно у прямокутнику D з підставою і висотою з = 4, щільність ймовірності якої .
Розігруємо n = 10 випадкових точок , Що належать прямокутнику D. Враховуючи, що складова X в інтервалі (0,2) розподілена рівномірно з щільністю і складова Y в інтервалі (0,4) розподілена рівномірно з щільністю , Розіграємо координати випадкової точки , Що належить прямокутнику D, по парі незалежних випадкових чисел : , . Звідси , .
|
Номер i |
|||||||
|
1 |
0,100 |
0,200 |
0,040 |
3,960 |
0,973 |
3,892 |
1 |
Якщо виявиться, що , То точка лежить під кривою і в «лічильник »Треба додати одиницю.
Результати десяти випробувань наведені в таблиці 3.
З таблиці 3 знаходимо .
Шукана оцінка інтеграла
Програма обчислення визначеного інтеграла методом Монте-Карло.
Обчислити визначений інтеграл за методом "Монте-Карло" за формулою
,
де n - число випробувань;
g (x) - щільність розподілу "допоміжної" випадкової величини X, причому, У програмі g (x) = 1 / (ba)
Програма написана на мові 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: = ba; {Змінній "k" привласнимо значення довжини проміжку інтегрування}
writeln ('k =', k);
for i: = 1 to n do begin {проведемо n випробувань}
g: = random; {g - мінлива дійсного типу, випадкова величина з проміжку [0; 1]}
x: = a + g * (ba); {За цією формулою виходить довільна величина з [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.
Потрібно вказати проміжок інтегрування і кількість випробувань, інтегрована функція вже задана в програмі (але її можна поміняти).
; .
|
Функція |
k |
N = 10 |
N = 100 |
N = 500 |
N = 1000 |
|
f (x) = 1 + x |
2 |
5.737 |
5.9702 |
6.02 |
5.99 |
|
f (x) = x * x |
3 |
9.6775 |
8.528 |
8.7463 |
8.937 |
Висновок
Метод Монте-Карло використовується дуже часто, часом некритично і неефективним чином.
Він має деякі очевидні переваги:
а) Він не вимагає ніяких пропозицій про регулярність, за винятком квадратичної інтегрованості. Це може бути корисним, так як часто дуже складна функція, чиї властивості регулярності важко встановити.
б) Він приводить до здійсненним процедурі навіть у багатовимірному випадку, коли чисельне інтегрування не застосовується.
в) Його легко застосовувати при малих обмеженнях або без попереднього аналізу завдання.
Він має, проте, деякі недоліки, а саме:
а) Межі помилки не визначені точно, але включають якусь випадковість. Це, однак, більш психологічна, ніж реальна, труднощі.
б) Статична похибка зменшується повільно.
в) Необхідність мати випадкові числа.
Література.
1. Гмурман В.Є. Керівництво вирішення задач з теорії ймовірностей та математичної статистики: Навч. посібник для студентів втузів. - 3-е изд., Перераб. І доп. - М.: Вищ. школа, 1979р.
2. Єрмаков С. М. Методи Монте-Карло і суміжні питання. М.: Наука, 1971.
3. Севастьянов Б. А. Курс теорії ймовірностей і математичної статистики. - М.: Наука, 1982.
4. Математика. Великий енциклопедичний словник / Гол. ред. Ю. В. Прохоров. - М.: Велика Російська енциклопедія, 1999р.
5. Гмурман В. Є. Теорія ймовірностей і математична статистика. Учеб. Посібник для втузів. Вид. 5-е, перероб. і доп. М., «Вищ. школа», 1977.