Введение в методы Монте-Карло
Статистическое моделирование как научное направление, области его применения. Методы Монте-Карло: анализ общей схемы, достоинства, недостатки и примеры применения. Случайные числа, генераторы случайных и псевдослучайных чисел. Метод Hit-Or-Miss.
| Рубрика | Математика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 18.07.2013 |
| Размер файла | 138,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Нижегородский государственный университет им. Н.И. Лобачевского
Лекционные материалы
Введение в методы Монте-Карло
Нижний Новгород
2005
Введение
Если люди не полагают,
что математика проста,
то только потому,
что они не понимают,
как на самом деле сложна жизнь.
Джон фон Нейман
Добрый день, уважаемый читатель!
Прежде всего, хотелось бы кратко охарактеризовать курс, который Вы начинаете изучать. Начнем с расшифровки названия «Статистическое моделирование и параллельные вычисления».
Статистическое моделирование - численный метод решения математических задач, при котором искомые величины представляют вероятностными характеристиками какого-либо случайного явления, это явление моделируется, после чего нужные характеристики приближённо определяют путём статистической обработки «наблюдений» модели [?14].
Статистическое моделирование - молодое и перспективное научное направление, получившее развитие в середине двадцатого века в связи с ростом возможностей вычислительной техники. Рассматриваемое научное направление имеет массу приложений в разных областях знания (биология, химия, физика, экономика и др.), что делает его изучение особенно актуальным.
Привязка содержания курса к параллельным вычислениям связана со следующими факторами:
- задачи статистического моделирования как правило требуют больших вычислительных ресурсов;
- алгоритмы статистического моделирования чаще всего допускают эффективное распараллеливание.
Данный курс предназначен для студентов старших курсов, магистрантов, обучающихся по специальностям «Прикладная математика», «Информационные технологии», «Информационные системы» и стажеров студенческих лабораторий, обучающихся на факультетах физико-математического профиля.
Целью курса является ознакомление с некоторыми задачами и алгоритмами статистического моделирования и методами генерации псевдослучайных чисел, а также рассмотрение основных методов распараллеливания данных задач и их эффективной реализации на многоядерных и многопроцессорных архитектурах.
В качестве дополнительной цели выступает знакомство с некоторыми индустриальными математическими пакетами, позволяющими решать задачи статистического моделирования.
Автор курса надеется, что в результате изучения теоретической части Вы будете обладать следующим набором знаний:
- Общая схема методов Монте-Карло, принципы ее реализации при помощи вычислительной техники.
- Основные классы линейных генераторов, основные методы генерации случайных чисел неравномерных распределений, способы их применения в параллельных вычислениях.
- Некоторые приемы тестирования качества генераторов случайных чисел.
- Некоторые приемы вычисления многомерных интегралов методом Монте-Карло.
- Некоторые задачи стохастической оптимизации (в частности, моделирование методом «имитации отжига»).
- Некоторые задачи финансовой математики и алгоритмы их решения.
В дополнение к указанной выше теоретической информации лабораторный практикум призван помочь Вам приобрести некоторые практические навыки, в частности Вы будете уметь:
- Использовать библиотеку Intel® MKL для решения задач статистического моделирования.
- Самостоятельно реализовывать генераторы случайных чисел различных распределений.
- Проводить тестирование качества генераторов случайных чисел.
- Проводить эксперименты на многопроцессорных и многоядерных системах.
Вы заинтересовались прочитанным? Постараюсь не обмануть Ваших ожиданий. В первом разделе курса мы познакомимся с идеологией статистического моделирования, методом статистических испытаний (методами Монте-Карло), историей его появления и развития. Мы поговорим об основных преимуществах и недостатках метода, областях его применения и деятельности первопроходцев в данной области. Наконец, мы проникнем в «сердце» метода - имитацию случайности. Итак, за дело!
1. Статистическое моделирование как научное направление
Прежде всего, попробуем поточнее понять, что скрывается за таинственным названием «Статистическое моделирование». Обратимся к Большой Советской Энциклопедии (БСЭ).
1.1 Понятие статистического моделирования
Статистическое моделирование - численный метод решения математических задач, при котором искомые величины представляют вероятностными характеристиками какого-либо случайного явления, это явление моделируется, после чего нужные характеристики приближённо определяют путём статистической обработки «наблюдений» модели. Например, требуется рассчитать потоки тепла в нагреваемой тонкой металлической пластине, на краях которой поддерживается нулевая температура. Распределение тепла описывается тем же уравнением, что и расплывание пятна краски в слое жидкости. Поэтому моделируют плоское броуновское движение частиц «краски» по пластине, следя за их положениями в моменты tk, k = 0, 1, 2,... Приближённо принимают, что за малый интервал t частица перемещается на шаг h равновероятно во всех направлениях. Каждый раз направление выбирается случайным образом, независимо от всего предыдущего. Соотношение между t и h определяется коэффициентом теплопроводности. Движение начинается в источнике тепла и кончается при первом достижении края (наблюдается налипание «краски» на край). Поток Q(C) тепла через участок С границы измеряется количеством налипшей краски. При общем количестве N частиц согласно закону больших чисел такая оценка даёт ошибку порядка . [14]
1.2 Схема проведения вычислений в статистическом моделировании
Статистическое моделирование предполагает следующую схему вычисления (оценивания) искомой величины. Так, искомую величину представляют математическим ожиданием числовой функции f от случайного исхода w некоторого явления:
, (1.1)
т. е. интегралом по вероятностной мере Р [14].
Таким образом, для того, чтобы оценить некоторое значение, необходимо подобрать случайную величину так, чтобы ее математическое ожидание равнялось искомому значению. После этого можно пронаблюдать случайную величину и оценить по выборке ее математическое ожидание. Полученный результат можно считать оценкой искомого значения.
Рассмотрим оценку математического ожидания случайной величины
(1.2)
где - исходы, состоявшиеся в результате наблюдений.
Оценку (1.2) можно рассматривать как квадратурную формулу для указанного интеграла со случайными узлами и случайной погрешностью .
Таким образом, рассматриваемая схема состоит в проведении серии экспериментов. Каждый i-ый эксперимент представляет собой получение случайного исхода и вычисление функции f(). После этого производятся вычисления по формуле (1.2) и полученный результат считается оценкой искомой величины.
Случайный выбор на каждом этапе проводится с помощью случайных чисел, которые необходимо генерировать тем или иным образом. Так, они могут генерироваться каким-либо физическим датчиком или имитироваться при помощи вычислительной техники по некоторому алгоритму, обеспечивающему заданное распределение (псевдослучайные числа). На эту тему мы еще поговорим в наших лекциях.
1.3 Области применения статистического моделирования
Статистическое моделирование широко применяется для решения задач из различных областей человеческого знания. Среди них такие актуальные области как биология, химия, физика, экономика и другие.
Среди задач, где может быть использован и часто используется этот подход, часто указывают следующие задачи: [16, 18, 19, 20, 22]
- численное интегрирование,
- расчеты в системах массового обслуживания,
- расчеты качества и надежности изделий,
- расчеты прохождения нейтронов сквозь пластину,
- передача сообщений при наличии помех,
- задачи теории игр,
- задачи динамики разреженного газа,
- задачи дискретной оптимизации,
- задачи финансовой математики (оценивание опционов и др.)
и многие другие.
Часть этих задачи имеют очевидную вероятностную природу (что характерно, например, для систем массового обслуживания или финансовой математики), а часть являют собой пример применения идей статистического моделирования для исследования математических моделей объектов, не имеющих таковой (например, вычисление определенного интеграла).
2. Метод статистических испытаний (методы Монте-Карло). История метода
Говоря о статистическом моделировании, люди часто подразумевают, что речь идет о так называемом методе статистических испытаний (методах Монте-Карло). Обратимся к БСЭ.
Метод статистических испытаний - метод вычислительной и прикладной математики, основанный на моделировании случайных величин и построении статистических оценок для искомых величин; то же, что Монте-Карло методы. Принято считать, что метод статистических испытаний возник в 1944 году, когда в связи с работами по созданию атомных реакторов американские учёные Дж. фон Нейман и С. Улам начали широко применять аппарат теории вероятностей для решения прикладных задач с помощью ЭВМ. Первоначально метод использовался главным образом для решения сложных задач теории переноса излучения и нейтронной физики, где традиционные численные методы оказались мало пригодными. Затем его влияние распространилось на больший класс задач статистической физики, очень разных по своему содержанию. Метод применяется для решения задач теории игр, теории массового обслуживания и математической экономики, задач теории передачи сообщений при наличии помех и т.д. [14]
Итак, таинственное название «Методы Монте-Карло». Откуда оно взялось и что стоит за этим звучным наименованием? Попробуем разобраться, для чего обратимся к истории.
Некоторые эксперименты по использованию метода статистических испытаний проводились достаточно давно. Так, еще французский естествоиспытатель Бюффон выполнял эксперименты по вычислению числа путем подбрасывания иглы и вычисления частоты пересечения иглы одной из параллельных прямых. В 1930 году Э. Ферми использовал то, что сейчас носит название методов Монте-Карло, в исследовании нейтронных потоков. Позже, он разработал «Fermiac», механическое устройство, которое использовалось в вычислениях в задачах ядерной физики. Настоящее распространение идей, связанных с подобными методами, стало реальностью с началом эры вычислительной техники, которая позволила проводить компьютерные эксперименты, в том числе и по получению случайных чисел.
Пионерами методов Монте-Карло принято считать американских математиков Стэнли Улама, Джона фон Неймана и Николаса Метрополиса. В сороковых годах XX века Джон фон Нейман заложил основу методов Монте-Карло, создав математический базис для функций плотности вероятности, интегральных функций обратного распределения и генераторов псевдослучайных чисел. Исследования выполнялись в тесном сотрудничестве со Стэнли Уламом, считается, что именно он первым осознал и продвинул в массы идею о необходимости компьютера для выполнения вычислений по методам Монте-Карло.
Происхождение названия методов связано с одноименным городом в княжестве Монако, в котором расположены одни из самых известных казино в мире. Дело в том, что случайные числа и их генерация составляют «сердце» методов Монте-Карло. Рулетка казино - один из наиболее простых приборов для генерации случайных чисел Заметим для любопытных читателей, что как справедливо подчеркнул в своей книге [?21] И.М. Соболь, метод Монте-Карло никак не помогает выигрывать в рулетку и вообще не имеет к этому никакого отношения!. Именно это и явилось наводящим соображением для названия. Как писал Стэнли Улам в автобиографии «Приключения математика», метод был назван в честь его дяди, который был заядлым игроком, по совету Метрополиса.
Датой рождения методов Монте-Карло принято считать 1949 год, когда появилась статья Улама и Метрополиса «Метод Монте-Карло» [8]. Как это часто бывало в истории науки, основным побуждающим фактором в развитии статистического моделирования стали военные исследования по заказу Министерства обороны США. Далее эти исследования не стали носить секретного характера, и результаты были успешно внедрены в разных областях, благодаря общности схемы метода и отсутствию привязки к конкретному объекту или предметной области.
Еще один интересный факт связан с тем, что некие случайные методы вычислений и проведения экспериментов разрабатывались и применялись и в «доисторическую компьютерную эру». Основная разница методов Монте-Карло с ранними исследованиями в области статистического моделирования заключается в следующем: Монте-Карло моделирование перевернуло стандартные представления о том, как нужно решать задачу, используя средства теории вероятности и математической статистики. Так, ранее предполагалось, что необходимо изучить детерминированную проблему, а потом использовать имитацию, чтобы проверить сделанные ранее выкладки. В Монте-Карло моделировании предполагается, что надо взять детерминированную проблему и найти ее стохастический аналог. Эта идея стала общим принципом, применимым для решения задач различной природы, благодаря фон Нейману, Метрополису и Уламу.
2.1 Методы Монте-Карло. Анализ общей схемы, достоинства и недостатки
Итак, для решения задачи по методам Монте-Карло прежде всего строят вероятностную модель, представляют искомую величину, например многомерный интеграл, в виде математического ожидания функционала от случайного процесса, который затем моделируется на компьютере [14]. В результате проведения вычислительного эксперимента получают нужную выборку и результаты всех испытаний усредняют [22].
Принципиальная математическая основа использования методов Монте-Карло - Усиленный закон больших чисел в форме А.Н. Колмогорова.
2.2 Теорема Колмогорова
Для того чтобы среднее арифметическое независимых реализаций случайной величины сходилось с вероятностью единица к ее математическому ожиданию необходимо и достаточно, чтобы это математическое ожидание существовало.
Итак, первое несомненное достоинство методов Монте-Карло - простая схема вычислительного алгоритма.
Поговорим о некоторых трудностях, которые могут встретиться нам на пути применения рассмотренного подхода. Заметим, что нам нужна не любая, а достаточно достоверная оценка искомой величины, т.е. оценка с малой погрешностью. Добиться этого далеко не так просто, как кажется. Большую роль, разумеется, играет адекватность построенной вероятностной модели (такие модели во многих задачах известны).
Следующая важная составляющая - моделирование случайных величин с заданными распределениями. Как правило, такое моделирование осуществляется путём преобразования одного или нескольких независимых значений случайного числа a, распределённого равномерно в интервале (0,1). Последовательности «выборочных» значений a обычно получают на ЭВМ с помощью теоретико-числовых алгоритмов, среди которых наибольшее распространение получил «метод вычетов». Такие числа называются «псевдослучайными», они проверяются статистическими тестами и решением типовых задач [14]. Итак, существенную роль играет качество используемых генераторов случайных чисел. Написание корректных генераторов - сложная задача, успешно решаемая в рамках разных научных и инженерных математических библиотек, например, в одной из лучших из них - Intel® Math Kernel Library (Intel® MKL), которой мы будем неоднократно пользоваться в рамках нашего курса.
Продолжая разговор о точности вычислений, посмотрим на этот вопрос немного с другой стороны. Как известно, ошибка вычислений по методу Монте-Карло обычно пропорциональна , где d - некоторая константа, а N - количество испытаний. Из формулы очевидно, что для повышения точности в 10 раз необходимо увеличить количество испытаний в 100 раз [22], а это значит, что метод Монте-Карло требует больших вычислительных ресурсов.
2.3 Примеры применения методов Монте-Карло
В данном разделе мы рассмотрим некоторые примеры применения методов Монте-Карло в практических задачах. Как Вы увидите, речь пойдет об известных математических задачах - вычислении площади фигуры и определении числа . Выбор данных задач вовсе не означает, что именно в них методы Монте-Карло ведут себя особенно эффективно, напротив, в этих задачах, как правило, применяются другие способы достижения результата. Дело в том, что в ходе изучения курса мы неоднократно будем встречаться с примерами применения методов Монте-Карло в реальных экономических, физических, математических задачах. Каждая из таких задач требует некоторой подготовки, как с точки зрения изучения метода статистических испытаний, так и подробного рассмотрения собственно постановки задачи. Поэтому в этом разделе мы и рассматриваем иллюстративные, сравнительно несложные примеры. Итак, для начала совсем простой пример.
2.4 Задача вычисления площади фигуры на плоскости
Пусть дана некоторая плоская фигура F, для которой требуется найти площадь.
Введем следующие предположения:
1. Для определенности предположим, что эта фигура целиком расположена внутри единичного квадрата.
2. С учетом предположения 1 периметр фигуры может быть устроен совершенно произвольно.
3. Фигура может не быть связной, т.е. может состоять из нескольких областей.
4. Фигура может быть задана аналитически или графически.
Размещено на http://www.allbest.ru/
Рис. 1.1 Площадь фигуры на плоскости. Метод Монте-Карло
Сгенерируем в квадрате N случайных точек (рис. 1.1). Пусть N* - количество точек, попавших внутрь рассматриваемой фигуры.
Тогда при достаточно больших значениях N площадь фигуры F может быть оценена как
(1.3)
Конечно, в задаче вычисления площади существуют и более точные алгоритмы нахождения площади, но данный пример демонстрирует простейший случай применения метода Монте-Карло.
2.5 Задача оценивания числа
История числа -
изящное маленькое зеркало
истории человечества.
Петр Бекманн
Из школьного прошлого всем известно, что число есть отношения длины окружности к ее диаметру. С древних времен внимание человечества было приковано к вычислению этого замечательного числа. Первоначально, заметив, что искомое отношение постоянно и не зависит от окружности, люди пытались представить его рациональной дробью. Такие попытки предпринимались в Древнем Египте, Индии, Древней Греции. Постепенно ученые осознали бесплодность попыток найти рациональную дробь, представляющую число , и дело сдвинулось с мертвой точки. Так Архимед, в III в до н.э. создал некоторый алгоритм приближенного вычисления и определил, что = 3.1419... [4]. Далее более точные решения были найдены в Древнем Китае, в Самарканде. В Европе результатами в данной области отметились Виет, Джонсон, Эйлер, ван Цейлен, Лежандр (доказал иррациональность числа), Лейбниц, Малчин.
Известен одновременно забавный и грустный факт, состоящий в том, что после более чем 20 лет работы в конце XIX века англичанин В. Шенкс нашел 707 знаков числа, но в 1945 году при помощи компьютера определили, что он ошибся в 520-м знаке и дальнейшие вычисления оказались неверными.
В эру современных компьютеров не составляет проблемы вычислить число с необходимой точностью (так, в 2002 году было вычислено 1 241 100 000 000 знаков числа). Все эти вычисления обычно проводятся при помощи суммирования некоторых рядов.
Мы в данном разделе рассмотрим подход к нахождению числа методом статистического моделирования.
2.6 Игла Бюффона
В 1777 году французский естествоиспытатель Жорж Луи Леклерк де Бюффон Georges Louis Leclerc Comte de Buffon (7.09.1707 - 16.04.1788, Франция) сформулировал задачу о нахождении вероятности того, что брошенная на разграфленный лист бумаги игла пересечет одну из линий. Оказалось, что эта вероятность связана с числом , что сделало возможным поиск этого числа вероятностными методами, т.е. методом Монте-Карло! Эта задача захватила умы многих исследователей. И сейчас, уважительно называемая теоремой, она имеет ряд интересных приложений [23].
Изучим проблему с точки зрения математики.
Для этого рассмотрим на плоскости параллельные прямые x = 0 и x = d, образующие бесконечную полосу ширины d. Пусть теперь мы произвольным образом бросаем на плоскость иглу длины . Вопрос: какова вероятность того, что игла пересечет одну из прямых?
Для решения задачи посмотрим на рис. 1.2.
Размещено на http://www.allbest.ru/
Рис. 1.2 Игла Бюффона. Положение иглы
Интересующее нас положение иглы на плоскости (y-координата неинтересна) описывается двумя параметрами (двумя независимыми случайными величинами): координатой одного из концов h и углом поворота относительно горизонтальной оси . Очевидно, .
Множество возможных положений иглы целиком определяется случайным выбором точки из области F(h, ) = .
Рассмотрим событие A - игла пересекает по прямую x = d.
(1.4)
Нарисуем в плоскости область, соответствующую событию A.
Размещено на http://www.allbest.ru/
Рис. 1.3 Игла Бюффона. Условие пересечения
Найдем площадь S+ этой области. Обозначим через S площадь всего прямоугольника, отвечающего пространству элементарных исходов, а S- - площадь под кривой
По определению S = S+ + S-.
Найдем .
Теперь вероятность события A может быть вычислена как
Итак, вероятность того, что игла пересечет прямую теоретически есть
(1.5)
Будем проводить эксперимент по бросанию иглы N раз, регистрируя в каждом эксперименте факт наступления/не наступления события A.
Рассмотрим случайную величину .
Введем частота наступления события A.
Тогда , причем данные исходы не равновероятны.
Известно, что случайная величина подчиняется биномиальному распределению. Определим параметры распределения.
Будем рассматривать - частоту наступления события A - в качестве оценки величины p - вероятности того, что игла пересекает одну из прямых. Зная теоретическую вероятность этого события , мы можем оценить эту вероятность по достаточно большой выборке () и рассмотреть следующее равенство:
(1.6)
Тогда
(1.7)
Попробуем понять, насколько хороша оценка (1.7).
Для этого докажем ряд утверждений.
Утверждение
, т.е. - несмещенная оценка значения p.
Доказательство:
Учитывая, что величина SN есть результат выполнения N независимых испытаний (биномиальное распределение), имеем:
, ч.т.д.
Несложно показать, что - эффективная оценка p (оценка с наименьшей дисперсией), а также состоятельная оценка p (сходится по вероятности - определение сходимости по вероятности. к p).
Итак, говоря неформальным языком, найденная нами оценка является довольно неплохой при достаточно большом количестве испытаний N. Рассмотрим вопрос, связанный с еще одним крайне желательным свойством оценки - уменьшением ее дисперсии.
Для того чтобы подобрать параметры эксперимента так, чтобы дисперсия была минимальной, необходимо решить задачу минимизации
(1.8)
Решив задачу, получаем, что минимум достигается при l = d.
Тогда .
Для исключения вырожденного случая SN = 0 определим нашу оценку числа следующим образом:
(1.9)
Можно показать, что оценка (1.9) сходится по вероятности к .
2.7 Метод Hit-Or-Miss
Еще один метод оценивания числа называется Hit-Or-Miss («попал - не попал»). Метод состоит в следующем: рассмотрим единичный квадрат на координатной плоскости и четверть окружности единичного радиуса с центром в начале координат (рис. 1.4).
Размещено на http://www.allbest.ru/
Рис. 1.4 Метод Hit-Or-Miss
Пусть единичный эксперимент состоит в том, что в единичном квадрате случайно выбирается любая точка. Рассмотрим событие A, состоящее в том, что точка попала в рассматриваемый сектор окружности.
Площадь квадрата Smax = 1, площадь выделенной области .
Рассмотрим случайную величину .
Введем частота наступления события A.
Тогда , случайная величина подчиняется биномиальному распределению. Определим параметры распределения.
Будем рассматривать - частоту наступления события A - в качестве оценки величины p - вероятности того, что точка попала в указанный сектор окружности. Зная теоретическую вероятность этого события , мы можем оценить эту вероятность по достаточно большой выборке () и рассмотреть следующее равенство:
(1.10)
Тогда можно рассмотреть
(1.11)
, таким образом (1.11) дает несмещенную оценку.
2.8 Метод Выборочного среднего
Рассмотрим функцию .
Рассмотрим .
Заметим, что что определяет функцию q(x) - плотность равномерного распределения на отрезке [0; 1].
Тогда
где . (1.12)
При этом - случайная величина, равномерно распределенная отрезке [0, 1].
Введем
Будем использовать в качестве оценки числа
(1.13)
Данная оценка также является несмещенной.
3. Случайность и имитация случайности
Всякий, кто питает слабость
к арифметическим методам
получения случайных чисел,
грешен вне всяких сомнений.
Джон фон Нейман
В данном разделе мы кратко коснемся инструментального аппарата методов Монте-Карло - случайных чисел и способов их получения.
3.1 Случайность и непредсказуемость
Случайность - интереснейшая тема, рассмотрением которой издревле занималась не только математика, но и философия, теология… Судя по всему, одни из первых замеченных людьми проявлений случайности - это гадание и игра. Гадание - определение судьбы человека по неким магическим надписям и событиям, и карточные игры со всеми своими атрибутами, несомненно, являют собой яркие примеры того, как случайность в отличие от свободного выбора влияет на жизнь человека. Разница между свободным выбором и определенностью всегда являлась предметом ожесточенных споров в философии и теологии.
Хотя азартные игры и гадание были приняты у многих культур и во многих странах, на них почти всюду долго существовало некоторое гласное или негласное табу. В лучшем случае, это считалось чем-то неприличным. Скорее всего, основой такого отношения явились церковные запреты. Тем не менее, еще Галилей и Кардано писали про азартные игры и проявление случайности, а Паскаль, Ферма и Гюйгенс направили исследования в направлении сегодняшней теории вероятности.
В первую очередь математики фокусировали внимание на статистической случайности и изучали частоты появления отдельных элементов и блоков элементов при экспериментах в качестве меры случайности. Впоследствии этот подход был расширен в теории информации (понятие энтропии - меры хаотичности информации). В 60-х годах XX века математики Колмогоров, Хаитин и Соломонофф независимо друг от друга представили важное понятие, которое известно как Колмогоровская сложность. В поисках точного и универсального определения закономерности и хаотичности они пришли к выводу, что оптимальной единицей измерения сложности любой информации является длина наиболее короткой программы, способной генерировать данную информацию.
Случайность не нужно путать с непредсказуемостью. Часть систем могут рассматриваться как случайные, но предсказуемые, а часть таковыми не являются. Действительно, рассматривая демографическую ситуацию в мире и рост популяции человечества, мы можем считать этот рост случайным, хотя он в целом является предсказуемым. Напротив, время жизни и точное время смерти каждого конкретного человека является не только случайным, но и непредсказуемым.
Непредсказуемость крайне необходима в некоторых приложениях, таких как, например, криптография. Напротив, при имитации, как правило, требуется предсказуемость При подготовке раздела использованы материалы Интернет-библиотеки Wikipedia..
Подводя некоторые итоги сказанному, необходимо отметить тот факт, что случайность по сей день остается сложной и актуальной проблемой современной науки, находящей массу приложений на практике.
3.2 Случайные числа и генераторы случайных чисел
В вычислениях, генераторы случайных чисел - устройства, которые генерируют эти числа из непредсказуемого физического процесса.
Допустим, мы хотим обеспечить настоящую «случайность» при получении чисел. Как это сделать? Получить их из какого-то процесса, который мы не только не контролируем полностью, но и не можем предсказывать. Устройства, базирующиеся на таких процессах, обычно работают с микроскопическими явлениями, такими как термический шум, фотоэффект или квантовые явления. Теоретически, эти процессы полностью непредсказуемы.
Обычно, квантовые генераторы случайных чисел содержат усилитель, который превращает выход физического процесса в некоторые макроскопические параметры, которые можно регистрировать, и преобразователь, который конвертирует выход процесса в цифровой сигнал.
Генераторы случайных чисел могут быть также получены из макроскопических явлений, таких как, например, игральные карты, игральные кости, рулетка. Их непредсказуемость связана с теорией неустойчивых динамических систем и теорией хаоса. Эти теории утверждают, что хотя макроскопические явления и являются детерминированными в рамках Ньютоновой механики, реальные системы развиваются непредсказуемо на практике из-за необходимости знания всех начальных условий. Заметим также, что эта необходимая точность начальных условий растет экспоненциально с ростом времени.
Реальные физические процессы являются сложными, трудно наблюдаемыми, плохо предсказуемыми. Таким образом, использование генераторов случайных чисел на основе физических процессов на практике сильно затруднено. Вместо них обычно используют так называемые генераторы псевдослучайных чисел4.
3.3 Генераторы псевдослучайных чисел (PRNG)
Генератор псевдослучайных чисел (ГПСЧ, PRNG) -- алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению. Никакой детерминированный алгоритм не может генерировать полностью случайные числа, а только лишь аппроксимировать некоторые свойства случайных чисел. При подготовке раздела использованы материалы Интернет-библиотеки Wikipedia.
Поскольку качество используемых случайных чисел проверяется с помощью специальных тестов, можно не интересоваться тем, как эти числа получены: лишь бы они удовлетворяли принятой системе тестов. Числа, получаемые по какой-либо формуле и имитирующие значения случайной величины, называются псевдослучайными числами. Под словом «имитирующие» подразумевается, что эти числа удовлетворяют ряду тестов так, как если бы они были значениями этой случайной величины. [22]
Первый алгоритм для получения псевдослучайных чисел был предложен Джоном фон Нейманом. Он называется методом середины квадратов. Поясним его на примере. Пусть задано 4-значное целое число n1 = 9876. Возведем его в квадрат. Получим, вообще говоря, 8-значное число 97 535 376. Выберем четыре средние цифры из этого числа и обозначим n2 = 5353. Затем возведем его в квадрат (28 654 609) и снова извлечем 4 средние цифры. Получим n3 = 6546. Далее, 42 850116, n4 = 8501 и т. д. В качестве значений случайной величины предлагалось использовать значения 0,9876; 0,5353; 0,6546; 0,8501; 0,2670; 0,1289 и т. д. [22]
Но этот алгоритм не оправдал себя: получалось больше чем нужно малых значений. Поэтому разными исследователями были разработаны другие алгоритмы. Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, linear feedback shift registers, generalized feedback shift registers.
Из современных ГПСЧ широкое распространение получил Mersenne twister, предложенный в 1997 году Мацумото и Нишимурой. Его достоинствами являются колоссальный период (219937-1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение от силы в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако существуют сложные алгоритмы, распознающие последовательность, порождаемую с помощью Mersenne twister, как неслучайную. Это в частности делает Mersenne twister неподходящим для криптографии.
Достоинства метода псевдослучайных чисел довольно очевидны.
Во-первых, на получение каждого числа затрачивается всего несколько простых операций, так что скорость генерирования случайных чисел зависит от скорости работы компьютера.
Во-вторых, любое из чисел может быть легко воспроизведено.
В-третьих, нужно лишь один раз проверить «качество» такой последовательности, затем ее можно много раз безбоязненно использовать при расчете сходных задач.
Один из главных недостатков метода - ограниченность «запаса» псевдослучайных чисел (наличие периода, ГПСЧ рано или поздно зацикливается). Однако существуют генераторы с очень большим периодом. Подавляющее большинство расчетов по методам Монте-Карло в настоящее время осуществляется с использованием псевдослучайных чисел. По материалам Wikipedia и книги Соболя [?22]
Заключение
Итак, в данном разделе мы заложили фундамент для дальнейшего рассмотрения материалов курса. Так, мы познакомились со следующими основными понятиями и фактами:
- статистическое моделирование;
- метод статистических испытаний (методы Монте-Карло);
- общая схема методов Монте-Карло;
- области применения статистического моделирования;
- примеры применения методов Монте-Карло;
- случайность;
- непредсказуемость;
- случайные числа;
- псевдослучайные числа;
- генераторы случайных чисел;
- генераторы псевдослучайных чисел.
В следующих разделах мы поговорим об этом подробнее.
статистическое моделирование монте карло
Литература
1. Gamerman, D. Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference. Boca Raton, FL: CRC Press, 1997.
2. Gentle J. Random Number Generation and Monte Carlo Methods. Springer-Verlag NY, 1998.
3. Gilks, W. R.; Richardson, S.; and Spiegelhalter, D. J. (Eds.). Markov Chain Monte Carlo in Practice. Boca Raton, FL: Chapman & Hall, 1996.
4. Gourdon X., Sebah P. and its computation through the ages. April 16, 2003. [http://numbers.computation.free.fr/Constants/constants.html]
5. Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdos and the Search for Mathematical Truth. New York: Hyperion, pp. 238-239, 1998.
6. Kuipers, L. and Niederreiter, H. Uniform Distribution of Sequences. New York: Wiley, 1974.
7. Manno, I. Introduction to the Monte Carlo Method. Budapest, Hungary: Akadйmiai Kiadу, 1999.
8. Metropolis N., Ulam S. The Monte Carlo method, J. Amer. statistical assoc., 1949, 44, N247, 335-341.
9. Metropolis, N. "The Beginning of the Monte Carlo Method." Los Alamos Science, No. 15, p. 125. [http://jackman.stanford.edu/mcmc/metropolis1.pdf]
10. Mikhailov, G. A. Parametric Estimates by the Monte Carlo Method. Utrecht, Netherlands: VSP, 1999.
11. Niederreiter, H. and Spanier, J. (Eds.). Monte Carlo and Quasi-Monte Carlo Methods 1998, Proceedings of a Conference held at the Claremont Graduate University, Claremont, California, USA, June 22-26, 1998. Berlin: Springer-Verlag, 2000.
12. Sobol, I. M. A Primer for the Monte Carlo Method. Boca Raton, FL: CRC Press, 1994.
13. Weisstein Eric W. "Monte Carlo Method." From MathWorld - A Wolfram Web Resource. [http://mathworld.wolfram.com/MonteCarloMethod.html]
14. Большая Советская Энциклопедия. Издание 3-е.-М., Советская энциклопедия, 1970.
15. Бусленко Н.П., Голенко Д.И., Соболь И.М., Срагович В.Г., Шреацидер Ю.А. Метод стохастических испытаний (метод Монте-Карло).-М.: ГИМФЛ, 1962.
16. Бусленко Н.П., Шрейдер Ю.А. Метод статистических испытаний Монте-Карло и его реализация в цифровых машинах.-Физматгиз, 1961.
17. Гмурман В.Е. Теория вероятности и математическая статистика.-М.: Высшая школа, 1977.
18. Ермаков С. М. Метод Монте-Карло и смежные вопросы.-М., 1971.
19. Ермаков С.М., Михайлов Г.А. Статистическое моделирование. М: Наука, 1982.
20. Ермаков С.Н., Михайлов Г.А. Курс статистического моделирования.- М.:Наука, 1976.
21. Крамер Г.. Математические методы статистики. М: Мир, 1975.
22. Соболь И.М. Численные методы Монте-Карло.-М.:Наука, 1973.
23. Тепляков А. Моделируя жизнь // Hard'n'soft, №8, 2001. [http://www.hardnsoft.ru/magazine.php?issue=86&article=18&page=2]
Размещено на Allbest.ru
...Подобные документы
Математическое обоснование алгоритма вычисления интеграла. Принцип работы метода Монте–Карло. Применение данного метода для вычисления n–мерного интеграла. Алгоритм расчета интеграла. Генератор псевдослучайных чисел применительно к методу Монте–Карло.
курсовая работа [100,4 K], добавлен 12.05.2009Некоторые сведения теории вероятностей. Математическое ожидание, дисперсия. Точность оценки, доверительная вероятность. Доверительный интервал. Нормальное распределение. Метод Монте-Карло. Вычисление интегралов методом Монте-Карло. Алгоритмы метода.
курсовая работа [112,9 K], добавлен 20.12.2002Исследование способа вычисления кратных интегралов методом Монте-Карло. Общая схема метода Монте-Карло, вычисление определенных и кратных интегралов. Разработка программы, выполняющей задачи вычисления значений некоторых примеров кратных интегралов.
курсовая работа [349,3 K], добавлен 12.10.2009Метод Монте-Карло як метод моделювання випадкових величин з метою обчислення характеристик їхнього розподілу, оцінка похибки. Обчислення кратних інтегралів методом Монте-Карло, його принцип роботи. Приклади складання програми для роботи цим методом.
контрольная работа [41,6 K], добавлен 22.12.2010Метод Гаусса, метод прогонки, нелинейное уравнение. Метод вращения Якоби. Интерполяционный многочлен Лагранжа и Ньютона. Метод наименьших квадратов, интерполяция сплайнами. Дифференцирование многочленами, метод Монте-Карло и Рунге-Кутты, краевая задача.
курсовая работа [4,8 M], добавлен 23.05.2013Многие переменные, минимизация их функций. Точки максимума и минимума называются точками экстремума функции. Условия существования экстремумов функции многих переменных. Квадратичная форма, принимающая, как положительные, так и отрицательные значения.
реферат [70,2 K], добавлен 05.09.2010Способы получения псевдослучайных чисел. Общая характеристика генератора псевдослучайных чисел фон Неймана. Сущность равномерного закона распределения. Понятие о критериях согласия. Анализ критериев Пирсона и Колмогорова.
курсовая работа [176,9 K], добавлен 28.04.2010Получение интервальной оценки. Построение доверительного интервала. Возникновение бутстрапа или практического компьютерного метода определения статистик вероятностных распределений, основанного на многократной генерации выборок методом Монте-Карло.
курсовая работа [755,6 K], добавлен 22.05.2015Основные определения теории уравнений в частных производных. Использование вероятностных, численных и эмпирических методов в решении уравнений. Решение прямых и обратных задач методом Монте-Карло на примере задачи Дирихле для уравнений Лапласа и Пуассона.
курсовая работа [294,7 K], добавлен 17.06.2014Понятие математического моделирования: выбор чисел случайным образом и их применение. Критерий частот, серий, интервалов, разбиений, перестановок, монотонности, конфликтов. Метод середины квадратов. Линейный конгруэнтный метод. Проверка случайных чисел.
контрольная работа [55,5 K], добавлен 16.02.2015Классическое, статистическое и геометрическое определения вероятности. Дискретные случайные величины и законы их распределения. Числовые характеристики системы случайных величин. Законы равномерного и нормального распределения систем случайных величин.
дипломная работа [797,0 K], добавлен 25.02.2011Теория вероятностей — раздел математики, изучающий закономерности случайных явлений: случайные события, случайные величины, их свойства и операции над ними. Методы решения задач по теории вероятности, определение математического ожидания и дисперсии.
контрольная работа [157,5 K], добавлен 04.02.2012Описание случайных ошибок методами теории вероятностей. Непрерывные случайные величины. Числовые характеристики случайных величин. Нормальный закон распределения. Понятие функции случайной величины. Центральная предельная теорема. Закон больших чисел.
реферат [146,5 K], добавлен 19.08.2015Метод Эйлера: сущность и основное содержание, принципы и направления практического применения, определение погрешности. Примеры решения задачи в Excel. Метод разложения решения в степенной ряд. Понятие и погрешность, решение с помощью метода Пикара.
контрольная работа [129,0 K], добавлен 13.03.2012Математические методы распознавания (классификации с учителем) и прогноза. Кластеризация как поиск оптимального разбиения и покрытия. Алгоритмы распознавания и интеллектуального анализа данных. Области практического применения систем распознавания.
учебное пособие [2,1 M], добавлен 14.06.2014Математика как одна из самых древних и консервативных наук. Понятие числа, построение их множеств, особенности натуральных чисел, представление иррациональных чисел. Смысл категории "пространство", последствия применения некорректных методов познания.
статья [32,3 K], добавлен 28.07.2010Как люди научились считать, возникновение цифр, чисел и систем счисления. Таблица умножения на "пальцах": методика умножения для чисел 9 и 8. Примеры быстрого счета. Способы умножения двузначного числа на 11, 111, 1111 и т.д. и трехзначного числа на 999.
курсовая работа [66,8 K], добавлен 22.10.2011Случайные величины. Функция и плотность распределения вероятностей дискретной случайной величины. Сингулярные случайные величины. Математическое ожидание случайной величины. Неравенство Чебышева. Моменты, кумулянты и характеристическая функция.
реферат [244,6 K], добавлен 03.12.2007Статистическое, аксиоматическое и классическое определение вероятности. Дискретные случайные величины. Предельные теоремы Лапласа и Пуассона. Функция распределения вероятностей для многомерных случайных величин. Формула Байеса. Точечная оценка дисперсии.
шпаргалка [328,7 K], добавлен 04.05.2015Свойства чисел натурального ряда. Периодическая зависимость от порядковых номеров чисел. Шестеричная периодизация чисел. Область отрицательных чисел. Расположение простых чисел в соответствии с шестеричной периодизацией.
научная работа [20,2 K], добавлен 29.12.2006
