Метод Монте-Карло
Одним из инструментов в области имитационного моделирования является способ решения задач с использованием эксперимента со случайными числами, который носит название метода Монте-Карло. Область применения этого метода и его алгоритм описаны в данной статье.
Что такое метод Монте-Карло
Метод Монте-Карло относится к группе численных методов решения задач, в условиях которых присутствует элемент неопределенности. Он позволяет получить приближенные результаты на множестве входных значений, которые подбираются произвольно путем генерации случайных чисел.
Название этого метода выбрано в честь города Монте-Карло, известного своими казино. Рулетка в казино – это своего рода генератор случайных чисел. Этот метод впервые был описан в 1949 году в совместной работе математиков Николаса Метрополиса и Станислава Улама. Известно, что название придумал Н. Метрополис в честь одного из своих родственников, который был азартным игроком и частым посетителем казино.
Использование метода Монте Карло для вычисления площади фигуры
Простым примером иллюстрации применения данного метода является способ определения площади фигуры сложной формы, когда контуры объекта не образуют геометрической формы, для которой существует готовая формула для расчета.
Чтобы вычислить площадь S такой фигуры, ее вписывают в квадрат стороной a. Затем, случайным образом выбирают точки внутри квадрата. Причем точки могут попадать как внутрь исследуемой фигуры сложной формы, так и вне ее.
Чем большую площадь занимает фигура внутри квадрата, тем чаще в нее будут попадать точки. Точки, попавшие внутрь фигуры, обозначают буквой m, а все выбранные точки внутри квадрата – буквой n.
Здесь проявляется закономерность: чем больше точек в эксперименте задействовано, тем с большей вероятностью можно утверждать, что процент точек, содержащихся в исследуемой фигуре стремится к отношению площади фигуры к площади квадрата. Математически это можно записать следующим образом: s=a*a*(m/n).
Таким образом, получен некоторый способ определения площади фигуры произвольной формы с использованием метода статистических испытаний. Модели для вычисления площади различных фигур сложной формы, сформированные этим способом, будут отличаться математическими описаниями фигур.
В теории вероятностей и математической статистике действует закон больших чисел, согласно которому результат эксперимента окажется свободным от случайных воздействий только в случае большого количества случайных факторов, то есть будет прослеживаться устойчивая закономерность. Проще говоря, чем больше число испытаний, тем точнее будет результат.
Алгоритм вычисления площади фигуры с помощью метода Монте Карло
Определим площадь фигуры, ограниченной уравнениями y = x^2, y = 0 и x = 1.
Составим модель: площадь искомой фигуры впишется в квадрат. Если значения координат x и y принадлежит диапазону [0;1], то точка принадлежит квадрату. Если выполняется система неравенств 0 < x < 1 и 0 < y – x^2, то точка принадлежит фигуре.
Так как длина стороны квадрата равна 1, то после подсчета количества точек, площадь фигуры определится по формуле: s=m/n
Алгоритм решения задачи будет выглядеть так:
- Задать n (определиться, сколько испытаний будет в задаче)
- m=0 (начальное значение точек, попавших в область фигуры. Переменная m будет выполнять функцию счетчика в алгоритме)
- Задать значение x путем генерации случайных чисел
- Задать значение y путем генерации случайных чисел
- Организовать повтор цикла (перебирать целочисленные значения от 0 до n с шагом 1). Тело цикла:
- проверить условие 0 < x < 1, если оно выполняется перейти к проверке второго условия, иначе увеличить счетчик цикла на 1
- проверить условие 0 < y – x^2, если условие верно, то организовать команду счетчика точек (m=m+1), иначе увеличить счетчик цикла на 1
- s=m/n
- Вывод результата s
Что мы узнали?
Одним из способов построения моделей является метод статистических испытаний, носящий название Метода Монте Карло. Важным условием применения статистических методов является проведения большого количества испытаний путем генерации случайных входных параметров. С помощью метода Монте Карло можно вычислить площадь фигуры произвольной формы.
