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

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

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

Область применения

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

• трансформирование неопределенности для обычных аналитических моделей;
• расчета вероятностей, если аналитические методы не могут быть использованы.

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

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

Входные данные

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

Процесс моделирования

Процесс включает следующие этапы:

1. Определение модели или алгоритма, которые наиболее точно описывают поведение исследуемой системы.
2. Многократное применение модели с использованием генератора случайных чисел для получения выходных данных модели (моделирование системы). При необходимости моделируют воздействие неопределенности. Модель записывают в форме уравнения, выражающего соотношение между входными и выходными параметрами. Значения, отобранные в качестве входных данных, получают исходя из соответствующих распределений вероятностей, характеризующих неопределенности данных.
3. С помощью компьютера многократно используют модель (часто до 10000 раз) с различными входными данными и получают выходные данные. Они могут быть обработаны с помощью статистических методов для получения оценок среднего, стандартного отклонения, доверительных интервалов.

Выходные данные

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

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

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

Анализ взаимосвязи входных и выходных величин может выявить относительное значение факторов работы системы и идентифицировать способы снижения неопределенности выходных величин.

Преимущества

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

Недостатки

• Точность решений зависит от количества итераций, которые могут быть выполнены (этот недостаток становится менее значимым с увеличением быстродействия компьютера).
• Метод предполагает, что неопределенность данных можно описать известным распределением.
• Большие и сложные модели могут представлять трудности для специалистов по моделированию и затруднять вовлечение заинтересованных сторон.
• Метод не может адекватно моделировать события с очень высокой или очень низкой вероятностью появления, что ограничивает его применение при анализе риска.

Стандарты

• МЭК 61649 Критерии согласия, доверительные интервалы и нижние доверительные границы для распределения Вейбулла
• Руководство ИСО/МЭК 98-3:2008 Неопределенность измерения. Часть 3. Руководство по выражению неопределенности измерения

Данный метод родился в 1949 благодаря усилиям американских ученых Дж. Неймана и Стива Улана в городе Монте-Карло (княжество Монако).

Метод Монте-Карло - численный метод решения математических задач при помощи моделирования случайных чисел.

Суть метода заключается в том, что посредствам специальной программы на ЭВМ производится последовательность псевдослучайных чисел с равномерным законом распределения от 0 до1. Затем данные числа с помощью специальных программ преобразуются в числа, распределенные по закону Эрланга, Пуассона, Релея и т.д.

Имитационное моделирование по методу Монте-Карло (Monte-Carlo Simulation) позволяет построить математическую модель для проекта с неопределенными значениями параметров, и, зная вероятностные распределения параметров проекта, а также связь между изменениями параметров (корреляцию) получить распределение доходности проекта.

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

Сущность метода Монте-Карло состоит в следующем: требуется найти значение а некоторой изучаемой величины. Для этого выбирают такую случайную величину Х, математическое ожидание которой равно а: М(Х)=а.

Практически же поступают так: производят n испытаний, в результате которых получают n возможных значений Х; вычисляют их среднее арифметическое и принимают x в качестве оценки (приближённого значения) a* искомого числа a:

Поскольку метод Монте-Карло требует проведения большого числа испытаний, его часто называют методом статистических испытаний. Теория этого метода указывает, как наиболее целесообразно выбрать случайную величину Х, как найти её возможные значения. В частности, разрабатываются способы уменьшения дисперсии используемых случайных величин, в результате чего уменьшается ошибка, допускаемая при замене искомого математического ожидания а его оценкой а*.

Применение метода имитации Монте-Карло требует использования специальных математических пакетов (например, специализированного программного пакета Гарвардского университета под названием Risk-Master) , в то время, как метод сценариев может быть реализован даже при помощи обыкновенного калькулятора.

Как уже отмечалось, анализ рисков с использованием метода имитационного моделирования Монте-Карло представляет собой “воссоединение” методов анализа чувствительности и анализа сценариев на базе теории вероятностей.

Результатом такого комплексного анализа выступает распределение вероятностей возможных результатов проекта (например, вероятность получения NPV<0).

Упоминаемый ранее программный пакет Risk-Master позволяет в диалоговом режиме осуществить процедуру подготовки информации к анализу рисков инвестиционного проекта по методу Монте-Карло и провести сами расчеты.

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

Как только функция распределения определена, можно применять процедуру Монте-Карло.

