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

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

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

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

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

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

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

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

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

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

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

В цьому випадку з імовірністю g верхня границя похибки

, (*)

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

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

В цьому випадку з імовірністю g верхня границя похибки

, (**)

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

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

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

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

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

Нехай функція неперервна в обмеженій замкнутій області 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 і ми маємо просто

2.1 Принцип роботи методу Монте–Карло

Датою народження методу Монте-Карло визнано вважати 1949 рік, коли американські учені Н. Метрополіс і С. Услам опублікували статтю під назвою «Метод Монте-Карло», в якій були викладені принципи цього методу. Назва методу походить від назви міста Монте–Карло, що славився своїми гральними закладами, неодмінним атрибутом яких була рулетка – один з простих засобів здобуття випадкових чисел з хорошим рівномірним розподілом, на використанні яких заснований цей метод. Метод Монте–Карло - це статистичний метод. Його використовують при обчисленні складних інтегралів, вирішенні систем рівнянь алгебри високого порядку, моделюванні поведінки елементарних часток, в теоріях передачі інформації, при дослідженні складних економічних систем. Суть методу полягає в тому, що в завдання вводять випадкову величину , що змінюється по якому те правилу . Випадкову величину вибирають так, щоб шукана в завданні величина стала математичною чекання від , тобто .

Таким чином, шукана величина визначається лише теоретично. Щоб знайти її чисельно необхідно скористатися статистичними методами. Тобто необхідно узяти вибірку випадкових чисел об'ємом . Потім необхідно обчислити вибіркове середнє варіанту випадкової величини по формулі:

. (1)

Обчислене вибіркове середнє приймають за наближене значення

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

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

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

де n – число випробувань ;g(x) – щільність розподілу.

3.1 Програма складена на мові програмування TURBO PASCAL 7.0

program MonteCarlo;

uses

crt;

const k=100;

Var a,b,c,d,ng,vg,x,y,s,integral : real;

n,i,j : integer;

integr:array[1..k]of real;

Function f(x,y:real):real;

Begin

f:=Sqrt(x+y);

end;

Function nm(x:real):real;

Begin

nm:=3*x;

end;

Function vm(x:real):real;

Begin

vm:=8*x;

end;

BEGIN

clrscr;

writeln('Vvedit znachennya granyts integruvannya ');

write('a='); readln(a);

write('b='); readln(b);

writeln('Vvedit chyslo vyprobuvan:');

readln(n);

c:=nm(a);

d:=vm(b);

randomize;

for j:=1 to k do

begin

s:=0; integral:=0;

For i:=1 to n do

begin

x:=a+(b-a)*random;

y:=c+(d-c)*random;

ng:=nm(x);

vg:=vm(x);

If (y <= vg) and(y >= ng) then s:=s + f(x, y);

end;

integr[j]:=(b-a)*(d-c)*s/n;

writeln(integr[j]:10:4);

end;

for j:=1 to k do

Integral:=integral+ integr[j];

writeln('Userednenyy integral=',(integral/k):10:4);

readln;

END.

3.2Програма складена в Matematica program MonteCarlo;

{$APPTYPE CONSOLE}

uses

SysUtils;

const k=100;

Var a,b,c,d,ng,vg,x,y,s,integral : real;

n,i,j : integer;

integr:array[1..k]of real;

Function f(x,y:real):real;

Begin

f:=Sqrt(x+y);

end;

Function nm(x:real):real;

Begin

nm:=3*x;

end;

Function vm(x:real):real;

Begin

vm:=8*x;

end;

BEGIN

writeln('Vvedit znachennya granyts integruvannya ');

write('a='); readln(a);

write('b='); readln(b);

writeln('Vvedit chyslo vyprobuvan:');

readln(n);

c:=nm(a);

d:=vm(b);

for j:=1 to k do

begin

s:=0; integral:=0;

randomize;

For i:=1 to n do

begin

x:=a+(b-a)*random;

y:=c+(d-c)*random;

ng:=nm(x);

vg:=vm(x);

If (y <= vg) and(y >= ng) then s:=s + f(x, y);

end;

integr[j]:=(b-a)*(d-c)*s/n;

writeln(integr[j]:10:4);

end;

for j:=1 to k do

Integral:=integral+ integr[j];

writeln('Userednenyy integral=',(integral/k):10:4);

readln;

END.

3.1Результат програми

Функція

N=100

N=500

N=1000

N=10000

Pascal

a=0

b=4

165.1777

162.6751

162.1815

162.1507

mathematica

a=0

b=4

Висновок

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

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

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

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

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

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

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

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

Джерела використаної інформації

1. Гмурман В.Е. Руководство к решению задач по теории вероятностей и математической статистике: Учеб. пособие для студентов втузов. – 3-е изд., перераб. И доп. – М.: Высш. школа, 1979г.

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

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

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

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

6. Демидович Б.П. Основы вычислительной математики. М., Государственное издательство физико-математической литературы