XVI Международная студенческая научная конференция Студенческий научный форум - 2024

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

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

Основная идея метода Монте-Карло заключается в многократном повторении случайного испытания, т.е. характерной особенностью этого метода является использование случайных чисел. Предположим, нам нужно найти значение x' некоторой исследуемой величины. Для этого мы находим N возможных значений X_i случайной величины X и подсчитываем их среднее арифметическое значение. Согласно закону больших чисел при N → ∞ среднее арифметическое этих величин сходится к математическому ожиданию X, если оно существует, поэтому x ≈ x' [1]. Таким образом, метод Монте-Карло является одним из способов приближенного вычисления значений интегралов с погрешностью, которая оценивается не гарантированно, а с некоторой степенью достоверности, которая растет с количеством испытаний. Рассмотрим этот метод на примере задачи из учебника Н.С. Бахвалова [2, с.232]:

Пусть требуется вычислить приближенное значение интеграла

Для упрощения выкладок предполагают, что μ(G) — мера области G равна 1. Далее через M(s) обозначают математическое ожидание случайной величины s, а через D(s) — ее дисперсию. Случайные величины s_j = f(P_j) попарно независимы и одинаково распределены, причем

и

где

Вследствие указанных свойств величин s_j имеем

С вероятностью 1 − η выполняется неравенство (неравенство Чебышева)

(1)

Полагая η = 0,01, получаем: с вероятностью 99% выполняется неравенство

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

Основными преимуществами метода Монте-Карло называют гибкость и универсальность: он применим к широкому спектру задач и классов функций. Также к плюсам относят независимость числа вычислений значений подынтегральной функции для обеспечения заданной точности от кратности интеграла [1].

К недостаткам метода Монте-Карло обычно относят вычислительную сложность и меньшую точность в сравнении с другими методами решения схожих задач, что отражено в статье «Сравнение эффективности численных методов вычисления тройных интегралов» [1]: согласно проведенным авторами расчетам, в схожих условиях метод Монте-Карло уступил методу ячеек как в скорости вычислений, так и в точности.

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

с точностью 0,01 каждым из этих методов, а также подсчитывающая временные затраты на каждое решение. В программе были определены начальное число точек метода Монте-Карло, а также начальное число подынтервалов метода Симпсона. Если вычисленный интеграл отличался от найденного аналитически значения 3,066(6) больше заданной точности, то число случайных точек или подынтервалов удваивается и интеграл вычисляется повторно до получения необходимой точности. Ниже приведены: фрагмент кода (рис.1, рис.2), пример выходных данных программы (рис. 3), а также таблица, в которую внесены данные за 10 запусков программы (таблица 1).

Рис. 1. Реализация методов Монте-Карло и Симпсона в программе

Рис. 2. Цикл с удвоением испытаний на примере метода Монте-Карло

Рис. 3. Пример выходных данных

Таблица 1

Результаты работы программы

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

Впрочем, метод Монте-Карло можно усовершенствовать, повысив его практическую эффективность. Вот приемы для ускорения сходимости, которые приводит Бахвалов [2, с. 239]:

1. Представить функцию f(P) в виде

где функция F(P) интегрируется явно и содержит в себе все резко меняющиеся компоненты f(P), а g(P) — плавно меняющаяся функция с небольшой дисперсией D(g). Также интегрируемую область могут разбивать на подобласти.

2. Подходящий подбор плотности распределения узлов p(P) также приводит к уменьшению дисперсии.

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

Скорость вычислений также может быть увеличена, например, с помощью использования адаптивного выбора шага [3], а также при помощи параллельных вычислений. В этом случае вычисления распределяются по нескольким процессорам или ядрам, что может существенно сократить время вычислений. Кроме того, можно комбинировать метод Монте-Карло с другими методами (например, метод Монте-Карло с цепями Маркова [4]).

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

Список литературы:

1. Корешков Д.С., Балабан Е.И. Сравнение эффективности численных методов вычисления тройных интегралов – 2022.

2. Н. С. Бахвалов, Н. П. Жидков, Г. М. Кобельков. Численные методы – 2015.

3. Алгоритм адаптивного размера шага для повышения эффективности расчета дозы протонного макроса методом Монте-Карло [Электронный ресурс] – режим доступа https://pubmed.ncbi.nlm.nih.gov/31500647/ (дата обращения 16.01.24).

4. Интуитивное использование методов Монте-Карло с цепями Маркова [Электронный ресурс] – режим доступа https://habr.com/ru/companies/netologyru/articles/460497/ (дата обращения 16.01.24).