Алгоритм метода имитации Монте-Карло

Шаг 1.Опираясь на использование статистического пакета, случайным образом выбираем, основываясь на вероятностной функции распределения значение переменной, которая является одним из параметров определения потока наличности.

Шаг 2. Выбранное значение случайной величины наряду со значениями переменных, которые являются экзогенными переменными используется при подсчете чистой приведенной стоимости проекта.

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

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

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

По прошлым наблюдениям за переменной можно установить частоту, с которой та принимает соответствующие значения. В этом случае вероятностное распределение есть то же самое частотное распределение, показывающее частоту встречаемости значения, правда, в относительном масштабе (от 0 до 1). Вероятностное распределение регулирует вероятность выбора значений из определенного интервала. В соответствии с заданным распределением модель оценки рисков будет выбирать произвольные значения переменной. До рассмотрения рисков мы подразумевали, что переменная принимает одно определенное нами значение с вероятностью 1. И через единственную итерацию расчетов мы получали однозначно определенный результат. В рамках модели вероятностного анализа рисков проводится большое число итераций, позволяющих установить, как ведет себя результативный показатель (в каких пределах колеблется, как распределен) при подстановке в модель различных значений переменной в соответствии с заданным распределением.

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

Существование коррелированных переменных в проектном анализе вызывает порой проблему, не рассмотреть которую означало бы заранее обречь себя на неверные результаты. Ведь без учета коррелированности, скажем, двух переменных - компьютер, посчитав их полностью независимыми, генерирует нереалистичные проектные сценарии. Допустим цена и количество проданного продукта есть две отрицательно коррелированные переменные. Если не будет уточнена связь между переменными (коэффициент корреляции), то возможны сценарии, случайно вырабатываемые компьютером, где цена и количество проданной продукции будут вместе либо высоки, либо низки, что естественно негативно отразится на результате.

Проведение расчетных итераций является полностью компьютеризированная часть анализа рисков проекта. 200-500 итераций обычно достаточно для хорошей репрезентативной выборки. В процессе каждой итерации происходит случайный выбор значений ключевых переменных из специфицированного интервала в соответствии с вероятностными распределениями и условиями корреляции. Затем рассчитываются и сохраняются результативные показатели (например, NPV). И так далее, от итерации к итерации.

Завершающая стадия анализа проектных рисков - интерпретация результатов, собранных в процессе итерационных расчетов. Результаты анализа рисков можно представить в виде профиля риска. На нем графически показывается вероятность каждого возможного случая (имеются в виду вероятности возможных значений результативного показателя).

Часто при сравнении вариантов капиталовложений удобнее пользоваться кривой, построенной на основе суммы вероятностей (кумулятивный профиль риска). Такая кривая показывает вероятности того, что результативный показатель проекта будет больше или меньше определенного значения. Проектный риск, таким образом, описывается положением и наклоном кумулятивного профиля риска.

Кумулятивный (интегральный, накопленный) профиль риска, показывает кумулятивное вероятностное распределение чистой текущей стоимости (NPV) с точки зрения банкира, предпринимателя и экономиста на определенный проект. Вероятность того, что NPV < 0 с точки зрения экономиста - около 0.4, в то время как для предпринимателя эта вероятность менее 0.2. С точки зрения банкира проект кажется совсем безопасным, так как вероятность того, что NPV > 0, около 95%.

Будем исходить из того, что проект подлежит рассмотрению и считается выгодным, в случае, если NPV > 0. При сравнении нескольких одноцелевых проектов выбирается тот, у которого NPV больше при соблюдении сказанного в предыдущем предложении.

Рассмотрим 5 иллюстративных случаев на Рис.3 принятия решений (см. учебные материалы Института экономического развития Всемирного банка). Случаи 1-3 имеют дело с решением инвестировать в отдельно взятый проект, тогда как два последних случая (4, 5) относятся к решению-выбору из альтернативных проектов. В каждом случае рассматривается как кумулятивный, так и некумулятивный профили риска для сравнительных целей. Кумулятивный профиль риска более полезен в случае выбора наилучшего проекта из представленных альтернатив, в то время как некумулятивный профиль риска лучше индуцирует вид распределения и показателен для понимания концепций, связанных с определением математического ожидания. Анализ базируется на показателе чистой текущей стоимости.

Случай 1: Минимальное возможное значение NPV выше, чем нулевое (см. Рис.3а,кривая 1).

