Лекционные материалы (стр. 1 )

Нижегородский государственный университет им.

Лекционные материалы.
Глава 1. Введение в методы Монте-Карло

Нижний Новгород

2005

Глава 1. Введение в методы Монте-Карло

Содержание

Введение. 3

Статистическое моделирование как научное направление. 5

Понятие статистического моделирования. 5

Схема проведения вычислений в статистическом моделировании. 5

Области применения статистического моделирования. 6

Метод статистических испытаний (методы Монте-Карло). История метода. 7

Методы Монте-Карло. Анализ общей схемы, достоинства и недостатки. 8

Примеры применения методов Монте-Карло. 9

Задача вычисления площади фигуры на плоскости. 10

Задача оценивания числа p. 11

Игла Бюффона. 11

Метод Hit-Or-Miss. 15

Метод Выборочного среднего. 16

Случайность и имитация случайности. 18

Случайность и непредсказуемость. 18

Случайные числа и генераторы случайных чисел. 19

Генераторы псевдослучайных чисел (PRNG) 19

Заключение. 22

Литература. 23

Введение

Если люди не полагают,
что математика проста,
то только потому,
что они не понимают,
как на самом деле сложна жизнь.

Джон фон Нейман

Добрый день, уважаемый читатель!

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

Статистическое моделирование – численный метод решения математических задач, при котором искомые величины представляют вероятностными характеристиками какого-либо случайного явления, это явление моделируется, после чего нужные характеристики приближённо определяют путём статистической обработки «наблюдений» модели [14].

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

Привязка содержания курса к параллельным вычислениям связана со следующими факторами:

-  задачи статистического моделирования как правило требуют больших вычислительных ресурсов;

-  алгоритмы статистического моделирования чаще всего допускают эффективное распараллеливание.

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

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

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

Автор курса надеется, что в результате изучения теоретической части Вы будете обладать следующим набором знаний:

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

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

-  Некоторые приемы тестирования качества генераторов случайных чисел.

-  Некоторые приемы вычисления многомерных интегралов методом Монте-Карло.

-  Некоторые задачи стохастической оптимизации (в частности, моделирование методом «имитации отжига»).

-  Некоторые задачи финансовой математики и алгоритмы их решения.

В дополнение к указанной выше теоретической информации лабораторный практикум призван помочь Вам приобрести некоторые практические навыки, в частности Вы будете уметь:

-  Использовать библиотеку Intel® MKL для решения задач статистического моделирования.

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

-  Проводить тестирование качества генераторов случайных чисел.

-  Проводить эксперименты на многопроцессорных и многоядерных системах.

Вы заинтересовались прочитанным? Постараюсь не обмануть Ваших ожиданий. В первом разделе курса мы познакомимся с идеологией статистического моделирования, методом статистических испытаний (методами Монте-Карло), историей его появления и развития. Мы поговорим об основных преимуществах и недостатках метода, областях его применения и деятельности первопроходцев в данной области. Наконец, мы проникнем в «сердце» метода – имитацию случайности. Итак, за дело!

Статистическое моделирование как научное направление

Прежде всего, попробуем поточнее понять, что скрывается за таинственным названием «Статистическое моделирование». Обратимся к Большой Советской Энциклопедии (БСЭ).

Понятие статистического моделирования

Статистическое моделирование – численный метод решения математических задач, при котором искомые величины представляют вероятностными характеристиками какого-либо случайного явления, это явление моделируется, после чего нужные характеристики приближённо определяют путём статистической обработки «наблюдений» модели. Например, требуется рассчитать потоки тепла в нагреваемой тонкой металлической пластине, на краях которой поддерживается нулевая температура. Распределение тепла описывается тем же уравнением, что и расплывание пятна краски в слое жидкости. Поэтому моделируют плоское броуновское движение частиц «краски» по пластине, следя за их положениями в моменты tk, k = 0, 1, 2,... Приближённо принимают, что за малый интервал t частица перемещается на шаг h равновероятно во всех направлениях. Каждый раз направление выбирается случайным образом, независимо от всего предыдущего. Соотношение между t и h определяется коэффициентом теплопроводности. Движение начинается в источнике тепла и кончается при первом достижении края (наблюдается налипание «краски» на край). Поток Q(C) тепла через участок С границы измеряется количеством налипшей краски. При общем количестве N частиц согласно закону больших чисел такая оценка даёт ошибку порядка . [14]

Схема проведения вычислений в статистическом моделировании

Статистическое моделирование предполагает следующую схему вычисления (оценивания) искомой величины. Так, искомую величину представляют математическим ожиданием числовой функции f от случайного исхода w некоторого явления:

, (1.1)

т. е. интегралом по вероятностной мере Р [14].

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

Рассмотрим оценку математического ожидания случайной величины

(1.2)

где – исходы, состоявшиеся в результате наблюдений.

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

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

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

Области применения статистического моделирования

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

Среди задач, где может быть использован и часто используется этот подход, часто указывают следующие задачи: [16, 18, 19, 20, 22]

-  численное интегрирование,

-  расчеты в системах массового обслуживания,

-  расчеты качества и надежности изделий,

-  расчеты прохождения нейтронов сквозь пластину,

-  передача сообщений при наличии помех,

-  задачи теории игр,

-  задачи динамики разреженного газа,

-  задачи дискретной оптимизации,

-  задачи финансовой математики (оценивание опционов и др.)

и многие другие.

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

Метод статистических испытаний (методы Монте-Карло). История метода

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