ММК_Io66hWx

Ме́тод Мо́нте-Ка́рло (методы Монте-Карло, ММК) — общее название группы численных методов, основанных на получении большого числа реализаций стохастического (случайного) процесса, который формируется таким образом, чтобы его вероятностные характеристики совпадали с аналогичными величинами решаемой задачи.
Метод Монте Карло используется для решения различных задач, где результат зависит от случайных процессов. В частности, метод широко используется в экономике, инвестиционных прогнозах и инвестиционном анализе, финансовом планировании. Моделирование по методу Монте Карло позволяет вычислить множество значений. Используя эти значения, определяется искомый результат путем вычисления среднего арифметического или диапазон, в котором может находиться нужный результат.
Откуда метод получил свое название? В Европе есть маленькое княжество Монако, где одна из территорий названа Монте-Карло. Это такой европейский Лос-Анджелес, где можно окунуться в роскошь и азартные развлечения. От знаменитого казино метод Монте-Карло получил свое имя.
Впервые о методе заговорили в конце 40-х годов прошлого столетия, когда ВВС США начало разработку водородной бомбы. Тогда, с появлением первых ЭВМ, было предложено использовать теорию вероятностей для решения прикладных задач.
Далее, в 1970-х годах, метод получил применение в нейтронной физике для задач, не поддающихся решению традиционными математическими методами. Впоследствии моделирование по методу Монте-Карло распространилось на другие области физики, а также на экономику и вычислительную математику.

Схема метода
Имитационное моделирование по методу Монте-Карло представляет собой определение математического ожидания (среднего значения случайной величины) путем проведения определенного количества симуляций (испытаний).
Предположим, требуется найти математическое ожидание α для случайной величины ​X​:
​M(X)=α.​
Классическая формула расчета математического ожидания выглядит так:
x1…n​ – значение величины от 1 до n;
​p1…n​ – вероятность от 1 до n.
Моделирование методом Монте-Карло выполняется следующим образом: проводится n симуляций (испытаний). В результате получится какое-то количество значений X. Далее определяется их среднее арифметическое, которое и будет приблизительным значением α.

Зачем нужен ММК и где он применяется
Чтобы не углубляться в математические дебри, сформулируем кратко суть метода.
Метод Монте-Карло относится к методам моделирования различных явлений, событий, параметров или процессов, как благоприятных, так и неблагоприятных, с целью определения вероятности их наступления. Для этого генерируется определенное количество случайных величин, отвечающих установленным критериям, а затем на их основе вычисляют приблизительное значение искомой величины.
ММК применяется в следующих областях:
1. Физика, химия, биология – для моделирования различных явлений.
2. Экономика и финансы – для оценки и прогнозирования инвестиций, расчета доходности финансовых инструментов, сроков окупаемости и др. Метод Монте-Карло широко применяется для оценки рисков;
3. Игровая индустрия – для моделирования искусственного интеллекта и др.
4. Технология и др. инженерные науки используют метод Монте-Карло в прогнозировании НТП.
5. Социология – для изучения общественного мнения (люди, принимающие участие в опросах, отбираются в случайном порядке).
По сути, методу можно найти применение во многих сферах, где необходимы расчеты и прогнозирование.

Входные данные
Данные для получения искомой величины определяются путем стохастической (случайной) выборки. Чтобы было более понятно, приведем простейший пример из компьютерных игр.
Предположим, у нас есть компьютерная игра, в которую мы играли много-много раз. При этом ведется статистика: сыграно 100 игр, из них 30 побед, 70 поражений. Это и будет нашими входными данными. А решение будет таким: вероятность победы – 30%, проигрыша – 70%.
Выходные данные
Выходными или итоговыми данными имитационного моделирования по методу Монте-Карло могут быть числовые значения или проценты.
Сколько имитационных испытаний необходимо выполнить
Количество симуляций зависит от цели исследования. Как уже упоминалось, моделирование повторяется сотни, тысячи, иногда десятки тысяч раз – чем больше испытаний, тем более достоверный результат будет получен на выходе. При наличии программы не возникает проблем в многократном повторении операции.

Достоинствами ММК являются:
1. Простота и универсальность – метод может применяться практически к любому типу данных.
2. ММК позволяет учитывать не только определенный тип данных в отдельности, но и взаимосвязи между различными типами данных.
3. Метод можно применять там, где не срабатывают привычные методы исследования, основанные на математических расчетах.
Недостатки:
1. Иногда требуется проведение большого количества испытаний, что может занять много времени.
2. Для выполнения симуляций по методу Монте-Карло в программе необходимо привлекать квалифицированных специалистов.
3. Метод не может дать достоверную оценку для событий, характеризующихся очень низкой или очень высокой вероятностью наступления.

