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

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

Методы используются для решения задач в различных областях физики, химии, математики, экономики, оптимизации, теории управления и др.

Название метода происходит от района Монте-Карло, известного своими казино.

Случайные величины использовались для решения различных прикладных задач достаточно давно. Примером может служить способ определения числа Пи, который был предложен Бюффоном ещё в 1777 году. Суть метода была в бросании иглы длиной ${\displaystyle L}$ на плоскость, расчерченную несколькими параллельными прямыми, расположенными на расстоянии ${\displaystyle r}$ друг от друга. Вероятность (при условии ${\displaystyle r>L}$ или математическое ожидание в ином случае) того, что отрезок пересечёт прямую, связана с числом Пи:

${\displaystyle p=\int \limits _{0}^{\pi }\int \limits _{0}^{l\sin {\theta }}{\frac {1}{r\pi }}dAd\theta ,}$

где

• ${\displaystyle A}$ — расстояние от начала иглы до ближайшей к ней прямой;
• ${\displaystyle \theta }$ — угол иглы относительно прямых.

Этот интеграл просто взять: ${\displaystyle p={\frac {2L}{r\pi \,}}}$ (при условии, что ${\displaystyle r>L}$), поэтому подсчитав долю отрезков, пересекающих прямые, можно приближённо определить это число. При увеличении количества попыток точность получаемого результата будет увеличиваться.

В 1864 году капитан Фокс, выздоравливая после ранения, чтобы как-то занять себя, реализовал эксперимент по бросанию иглы^[1]. Результаты представлены в следующей таблице:^[2]

Комментарии:

• Длины указаны в дюймах.
• Вращение плоскости применялось (и как показывают результаты — успешно) для того, чтобы уменьшить систематическую ошибку^[2].
• В третьей попытке длина иглы была больше расстояния между линиями, что позволило, не увеличивая числа бросаний, эффективно увеличить число событий и повысить точность (за одно бросание могло возникнуть несколько пересечений).

Создание математического аппарата стохастических методов началось в конце XIX века. В 1899 году лорд Релей показал, что одномерное случайное блуждание на бесконечной решётке может давать приближённое решение одного из видов параболического дифференциального уравнения^[3]. Андрей Николаевич Колмогоров в 1931 году дал большой толчок развитию стохастических подходов к решению различных математических задач, поскольку он сумел доказать, что цепи Маркова связаны с некоторыми интегро-дифференциальными уравнениями. В 1933 году Иван Георгиевич Петровский показал, что случайное блуждание, образующее Марковскую цепь, асимптотически связано с решением эллиптического дифференциального уравнения в частных производных. После этих открытий стало понятно, что стохастические процессы можно описывать дифференциальными уравнениями и, соответственно, исследовать при помощи хорошо на тот момент разработанных математических методов решения этих уравнений.

С развитием вычислительной техники возрастает роль численных методов решения прикладных задач. Важное место в этом процессе занимают алгоритмы численного статистического моделирования или методы Монте-Карло. Особое место этих методов связано с простотой и естественностью их распараллеливания с целью эффективного применения современных многопроцессорных компьютерных систем. Под численным статистическим моделированием обычно понимают реализацию с помощью компьютера вероятностной модели того или иного объекта с целью оценивания изучаемых интегральных параметров (средних значений нужных характеристик) на основе закона больших чисел. Исторически интенсивное развитие теории и приложений метода Монте-Карло было связано с разработкой численных моделей ядерных процессов (при создании соответствующих военных и технических устройств — бомб, реакторов и т. п.) в СССР и США в 50-е годы XX века. Разработка теории метода связана с фундаментальными работами Дж. Неймана, С. Улама, Н. Метрополиса, Н. И. Бусленко, Дж. М. Хеммерсли, Дж. Спанье, И. М. Соболя, С. М. Ермакова, Г. А. Михайлова, Г. И. Марчука, М. Кейлоса и др. В последние шестьдесят лет область применения численного статистического моделирования значительно расширилась. Была разработана содержательная теория вероятностных представлений решений задач математической физики. На базе этой теории были построены эффективные(экономичные) оцениватели метода Монте-Карло. Алгоритмы численного статистического моделирования конструируются и используются также для решения задач статистической физики (схема Метрополиса — Хастингса, модель Изинга и др.), физической и химической кинетики (многочастичные схемы, численные методы решения уравнений Больцмана и Смолуховского, моделирование реакций и фазовых переходов, построение вероятностных клеточных автоматов и др.), теории массового обслуживания (марковские модели с пуассоновскими потоками заявок), финансовой математики (вероятностные формулы и итерационные процессы, алгоритмы решения стохастических дифференциальных уравнений и др.), теории турбулентности, математической биологии и т. д. Особое развитие получают также численные модели случайных процессов и полей (с применениями в метеорологии, физике атмосферы и океана и других областях), а также смешанные рандомизированные проекционные и дискретностохастические численные схемы (включая функциональные алгоритмы).

