Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

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


1. Історія

1.1. Алгоритм Бюффона для визначення числа Пі

Випадкові величини використовувалися для вирішення різних прикладних задач досить давно. Прикладом може служити спосіб визначення числа Пі, який був запропонований Бюффоном ще в 1777. Суть методу була в киданні голки довжиною L на площину, розкреслену паралельними прямими, розташованими на відстані r один від одного (див. Рис. 1).

Рисунок 1. Метод Бюффона

Імовірність (як видно з подальшого контексту, мова йде не про ймовірність, а про математичному очікуванні кількості перетинів за один досвід; ймовірністю це стає лише за умови, що r> L ) Того, що відрізок перетне пряму, пов'язана з числом Пі :

p = \ int \ limits_ {0} ^ {\ pi} \ int \ limits_ {0} ^ {l \ sin {\ theta}} \ frac {1} {r \ pi} dAd \ theta , Де

  • A - Відстань від початку голки до найближчої до неї прямої;
  • θ - Кут голки відносно прямих.

Цей інтеграл просто взяти: p = \ frac {2L} {r \ pi \,} (За умови, що r> L ), Тому підрахувавши частку відрізків, які перетинають прямі, можна приблизно визначити це число. При збільшенні кількості спроб точність отримуваного результату буде збільшуватися.

В 1864 капітан Фокс, одужуючи після поранення, щоб якось зайняти себе, реалізував експеримент з кидання голки. Результати представлені в таблиці:

Число бросаний Число перетинів Довжина голки Відстань між прямими Обертання Значення Пі
Перша спроба 500 236 3 4 відсутня 3.1780
Друга спроба 530 253 3 4 присутній 3.1423
Третя спроба 590 371 5 2 присутній 3.1416

Коментарі:

  • Обертання площини застосовувалося [джерело не вказано 885 днів] (і як показують результати - успішно) для того, щоб зменшити систематичну помилку.
  • У третій спробі довжина голки була більше відстані між лініями, що дозволило не збільшуючи числа бросаний ефективно збільшити число подій і підвищити точність.

1.2. Зв'язок стохастичних процесів і диференціальних рівнянь

Створення математичного апарату стохастичних методів почалося в кінці XIX століття. В 1899 лорд Релей показав, що одномірне випадкове блукання на нескінченній решітці може давати наближене рішення параболічного диференціального рівняння. Андрій Колмогоров в 1931 дав великий поштовх розвитку стохастичних підходів до вирішення різних математичних завдань, оскільки він зумів довести, що ланцюга Маркова пов'язані з деякими інтегро-диференціальними рівняннями. В 1933 Іван Петровський показав, що випадкове блукання, створююче Марковскую ланцюг, асимптотично пов'язано з рішенням еліптичного диференціального рівняння в приватних похідних. Після цих відкриттів стало зрозуміло, що стохастичні процеси можна описувати диференціальними рівняннями і, відповідно, досліджувати за допомогою добре на той момент розроблених математичних методів вирішення цих рівнянь.


1.3. Народження методу Монте-Карло в Лос-Аламосі

Спочатку Енріко Фермі в 1930-х роках в Італії, а потім Джон фон Нейман і Станіслав Улам в 1940-х в Лос-Аламосі припустили, що можна використовувати зв'язок між стохастичними процесами і диференціальними рівняннями "у зворотний бік". Вони запропонували використовувати стохастичний підхід для апроксимації багатовимірних інтегралів в рівняннях перенесення, що виникли у зв'язку із завданням про рух нейтрона в ізотропного середовищі.

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

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

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


1.4. Подальший розвиток і сучасність

В 1950-х роках метод використовувався для розрахунків при розробці водневої бомби. Основні заслуги у розвитку методу в цей час належать співробітникам лабораторій ВПС США і корпорації RAND.

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

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


2. Інтегрування методом Монте-Карло

Рисунок 2. Чисельне інтегрування функції детерміністичним методом

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

Для визначення цієї площі можна скористатися одним зі звичайних чисельних методів інтегрування : розбити відрізок на подотрезкі, підрахувати площу під графіком функції на кожному з них і скласти. Припустимо, що для функції, представленої на малюнку 2, досить розбиття на 25 відрізків і, отже, обчислення 25 значень функції. Уявімо тепер, ми маємо справу з n -Мірної функцією. Тоді нам необхідно 25 n відрізків і стільки ж обчислень значення функції. При розмірності функції більше 10 завдання стає величезною. Оскільки простору великої розмірності зустрічаються, зокрема, в задачах теорії струн, а також багатьох інших фізичних завданнях, де є системи з багатьма ступенями свободи, необхідно мати метод рішення, обчислювальна складність якого б не настільки сильно залежала від розмірності. Саме такою властивістю володіє метод Монте-Карло.