Упрощенно схему алгоритма можно представить в виде:
Генератор
случайных чисел
Вычислитель
Анализатор
Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте-Карло и имитационного моделирования до криптографии. При этом от качества используемых ГПСЧ напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм Роберта Р. Кавью из ORNL (англ.): «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».
Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается — начинает повторять одну и ту же последовательность чисел.
Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков.
В частности, алгоритм RANDU, десятилетиями использовавшийся на мейнфреймах, оказался очень плохим, что вызвало сомнения в достоверности результатов многих исследований, использовавших этот алгоритм.

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

Постановка задачи (этап 1)
Задача. Методом Монте-Карло вычислить значение числа π.
Выбор плана создания модели (этап 2)
Геометрический метод Монте-Карло позволяет вычислять площади плоских фигур. Если этим методом найти площадь круга S заданного радиуса r, то, пользуясь известной формулой S = πr2, можно найти значение
π = S/r2.
Изберем следующий план создания модели:
3а) создание документальной математической модели;
3б) создание документальной расчетной модели;
3в) создание компьютерной расчетной модели.
Пример

Создание документальной математической модели (этап 3а)
Так как значение радиуса круга ограничений не имеет, возьмем круг единичного радиуса (r = 1). Тогда минимальный базовый прямоугольник можно построить в форме квадрата со стороной 2.
Площадь базового квадрата S0 = 4.
Пусть S — искомая площадь круга.
Методом Монте-Карло необходимо имитировать процесс посыпания базового квадрата точками-песчинками, подсчитывая общее число n точек и число k точек, попавших в круг.
Для создания компьютерной расчетной модели можно использовать электронные таблицы и язык программирования. Но в электронных таблицах общее число n точек будет определяться числом строк в расчетной таблице, а в программе на языке Pascal — только числом повторений цикла. Поэтому выбираем систему PascalABC.NET.
Построим базовый квадрат и круг в прямоугольной системе координат следующим образом:

Создание документальной расчетной модели (этап 3б)
В программе на языке Pascal следует организовать цикл for с числом повторений n и в нем генерировать случайные координаты x и y точек на базовом квадрате.
Для подсчета числа точек, попавших на единичный круг, в цикле следует использовать оператор if с условием попадания точки в круг (x – 1)2 + (y – 1)2 ≤ 1 и при выполнении этого условия оператором k:=k+1 организовать накопление значений переменной k, как счетчика. После цикла необходимо организовать вывод результата на экран.
Для генерации координат точек воспользуемся функцией random(). Функция генерирует случайные действительные числа от 0 до 1, а координаты точек-песчинок на базовом квадрате должны принимать значения от 0 до 2. Тогда координаты точек нужно вычислять, используя выражение 2*random().

Для сравнения выведем на экран рассчитанное значение числа и фактическое значение, которое хра­нится в системе PascalABC.NET как значение переменной с именем pi.
Создание компьютерной расчетной модели (этап 3в)
В системе PascalABC.NET создадим программу montekarlo. В ней объявим переменные n и k типа integer для хранения числа точек-песчинок на базовом квадрате и на круге соответственно, а также переменные s, x и y типа real для хранения значений площади круга и координат точек-песчинок соответственно.
В основном разделе программы, задаем начальные значения и организуем цикл.
Задаем начальные значения:
n := 1000;
k:= 0;
В цикле for с начальным значением переменной цикла 1 и конечным значением n присваиваем случайные значения координатам очередной точки:
x := 2 * random();
y := 2 * random();
С помощью условного оператора if организуем подсчет числа k точек, которые попали в круг:
if sqr(x-1)+sqr(y-1)<=1 then k:=k+1;

Осталось подсчитать площадь круга по основной формуле метода.
Далее подсчитываем результат, выводим на экран результат и точное значение числа :
s := 4 * k / n;
writeln('Результат pi = ',s);
writeln('Точно pi = ',pi);
Проверка адекватности модели (этап 4)
Адекватность модели проверяется сравнением полученного значения числа с точным. При числе повторений 1000 рассчитанное значение должно находиться в пределах от 3,0 до 3,3.
Каждый новый запуск программы меняет рассчитанное значение, так как каждый раз используется новый набор из 1000 точек-песчинок с другими случайными координатами.

Получение решения задачи с помощью модели (этап 5)
В результате нескольких запусков программы можно заметить, что для числа точно определяется только целая часть значения — число 3.
Уточнить результат позволяет увеличение числа n точек-песчинок. Теоретически, если увеличить число n точек-песчинок в 100 раз, точность результата увеличится на 1 десятичный разряд вправо/
Увеличим число n в 100 раз, дописывая в программе нули в его значении справа. В результате нескольких запусков программы можно убедиться, что в значении числа p определяются уже два разряда — 3,1.
Увеличим число n еще в 100 раз. Точность вычислений увеличивается до трех разрядов — 3,14. Но при этом растет и время исполнения программы.