САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИЙУНИВЕРСИТЕТ
ФАКУЛЬТЕТИНФОРМАТИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
КУРСОВАЯРАБОТА
ВЫЧИСЛЕНИЕИНТЕГРАЛОВ МЕТОДОМ МОНТЕ — КАРЛО
Выполнил:
Руководитель:
Саратов, 2009
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. МАТЕМАТИЧЕСКОЕ ОБОСНОВАНИЕ АЛГОРИТМА ВЫЧИСЛЕНИЯИНТЕГРАЛА
1.1 Принцип работы метода Монте – Карло
1.2 Применение метода Монте – Карло для вычисления n – мерного интеграла.
1.3 Сплайн – интерполяция 8
1.4 Алгоритм расчета интеграла
2. ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ
2.1 Генератор псевдослучайных чисел применительно к методуМонте – Карло.
2.2 Алгоритм генератора псевдослучайных чисел
2.3 Проверка равномерности распределения генератора псевдослучайных чисел.
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ВВЕДЕНИЕ
Целью данной работыявляется создание программного продукта для участия в конкурсе, проводимомгруппой компаний «Траст» по созданию программных разработок. Для реализациибыло выбрано следующее технической задание:
Задание 12 Вычислениеинтегралов методом Монте – Карло.
Цель:
1) Реализация генератора случайных чиселдля метода Монте – Карло.
2) Сравнение равномерного распределенияи специально разработанного.
3) Вычисление тестового многомерногоинтеграла в сложной области.
Продукт:
1) Программный код в виде функции наязыке С++ или Fortran .
2) Тестовые примеры в виде программы,вызывающие реализованные функции.
3) Обзор использованной литературы.
Для реализации данного техническогозадания был выбран язык C++.Код реализован в интегрированной среде разработки приложений Borland C++ Builder Enterprises иматематически обоснован соответствующий способ вычисления интеграла.
1. МАТЕМАТИЧЕСКОЕОБОСНОВАНИЕ АЛГОРИТМА ВЫЧИСЛЕНИЯ ИНТЕГРАЛА 1.1 Принцип работы метода Монте – Карло
Датой рождения методаМонте — Карло признано считать 1949 год, когда американские ученые Н. Метрополиси С. Услам опубликовали статью под названием «Метод Монте — Карло», в которойбыли изложены принципы этого метода. Название метода происходит от названиягорода Монте – Карло, славившегося своими игорными заведениями, непременныматрибутом которых являлась рулетка – одно из простейших средств получения случайныхчисел с хорошим равномерным распределением, на использовании которых основанэтот метод.
Метод Монте – Карло этостатистический метод. Его используют при вычислении сложных интегралов, решениисистем алгебраических уравнений высокого порядка, моделировании поведенияэлементарных частиц, в теориях передачи информации, при исследовании сложныхэкономических систем.
Сущность метода состоит втом, что в задачу вводят случайную величину />,изменяющуюся по какому то правилу />.Случайную величину выбирают таким образом, чтобы искомая в задаче величина /> стала математическим ожиданиеот />, то есть />.
Таким образом, искомаявеличина /> определяется лишьтеоретически. Чтобы найти ее численно необходимо воспользоватьсястатистическими методами. То есть необходимо взять выборку случайных чисел /> объемом />. Затем необходимовычислить выборочное среднее /> вариантаслучайной величины /> по формуле:
/>. (1)
Вычисленное выборочноесреднее принимают за приближенное значение />.
Для получения результатаприемлемой точности необходимо большое количество статистических испытаний.
Теория метода Монте –Карло изучает способы выбора случайных величин /> длярешения различных задач, а также способы уменьшения дисперсии случайныхвеличин. 1.2 Применение метода Монте – Карло для вычисления n – мерного интеграла.
Рассмотрим n– мерный интеграл
/> для />. (2)
Будем считать, чтообласть интегрирования />, и что /> ограниченное множество в />. Следовательно, каждаяточка х множества /> имеет n координат: />.
Функцию /> возьмем такую, что онаограничена сверху и снизу на множестве />:/>.
Воспользуемсяограниченностью множества /> ивпишем его в некоторый n– мерный параллелепипед />,следующим образом:
/>,
где /> — минимумы и максимумы,соответственно, /> - ой координатывсех точек множества />: />.
Доопределяемподынтегральную функцию /> такимобразом, чтобы она обращалась в ноль в точках параллелепипеда />, которые не принадлежат />:
/> (3)
Таким образом, уравнение(2) можно записать в виде
/>. (4)
Область интегрированияпредставляет собой n– мерныйпараллелепипед /> со сторонамипараллельными осям координат. Данный параллелепипед можно однозначно задатьдвумя вершинами />, которые имеютсамые младшие и самые старшие координаты всех точек параллелепипеда.
Обозначим через /> n-мерный вектор, имеющий равномерноераспределение в параллелепипеде />: />, где />.
Тогда ее плотностьвероятностей /> будет определена следующимобразом
/> (5)
Значение подынтегральнойфункции /> от случайного вектора /> будет случайной величиной />, математическое ожидание /> которой является среднимзначением функции на множестве />:
/>. (6)
Среднее значение функциина множестве /> равняется отношению значенияискомого интеграла к объему параллелепипеда />:
/> (7)
Обозначим /> объем параллелепипеда />.
Таким образом, значениеискомого интеграла можно выразить как произведение математического ожиданияфункции и объема n — мерногопараллелепипеда />:
/> (8)
Следовательно, необходимонайти значение математического ожидания />.Его приближенное значение можно найти произведя n испытаний, получив, таким образом, выборку /> случайных векторов, имеющихравномерное распределение на />. Обозначим/> и />. Для оценкиматематического ожидания воспользуемся результатом
/>, (9)
где />,
/>,
/> - квантиль нормальногораспределения, соответствующей доверительной вероятности />.
Умножив двойноенеравенство из (9) на /> получим интервалдля I:
/>. (10)
Обозначим /> точечную оценку />. Получаем оценку (с надежностью/>):
/>. (11)
Аналогично можно найтивыражение для относительной погрешности />:
/>. (12)
Если задана целеваяабсолютная погрешность />, из (11) можноопределить объем выборки, обеспечивающий заданную точность и надежность:
/>. (13)
Если задана целеваяотносительная погрешность, из (12) получаем аналогичное выражение для объемавыборки:
/>. (14) 1.3 Сплайн – интерполяция.
В данном программномпродукте реализована возможность задавать дополнительные ограничения областиинтегрирования двумя двумерными сплайн – поверхностями (для подынтегральнойфункции размерности 3). Для задания этих поверхностей используются двумерныесплайны типа гибкой пластинки \4\.
Под сплайном (от англ.spline — планка, рейка) обычно понимают агрегатную функцию, совпадающую сфункциями более простой природы на каждом элементе разбиения своей областиопределения. Сплайн – функция имеет следующий вид:
/>. (15)
Исходные данныепредставляют собой /> троек точек />.
Коэффициенты /> и /> определяются из системы:
/>, (16)
где />,
/>
/>. 1.4 Алгоритм расчета интеграла
Реализованный алгоритмвключает следующие шаги:
1) выбираетсяначальное значение />, разыгрываютсяслучайные векторы из /> и определяются /> и />;
2) в зависимости отвида погрешности (абсолютная, относительная) определяется достигнутаяпогрешность; если она меньше целевой, вычисление прерывается;
3) по формулам (13)или (14) вычисляется новый объем выборки;
4) объем выборкиувеличивается на 20%
5) переход к шагу 1;
6) конец.
2. ГЕНЕРАТОРПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ 2.1 Генератор псевдослучайных чисел применительно к методуМонте – Карло.
В любом алгоритмеиспользующем метод Монте – Карло генератор псевдослучайных чисел играет оченьважную роль. Степень соответствия псевдослучайных чисел заданному распределениюявляется важным фактором проведения качественных статистических испытаний. 2.2 Алгоритм генератора псевдослучайных чисел
В программе реализованконгруэнтный метод генерации псевдослучайных чисел \3\:
/>, (17)
где />=8192,
/>=67101323.
Авторский код,реализующий защиту от переполнения был, реализован на С++. Перед использованиепервые три числа последовательности удаляются. Для получении чисел из интервала(0,1) все числа делятся на />. 2.3 Проверка равномерности распределения генератора псевдослучайныхчисел.
Проверка равномерностираспределения псевдослучайных чисел проводилась с помощью стандартного критерияχ2 \2\.
Были использованы 3последовательности псевдослучайных чисел, определяемых стартовыми значениями 1,1001, 1000000 длиной 300000.
Интервал (0,1)подразделялся на 50 равных интервалов и программно подсчитывались абсолютныечастоты (рис. 1).
Рис.1
/>
Результаты проверки приведеныв Таблице 1.
Таблица1 стартовое значение ГСЧ 1 1001 1000000 хи-квадрат 44.0533333333333 45.007 48.618 df 50 50 50 p-значение 0.709735881642893 0.673522612551685 0.528941919633451
Следовательно,равномерность распределения не отвергается на уровне 5%.
ЗАКЛЮЧЕНИЕ
В заключение можносказать, что поставленная задача была полностью выполнена. То есть на языке С++были разработаны генератор псевдослучайных чисел, функция рассчитывающаяинтеграл методом Монте – Карло (Приложение 1); был проведен расчет тестовых многомерныхинтегралов (Приложение 2); в интегрированной среде разработки приложений Borland C++ Builder Enterprises 7.0был создан программный продукт «CarloS»,реализующий описанные выше алгоритмы (Приложение 3).
СПИСОК ИСПОЛЬЗОВАННЫХИСТОЧНИКОВ
1. Бережная Е. В., Бережной В. И.Математические методы моделирования экономических систем. – М.: Финансы истатистика, 2001. – 368 с.
2. Мюллер П., Нойман П., Шторм Р.Таблицы по математической статистике. – М.: Финансы и статистика, 1982. – 278с.
3. Теннант-Смит Дж. Бейсик длястатистиков. – М.: Мир, 1988. – 208 с.
4. Baranger J. Analyse numérique.Hermann, 1991.
5. Маделунг Э. Математический аппаратфизики. Справочное руководство. М.: Наука, 1968., с.287.
6. В.Е. Гмурман Теория вероятностей иматематическая статистика – М.: Высшая школа, 2003