Предположим, необходимо взять интеграл от некоторой функции. Воспользуемся неформальным геометрическим описанием интеграла и будем понимать его как площадь под графиком этой функции.

Для определения этой площади можно воспользоваться методом прямоугольников: разбить отрезок на подотрезки равной ширины, подсчитать площадь всех этих подотрезков и сложить. В итоге мы получим площадь приблизительно равную площади под графиком. Предположим, что для функции, представленной на рисунке, достаточно разбиения на 25 отрезков и, следовательно, вычисления 25 значений функции. Представим теперь, мы имеем дело с ${\displaystyle n}$-мерной функцией. Тогда нам необходимо ${\displaystyle 25^{n}}$ отрезков и столько же вычислений значения функции. При размерности функции больше 10 задача становится огромной. Поскольку пространства большой размерности встречаются, в частности, в задачах теории струн, а также многих других физических задачах, где имеются системы со многими степенями свободы, необходимо иметь метод решения, вычислительная сложность которого бы не столь сильно зависела от размерности. Именно таким свойством обладает метод Монте-Карло.

В самом общем виде схема метода Монте-Карло выглядит следующим образом. Пусть требуется приближённо вычислить на компьютере некоторую величину ${\displaystyle \mathrm {I} }$. Предполагается, что можно построить (выбрать) случайную величину ${\displaystyle \zeta }$, математическое ожидание ${\displaystyle \mathrm {E} \zeta }$ которой равно ${\displaystyle \mathrm {I} }$ (или достаточно близко к этой величине), дисперсия ${\displaystyle D\zeta =\mathrm {E} (\zeta -\mathrm {E} \zeta )^{2}}$ конечна, и кроме того, выборочные значения ${\displaystyle \zeta }$ случайной величины ${\displaystyle \zeta }$ могут быть достаточно эффективно (экономично) численно смоделированы (реализованы на компьютере).

АЛГОРИТМ 1. Численно моделируем (реализуем на компьютере) достаточно большое количество ${\displaystyle n}$ выборочных значений ${\displaystyle \zeta _{i},...,\zeta _{n}}$ случайной величины ${\displaystyle \zeta }$ и, используя закон больших чисел, получаем приближение требуемой величины:

${\displaystyle \mathrm {I} =\mathrm {E} \zeta \thickapprox \mathrm {Z} _{n}={\frac {\zeta _{1}+...+\zeta _{n}}{n}}}$

В русскоязычной литературе по методам Монте-Карло базовая случайная величина ${\displaystyle \zeta }$ называется оценкой величины ${\displaystyle \mathrm {I} }$ (в англоязычной литературе используется термин «estimator», реже — «estimate»). Чаще всего монте-карловская оценка ${\displaystyle \zeta }$ имеет вид

${\displaystyle \zeta =q(\xi ),}$

где ${\displaystyle \xi =(\xi ^{(1)},...\xi ^{(d)})}$ — это случайный вектор или отрезок последовательности случайных величин с заданными распределениями, а ${\displaystyle q(x)}$ — функция (неслучайная) ${\displaystyle d}$ переменных.