Вероятность отрицательного NPV равна 0, так как нижний конец кумулятивного профиля риска лежит справа от нулевого значения NPV. Так как данный проект имеет положительное значение NPV во всех случаях, ясно, что проект принимается.

Случай 2: Максимальное возможное значение NPV ниже нулевого(см. Рис.3а, кривая 2).

Вероятность положительного NPV равна 0 (см. следующий рисунок)., так как верхний конец кумулятивного профиля риска лежит слева от нулевого значения NPV. Так как данный проект имеет отрицательное значение NPV во всех случаях, ясно, что проект не принимается.

Случай 3: Максимальное значение NPV больше, а минимальное меньше нулевого (см. Рис3а, кривая 3).

Вероятность нулевого NPV больше, чем 0, но меньше, чем 1, так как вертикаль нулевого NPV пересекает кумулятивный профиль рисков. Так как NPV может быть как отрицательным, так и положительным, решение будет зависеть от предрасположенности к риску инвестора. По-видимому, если математическое ожидание NPV меньше или равно 0 (пик профиля рисков слева от вертикали или вертикаль точно проходит по пику) проект должен отклоняться от дальнейшего рассмотрения.

Случай 4: Непересекающиеся кумулятивные профили рисков альтернативных (взаимоисключающих) проектов (см. Рис.3б).

При фиксированной вероятности отдача проекта В всегда выше, нежели у проекта А. Профиль рисков также говорит о том, что при фиксированной NPV вероятность, с которой та будет достигнута, начиная с некоторого уровня будет выше для проекта В, чем для проекта А. Таким образом, мы подошли к правилу 1.

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

Случай 5: Пересекающиеся кумулятивные профили рисков альтернативных проектов. (см. Рис.3в).

Склонные к риску инвесторы предпочтут возможность получения высокой прибыли и, таким образом, выберут проект А. Несклонные к риску инвесторы предпочтут возможность нести низкие потери и, вероятно, выберут проект В.

Правило 2: Если кумулятивные профили риска альтернативных проектов пересекаются в какой-либо точке, то решение об инвестировании зависит от склонности к риску инвестора.

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

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

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

6. Моделями типа «черный ящик являются»

1) модели мышления

2) модели, описывающие зависимость параметров состояния объекта от входных параметров

3) модели «аварийного» ящика на самолетах

4) модели, описывающие входные и выходные параметры объекта без учета внутренней структуры объекта

Определение целей моделирования осуществляется на этапе

1) разработки концептуальной модели

2) разработки математической модели

3) разработки имитационной модели

1. постановки задачи

Поставьте в соответствие друг другу определения для представленной таблицы моделирования

Среди общепринятых классификаций видов моделей отсутствует их классификация на

1) дискретные – непрерывные

2) логические – сенсорные

3) детерминированные – стохастические

1. статические – динамические

10. В отношении «объект-модель» не находятся понятия

1) микромир – квантовая механика

2) книга – абзац

3) знания – оценка

4) дом – план

Компьютерные сети

План

1. Основные понятия компьютерных сетей
2. Топология компьютерных сетей
3. Структура вычислительной сети
4. Локальные сети
5. Организация работы в локальной сети
6. Возможности сети Интернет
7. Службы Интернета
8. Сетевая операционная система
9. Тесты для самопроверки

Основные понятия компьютерных сетей

Информационно – вычислительная сеть - ИВС (часто используется название - вычислительная сеть, компьютерная сеть), представляет собой систему компьютеров, объединенных каналами передачи данных.

Канал (channel) - средство или путь, по которому передаются сигналы либо данные.

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

Решение этих задач обеспечивается:

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

Первые ИВС появились в 60-х годах, и это было технической революцией, сравнимой по значимости с появлением первых ЭВМ. В них была предпринята попытка объединения технологий сбора, хранения, передачи и обработки информации на ЭВМ с техникой связи.

Одной из первых сетей, оказавших влияние на дальнейшее развитие, явилась сеть АРПА. Она была создана пятидесятью университетами и фирмами США. В последнее время она охватывает всю территорию США, часть Европы и Азии. Её основное значение состоит в том, что она доказала техническую возможность и экономическую целесообразность разработки и эксплуатации больших сетей.

