Метод Монте-Карло

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

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

Метод Монте-Карло широко використовується у всіх випадках симуляції на ЕОМ.

Огляд

Метод Монте-Карло застосовується для апроксимації значення π. Після розміщення 30000 випадкових точок, оцінка для π знаходиться в межах 0,07 % від фактичного значення.

Не існує єдиного методу Монте-Карло, цей термін описує великий і широко використовуваний клас підходів. Проте ці підходи використовують в своїй основі єдиний шаблон:

1. Визначити область можливих вхідних даних.
2. Випадковим чином згенерувати вхідні дані із визначеної вище області за допомогою деякого заданого розподілу ймовірностей.
3. Виконати детерміновані обчислення над вхідними даними.
4. Проміжні результати окремих розрахунків звести у кінцевий результат.

Наприклад, можна отримати наближене значення числа $\pi$ за допомогою методу Монте-Карло:

1. Намалюйте квадрат на підлозі, а потім впишіть круг всередину квадрата. З геометрії, співвідношення площі вписаною круга до площі зовнішнього квадрата становить $\pi /4$.
2. Рівномірно розкидати деякі об'єкти однакового розміру по всій площі квадрата. Наприклад, це можуть бути зерна рису.
3. Оскільки дві області знаходяться в співвідношенні $\pi /4$, об'єкти повинні потрапити в області приблизно в тій же пропорції. Таким чином, підрахувавши кількість об'єктів в колі і розділити на загальну кількість об'єктів в квадраті, отримаємо наближене значення $\pi /4$.
4. Помноживши результат на 4 буде отримано наближене значення власне самого $\pi$.

У цій процедурі вхідною областю є квадрат, який описує коло. Генеруються випадкові вхідні дані, тобто розсіювання зерна на квадрат, потім виконуються обчислення на кожному вході(проводиться перевірка на те, чи попало зерно в коло). Кінцево, ми сумуємо результати, щоб отримати остаточний результат, безпосередньо наближення $\pi$.

Є два важливих моменти, які слід враховувати: По-перше, якщо зерна не розподілені рівномірно, то наше наближення буде мінімальним.

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

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

Історія

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

Енріко Фермі в 1930-х і Станіславу Уляму в 1946 році першим прийшла в голову ідея подібного методу. Улям пізніше зв'язався з Джоном фон Нейманом, щоб працювати над ним.

Фізики з Лос-Аламоської наукової лабораторії досліджували радіаційний захист та відстань, яку нейтрони проходять через різні матеріали. Зважаючи на велику кількість необхідних даних, таких як середня відстань, яку нейтрони проходять в речовині до зіткнення з атомним ядром або скільки енергії нейтрони мають віддати, щоб зіткнутися з ядром, задача не могла бути розв'язана за допомогою аналітичних розрахунків.

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

Над методом Монте-Карло працював також Ніколас Костянтин Метрополіс.

Визначення

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

• Моделювання: Зображення однієї псевдо-випадкової однорідної змінної з інтервалу [0,1] може бути використане для імітації кидання монети: Якщо значення менше або дорівнює 0,50 вважають, що результат — орел, якщо значення більше ніж 0,50 позначають результат, як решка.
• Метод Монте-Карло: висипають коробку монет на столі, а потім обчислюють співвідношення монет, які приземляються різними сторонами.
• Моделювання Монте-Карло: Накреслюється велика кількість псевдовипадкових однорідних змінних з інтервалу [0,1], а також присвоюють значення менше або рівне 0,50 — моделювання методом Монте-Карло для поведінки повторних підкидань монет.

Монте-Карло і випадкові числа

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

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

Савіловський перерахував характеристики високоякісного моделювання методом Монте-Карло:

• (Псевдо-випадковий) генератор чисел має певні характеристики (наприклад, довгий «період» до того, як послідовність повторюється)
• (Псевдо-випадковий) генератор чисел генерує значення, які проходять випробування на випадковість
• є достатня кількість зразків для забезпечення точних результатів
• використовується належний метод вибірки
• алгоритм, який використовується, є дієвим для ситуації, що моделюється
• він імітує явища.

Застосування

Методи Монте-Карло особливо корисні для моделювання явищ зі значною невизначеністю вхідних даних і систем з великим числом пов'язаних ступенів вільності. Області застосування:

Фізичні науки

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

Інженерія

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

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

Дизайн і візуальні

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

Фінанси і бізнес

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

Джерела

• Карташов М. В. Імовірність, процеси, статистика. — Київ : ВПЦ Київський університет, 2007. — 504 с.
• Гнеденко Б. В. Курс теории вероятностей. — 6-е изд. — Москва : Наука, 1988. — 446 с.(рос.)
• Гихман И. И., Скороход А. В., Ядренко М. В. Теория вероятностей и математическая статистика. — Київ : Вища школа, 1988. — 436 с.(рос.)
• Статистичні та Монте-Карло алгоритми моделювання випадкових процесів у макро- і мікросистемах у MathCAD: монографія / П. С. Кособуцький ; М-во освіти і науки України, Нац. ун-т «Львів. політехніка». — Львів: Вид-во Львів. політехніки, 2014. — 412 с. : іл. — Тит. арк. парал. англ. — Бібліогр. в кінці розділів. — ISBN 978-617-607-611-7
• Методы Монте-Карло в статистической физике. — М. : Мир, 1982. — 400 с.
• Биндер К., Хеерман Д. В. Моделирование методом Монте-Карло в статистической физике. — М. : Физматлит, 1995. — 144 с.
• Гулд Х., Тобочник Я. Компьютерное моделирование в физике. — М. : Мир, 1990. — Т. 2. — 400 с.
• Кунин С. Вычислительная физика. — М. : Мир, 1992. — 518 с.
• Соболь И. М. Численные методы Монте-Карло. — М. : Наука, 1973. — 312 с.
• Хеерман Д. В. Методы компьютерного эксперимента в теоретической физике. — М. : Наука, 1990. — 176 с.\
• Жерновий Ю. В. Імітаційне моделювання систем масового обслуговування: практикум / Ю. В. Жерновий. — Львів: Видавничий центр ЛНУ імені Івана Франка, 2007.

Посилання

• Стаття «Моделируя жизнь», автор Андрій Тепляков (рос.)
• Книга «Fundamentals of the Monte Carlo method for neutral and charged particle transport», автор Alex F Bielajew (англ.)
• Стаття «Metopolis, Monte Carlo and the MANIAC»
• N. Metropolis, S. Ulam, The Monte Carlo Method, J. Amer. statistical assoc. 1949 44 № 247 335—341.
• Книга «Fundamentals of the Monte Carlo method for neutral and charged particle transport», автор Alex F Bielajew (на английском)
• W. M. C. Foulkes, L. Mitas, R. J. Needs and G. Rajagopal, Quantum Monte Carlo simulations of solids, reviews of Modern Physics 73 (2001) 33.
• Статья «Metopolis, Monte Carlo and the MANIAC»
• Статья о Монте-Карло на www.riskglossary.com
• Cuba — a library for multidimensional numerical integration