АЛГОРИТМ 1.1 Пусть у нас есть интеграл ${\displaystyle \mathrm {I} }$:

${\displaystyle \mathrm {I} =\int \limits _{X}^{}g(x)dx;X\subseteq \mathbb {R} ^{d}}$

Выберем плотность распределения ${\displaystyle f_{\xi }(x),x\in \mathbb {R} ^{d}}$, случайного вектора ${\displaystyle \xi }$ так, что ${\displaystyle f_{\xi }(x)>0}$ и ${\displaystyle g(x)\neq 0}$.Численно приближаем интеграл ${\displaystyle \mathrm {I} }$ следующим образом:

${\displaystyle \mathrm {I} =\int \limits _{X}^{}g(x)dx=\int \limits _{X}^{}{\frac {g(x)}{f_{\xi }(x)}}f_{\xi }(x)dx=\mathrm {E} \zeta \approx {\frac {1}{n}}{\Biggl (}{\frac {g(\xi _{1})}{f_{\xi }(\xi _{1})}}+...+{\frac {g(\xi _{n})}{f_{\xi }(\xi _{n})}}{\Biggr )}}$,

где ${\displaystyle \zeta =q(\xi )={\frac {g(\xi )}{f_{\xi }(\xi )}}}$ и ${\displaystyle \xi =(\xi ^{(1)},...\xi ^{(d)})}$ это выборочные значения случайного вектора ${\displaystyle \xi }$, смоделированные на компьютере согласно выбранной плотности ${\displaystyle f_{\xi }(x)}$.

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

• ограничим функцию прямоугольником (${\displaystyle n}$-мерным параллелепипедом в случае ${\displaystyle d}$-мерных измерений), площадь которого ${\displaystyle S}$ можно легко вычислить;
• «набросаем» в этот прямоугольник (параллелепипед) некоторое количество точек (${\displaystyle N}$ штук), координаты которых будем выбирать случайным образом;
• определим число точек (${\displaystyle K}$ штук), которые попадут под график функции;
• площадь области, ограниченной функцией и осями координат, будет считаться по формуле ${\displaystyle S={\frac {K}{N}}}$

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

К преимуществам алгоритмов численного статистического моделирования относятся:

• возможность решения многомерных (в том числе бесконечномерных) задач численного интегрирования со сложными (в том числе негладкими) начальными данными;
• возможность решения задач со случайными параметрами, в том числе возможность моделирования траекторий случайных процессов и полей;
• универсальная (хотя и невысокая) скорость сходимости (порядка ${\displaystyle {\frac {1}{\surd n}}}$ по числу выборочных значений {${\displaystyle \zeta _{i};i=1,...n}$});

К недостаткам алгоритмов численного статистического моделирования относятся:

• большое количество вычислений, что в свою очередь связана с относительно медленной сходимостью метода (порядка ${\displaystyle {\frac {1}{\surd n}}}$);
• затратным получение каждого выборочного значения ${\displaystyle \zeta _{i}}$ (во всяком случае для прикладных задач с повышенной точностью среднее время расчётов может быть значительным).

Важным преимуществом метода Монте-Карло является относительная простота подсчёта затрат. Вычислительные затраты метода Монте-Карло близки к времени вычисления суммы 𝑆𝑛 и приблизительно равны величине

${\displaystyle s=t\times n}$,

где ${\displaystyle t}$ — это среднее время подсчёта одного выборочного значения ${\displaystyle \zeta }$

случайной величины ${\displaystyle \zeta =q(\xi )}$ (слово «среднее» здесь является принципиальным!).

${\displaystyle \delta _{n}\sim \mathrm {H} \times {\frac {\surd D\zeta }{\sqrt {n}}}}$