В 60-х годах в Европе были разработаны и внедрены международные сети EIN и Евронет, затем стали появляться национальные сети. В СССР первая сеть стала рентабельной в 60-х годах в Академии наук в Ленинграде. В 1985 г. к ней подсоединилась региональная подсеть «Северо-запад» с академическими центрами в Риге и Москве.

В 1980 г. сдана в эксплуатацию система телеобработки статистической информации (СТОСИ), обслуживающая ГВЦ ЦСУ СССР в Москве и республиканский ВЦ в союзных республиках.

В настоящее время в мире зарегистрировано более 200 глобальных сетей, (при этом более четверти из них – созданы в США). С появлением микроЭВМ и ПЭВМ появились локальные вычислительные сети (ЛВС). Объединение ЛВС с глобальными сетями позволило получить доступ к мировым информационным ресурсам.

В общем случае, для создания компьютерных сетей необходимо специальное аппаратное обеспечение (сетевое оборудование ) и специальное программное обеспечение (сетевые программные средства ).

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

Простейшая компьютерная сеть образуется при соединении двух недалеко отстоящих друг от друга компьютеров (в пределах 10 - 20 м) с помощью специального кабеля, называемого нуль-модемом, который подключается к последовательным или параллельным портам обоих компьютеров. Такое временное соединение называется прямым компьютерным соединением (ПКС). В настоящее время получили развитие инфракрасные порты, позволяющие организовать соединение напрямую, без кабеля. ПКС используется в основном для обмена информацией между портативным и стационарным персональным компьютером.

Локальная сеть представляет собой расположенные на небольшом расстоянии компьютеры (на удалении в пределах 50-100 м внутри одного или соседних зданий), между которыми необходимо организовать постоянный информационный обмен, стационарно соединенные специально предназначенными для этих целей кабелями. Благодаря относительно небольшим длинам линий связи, по локальной сети можно передавать информацию в цифровом виде с высокой скоростью. Сеть указанного типа называется локальной вычислительной сетью (ЛВС) или по-английски LAN - Local Area Net .

Распределенная сеть объединяет значительно удаленные друг от друга компьютеры (например, расположенные в разных концах города или в разных городах), между которыми необходимо организовать постоянный обмен большими потоками информации; компьютеры в этих сетях соединяются специальными постоянно действующими выделенными каналами . Физически выделенные каналы могут реализовываться с помощью телефонных каналов или оптических кабелей, а также с помощью спутниковых или радиоканалов. С помощью выделенных каналов обычно соединяются удаленные компьютеры одной организации (например, компьютеры центрального офиса банка с компьютерами в его филиалах). Сети, связывающие значительно удаленные компьютеры, называются распределенными. Доступ к распределенным сетям организаций ограничен определенным кругом лиц, для которых работа в таких сетях связана с выполнением их должностных обязанностей. По своему функциональному назначению сети подобного типа эквиваленты локальным и называются региональными или по-английски Metropolitan Area Net - MAN .

Региональная сеть организации, в которой создана специальная коммуникационная система обмена сообщениями (электронная почта, факс, совместная работа над документами), называется корпоративной .

Глобальная сеть или Wide Area Net – WAN – это сеть компьютеров, распределенных по всему миру и постоянно связанных каналами с очень высокой пропускной способностью, на которых имеется большой объем разнообразной информации, доступной на коммерческой основе всем желающим.

Временная связь между удаленными ПК с помощью обычной телефонной сети через АТС может быть установлена с помощью устройства, называемого модемом (факс-модем). Такой способ связи называется связью по коммутируемому каналу . С помощью модема можно организовать информационный обмен между «обычными компьютерами», можно подключиться к локальной сети офиса или к глобальной сети.

Наряду с сетями, объединяющими несколько компьютеров, существуют сети терминалов, или терминальные сети , связывающие мощные компьютеры (мэйнфреймы) со специальными устройствами - терминалами, которые могут быть достаточно сложными, но вне сети их работа или невозможна, или вообще теряет смысл. Примерами терминальных устройств и терминальных сетей могут служить сеть банкоматов, сеть кассовых аппаратов в магазинах и др.

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

Метод Монте-Карло

Рассмотрим метод Монте-Карло на примере вычисления интеграла, значение которого аналитическим способом найти не удается.

Задача 1. Найти значение интеграла:

На рис. 1.1 представлен график функции f (x ). Вычислить значение интеграла этой функции - значит, найти площадь под этим графиком.

Рис. 1.1

