Вычисление π: моделирование методом Монте-Карло

Data Science

Каждый год 14 марта любители математики отмечают День числа пи! Есть много способов вычислить это легендарное число π, которое примерно равно 3,14159…

Обсудим все эти методы и рассмотрим три способа вычисления π с использованием моделирования методом Монте-Карло!

Что такое пи?

Пи  —  это число, которое выражает отношение длины окружности к её диаметру, приблизительно равное 3,14159…

Нарисуем единичную окружность (т.е. окружность с радиусом 1).

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020Единичная окружность с площадью A(1) = π и периметром U(1) = 2π.

Как известно, площадь круга (окружности) равна:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

А периметр:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Для единичной окружности, где r = 1, площадь равна π, а периметр равен 2π. То есть π — это есть одновременно и площадь единичной окружности, и её полупериметр.

Существует великое множество способов вычисления числа π. Помимо детерминистских методов, то есть методов без использования элемента случайности, есть ещё вероятностные методы. Последние объединяются под одним общим названием «моделирование методом Монте-Карло». Прежде чем уходить с головой в математику, разберёмся с тем, что представляет собой моделирование методом Монте-Карло.

Что такое моделирование методом Монте-Карло?

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

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

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

Мне больше нравится третья причина, так что давайте скорее начнём вычислять наше любимое число π! У меня для вас три способа вычисления пи: простой, сложный и неожиданный.

Просто: единичный квадрат и единичная окружность

Рисуем единичный квадрат  —  такой же, как на рисунке ниже  —  и наносим, равномерно распределяя по всему квадрату, n точек. Пусть внутри круга с радиусом 1 оказалось m точек этого квадрата. Напомним, что квадрант  —  это четверть окружности.

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Дробь m/n определяет отношение площадей квадранта и квадрата, равное 1/4 π.

Давайте разберёмся, откуда взялись такие цифры.

Площадь квадрата, в котором оказался наш квадрант с точками, определяется так:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Площадь квадранта определяется так:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Используя соотношение этих площадей, находим π:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Теперь это отношение площадей умножаем на четыре и получаем π. Например, если из 100 точек 76 оказались внутри четверти окружности, то π будет приблизительно равно:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Что ж, неплохо. Теперь нанесём 1 000 точек, 780 из которых внутри четверти окружности, тогда π будет равно:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

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

Этот способ отлично подходит для общего понимания моделирования методом Монте-Карло. Его без труда могут освоить даже младшие школьники. Обратимся теперь к менее очевидному и математически более сложному способу.

2. Средние значения функций

Этот способ очень часто используют при вычислении интегралов, когда вычислительные затраты, связанные с получением точных результатов, слишком велики. Среднее значение непрерывной функции f(x) определяется следующим образом:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Мы можем использовать его для вычисления π, потому что для этой функции

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

интеграл

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

равен π/4. Следовательно, и вот этот интеграл

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

тоже равен π/4. И среднее значение этой функции на интервале [0,1] тоже равно π/4. Вычислим это математически. Первообразная функции f(x) определяется так:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Перепроверять дважды очень муторно, вы можете поверить мне на слово. Поэтому я пропущу этот момент. Теперь мы можем вычислить неопределённый интеграл, то есть среднее приведённой выше функции:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Вычислить π мы можем, протестировав случайные значения xᵢ, i=1,…n между 0 и 1, посчитав для них f(xᵢ) и взяв среднее. Умножив на четыре, получим приблизительное значение π.

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Этот способ вычисления π тоже довольно прост, хотя математическое объяснение чуть более сложное, чем для первого метода.

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

3. Неожиданный способ: бросание игл

Неожиданный и странный на первый взгляд, но очень красивый способ вычисления π: бросаем иголки. С помощью таких элегантных упрощений математика становится понятнее!

Нарисуйте на листке бумаги параллельные прямые на расстоянии примерно 4 сантиметра друг от друга. Теперь возьмите n иголок или спичек. Бросьте их на бумагу и сосчитайте количество m, оказавшихся на прямых.

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 202011 иголок (или спичек) бросаются на лист бумаги с начерченными на нём параллельными линиями. Из этих 11 иголок 7 пересекают линии (выделены бирюзовым цветом).

Соотношение m/n будет приблизительно равно 2/π, то есть:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Отсюда выводится π:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

В этом примере у нас 11 иголок, 7 из которых лежат на прямых. Здесь π вычисляется так: 2 ⋅ 11/7 ≈ 3,1428 (очень неплохо!). Не ожидали такой точности? Я и сам, признаться, не сразу понял, как мне повезло! Попробуем разобраться, почему так получилось.

Пусть точка x находится на середине иголки. Будет иголка пересекать линию или нет, зависит только от положения иголки.

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Иголка может находиться где-то между 0 и 180°, то есть π радианами. Она будет пересекать линию, если будет находиться внутри части круга, ограниченного углом 2⋅ α(x) от середины иголки.

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Для радиуса r = 1 иголка длиной 1 пересечёт линию с вероятностью P, которая зависит от угла α(x). Полукруг имеет радиан π. Иголка пересекает линию, если мы в розоватом секторе. Розоватый сектор принимает дробь 2α(x)/π розового и бирюзового секторов вместе, и здесь вероятность пересечения линии будет определяться так:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Потому что для

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

интеграл высчитывается так:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Проще всего сделать проверку, посчитав производную:

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020

Я эту часть снова оставлю вам: вы сами прекрасно справитесь.

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

Вычислять пи этим методом вы можете лёжа на пляже: качество вычислений от этого не пострадает. Разве это не красиво?

Заключение

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

Вычисление π: моделирование методом Монте-Карло — IT-МИР. ПОМОЩЬ В IT-МИРЕ 2020Photo by sheri silver on Unsplash. Мой второй любимый пи(рог).

А какой ваш любимый способ вычисления π?

Специально для сайта ITWORLD.UZ. Новость взята с сайта NOP::Nuances of programming