Метод статистичних випробовувань
Метод Монте-Карло (за назвою міста, яке відоме своїми гральними домами) — загальна назва групи числових методів, основаних на одержанні великої кількості реалізацій стохастичного (випадкового) процесу, який формується у той спосіб, щоб його імовірнісні характеристики співпадали з аналогічними величинами задачі, яка вирішується. Використовується для вирішення задач у фізиці, математиці, економіці, оптимізації, теорії управління тощо.
Метод Монте-Карло — це метод імітації для приблизного відтворення реальних явищ. Він об'єднує аналіз чутливості (сприйнятливості) і аналіз розподілювання ймовірностей вхідних змінних. Цей метод дає змогу побудувати модель, мінімізуючи дані, а також максимізувати значення даних, які використовуються в моделі. Побудова моделі починається з визначення функціональних залежностей у реальній системі. Після чого можна одержати кількісне рішення, використовуючи теорію ймовірності й таблиці випадкових чисел.
Огляд
Не існує єдиного методу Монте-Карло, цей термін описує великий і широко використовуваний клас підходів. Проте ці підходи використовують в своїй основі єдиний шаблон:
1. Визначити область можливих вхідних даних.
2. Випадковим чином згенерувати вхідні дані із визначеної вище області за допомогою деякого заданого розподілу ймовірностей.
3. Виконати детерміновані обчислення над вхідними даними.
4. Проміжні результати окремих розрахунків звести у кінцевий результат.
Наприклад, значення π можна наблизити використанням методу Монте-Карло:
1. Намалюйте квадрат на підлозі, а потім вмалюйте коло всередину нього. З геометрії, співвідношення площі вписаною кола до площі зовнішнього квадрата становить π / 4.
2. Рівномірно розкидати деякі об'єкти однакового розміру по всій площі квадрата. Наприклад, це можуть бути зерна рису.
3. Оскільки дві області знаходяться в співвідношенні π / 4 , об'єкти повинні потрапити в області приблизно в тій же пропорції. Таким чином, підрахувавши кількість об'єктів в колі і розділити на загальну кількість об'єктів в квадраті, отримаємо наближене значення π / 4.
4. Помноживши результат на 4 буде отримано наближене значення власне самого π.
Історія
Алгоритм Буффона для визначення числа Пі
Випадкові величини використовувалися для вирішення різних прикладних завдань достатньо давно. Прикладом може служити спосіб визначення числа Пі, який був запропонований Буффоном ще в 1777 році. Суть методу була в киданні голки довжиною L на плоскість, розкреслену паралельними прямими, розташованими на відстані r один від одного (див. Рис. 1).
,
де
- A — відстань від початку голки до ближчой до неї прямої;
- O — кут голки відносно прямих.
Цей інтеграл легко взяти: 
(при умові, що r > L) тому підрахувавши долю відрізків, що пересікають прямі, можна приблизно визначити це число. При збільшенні кількості спроб точність отримуваного результату збільшуватиметься.
У 1864 році капітан Фокс, видужуючи після поранення, щоб якось зайняти себе, реалізував експеримент по киданню голки. Результати представлені в наступній таблиці:
| Число кидків | Число пересічень | Довжина голки | Відстань між прямими | Обертання | Значення Пі | |
|---|---|---|---|---|---|---|
| Перша спроба | 500 | 236 | 3 | 4 | Відсутня | 3,1780 |
| Друга спроба | 530 | 253 | 3 | 4 | Присутня | 3,1423 |
| Третя спроба | 590 | 939 | 5 | 2 | Присутня | 3,1416 |
Коментарі:
- Обертання плоскості застосовувалося (і як показують результати — успішно) для того, щоб зменшити систематичну помилку.
- У третій спробі довжина голки була більше відстані між лініями, що дозволило не збільшуючи числа кидань ефективно збільшити число подій і підвищити точність.
Зв'язок стохастичних процесів і диференціальних рівнянь
Створення математичного апарату стохастичних методів почалося в кінці 19-го століття. У 1899 році лорд Релей показав, що одновимірне випадкове блукання на безконечних гратах може давати наближене вирішення параболічного диференціального рівняння. Андрій Колмогоров в 1931 році дав великий поштовх розвитку стохастичних підходів до вирішення різних математичних завдань, оскільки він зумів довести, що ланцюги Марков пов'язані з деякими інтегро-дифференційними рівняннями. У 1933 році Іван Петровський показав, що випадкове блукання, створююче Марківський ланцюг, асимптотика пов'язане з вирішенням еліптичного диференціального рівняння в приватних похідних. Після цих відкриттів стало зрозуміло, що стохастичні процеси можна описувати диференціальними рівняннями і, відповідно, досліджувати при допомозі добре на той момент розроблених математичних методів вирішення цих рівнянь.
Народження методу Монте-Карло в Лос-Аламосе
Спочатку Енріко Фермі в 1930-х роках в Італії, а потім Джон фон Нейман і Станіслав Улам в 1940-х в Лос-Аламосе передбачили, що можна використовувати зв'язок між стохастичними процесами і диференціальними рівняннями «у зворотний бік». Вони запропонували використовувати стохастичний підхід для апроксимації багатовимірних інтегралів в рівняннях перенесення, що виникли у зв'язку із завданням про рух нейтрона в ізотропному середовищі.
Ідея була розвинена Уламом, який, за іронією долі, також як і Фокс боровся з вимушеним неробством під час одужання після хвороби, і, розкладаючи пасьянси, задався питанням, яка вірогідність того, що пасьянс «складеться». Йому в голову прийшла ідея, що замість того, щоб використовувати звичайні для подібних завдань міркування комбінаторики, можна просто поставити «експеримент» велике число разів і, таким чином, підрахувавши число вдалих результатів, оцінити їх вірогідність. Він же запропонував використовувати комп'ютери для розрахунків методом Монте-Карло.
Поява перших електронних комп'ютерів, які могли з великою швидкістю генерувати псевдовипадкові числа, різко розширила круг завдань, для вирішення яких стохастичний підхід виявився ефективнішим, ніж інші математичні методи. Після цього стався великий прорив і метод Монте-Карло застосовувався в багатьох завданнях, проте його використання не завжди було виправдане через велику кількість обчислень, необхідних для здобуття відповіді із заданою точністю.
Роком народження методу Монте-Карло вважається 1949 рік, коли в світ виходить стаття Метрополіса і Улама «Метод Монте-Карло». Назва методу походить від назви міста в князівстві Монако, широко відомого своїми багаточисельними казино, оскільки саме рулетка є одним з широко найвідоміших генераторів випадкових чисел. Станіслав Улам пише в своїй автобіографії «Пригоди математика», що назва була запропонована Ніколасом Метрополісом на честь його дядька, який був азартним гравцем.
Подальший розвиток і сучасність
У 1950-х роках метод використовувався для розрахунків при розробці водневої бомби. Основні заслуги в розвитку методу в цей час належать співробітникам лабораторій ВПС США і корпорації RAND.
У 1970-х роках в нової області математики — теорії обчислювальної складності було показано, що існує клас завдань, складність (кількість обчислень, необхідних для здобуття точної відповіді) яких зростає з розмірністю завдання експоненціально. Інколи можна, пожертвувавши точністю, знайти алгоритм, складність якого зростає повільніше, але є велика кількість завдань, для якої цього не можна зробити (наприклад, завдання визначення об'єму опуклого тіла в 'n'-мірнім евклідовим просторі) і метод Монте-Карло є єдиною можливістю для здобуття досить точної відповіді за прийнятний час. В даний час основні зусилля дослідників направлені на створення ефективних Монте-Карло алгоритмів різних фізичних, хімічних і соціальних процесів для паралельних обчислювальних систем.
Інтегрування методом Монте-Карло
Припустимо, необхідно взяти інтеграл від деякої функції. Скористаємося неформальним геометричним описом інтеграла і розумітимемо його як площа під графіком цієї функції.
Для визначення цієї площі можна скористатися одним із звичайних чисельних методів інтеграції: розбити відрізок на підвідрізки, підрахувати площу під графіком функції на кожному з них і скласти. Передбачимо, що для функції, представленої на малюнку 2, досить розбиття на 25 відрізків іі, отже, обчислення 25 значень функції. Представимо тепер, ми маємо справу з n-мірною функцією. Тоді нам необхідно 25^n відрізків і стільки ж обчислень значення функції. При розмірності функції більше 10 завдання стає величезним. Оскільки простори великої розмірності зустрічаються, зокрема, в завданнях теорії струн, а також багатьох інших фізичних завданнях, де є системи з багатьма мірами свободи, необхідно мати метод рішення,би не настільки сильно залежала від розмірності. Саме такий властивістю володіє метод Монте-Карло.
Звичайний алгоритм Монте-Карло інтегрування
Для визначення площі під графіком функції можна використовувати наступний стохастичний алгоритм:
- обмежимо функцію прямокутником (n-вимірнім паралелепіпедом в разі багатьох вимірів), площу якого S(par) можна легко обчислити;
- «накидаємо» в цей прямокутник (паралелепіпед) деяку кількість точок N штук), координати яких вибиратимемо випадковим чином;
- визначимо число точок (K штук), які попадуть під графік функції;
- площа області, обмеженою функцією і осями координат, S дається
Для малого числа вимірів інтегрованої функції продуктивність Монте-Карло інтеграції набагато нижча, ніж продуктивність детермінованих методів. Проте, в деяких випадках, коли функція задана неявно, а необхідно визначити область, задану у вигляді складних нерівностей, стохастичний метод може виявитися переважнішим.
Використання вибірки за значимістю
Очевидно, що точність обчислень можна збільшити, якщо область, що обмежує шукану функцію, буде максимальна до неї наближена. Для цього необхідно використовувати випадкові величини з розподілом, форма якого максимально близька до форми інтегрованої функції. На цьому заснований один з методів поліпшення збіжності в обчисленнях методом Монте-Карло: вибірка за значимістю.
Оптимізація
Застосування в фізіці
Комп'ютерне моделювання грає в сучасній фізиці важливу роль і метод Монте-Карло є одним з найпоширеніших в багатьох областях від квантової фізики до фізики твердого тіла, фізики плазми і астрофізики.
Алгоритм Метрополіса
Традиційно метод Монте-Карло застосовувався для визначення різних фізичних параметрів систем, що знаходяться в стані термодинамічної рівноваги. Припустимо є набір W(S) можливих станів фізичної системи S. Для визначення середнього значення 
деякої величини A необхідно розрахувати 
, где підсумовування виробляється по тих, що всім складаються S з W(S), P(S) — вірогідність стану S.
Динамічне (кінетична) формулювання
Пряме моделювання методом Монте-Карло
Пряме моделювання методом Монте-Карло якого-небудь фізичного процесу має на увазі моделювання поведінки окремих елементарних частин фізичної системи. По суті це пряме моделювання близьке до рішення задачі з перших принципів, проте зазвичай для прискорення розрахунків допускається вживання яких-небудь фізичних наближень. Прикладом можуть служити розрахунки різних процесів методом молекулярної динаміки: з одного боку система описується через поведінку її елементарних складених частин, з іншого боку, використовуваний потенціал взаємодії частенько є емпіричним.
Приклади прямого моделювання методом Монте-Карло:
- Моделювання опромінення твердих тіл іонами в наближенні бінарних зіткнень.
- Пряме Монте-Карло моделювання розріджених газів.
- Більшість кінетичних Монте-Карло моделей належать до прямих (зокрема, дослідження молекулярно-пучкової епітаксиі).
Квантовий метод Монте-Карло
Квантовий метод Монте-Карло широко застосовується для дослідження складних молекул і твердих тіл. Цю назву об'єднує декілька різних методів. Перший з них це варіаційний метод Монте-Карло, яке по суті є чисельною інтеграцією багатовимірних інтегралів, що виникають при вирішенні рівняння Шредінгера. Для вирішення завдання, в якому бере участь 1000 електронів, необхідне узяття 3000-мірних інтегралів, і при вирішенні таких завдань метод Монте-Карло має величезну перевагу в продуктивності у порівнянні з іншими чисельними методами інтеграції. Інший різновид методу Монте-Карло — це дифузійний метод Монте-Карло, який, втім, не дуже раціональний.