Ограничиваем кривую сверху, справа и слева. Случайным образом распределяем точки в прямоугольнике поиска. Обозначим через N 1 количество точек, принятых для испытаний (то есть попавших в прямоугольник, эти точки изображены на рис. 1.1 красным и синим цветом), и через N 2 - количество точек под кривой, то есть попавших в закрашенную площадь под функцией (эти точки изображены на рис. 1.1 красным цветом). Тогда естественно предположить, что количество точек, попавших под кривую по отношению к общему числу точек пропорционально площади под кривой (величине интеграла) по отношению к площади испытуемого прямоугольника. Математически это можно выразить так:

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

Фрагмент алгоритма метода Монте-Карло в виде блок-схемы выглядит так, как показано на рис. 1.2

Рис. 1.2

Значения r 1 и r 2 на рис. 1.2 являются равномерно распределенными случайными числами из интервалов (x 1 ; x 2) и (c 1 ; c 2) соответственно.

Метод Монте-Карло чрезвычайно эффективен, прост, но необходим "хороший" генератор случайных чисел. Вторая проблема применения метода заключается в определении объема выборки, то есть количества точек, необходимых для обеспечения решения с заданной точностью. Эксперименты показывают: чтобы увеличить точность в 10 раз, объем выборки нужно увеличить в 100 раз; то есть точность примерно пропорциональна корню квадратному из объема выборки:

Схема использования метода Монте-Карло при исследовании систем со случайными параметрами

Построив модель системы со случайными параметрами, на ее вход подают входные сигналы от генератора случайных чисел (ГСЧ), как показано на рис. 1.3 ГСЧ устроен так, что он выдает равномерно распределенные случайные числа r рр из интервала . Так как одни события могут быть более вероятными, другие - менее вероятными, то равномерно распределенные случайные числа от генератора подают на преобразователь закона случайных чисел (ПЗСЧ), который преобразует их в заданный пользователем закон распределения вероятности, например, в нормальный или экспоненциальный закон. Эти преобразованные случайные числа x подают на вход модели. Модель отрабатывает входной сигнал x по некоторому закону y = ц (x ) и получает выходной сигнал y , который также является случайным.

статистическое моделирование случайная величина

Рис. 1.3

В блоке накопления статистики (БНСтат) установлены фильтры и счетчики. Фильтр (некоторое логическое условие) определяет по значению y , реализовалось ли в конкретном опыте некоторое событие (выполнилось условие, f = 1) или нет (условие не выполнилось, f = 0). Если событие реализовалось, то счетчик события увеличивается на единицу. Если событие не реализовалось, то значение счетчика не меняется. Если требуется следить за несколькими разными типами событий, то для статистического моделирования понадобится несколько фильтров и счетчиков N i . Всегда ведется счетчик количества экспериментов - N .

Далее отношение N i к N , рассчитываемое в блоке вычисления статистических характеристик (БВСХ) по методу Монте-Карло, дает оценку вероятности p i появления события i , то есть указывает на частоту его выпадения в серии из N опытов. Это позволяет сделать выводы о статистических свойствах моделируемого объекта.

Например, событие A совершилось в результате проведенных 200 экспериментов 50 раз. Это означает, согласно методу Монте-Карло, что вероятность совершения события равна: p A = 50/200 = 0.25. Вероятность того, что событие не совершится, равна, соответственно, 1 - 0.25 = 0.75.

Обратите внимание: когда говорят о вероятности, полученной экспериментально, то ее называют частостью; слово вероятность употребляют, когда хотят подчеркнуть, что речь идет о теоретическом понятии.

При большом количестве опытов N частота появления события, полученная экспериментальным путем, стремится к значению теоретической вероятности появления события.

В блоке оценки достоверности (БОД) анализируют степень достоверности статистических экспериментальных данных, снятых с модели (принимая во внимание точность результата е , заданную пользователем) и определяют необходимое для этого количество статистических испытаний. Если колебания значений частоты появления событий относительно теоретической вероятности меньше заданной точности, то экспериментальную частоту принимают в качестве ответа, иначе генерацию случайных входных воздействий продолжают, и процесс моделирования повторяется. При малом числе испытаний результат может оказаться недостоверным. Но чем более испытаний, тем точнее ответ, согласно центральной предельной теореме.

Заметим, что оценивание ведут по худшей из частот. Это обеспечивает достоверный результат сразу по всем снимаемым характеристикам модели.