2.1. Звичайний алгоритм Монте-Карло інтегрування

Припустимо, потрібно обчислити певний інтеграл \ Int \ limits_ {a} ^ {b} f (x) \, dx

Розглянемо випадкову величину ~ U , Рівномірно розподілену на відрізку інтегрування ~ [A, b] . Тоді ~ F (u) так само буде випадковою величиною, причому її математичне сподівання виражається як
\ Mathbb {E} f (u) = \ int \ limits_a ^ b f (x) \ phi (x) \, dx , Де ~ \ Phi (x) - Щільність розподілу випадкової величини ~ U , Що дорівнює \ Frac {1} {b-a} на ділянці ~ [A, b] .

Таким чином, шуканий інтеграл виражається як
\ Int \ limits_ {a} ^ {b} f (x) \, dx = (b-a) \ mathbb {E} f (u) .

Але матожидание випадкової величини ~ F (u) можна легко оцінити, змоделювавши цю випадкову величину і порахувавши вибіркове середнє.

Отже, кидаємо ~ N точок, рівномірно розподілених на ~ [A, b] , Для кожної точки ~ U_i обчислюємо ~ F (u_i) . Потім обчислюємо вибіркове середнє: \ Frac {1} {N} \ sum ^ {N} _ {i = 1} f (u_i) .

У підсумку отримуємо оцінку інтеграла: \ Int \ limits_ {a} ^ {b} f (x) \, dx \ approx \ frac {ba} {N} \ sum ^ {N} _ {i = 1} f (u_i)

Точність оцінки залежить тільки від кількості точок ~ N .

Цей метод має і геометричну інтерпретацію. Він дуже схожий на описаний вище детерминистический метод, з тією різницею, що замість рівномірного розподілу області інтегрування на маленькі інтервали і підсумовування площ одержані "стовпчиків" ми закидаємо область інтегрування випадковими точками, на кожній з яких будуємо такий же "стовпчик", визначаючи його ширину як \ Frac {b-a} {N} , І підсумовуємо їх площі.


2.2. Геометричний алгоритм Монте-Карло інтегрування

Рисунок 3. Чисельне інтегрування функції методом Монте-Карло

Для визначення площі під графіком функції можна використовувати наступний стохастичний алгоритм:

  • обмежимо функцію прямокутником (n-мірним параллелепипедом в разі багатьох вимірів), площа якого S p a r можна легко обчислити;
  • "Накидаємо" в цей прямокутник (паралелепіпед) деяку кількість точок ( N штук), координати яких вибиратимемо випадковим чином;
  • визначимо число точок ( K штук), які потраплять під графік функції;
  • площа області, обмеженої функцією і осями координат, S дається виразом S = S_ {par} \ frac {K} {N}

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


2.3. Використання вибірки за значимістю

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


3. Оптимізація

4. Застосування у фізиці

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

4.1. Алгоритм Метрополіса

Традиційно метод Монте-Карло застосовувався для визначення різних фізичних параметрів систем, що знаходяться в стані термодинамічної рівноваги. Припустимо, що є набір W (S) можливих станів фізичної системи S . Для визначення середнього значення \ Overline {A} деякої величини A необхідно розрахувати \ Overline {A} = \ sum_ {S} A (S) P (S) , Де підсумовування проводиться по всіх станів S з W (S) , P (S) - Ймовірність стану S .


4.2. Динамічна (кінетична) формулювання

4.3. Пряме моделювання методом Монте-Карло

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

Приклади прямого моделювання методом Монте-Карло:


4.4. Квантовий метод Монте-Карло

Квантовий метод Монте-Карло широко застосовується для дослідження складних молекул і твердих тіл. Ця назва об'єднує декілька різних методів. Перший з них це варіаційний метод Монте-Карло, який по суті є чисельною інтеграцією багатовимірних інтегралів, що виникають при вирішенні рівняння Шредінгера. Для вирішення завдання, в якій бере участь 1000 електронних, необхідно взяття 3000-мірних інтегралів, і при вирішенні таких завдань метод Монте-Карло має величезну перевагу в продуктивності в порівнянні з іншими чисельними методами інтегрування. Інший різновид методу Монте-Карло - це дифузійний метод Монте-Карло.


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Монте-Карло
Монте, П'єр
Монте-Альто
Монте-Албан
Монте, П'єр (значення)
Монте-Пердідо
Янг, Ла Монте
Монте-Гаргано
Монте-Дженерозо
© Усі права захищені
написати до нас
Рейтинг@Mail.ru