Численная оценка интеграла методом Монте-Карло. Антонов Илья. 6 курс
Цель работы
При применении технологии параллельных вычислениях в разных задачах зачастую наибольший интерес представляет характер убывания времени расчета при увеличении числа процессов на практике. Зная эту характеристику, например, для двух разных методов решения задачи, можно определить, какой из них будет предпочтительней при заданных условиях.
Основная цель данной работы — исследовать на распараллеливание простейший метод Монте-Карло численной оценки интеграла и сравнить его с классическим методом прямоугольников; по характеру убывания времени расчета и относительной погрешности определить, почему метод Монте-Карло для данной задачи используется лишь в качестве оценки; определить, как число процессов и выбор генератора случайных чисел сказывается на относительной погрешности при оценке интеграла методом Монте-Карло.
Описание исследования
Оценка интеграла методом Монте-Карло алгоритмически довольно проста. Подинтегральная функция геометрически заключается в простую фигуру, например, в прямоугольник (с заранее определенными минимальными и максимальными значениями функции в качестве высоты и пределами интегрирования в качестве ширины), по которому равномерно последовательно случайным образом разбрасываются точки. Испытание считается успешным, если точка попала под интегрируемую функцию. Значение интеграла оценивается как отношение числа успешных испытаний к общему числу испытаний, умноженному на площадь фигуры, в которую заключена подинтегральная функция. Кроме того, точность оценки будет зависеть от равномерности распределения случайных точек по фигуре, то есть, в конечном счете, от генератора случайных чисел и генерируемого им равномерно-распределенных псевдослучайных чисел (РРПСЧ). Предлагается сравнить стандартное РРПСЧ для C++ rand() и РРСПЧ из вихря Мерсенна (std::mt19937) для данного метода.
Такая задача довольно просто может быть распараллелена использованием своего генератора случайных чисел для каждого из процессов.
Для расчета был выбран следующий интеграл, заключенный в прямоугольник [(0,0);(10,1)]:
Решение задачи
Для сравнения методов было разработано консольное приложение на языке C++ с использованием технологии MPI для распараллеливания вычислений, которое позволяло рассчитать значение интеграла, определить время расчета и оценку относительной погрешности для:
- численного интегрирования функции методом прямоугольников;
- численной оценки интеграла методом Монте-Карло с использованием srand() в качестве РРПСЧ
- численной оценки интеграла методом Монте-Карло с использованием std::mt19937 generator() в качестве РРПСЧ
Результаты
Метод прямоугольников:
Метод Монте-Карло, srand():
Метод Монте-Карло, вихрь Мерсенна:
Выводы
Как видно по графикам, метод прямоугольников использовать явно предпочтительней, так как он сходится по времени при увеличении числа процессов так же, как и методы Монте-Карло, при этом точность вычисления остается выше и увеличивается стабильно. Для методов Монте-Карло такого эффекта не наблюдается, поэтому их разумно использовать только для быстрой оценки значения интеграла в особых случаях. Также интересно, что при замене srand() на вихрь Мерсенна значительно увеличивается время расчета, сходимость при этом по времени остается неизменной, а значения погрешности на графиках при той же сходимости имеют меньший разброс. Причиной тому, возможно, является сам генератор случайных чисел.