Пример 1. Решим простую задачу. Какова вероятность выпадения монеты орлом кверху при падении ее с высоты случайным образом?

Начнем подбрасывать монетку и фиксировать результаты каждого броска (см. табл. 1.1).

Таблица 1.1.

Результаты испытаний бросания монеты

Будем подсчитывать частость выпадения орла как отношение количества случаев выпадения орла к общему числу наблюдений. Посмотрите в табл. 1.1 случаи для N = 1, N = 2, N = 3 - сначала значения частости нельзя назвать достоверными. Попробуем построить график зависимости P о от N - и посмотрим, как меняется частость выпадения орла в зависимости от количества проведенных опытов. Разумеется, при различных экспериментах будут получаться разные таблицы и, следовательно, разные графики. На рис. 1.4 показан один из вариантов.

Рис. 1.4

Сделаем некоторые выводы.

• 1. Видно, что при малых значениях N , например, N = 1, N = 2, N = 3 ответу вообще доверять нельзя. Например, P о = 0 при N = 1, то есть вероятность выпадения орла при одном броске равна нулю! Хотя всем хорошо известно, что это не так. То есть пока мы получили очень грубый ответ. Однако, посмотрите на график: в процессе накопления информации ответ медленно, но верно приближается к правильному (он выделен пунктирной линией). К счастью, в данном конкретном случае правильный ответ нам известен: в идеале, вероятность выпадения орла равна 0.5 (в других, более сложных задачах, ответ нам, конечно, будет неизвестен). Допустим, что ответ нам надо знать с точностью е = 0.1. Проведем две параллельные линии, отстоящие от правильного ответа 0.5 на расстояние 0.1 (см. рис. 1.4). Ширина образовавшегося коридора будет равна 0.2. Как только кривая P о (N ) войдет в этот коридор так, что уже никогда его не покинет, можно остановиться и посмотреть, для какого значения N это произошло. Это и есть экспериментально вычисленное критическое значение необходимого количества опытов N кр э для определения ответа с точностью е = 0.1; е -окрестность в наших рассуждениях играет роль своеобразной трубки точности. Заметьте, что ответы P о (91), P о (92) и так далее уже не меняют сильно своих значений (см. рис. 1.4); по крайней мере, у них не изменяется первая цифра после запятой, которой мы обязаны доверять по условиям задачи.
• 2. Причиной такого поведения кривой является действие центральной предельной теоремы . Пока здесь мы сформулируем ее в самом простом варианте "Сумма случайных величин есть величина неслучайная". Мы использовали среднюю величину P о, которая несет в себе информацию о сумме опытов, и поэтому постепенно эта величина становится все более достоверной.
• 3. Если проделать еще раз этот опыт сначала, то, конечно, его результатом будет другой вид случайной кривой. И ответ будет другим, хотя примерно таким же. Проведем целую серию таких экспериментов (см. рис. 1.5). Такая серия называется ансамблем реализаций. Какому же ответу в итоге следует верить? Ведь они, хоть и являются близкими, все же разнятся. На практике поступают по-разному. Первый вариант - вычислить среднее значение ответов за несколько реализаций (см. табл. 1.2).

Рис. 1.5

Мы поставили несколько экспериментов и определяли каждый раз, сколько необходимо было сделать опытов, то есть N кр э. Было проделано 10 экспериментов, результаты которых были сведены в табл. 1.2 По результатам 10-ти экспериментов было вычислено среднее значение N кр э.

Таблица 1.2.

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

Таким образом, проведя 10 реализаций разной длины, мы определили, что достаточно в среднем было сделать 1 реализацию длиной в 94 броска монеты.

Еще один важный факт. Внимательно рассмотрите график на рис.21.5 На нем нарисовано 100 реализаций - 100 красных линий. Отметьте на нем абсциссу N = 94 вертикальной чертой. Есть какой-то процент красных линий, которые не успели пересечь е -окрестность, то есть (P эксп - е ? P теор? P эксп + е ), и войти в коридор точности до момента N = 94. Обратите внимание, таких линий 5. Это значит, что 95 из 100, то есть 95%, линий достоверно вошли в обозначенный интервал.

Таким образом, проведя 100 реализаций, мы добились примерно 95% -ного доверия к полученной экспериментально величине вероятности выпадения орла, определив ее с точностью 0.1.

