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

У этого термина существуют и другие значения, см. Монте-Карло (значения).

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

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

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

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

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

Сначала Энрико Ферми в 1930-х годах в Италии, а затем Джон фон Нейман и Станислав Улам в 1940-х в Лос-Аламосе предположили, что можно использовать связь между стохастическими процессами и дифференциальными уравнениями «в обратную сторону». Они предложили использовать стохастический подход для аппроксимации многомерных интегралов в уравнениях переноса, возникших в связи с задачей о движении нейтрона в изотропной среде.

Идея была развита Уламом, который, раскладывая пасьянсы во время выздоровления после болезни, задался вопросом, какова вероятность того, что пасьянс сложится. Вместо того, чтобы использовать обычные для подобных задач соображения комбинаторики, Улам предположил, что можно просто поставить эксперимент большое число раз и, подсчитав число удачных исходов, оценить вероятность. Но из-за необходимости проведения большого количества однотипных экспериментальных действий метод не получил большого распространения.

С появлением первого электронного компьютера ENIAC, который мог с большой скоростью генерировать псевдослучайные числа и использовать их в математических моделях, возобновился интерес к стохастическим методам. Станислав Улам обсудил свои идеи с Джоном фон Нейманом, который в конечном итоге использовал ENIAC для предложенного Уламом метода статистического отбора при решении различных проблем перемещения нейтронов[4]. Из-за необходимости в конце 1946 года выключить ENIAC на значительное время, для продолжения исследований перемещения нейтронов Энрико Ферми даже разработал специализированный аналоговый компьютер, которому дали имя FERMIAC (по аналогии с ENIAC, но с указанием на авторство Ферми), где также был на механическом уровне реализован метод Монте-Карло.

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

Годом рождения термина «метод Монте-Карло» считается 1949 год, когда в свет вышла статья Метрополиса и Улама «Метод Монте-Карло». Название метода происходит от названия коммуны в княжестве Монако, широко известного своими многочисленными казино, поскольку именно рулетка является одним из самых широко известных генераторов случайных чисел. Станислав Улам пишет в автобиографии «Приключения математика», что название было предложено Николасом Метрополисом в честь его дяди, который был азартным игроком.

В 1950-х годах метод использовался для расчётов при разработке водородной бомбы. Основные заслуги в развитии метода в это время принадлежат сотрудникам лабораторий ВВС США и корпорации RAND. Одними из первых Метод Монте-Карло для расчёта ливней частиц применили советские физики А. А. Варфоломеев и И. А. Светлолобов[5].

В 1970-х годах в новой области математики — теории вычислительной сложности было показано, что существует класс задач, сложность (количество вычислений, необходимых для получения точного ответа) которых растёт с размерностью задачи экспоненциально. Иногда можно, пожертвовав точностью, найти алгоритм, сложность которого растёт медленнее, но есть большое количество задач, для которого этого нельзя сделать (например, задача определения объёма выпуклого тела в n-мерном евклидовом пространстве) и метод Монте-Карло является единственной возможностью для получения достаточно точного ответа за приемлемое время.

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

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

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

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

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

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

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

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

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