Метод монте карло реферат
Обновлено: 07.07.2024
Метод Монте-Карло можно определить как метод моделирования случайных величин с целью вычисления характеристик их распределений.
Возникновение идеи использования случайных явлений в области приближённых вычислений принято относить к 1878 году, когда появилась работа Холла об определении числа p с помощью случайных бросаний иглы на разграфлённую параллельными линиями бумагу. Существо дела заключается в том, чтобы экспериментально воспроизвести событие, вероятность которого выражается через число p, и приближённо оценить эту вероятность. Отечественные работы по методу Монте-Карло появились в 1955-1956 годах. С того времени накопилась обширная библиография по методу Монте-Карло. Даже беглый просмотр названий работ позволяет сделать вывод о применимости метода Монте-Карло для решения прикладных задач из большого числа областей науки и техники.
Первоначально метод Монте-Карло использовался главным образом для решения задач нейтронной физики, где традиционные численные методы оказались мало пригодными. Далее его влияние распространилось на широкий класс задач статистической физики, очень разных по своему содержанию.
Метод Монте-Карло оказал и продолжает оказывать существенное влияние на развитие методов вычислительной математики (например, развитие методов численного интегрирования) и при решении многих задач успешно сочетается с другими вычислительными методами и дополняет их. Его применение оправдано в первую очередь в тех задачах, которые допускают теоретико-вероятностное описание. Это объясняется как естественностью получения ответа с некоторой заданной вероятностью в задачах с вероятностным содержанием, так и существенным упрощением процедуры решения.
Глава 1. Некоторые сведения теории вероятностей
§1. Математическое ожидание, дисперсия.
Дискретной называют случайную величину, которая принимает отдельные, изолированные возможные значения с определёнными вероятностями. Число возможных значений дискретной случайной величины может быть конечным или бесконечным.
Математическим ожиданием дискретной случайной величины называют сумму произведений всех её возможных значений на их вероятность.
где Х – случайная величина, - значения, вероятности которых соответственно равны .
Математическое ожидание приближённо равно (тем точнее, чем больше число испытаний) среднему арифметическому наблюдаемых значений случайной величины.
Дисперсией (рассеянием) случайной величины называют математическое ожидание квадрата отклонения случайной величины от её математического ожидания: .
Средним квадратичным отклонением случайной величины Х называют квадратный корень из дисперсии: .
§2. Точность оценки, доверительная вероятность. Доверительный интервал.
Точечной называют оценку, которая определяется одним числом.
Интервальной называют оценку, которая определяется двумя числами – концами интервала. Интервальные оценки позволяют установить точность и надёжность оценок.
Пусть, найденная по данным выборки, статистическая характеристика служит оценкой неизвестного параметра . Ясно, что тем точнее определяет параметр , чем меньше абсолютная величина разности . Другими словами, если d>0 и , то , чем меньше d, тем оценка точнее. Положительное число d характеризует точность оценки.
Надёжностью (доверительной вероятностью) оценки по называют вероятность g, с которой осуществляется неравенство .
Доверительным называют интервал , который покрывает неизвестный параметр с заданной надёжностью g.
§3. Нормальное распределение.
Нормальным называют распределение вероятностей непрерывной случайной величины, которое описывается дифференциальной функцией
а - математическое ожидание, s - среднее квадратичное отклонение нормального распределения.
Глава 2. Метод Монте-Карло
§1. Общая схема метода Монте-Карло.
Сущность метода Монте-Карло состоит в следующем: требуется найти значение а некоторой изучаемой величины. Для этого выбирают такую случайную величину Х, математическое ожидание которой равно а: М(Х)=а.
Практически же поступают так: производят n испытаний, в результате которых получают n возможных значений Х; вычисляют их среднее арифметическое и принимают x в качестве оценки (приближённого значения) a* искомого числа a:
Поскольку метод Монте-Карло требует проведения большого числа испытаний, его часто называют методом статистических испытаний. Теория этого метода указывает, как наиболее целесообразно выбрать случайную величину Х, как найти её возможные значения. В частности, разрабатываются способы уменьшения дисперсии используемых случайных величин, в результате чего уменьшается ошибка, допускаемая при замене искомого математического ожидания а его оценкой а*.
§2. Оценка погрешности метода Монте-Карло.
Пусть для получения оценки a* математического ожидания а случайной величины Х было произведено n независимых испытаний (разыграно n возможных значений Х) и по ним была найдена выборочная средняя , которая принята в качестве искомой оценки: . Ясно, что если повторить опыт, то будут получены другие возможные значения Х, следовательно, другая средняя, а значит, и другая оценка a*. Уже отсюда следует, что получить точную оценку математического ожидания невозможно. Естественно возникает вопрос о величине допускаемой ошибки. Ограничимся отысканием лишь верхней границы d допускаемой ошибки с заданной вероятностью (надёжностью) g: .
Случайная величина Х распределена нормально и её среднее квадратичное отклонение d известно.
В этом случае с надёжностью g верхняя граница ошибки
где n число испытаний (разыгранных значений Х); t – значение аргумента функции Лапласа, при котором , s - известное среднее квадратичное отклонение Х.
Случайная величина Х распределена нормально, причём её среднее квадратическое отклонение s неизвестно.
В этом случае с надёжностью g верхняя граница ошибки
Случайная величина Х распределена по закону, отличному от нормального.
Из изложенного следует, что метод Монте-Карло тесно связан с задачами теории вероятностей, математической статистики и вычислительной математики. В связи с задачей моделирования случайных величин (в особенности равномерно распределённых) существенную роль играют также методы теории чисел.
Среди других вычислительных методов, метод Монте-Карло выделяется своей простотой и общностью. Медленная сходимость является существенным недостатком метода, однако, могут быть указаны его модификации, которые обеспечивают высокий порядок сходимости при определённых предположениях. Правда, вычислительная процедура при этом усложняется и приближается по своей сложности к другим процедурам вычислительной математики. Сходимость метода Монте-Карло является сходимостью по вероятности. Это обстоятельство вряд ли следует относить к числу его недостатков, ибо вероятностные методы в достаточной мере оправдывают себя в практических приложениях. Что же касается задач, имеющих вероятностное описание, то сходимостью по вероятности является даже в какой-то мере естественной при их исследовании.
Глава 3. Вычисление интегралов методом Монте-Карло.
§1. Алгоритмы метода Монте-Карло для решения интегральных уравнений второго рода.
Пусть необходимо вычислить линейный функционал , где , причём для интегрального оператора K с ядром выполняется условие, обеспечивающее сходимость ряда Неймана: . Цепь Маркова определяется начальной плотностью и переходной плотностью ; вероятность обрыва цепи в точке равна . N – случайный номер последнего состояния. Далее определяется функционал от траектории цепи, математическое ожидание которого равно . Чаще всего используется так называемая оценка по столкновениям , где , . Если при , и при , то при некотором дополнительном условии . Важность достижения малой дисперсии в знакопостоянном случае показывает следующее утверждение: если и , где , то , а . Моделируя подходящую цепь Маркова на ЭВМ, получают статистическую оценку линейных функционалов от решения интегрального уравнения второго рода. Это даёт возможность и локальной оценки решения на основе представления: , где . Методом Монте-Карло оценка первого собственного значения интегрального оператора осуществляется интерациональным методом на основе соотношения . Все рассмотренные результаты почти автоматически распространяются на системы линейных алгебраических уравнений вида . Решение дифференциальных уравнений осуществляется методом Монте-Карло на базе соответствующих интегральных соотношений.
§2. Способ усреднения подынтегральной функции.
В качестве оценки определённого интеграла принимают
где n – число испытаний; - возможные значения случайной величины X, распределённой равномерно в интервале интегрирования , их разыгрывают по формуле , где - случайное число.
Дисперсия усредняемой функции равна
Функцию f(x) желательно выбирать так, чтобы отношение при различных значениях x изменялось незначительно. В частности, если , то получим оценку .
Задача. Найти оценку интеграла .
Запишем искомый интеграл так:
Таким образом, интеграл I представлен в виде математического ожидания функции . В качестве искомой оценки примем выборочную среднюю (для простоты ограничимся десятью испытаниями):
где - возможные значения X, которые надо разыграть по известной плотности . По правилу (для того, чтобы разыграть возможное значение непрерывной случайной величины X, зная её плотность вероятности f(x), надо выбрать случайное число и решить относительно уравнение
где a – наименьшее конечно возможное значение X), имеем . Отсюда находим явную формулу для разыгрывания возможных значений X:
В таблице 2 приведены результаты 10 испытаний.
Сложив числа последней строки таблицы 2, получим . Искомая оценка равна .
Управление рисками на сегодняшний день является актуальной проблемой. Поэтому особое внимание уделяется методам управления рисками.
Актуальность исследования состоит в изучении методов управления рисками, а в честности метода Монте - Карло.
Итак, предметом данной работы является метод. Объектом написания данной работы - метод Монте - Карло.
При написании данной работы были поставлены ряд задач и целей.
Цель: всесторонне охарактеризовать применение метода Монте - Карло в управлении рисками предприятия.
Исходя из поставленной цели, были выдвинуты ряд задач:
1. Метод Монте - Карло при анализе риска.
2. Метод Монте - Карло в условиях управления рыночными рисками.
Метод Монте - Карло при анализе риска
Широкое распространение особенно при анализе риска получил метод Монте-Карло. Этот метод имитации применим для решения почти всех задач при условии, что альтернативы могут быть выражены количественно. Построение модели начинается с определения функциональных зависимостей в реальной системе, которые в последствии позволяют получить количественное решение, используя теорию вероятности и таблицы случайных чисел.
Модель Монте-Карло не столь формализована и является более гибкой, чем другие имитирующие модели. Причины здесь следующие:
при моделировании по методу Монте-Карло нет необходимости определять, что именно оптимизируется;
нет необходимости упрощать реальность для облегчения решения, поскольку применение ЭВМ позволяет реализовать модели сложных систем;
в программе для ЭВМ можно предусмотреть опережения во времени.
Типичным примером задачи, которая может быть решена на основе модели Монте-Карло, может быть задача на обслуживание. Например, при планировании стратегии развития ресторана быстрого обслуживания необходимо знать, как долго в среднем приходится посетителю ждать обслуживания (среднее значение ожидания). Работа ресторана характеризуется следующими парами. Посетители обслуживаются последовательно на одной кухне. Прибытие клиентов носит случайный характер. Поступление заказов характеризуется следующими данными: интервалы поступления требований до 10 мин составляют 40% случаев, от 10 до 20 мин -- 60%. Продолжительность обслуживания в зависимости от вкусов клиентов-- также величина случайная. В 80 % случаев на обслуживание требуется 10 мин, в остальных -- 30 мин.
В таблице 1 представлены результаты решения задачи на основе имитационной модели Монте-Карло, в которой интервалы между прибытием клиентов и временем обслуживания представлены последовательностью случайных чисел.
Решение задачи обслуживания с применением метода Монте - Карло.
Первая случайная цифра
Интервал до прибытия, мин.
Время начала обслуживания
Вторая случайная цифра
Время до обслуживания мин.
Время окончания обслуживания
Время ожидания, мин
Время простоя, мин
Примечание. Колонка 8 = колонка 5 + колонка 7, колонка 9 = колонка 5 - колонка 4, колонка 10 = колонка 5 - цифра в предшествующем ряду колонки 8.
Для интервалов между прибытиями выберем следующую случайную последовательность: 0, 1,2, 3,4, 5, 6, 7, 8 или 9 - называют случайной цифрой. Если выбраны числа 0, 1, 2 или 3, то продолжительность интервала между поступлением двух требований составляет 10 мин. Если выбраны числа 4,5,6,7,8 или 9, продолжительность интервала равна 20 мин. Аналогичным образом определяется время обслуживания, которое наступает после истечения интервала прибытия. Для этого выбирается второе случайное число.
Если выбраны числа 0, 1,2, 3, 4, 5, 6 или 7, время обслуживания составит 10 мин. Если выбраны числа 8 или 9, обслуживание клиента длится 30 мин.
Из таблицы 3.2 видно, что для 10 испытаний, приведенных в таблице, суммарное время ожидания составляет 60 мин, или в среднем по 6 мин на клиента. Данный пример оставляет без ответа многие вопросы, и среди них вопрос о необходимом количестве испытаний, позволяющем с достаточной точностью определить время ожидания.
Предположим, что мы произвели N независимых опытов, в результате которых получили N случайных цифр. Записав эти цифры (в порядке их появления) в таблицу, получим то, что называется таблицей случайных цифр может иметь следующий вид (цифры разбиты на группы для удобства чтения таблицы):
86515 90795 66155 66434 56558 12332
69186 03393 42502 99224 88955 53758
41686 42163 85181 38967 33181 72664
86522 47171 88059 89342 67248 09082
72587 93000 89688 78416 27589 99528
Случайным числом называется случайная величина
где г 1, г2, … ,гs … - независимые случайные цифры. Иными словами, случайное число -- это случайная величина, равномерно распределенная на промежутке [0, 1). В настоящее время существуют специальные компьютерные программы для построения случайных чисел в любом количестве. Такие программы называют генераторами случайных чисел.
Рассмотрим теперь дискретную случайную величину о, распределение которой имеет вид:
Для моделирования случайной величины о промежуток [0, 1) разделим на участки ? i так, чтобы длина промежутка ? i равнялась Рi, i = 1, 2, . , п. Новая
случайная величина о^определяемая равенством:
о^ = Х I, если д Є ? I , I - 1, 2, … , п,
где д - случайное число, имеет такое же распределение, что и случайная величина о.
Предыдущее равенство позволяет каждому случайному числу приписать определенное значение случайной величине о. Такой процесс приписывания значений случайной величине о часто называют разыгрыванием этой случайной величины.
Предположим, что даны две случайные величины о и з совместное распределение которых имеет вид:
Для моделирования пары случайных величин о и з промежуток [0, 1) разделим на части ? ij так, чтобы длина полуинтервала ? ij равнялась Р ij, I =1, 2. m; j = 1, 2, . n.
В этом случае пара случайных величин о ^,з ^, где
о ^ = Х i, з ^ = y j, при д Є ? ij.
имеет такое же распределение, что и пара о и з.
Предыдущее равенство позволяет каждому случайному числу приписать определенную пару значений случайных величин о и з. Такой процесс приписывания значений паре случайных величин о и з азывают разыгрыванием этой пары.
Если случайные величины о и з независимы, то для разыгрывания пары о и з достаточно разыграть каждую случайную величину в отдельности. Для разыгрывания непрерывной случайной величины можно вначале найти дискретную случайную величину, близкую к данной случайной величине, а затем разыграть эту дискретную случайную величину.
Метод Монте-Карло позволяет численно находить различные вероятностные характеристики случайной величины з, зависящей от большого числа других случайных величин о1, о2, …, о n. Этот метод сводится к следующему: разыгрывается последовательность случайных величин о1, о2, …, о n для каждого розыгрыша определяется соответствующее значение случайной величины з, а по найденным значениям строится эмпирическое распределение вероятностей этой случайной величины.
Рассмотрим пример. Инвестор владеет портфелем, состоящим из одной казначейской облигации и двух корпоративных облигаций одного и того же кредитного рейтинга. Основные параметры портфеля указаны в таблице:
Срок до погашения, лет
Номинал, млн. долл.
Доходность к погашению, %
Инвестора интересует реализуемая доходность портфеля облигаций за 6 месяцев. По его мнению, реализуемая доходность портфеля будет определяться следующими двумя факторами: кривой доходностей казначейских облигаций через 6 месяцев и спредом между доходностями корпоративных и казначейских облигаций. Предположим, что инвестор располагает еще и следующей информацией:
Доходности казначейских облигаций, %
Разбиение промежутка [0,1)
доходностями, б, п.*
Разбиение промежутка [0,1)
Для определения реализуемой доходности портфеля облигаций можно использовать метод Монте-Карло. Первая итерация (случайные числа: 0,91 для кривой доходностей и 0,12 для спреда между доходностями). В этом случае доходности казначейских облигаций со сроком до погашения 5, 15 и 25 лет составят соответственно 10, 8 и 8%, а доходности корпоративных облигаций со сроком до погашения 15 и 25 лет -- 9 и 9%.
Тогда цены облигаций (на номинал в 100 долл.) через 6 месяцев определяются следующим образом:
P1 = 6/0,1 (1- 1/ (1+0,05)10)+100/(1+0,05)10 = 84,55653
P2 = 100 (купонная ставка совпадает с доходностью).
P3 = 10,5/0,09 (1 - 1/(1,045)50)+ 100/(1,045)50 = 114,82151
Значит, реализуемая доходность портфеля облигаций составит:
P1 * 5*104+P2*4*104+ P3* 6*104+15 *104+18*104+315*103-15*106=0,1016
Предположим, что было проведено 100 итераций. При этом оказалось, что наименьшая реализуемая доходность портфеля равна -3,905%, а наибольшая реализуемая доходность составляет 24,97%.
Разделив отрезок (-3,905%; 24,97%) на достаточно большое число частей, подсчитаем для каждой части число итераций, дающих реализуемую доходность из этой части.
Таким образом, будет построено эмпирическое распределение вероятностей реализуемой доходности портфеля облигаций. После чего можно получить различные числовые характеристики этой реализуемой доходности: среднее значение, стандартное отклонение и т. д.
2. Метод Монте-Карло в условиях управления рыночными рисками.
Метод Монте-Карло, или метод стохастического моделирования (Monte Carlo simulation), основан на моделировании случайных процессов с заданными характеристиками. В отличие от метода исторического моделирования, в методе Монте-Карло изменения цен активов генерируются псевдослучайным образом в соответствии с заданными параметрами распределения, например математическим ожиданием м и волатильностью у. Имитируемое распределение может быть, в принципе, любым, а количество сценариев -- весьма большим (до нескольких десятков тысяч). Выделяют:
метод Монте-Карло для одного фактора риска;
метод Монте-Карло для портфеля активов.
Рассмотрим Метод Монте-Карло для одного фактора риска. Моделирование траектории цен производится по различным моделям. Например, распространенная модель геометрического броуновского движения дает в итоге следующие выражения для моделирования цен S на каждом шаге процесса, состоящего из очень большого количества шагов, охватывающих период Т:
dSt = St (мdt + уdzt), (1)
, где dzt -- винеровский случайный процесс.
Воспользовавшись определением винеровского процесса, уравнение (1) можно записать в дискретной форме:
уу?St= St-1 (м?t + уеv?t) , (2)
St+1 = St + St (м?t + уе1v?t), (3)
St+1 = St+1 + St+1 (м?t + уе2v?t), (4)
Если траектория цен состоит из n равных шагов (например, n дней), то один шаг ?t = 1/n, а случайная величина е подчиняется стандартному нормальному распределению (м = 0, у = 1). Можно использовать и иные модели эволюции цен, например экспоненциальную.
Траектория цен -- это последовательность псевдослучайным образом смоделированных цен, начиная от текущей цены и заканчивая ценой на некотором конечном шаге, например на тысячном или десятитысячном. Чем больше число шагов, тем выше точность метода.
Каждая траектория представляет собой сценарий, по которому определяется цена на последнем шаге исходя из текущей цены. Затем производится полная переоценка портфеля по цене последнего шага и расчет изменения его стоимости для каждого сценария. Оценка VaR производится по распределению изменений стоимости портфеля.
Генерация случайных чисел в методе Монте-Карло состоит из двух шагов. Сначала можно воспользоваться генератором случайных чисел, равномерно распределенных на интервале между 0 и 1 (рассмотрено выше). Затем, используя как аргументы полученные случайные числа, вычисляют значения функций моделируемых распределений.
Рассмотрим пример: элементы расчета VaR методом Монте-Карло на современном российском рынке. Для расчета VaR можно использовать различные модификации метода Монте-Карло; в данном случае метод описывается следующим образом:
По ретроспективным данным рассчитываются оценки математического ожидания х и волатильности у.
С помощью датчика случайных чисел генерируются нормально распределенные случайные числа е с математическим ожиданием, равным х, и стандартным отклонением у.
Полученными на предыдущем шаге случайными числами е заполняется таблица размерностью 500 столбцов на 1000 строк (вообще говоря, размерность таблицы произвольная и зависит, например, от имеющихся вычислительных мощностей, но, чтобы метод обеспечивал приемлемую точность, она должна быть достаточно большой).
Вычисляется траектория моделируемых цен вплоть до S1000 по формуле St= St-1e еt-1, где е -- основание натурального логарифма, St-- текущая цена (курс) актива.
Производится переоценка стоимости портфеля (состоящего в данном примере из одного актива) по формуле: ?V= Q (S1000 - S0), где Q -- количество единиц актива.
Шаги 4 и 5 выполняются 500 раз для заполнения таблицы 500 х 1000. Полученные 500 значений ?V сортируются по убыванию (от самого большого прироста до самого большого убытка). Эти ранжированные изменения можно пронумеровать от 1 до 500. В соответствии с желаемым уровнем доверия (1 - б) риск-менеджер может определить VaR как такой максимальный убыток, который не превышается в 500(1 - б) случаях, т. е. VaR равен абсолютной величине изменения с номером, равным 500(1 - б).
Шаги 1-6 повторяются для каждого расчета каждого дневного VaR.
В качестве объекта исследования был выбран индекс РТС. Генерация случайных чисел производилась при помощи встроенного генератора МS Ехсеl.
Метод Монте-Карло является наиболее технически сложным из всех описанных методов расчета VaR. Кроме того, для выполнения расчетов в полном объеме необходимы значительные вычислительные мощности и временные ресурсы. Современные компьютеры пока еще не позволяют обрабатывать информацию в режиме реального времени, как этого требуют трейдеры, если риск-менеджеры хотят устанавливать VaR-лимиты на величину открытых позиций с помощью метода Монте-Карло.
Теперь рассмотрим метод Монте-Карло для портфеля активов. Чтобы проводить моделирование по Монте-Карло для многофакторного процесса, можно точно так же моделировать каждый из к рассматриваемых факторов исходя из сгенерированных случайных чисел:
dSt,j = мt,j St,j dt + уt,j St,j Sdzt,j, j = 1,2, …, k, (5)
или для дискретного времени:
?St,j = St-1,j(мj?t + уjеjv?t), j = 1,2, …, k. (6)
С целью учета корреляции между факторами необходимо, чтобы случайные величины еi и еj точно так же коррелировали между собой. Для этого используется разложение Холецкого, суть которого состоит в разложении корреляционной матрицы на две (множители Холецкого) и использовании их для вычисления коррелированных случайных чисел.
Корреляционная матрица является симметричной и может быть представлена произведением треугольной матрицы низшего порядка с нулями в верхнем правом углу на такую же транспонированную матрицу. Например, для случая двух факторов имеем:
Коррелированные случайные числа е1 и е2 получаются путем перемножения множителя Холецкого и вектора независимых случайных чисел з:
При расчетах необходимо правильно выбрать количество множителей,
чтобы получилась положительно определенная матрица.
Достоинства метода Монте-Карло:
высокая точность расчетов;
высокая точность применительно к инструментам с нелинейными ценовыми характеристиками;
Недостатки метода Монте-Карло:
высокая сложность моделей и соответственно высокий риск неадекватности моделей;
высокие требования к вычислительной мощности и значительные затраты времени на проведение расчетов.
В данной работе был рассмотрен метод Монте - Карло. Этот метод имитации применим для решения почти всех задач при условии, что альтернативы могут быть выражены количественно. Построение модели начинается с определения функциональных зависимостей в реальной системе, которые в последствии позволяют получить количественное решение, используя теорию вероятности и таблицы случайных чисел.
Модель Монте-Карло не столь формализована и является более гибкой, чем другие имитирующие модели. Причины здесь следующие:
при моделировании по методу Монте-Карло нет необходимости определять, что именно оптимизируется;
нет необходимости упрощать реальность для облегчения решения, поскольку применение ЭВМ позволяет реализовать модели сложных систем;
в программе для ЭВМ можно предусмотреть опережения во времени.
Данный метод является общепризнанным и наилучшим, так как обладает рядом непреодолимых достоинств, в частности использует гипотезу о нормальном распределении доходностей, показывает высокую точность для нелинейных инструментов и устойчив к выбор ретроспективы. К недостаткам можно отнести техническую сложность расчётов и модельный риск.
Список литературы
Метод статистического моделирования, главные особенности. Экономико-математическая модель задачи, область допустимых решений. Задача на определение: оптимального размера поставки, годовых расходов на хранение запасов. Относительная пропускная способность.
| Рубрика | Экономико-математическое моделирование |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 25.05.2013 |
| Размер файла | 288,3 K |
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Введение
Метод Монте-Карло можно определить как метод моделирования случайных величин с целью вычисления характеристик их распределений. Возникновение идеи использования случайных явлений в области приближённых вычислений принято относить к 1878 году, когда появилась работа Холла об определении числа p с помощью случайных бросаний иглы на разграфлённую параллельными линиями бумагу. Существо дела заключается в том, чтобы экспериментально воспроизвести событие, вероятность которого выражается через число p, и приближённо оценить эту вероятность. Отечественные работы по методу Монте-Карло появились в 1955-1956 годах. С того времени накопилась обширная библиография по методу Монте-Карло. Даже беглый просмотр названий работ позволяет сделать вывод о применимости метода Монте-Карло для решения прикладных задач из большого числа областей науки и техники.
Первоначально метод Монте-Карло использовался главным образом для решения задач нейтронной физики, где традиционные численные методы оказались мало пригодными. Далее его влияние распространилось на широкий класс задач статистической физики, очень разных по своему содержанию. Метод Монте-Карло оказал и продолжает оказывать существенное влияние на развитие методов вычислительной математики (например, развитие методов численного интегрирования) и при решении многих задач успешно сочетается с другими вычислительными методами и дополняет их. Его применение оправдано в первую очередь в тех задачах, которые допускают теоретико-вероятностное описание. Это объясняется как естественностью получения ответа с некоторой заданной вероятностью в задачах с вероятностным содержанием, так и существенным упрощением процедуры решения.
1. Метод статистического моделирования (метод Монте-Карло)
Две особенности метода Монте-Карло
Первая особенность метода - простая структура вычислительного алгоритма.
Вторая особенность метода - погрешность вычислений, как правило, пропорциональна D/N2, где D - некоторая постоянная, N - число испытаний. Отсюда видно, что для того, чтобы уменьшить погрешность в 10 раз (иначе говоря, чтобы получить в ответе еще один верный десятичный знак), нужно увеличить N (т. е. объем работы) в 100 раз. Ясно, что добиться высокой точности таким путем невозможно. Поэтому обычно говорят, что метод Монте-Карло особенно эффективен при решении тех задач, в которых результат нужен с небольшой точностью (5-10%). Способ применения метода Монте-Карло по идее довольно прост. Чтобы получить искусственную случайную выборку из совокупности величин, описываемой некоторой функцией распределения вероятностей, следует:
1. Построить график или таблицу интегральной функции распределения на основе ряда чисел, отражающего исследуемый процесс (а не на основе ряда случайных чисел), причем значения случайной переменной процесса откладываются по оси абсцисс (х), а значения вероятности (от 0 до 1) - по оси ординат (у).
2.С помощью генератора случайных чисел выбрать случайное десятичное число в пределах от 0 до 1 (с требуемым числом разрядов).
3. Провести горизонтальную прямую от точки на оси ординат соответствующей выбранному случайному числу, до пересечения с кривой распределения вероятностей.
4.Опустить из этой точки пересечения перпендикуляр на ось абсцисс.
5. Записать полученное значение х. Далее оно принимается как выборочное значение. б. Повторить шаги 2-5 для всех требуемых случайных переменных, следуя тому порядку, в котором они были записаны.
В задачах исследования операций метод Монте-Карло применяется в трех основных ролях:
1) при моделировании сложных, комплексных операций, где присутствует много взаимодействующих случайных факторов;
2) при проверке применимости более простых, аналитических методов и выяснении условий их применимости;
2. Задача 1
При производстве двух видов продукции используется 4 типа ресурсов. Норма расхода ресурсов на производство единицы продукции, общий объем каждого ресурса заданы в таблице.
Метод Монте-Карло – это численный метод решения математических задач при помощи моделирования случайных величин.
Датой рождения метода Монте-Карло принято считать 1949 год. Создателями этого метода считают американских математиков Дж. Неймана и С. Улама. В России первые статьи о методе Монте-Карло были опубликованы в 1955-1956 годах.
Любопытно, что теоретическая основа метода была известна давно. Более того, некоторые задачи статистики рассчитывались иногда с помощью случайных выборок, то есть фактически методом Монте-Карло. Однако до появления электронных вычислительных машин этот метод не мог найти сколько-нибудь широкого применения, ибо моделировать случайные величины вручную – очень трудоемкая работа. Таким образом, возникновение метода Монте-Карло как весьма универсального численного метода стало возможным только благодаря появлению ЭВМ.
Цели и задачи
Цель работы заключается в рассмотрении метода Монте-Карло как одного из способов решения задач с помощью моделирования случайных величин или случайных процессов, а так же применение рассмотренного метода в решении некоторых практических задач.
Рассмотреть общую схему метода Монте-Карло;
Научиться вычислять сопутствующие методу величины: математическое ожидание, дисперсию, среднее квадратичное отклонение;
Решить прикладную задачу на вычисление площади фигуры произвольной формы с использованием данного метода;
Проанализировать оценку погрешности вычисления в зависимости от количества используемых случайных величин;
Получить искомую величину площади с помощью формулы, определяющей метод Монте-Карло и сравнить полученные результаты практической и аналитической выкладки данного метода;
Вычисление интегралов с помощью данного метода, используя для моделирования случайных величин составленную компьютерную программу на языке Lazarus;
Классическое определение вероятности
При проведении какого-либо эксперимента все исходы эксперимента имеют равные шансы, поэтому они называются равновозможными. Чаще всего равновозможность следует из условий проведения опытов и симметрии тех объектов, которые в нём участвуют. Можно сформулировать простое правило подсчёта вероятности любого случайного события, получившее название формулы классической вероятности или формулы Лапласа.
Рассмотрим случайный эксперимент, который может завершиться одним из N равновозможных исходов. Пусть ровно N1 из этих исходов благоприятствуют событию А. Тогда вероятность этого события может быть вычислена по формуле:
Р(А) =
Дискретная случайная величина и её характеристики
Случайная величина называется дискретной, если она может принимать дискретное множество значений (значения некоторой конечной или бесконечной числовой последовательности).
Дискретная случайная величина определяется таблицей распределения:
, где
Математическим ожиданием дискретной случайной величины называется:
При одинаковых вероятностях всех величин x математическое ожидание будет средним арифметическим всех x.
Дисперсией дискретной случайной величины называется:
Эту формулу можно преобразовать в:
Среднеквадратичным отклонением дискретной случайной величины называется квадратный корень из дисперсии.
Непрерывная случайная величина и её характеристики
Случайная величина называется непрерывной, если она может принимать любое значение из некоторого интервала (a,b).
Непрерывная случайная величина определяется заданием интервала и плотностью вероятностей (плотностью распределения) p().
Если интервал (a`,b`) содержится в (a,b), то вероятность того, что окажется в (a`,b`) равна
(1)
Это физический смысл плотности распределения.
Свойства плотности распределения:
, т.е. гарантировано попадёт в (a,b).
Математическим ожиданием непрерывной случайной величины называется:
Также для математического ожидания случайной функции существует формула (2), где p(x) – плотность , f(x) – произвольная непрерывная функция.
Формула дисперсии непрерывной случайной величины такая же, как и для дискретной.
Равномерно распределённой случайной величиной называется случайная величина, определённая в (0,1) и имеющая плотность p(x)=1. Действительно, вероятность того, что попадёт в интервал (a`,b`), содержащийся в (0,1) равна: одинакова для любого интервала (a`,b`). Можно вычислить, что = , а .
Общая схема метода Монте-Карло
Нормальной (гауссовской) случайной величиной называется случайная величина которая определена на всём множестве действительных чисел и плотность которой равна:
(3), где a=
Из (3) можно вычислить, что при любых a и σ справедливо равенство:
Правило трёх сигм: при испытании получаемая случайная величина с вероятностью 99,7% будет отличаться от математического ожидания этой случайной величины не более чем на три среднеквадратичных отклонения.
Центральная предельная теорема теории вероятностей: при большом (или стремящимся к бесконечности) числе случайных величин их сумму можно считать нормальной. Или, выражаясь формулой:
Общая схема метода. Пусть нам нужно найти значение какой-то величины m. Возьмём такую случайную величину ε, чтобы . При этом пусть.
Рассмотрим (выберем, разыграем) n случайных величин , плотность распределения которых совпадает с плотностью ε. При достаточно большом n согласно (5) плотность распределения можно будет считать нормальным.
Перепишем (4) :
Поделим неравенство внутри скобки на n:
Двойное неравенство заменим на одинарное через модуль, а представим через знак суммы:
При очень большом n значение модуля будет практически неотличимо от математическое ожидания. Поэтому искомое .
Разыгрывание непрерывной случайной величины по определённой плотности
При решении задач удобно, когда все случайные величины имеют одинаковую плотность. Пусть нам нужно получить (разыграть) значения непрерывной случайной величины ε на интервале (a,b) с плотностью распределения p(x). Эти значения можно получить решив следующее уравнение относительно ε:
(7), где - произвольная случайная величина.
Рассмотрим функцию . Из свойств плотности следует, что y(a)=0, а значение интеграла (y(b)) = 1, а производная y`(x)=p(x)0. Значит y(x) на участке (0,1) монотонно возрастает. Отсюда следует, что любая прямая y= ( пересекает график y(x) только один раз. Т. к. y=γ - прямая, то γ равномерно распределена на (a,b). Абсциссу этой точки пересечения примем за ε. Значит мы доказали, что (6) имеет только 1 решение.
Выберем произвольный интервал (a`,b`), содержащийся в (a,b). Точкам этого интервала будут соответствовать ординаты y(x), удовлетворяющие неравенству y(a`) и наоборот. Отсюда следует, что . Т.к. γ равномерно распределена в (0,1), то: . Из-за зависимости между x и y последнее равенство применимо и для x: . А это значит, что ε (корень уравнения) имеет плотность p(x).
Разыгрывание равномерно распределённой величины. Пусть η - такая величина, распределённая в (a,b). тогда её плотность равна:
Чтобы разыграть значения η, составим уравнение: . Интеграл равен . Отсюда (8) .
Вычисление площади фигуры методом Монте-Карло
Пусть нам нужно вычислить площадь произвольной фигуры A. Разместим А в 1-ой четверти системы координат 0xy в квадрате, ограниченном осями и линиями y=100, x=100. Пусть площадь этого квадрата ранва S.
Разыграем n случайных чисел ε ( и произвольно сгруппируем их попарно. Первое число в паре будет абсциссой, второе - ординатой. Мы получили координат точек. Нанесём эти точки в систему координат. Пусть число точек, попавших в фигуру A равно n`. Тогда площадь фигуры A равна
Для проверки этой формулы на практике я выбрал фигуру, площадь которой доподлинно известна - трапецию (a=8, b=4, h=6). Вычисления проводились 6 раз, при этом каждый раз n увеличивалось. Результаты вычислений:
, n=16; (см. Рисунок 1 в Приложении)
, n=32; (см. Рисунок 2 в Приложении)
, n=48; (см. Рисунок 3 в Приложении)
, n=64; (см. Рисунок 4 в Приложении)
, n=80; (см. Рисунок 5 в Приложении)
, n=88; (см. Рисунок 6 в Приложении)
Истинное значение площади: .
Из приведённого выше можно заметить:
Чем больше n, тем точнее результат;
Погрешность вычислений убывает довольно медленно.
Изображения эксперимента приведены в Приложении 1.
Вычисление интеграла методом Монте-Карло
Пусть дана функция y(x), заданная на интервале (a,b). Требуется вычислить значение интеграла .
Возьмём произвольную случайную величину ε с плотностью распределения , определённую на (a,b). Также возьмём случайную величину .
Рассмотрим n случайных величин . Согласно центральной предельной теореме теории вероятностей при большом n η можно считать нормальной. Применим (6): .
При достаточно большом n: (10). При этом ошибка вычисления будет не более .
Приближённо вычислим интеграл . (Его истинное значение равно 1).
Проведём вычисление 2 раза. В первый раз возьмём равномерно распределённую ε. . Разыграем ε: . Формула (10) примет вид: . Т.к. плотность для всех ε одинакова, то вынесем её из суммы: . Напишем программу для вычисления I. Были получены результаты:
Теперь возьмём плотность . Как видно по рисунку график этой плотности сильно близок к синусоиде или, другими словами, пропорциональна . По идее, в данном случае I должно быть точнее, чем в предыдущем вычислении.
Разыграем ε: . Формула (10) примет вид: . Составим программу для вычисления I (смотреть Программа_1). Были получены результаты:
Как видно, второй способ показывал более точный результат, однако при таком n это не так уж и важно.
Теперь приближённо вычислим интеграл . Этот интеграл, в отличии от предыдущего, трудно взять аналитическим путём.
Возьмём с равномерной плотностью распределения . Разыграем ε: . Формула (10) примет вид: . Напишем программу для вычисления I (смотреть Программа_2). Были получены результаты:
Метод Монте-Карло сегодня используется очень часто (порой весьма неэффективно). Его применяют при расчёте площадей и интегралов (что было показано в данной работе), при оценке кредитного риска, расчётах в системах массового обслуживания, оценке прочности изделий (в том числе изделий, состоящих из большого числа элементов). Метод имеет некоторые преимущества:
Он приводит к выполнимой (и сравнительно простой) процедуре даже в многомерном случае. Им удобно решать многомерные интегралы;
Его легко применять при малых ограничениях или без предварительного анализа задачи.
Вместе с тем он обладает определёнными недостатками:
Границы ошибки не определены точно, но включают некую случайность (при решении последней задачи при одной и той же n получились различные I);
Статистическая погрешность убывает весьма медленно (это показано в задаче на вычисление площади фигуры).
Исходя из этого, метод применяют в задачах, где нужен ответ с небольшой точностью (до 5%).
В данной работе было показано применение метода при нахождении площади фигуры и вычислении интеграла. Однако это работа не закончена, и в будущем планируется продолжить работу, применив метод для решения других задач.
Математика. Большой энциклопедический словарь / Гл. ред. Ю. В. Прохоров. – М.: Большая Российская энциклопедия,1999г.
Ермаков С. М. Метод Монте-Карло и смежные вопросы. /М.: Наука, 1971г.
Читайте также: