Метод Монте-Карло в вычислениях¶

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

¶Общая идея

Метод строится на следующем принципе: искомая величина представляется как математическое ожидание некоторой случайной функции, после чего это ожидание оценивается по выборке. Например, для оценки площади фигуры в неё «бросают» случайные точки в охватывающем прямоугольнике и вычисляют долю попавших внутрь. Точность оценки растёт с числом испытаний пропорционально величине, обратной квадратному корню из их количества. Это означает медленную, но устойчивую сходимость, не зависящую от размерности задачи, — ключевое преимущество перед сеточными методами в многомерных пространствах.

¶История

Возникновение метода связано с работами по ядерной физике середины 1940-х годов. В Лос-Аламосской национальной лаборатории (США) Станислав Улам и Джон фон Нейман предложили использовать случайную выборку для расчётов переноса нейтронов, где аналитические решения были невозможны. Название «Монте-Карло» дано по городу Монако, известному казино, — как отсылка к случайности.

В СССР метод развивался в 1950-х годах. Значительный вклад внесли математики, работавшие над задачами вычислительной математики и физики: в Институте прикладной математики АН СССР под руководством Мстислава Келдыша разрабатывались методы решения задач переноса излучения и нейтронной физики. Среди советских исследователей, занимавшихся теорией и применением метода, — Гелий Марчук, работавший над численными методами атмосферной физики и ядерных расчётов. В дальнейшем метод распространился на статистическую физику, теорию массового обслуживания, экономику и другие области.

¶Разновидности

Существует несколько основных подходов:

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

¶Генерация случайных чисел

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

¶Применение

Метод используется в широком круге областей:

В России метод применяется в расчётах ядерных реакторов, в климатических моделях, в финансовом анализе и в задачах машинного обучения.

¶Достоинства и ограничения

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

¶Пример

Классический пример — оценка числа π. В квадрат со стороной 1 вписывают четверть круга радиуса 1. Генерируют N случайных точек с координатами в единичном квадрате и подсчитывают долю попавших внутрь четверти круга. Эта доля приближённо равна π/4, откуда получают оценку π. При увеличении N оценка сходится к истинному значению, хотя и с флуктуациями, убывающими как корень из N.

¶Значение

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

Источники: учебные пособия по вычислительной математике и теории вероятностей, работы по истории вычислительных методов, материалы по статистическому моделированию.