Для сравнения полученного результата вычислим теоретическое значение N кр т теоретически. Однако для этого придется ввести понятие доверительной вероятности Q F , которая показывает, насколько мы готовы верить ответу.

Например, при Q F = 0.95 мы готовы верить ответу в 95% случаев из 100. Имеет вид: N кр т = k (Q F ) · p · (1 - p ) /е 2 , где k (Q F ) - коэффициент Лапласа, p - вероятность выпадения орла, е - точность (доверительный интервал). В табл. 1.3 показаны значения теоретической величины количества необходимых опытов при разных Q F (для точности е = 0.1 и вероятности p = 0.5).

Таблица 1.3.

Теоретический расчет необходимого количества бросков монеты для достижения точности е = 0.1 при вычислении вероятности выпадения орла

Как видите, полученная нами оценка длины реализации, равная 94 опытам очень близка к теоретической, равной 96. Некоторое несовпадение объясняется тем, что, видимо, 10 реализаций недостаточно для точного вычисления N кр э. Если вы решите, что вам нужен результат, которому следует доверять больше, то измените значение доверительной вероятности. Например, теория говорит нам, что если опытов будет 167, то всего 1-2 линии из ансамбля не войдут в предложенную трубку точности. Но имейте в виду, количество экспериментов с ростом точности и достоверности растет очень быстро.

Второй вариант, используемый на практике - провести одну реализацию и увеличить полученное для нее N кр э в 2 раза . Это считают хорошей гарантией точности ответа (см. рис. 1.6).

Рис. 1.6. Иллюстрация экспериментального определения N кр э по правилу "умножь на два"

Если присмотреться к ансамблю случайных реализаций , то можно обнаружить, что сходимость частости к значению теоретической вероятности происходит по кривой, соответствующей обратной квадратичной зависимости от числа экспериментов (см. рис. 1.7).

Рис. 1.7

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

Таблица 1.4.

Теоретическая зависимость количества экспериментов, необходимых для обеспечения заданной точности при Q F = 0.95

Построим по табл. 1.4 график зависимости N кр т (е ) (см. рис. 1.8).

Рис. 1.8 Зависимость числа экспериментов, требуемых для достижения заданной точности е при фиксированном Q F = 0.95

Итак, рассмотренные графики подтверждают приведенную выше оценку:

Заметим, что оценок точности может быть несколько.

Пример 2. Нахождение площади фигуры методом Монте-Карло. Определите методом Монте-Карло площадь пятиугольника с координатами углов (0, 0), (0,10), (5, 20), (10,10), (7, 0).

Нарисуем в двухмерных координатах заданный пятиугольник, вписав его в прямоугольник, чья площадь, как нетрудно догадаться, составляет (10 - 0) · (20 - 0) = 200 (см. рис. 1.9).

Рис. 1.9

Используем таблицу случайных чисел для генерации пар чисел R , G , равномерно распределенных в интервале от 0 до 1. Число R X (0 ? X ? 10), следовательно, X = 10 · R . Число G будет имитировать координату Y (0 ? Y ? 20), следовательно, Y = 20 · G . Сгенерируем по 10 чисел R и G и отобразим 10 точек (X ; Y ) на рис. 1.9 и в табл. 1.5

Таблица 1.5.

Решение задачи методом Монте-Карло

Статистическая гипотеза заключается в том, что количество точек, попавших в контур фигуры, пропорционально площади фигуры: 6: 10 = S : 200. То есть, по формуле метода Монте-Карло, получаем, что площадь S пятиугольника равна: 200 · 6/10 = 120.

Проследим, как менялась величина S от опыта к опыту (см. табл. 1.6).

Таблица 1.6.

Оценка точности ответа

Поскольку в ответе все еще меняется значение второго разряда, то возможная неточность составляет пока больше 10%. Точность расчета может быть увеличена с ростом числа испытаний (см. рис. 1.10).

Рис. 1.10 Иллюстрация процесса сходимости определяемого экспериментально ответа к теоретическому результату

Лекция 2. Генераторы случайных чисел

В основе метода Монте-Карло (см. Лекцию 1. Статистическое моделирование) лежит генерация случайных чисел, которые должны быть равномерно распределены в интервале (0;1).

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

Математическое ожидание m r и дисперсия D r такой последовательности, состоящей из n случайных чисел r i , должны быть следующими (если это действительно равномерно распределенные случайные числа в интервале от 0 до 1):

