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

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

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

История метода

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

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

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

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

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

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

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

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

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

Общая схема метода.

Сущность метода Монте-Карло состоит в следующем: требуется найти значение а некоторой изучаемой величины. Для этого выбирают такую случайную величину Х, математическое ожидание которой равно а: М(Х)=а.

Практически же поступают так: производят n испытаний, в результате которых получают n возможных значений Х; вычисляют их среднее арифметическое

 и принимают x в качестве оценки (приближённого значения) a* искомого числа a:

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

Вычисления с помощью метода.

С помощью метода Монте-Карло можно вычислить число Пи.

Вписав круг в квадрат (диаметр круга равен стороне квадрата), можно выразить отношение площади круга к площади квадрата следующим образом:

Если мы можем рассчитать это соотношение, то мы можем получить значение Pi.

Заполните квадрат точками со случайными координатами. Мы рассчитываем соотношение между количеством точек на круге и общим количеством точек. Умножьте результат на 4, чтобы получить значение Pi.

Чем больше количество точек, тем ближе полученное значение будет ближе к истинному значению числа Пи.

Можно привести и другой пример. Мы можем смоделировать транспортный поток, используя модель Нагеля-Шрекенберга. В рамках этой модели трасса состоит из ячеек, устанавливаются максимально допустимая скорость и определенное количество транспортных средств (ОВД). На каждом этапе статус всех бирж обновляется в соответствии со следующими правилами:

• Скорость данной v УАТС увеличивается на единицу, если она меньше максимально допустимой скорости.
• Найдите расстояние d между данной УАТС и передней АТС. Если скорость этого обмена больше или равна расстоянию d, она уменьшается до d-1.
• Используя метод Монте-Карло, мы добавляем элемент случайности. С вероятностью p скорость данной ОВД уменьшается на единицу.
• Это ATS продвигает v единиц.

Эта модель довольно простая, но очень эффективная. Эта модель не учитывает несчастные случаи или плохое вождение. Его целью является моделирование спонтанных изменений в характере транспортных потоков. Существуют более сложные модели, но многие из них основаны на модели Нагеля-Шрекенберга.

Проблема в рамках метода

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

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

Метод Монте-Карло является очень интересным предметом для изучения.