Данная формула определяет поведение погрешности ${\displaystyle \delta _{n}}$ , при этомконстанта ${\displaystyle \mathrm {H} }$ невелика. Проведённые нами тестовые вычисления дали значение ${\displaystyle \mathrm {H} \thickapprox 0,80}$… — точно устанавливаются только две первые десятичные цифры мантиссы. Отсюда получается, что при заданном уровне погрешности ${\displaystyle \vartriangle }$ дисперсия ${\displaystyle D\zeta }$ пропорциональна числу выборочных значений ${\displaystyle n}$. Из неравенства

${\displaystyle \mathrm {H} \times {\frac {\surd D\zeta }{\sqrt {n}}}}$ = ${\displaystyle \vartriangle }$ следует соотношение ${\displaystyle {\Bigl (}{\frac {\mathrm {H} }{\vartriangle }}{\Bigr )}^{2}\times D\zeta }$

Это обосновывает возможность использования вместо затрат ${\displaystyle s}$ пропорциональной ей, более практичной и информативной величины

${\displaystyle S=t\times D\zeta }$

Как правило, уменьшение величины ${\displaystyle t}$ связано с оптимизацией моделирования случайного вектора ${\displaystyle \xi }$. Методы уменьшения дисперсии ${\displaystyle D\zeta }$

случайной величины ${\displaystyle \zeta ={\frac {g(\xi )}{f_{\xi }(\xi )}}}$.

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

Различные вариации метода Монте-Карло можно использовать для решения задач оптимизации. Например, алгоритм имитации отжига.

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

Традиционно метод Монте-Карло применялся для определения различных физических параметров систем, находящихся в состоянии термодинамического равновесия. Предположим, что имеется набор ${\displaystyle W(S)}$ возможных состояний физической системы ${\displaystyle S}$. Для определения среднего значения ${\displaystyle {\overline {A}}}$ некоторой величины ${\displaystyle A}$ необходимо рассчитать ${\displaystyle {\overline {A}}=\sum _{S}A(S)P(S)}$, где суммирование производится по всем состояниям ${\displaystyle S}$ из ${\displaystyle W(S)}$, ${\displaystyle P(S)}$ — вероятность состояния ${\displaystyle S}$.

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

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

• Моделирование облучения твёрдых тел ионами в приближении бинарных столкновений.
• Прямое Монте-Карло моделирование разреженных газов.
• Большинство кинетических Монте-Карло моделей относятся к числу прямых (в частности, исследование молекулярно-пучковой эпитаксии).

Квантовый метод Монте-Карло широко применяется для исследования сложных молекул и твёрдых тел. Это название объединяет несколько разных методов. Первый из них это вариационный метод Монте-Карло, который по сути является численным интегрированием многомерных интегралов, возникающих при решении уравнения Шрёдингера. Для решения задачи, в которой участвует 1000 электронов, необходимо взятие 3000-мерных интегралов, и при решении таких задач метод Монте-Карло имеет огромное преимущество в производительности по сравнению с другими численными методами интегрирования. Другая разновидность метода Монте-Карло — это диффузионный метод Монте-Карло.

• Формула Фейнмана — Каца
• Генераторы псевдослучайных чисел
• Лас-Вегас (алгоритм)
• Семплирование
• AQUA@home
• QMC@Home
• QuantumFire
• Задача Бюффона о бросании иглы
• Метод энтропического моделирования
• Алгоритм Ванга-Ландау
• Использование метода Монте-Карло для поиска в дереве при игре в го.

• Соболь И. М. Метод Монте-Карло. — М.: Наука, 1968. — 64 с. — (Популярные лекции по математике). — 79 000 экз.
• Статья «Моделируя жизнь», автор Андрей Тепляков
• Metropolis, N., Ulam, S. The Monte Carlo Method, — Journal of the American Statistical Association 1949 44 № 247 335—341.
• Alex F Bielajew. Fundamentals of the Monte Carlo method for neutral and charged particle transport. 2001
• 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.
• Статья «Metropolis, Monte Carlo and the MANIAC»
• Fishman, George S. Monte Carlo : concepts, algorithms, and applications. — Springer, 1996. — ISBN 0-387-94527-X.

В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (22 мая 2011)