Если пользователю потребуется, чтобы случайное число x находилось в интервале (a ; b ), отличном от (0;

• 1), нужно воспользоваться формулой x = a + (b - a ) · r , где r - случайное число из интервала (0;
• 1). Законность данного преобразования демонстрируется на рис. 2.1

Рис. 2.1

1) в интервал (a; b)

Теперь x - случайное число, равномерно распределенное в диапазоне от a до b .

За эталон генератора случайных чисел (ГСЧ) принят такой генератор, который порождает последовательность случайных чисел с равномерным законом распределения в интервале (0;

• 1). За одно обращение данный генератор возвращает одно случайное число. Если наблюдать такой ГСЧ достаточно длительное время, то окажется, что, например, в каждый из десяти интервалов (0; 0.1), (0.1; 0.2), (0.2; 0.3), …, (0.9;
• 1) попадет практически одинаковое количество случайных чисел - то есть они будут распределены равномерно по всему интервалу (0;
• 1). Если изобразить на графике k = 10 интервалов и частоты N i попаданий в них, то получится экспериментальная кривая плотности распределения случайных чисел (см. рис. 2.2).

Рис. 2.2

Заметим, что в идеале кривая плотности распределения случайных чисел выглядела бы так, как показано на рис. 2.3. То есть в идеальном случае в каждый интервал попадает одинаковое число точек: N i = N /k , где N - общее число точек, k - количество интервалов, i = 1, …, k .

Рис. 2.3

Следует помнить, что генерация произвольного случайного числа состоит из двух этапов:

• · генерация нормализованного случайного числа (то есть равномерно распределенного от 0 до 1);
• · преобразование нормализованных случайных чисел r i в случайные числа x i , которые распределены по необходимому пользователю (произвольному) закону распределения или в необходимом интервале.

Генераторы случайных чисел по способу получения чисел делятся на:

• · физические;
• · табличные;
• · алгоритмические.

Введение

Метод Монте-Карло – это численный метод решения математических задач при помощи моделирования случайных величин.

Датой рождение метода Монте-Карло принято считать 1949 г., когда появилась статья под названием «Метод Монте-Карло» (Н. Метрополис, С. Улам). Создателями этого метода считают американских математиков Дж. Неймана и С. Улама. В нашей стране первые статьи были опубликованы в 1955–56 гг. (В.В. Чавчанидзе, Ю.А. Шрейдер, В.С. Владимиров)

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

Само название «Монте-Карло» происходит от города Монте-Карло в княжестве Монако, знаменитого своим игорным домом, а одним из простейших механических приборов для получения случайных величин является рулетка.

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

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

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

1. Теоретическая часть

1.1 Сущность метода Монте-Карло и моделирование случайных величин

Предположим, что нам необходимо вычислить площадь плоской фигуры

. Это может быть произвольная фигура, заданная графически или аналитически (связная или состоящая из нескольких частей). Пусть это будет фигура, заданная на рис. 1.1.

Предположим, что эта фигура расположена внутри единичного квадрата.

Выберем внутри квадрата

случайных точек. Обозначим через число точек, попавших внутрь фигуры . Геометрически видно, что площадь фигуры приближенно равна отношению . Причем, чем больше число , тем больше точность этой оценки.

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

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

Непрерывная случайная величина

определяется заданием интервала , содержащего возможные значения этой величины, и функции , которая называется плотностью вероятностей случайной величины (плотностью распределения ). Физический смысл следующий: пусть - произвольный интервал, такой что , тогда вероятность того, что окажется в интервале , равна интегралу (1.1)

Множество значений

может быть любым интервалом (возможен случай ). Однако плотность должна удовлетворять двум условиям:

1) плотность

положительна: ; (1.2)

2) интеграл от плотности

по всему интервалу равен 1: (1.3)

Математическим ожиданием непрерывной случайной величины называется число

(1.4)

Дисперсией непрерывной случайной величины называется число:

Нормальной случайной величиной называется случайная величина

, определённая на всей оси и имеющая плотность (1.5) - числовые параметры

Любые вероятности вида

легко вычисляются с помощью таблицы, в которой приведены значения функции , называемой обычно интегралом вероятностей.

Согласно (1.1)

В интеграле сделаем замену переменной

, тогда получим , Отсюда следует, что Также

Нормальные случайные величины очень часто встречаются при исследовании самых различных по своей природе вопросов.