САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ИНФОРМАТИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
КУРСОВАЯ РАБОТА
ВЫЧИСЛЕНИЕ ИНТЕГРАЛОВ МЕТОДОМ МОНТЕ - КАРЛО
Выполнил:
Руководитель:
Саратов, 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 год, когда американские ученые Н. Метрополис и С. Услам опубликовали статью под названием «Метод Монте - Карло», в которой были изложены принципы этого метода. Название метода происходит от названия города Монте – Карло, славившегося своими игорными заведениями, непременным атрибутом которых являлась рулетка – одно из простейших средств получения случайных чисел с хорошим равномерным распределением, на использовании которых основан этот метод.
Метод Монте – Карло это статистический метод. Его используют при вычислении сложных интегралов, решении систем алгебраических уравнений высокого порядка, моделировании поведения элементарных частиц, в теориях передачи информации, при исследовании сложных экономических систем.
Сущность метода состоит в том, что в задачу вводят случайную величину 
, изменяющуюся по какому то правилу 
. Случайную величину выбирают таким образом, чтобы искомая в задаче величина 
стала математическим ожидание от , то есть 
.
Таким образом, искомая величина определяется лишь теоретически. Чтобы найти ее численно необходимо воспользоваться статистическими методами. То есть необходимо взять выборку случайных чисел объемом $IMAGE8$. Затем необходимо вычислить выборочное среднее $IMAGE8$ варианта случайной величины $IMAGE10$ по формуле:
$IMAGE11$. (1)
Вычисленное выборочное среднее принимают за приближенное значение $IMAGE12$.
Для получения результата приемлемой точности необходимо большое количество статистических испытаний.
Теория метода Монте – Карло изучает способы выбора случайных величин для решения различных задач, а также способы уменьшения дисперсии случайных величин.
1.2 Применение метода Монте – Карло для вычисления n – мерного интеграла.
Рассмотрим n – мерный интеграл
$IMAGE14$ для $IMAGE15$. (2)
Будем считать, что область интегрирования $IMAGE15$, и что $IMAGE17$ ограниченное множество в $IMAGE18$. Следовательно, каждая точка х множества $IMAGE17$ имеет n координат: $IMAGE20$.
Функцию $IMAGE21$ возьмем такую, что она ограничена сверху и снизу на множестве $IMAGE17$: $IMAGE23$.
Воспользуемся ограниченностью множества $IMAGE17$ и впишем его в некоторый n – мерный параллелепипед $IMAGE25$, следующим образом:
$IMAGE26$,
где $IMAGE27$- минимумы и максимумы, соответственно, $IMAGE28$ - ой координаты всех точек множества $IMAGE17$: $IMAGE30$.
Доопределяем подынтегральную функцию $IMAGE21$ таким образом, чтобы она обращалась в ноль в точках параллелепипеда $IMAGE25$, которые не принадлежат $IMAGE17$:
$IMAGE34$ (3)
Таким образом, уравнение (2) можно записать в виде
$IMAGE35$. (4)
Область интегрирования представляет собой n – мерный параллелепипед $IMAGE25$ со сторонами параллельными осям координат. Данный параллелепипед можно однозначно задать двумя вершинами $IMAGE37$, которые имеют самые младшие и самые старшие координаты всех точек параллелепипеда.
Обозначим через $IMAGE38$ n-мерный вектор, имеющий равномерное распределение в параллелепипеде $IMAGE25$: $IMAGE40$, где $IMAGE41$.
Тогда ее плотность вероятностей $IMAGE42$ будет определена следующим образом
$IMAGE43$ (5)
Значение подынтегральной функции $IMAGE44$ от случайного вектора $IMAGE38$ будет случайной величиной $IMAGE46$, математическое ожидание $IMAGE47$ которой является средним значением функции на множестве $IMAGE25$:
$IMAGE49$. (6)
Среднее значение функции на множестве $IMAGE25$ равняется отношению значения искомого интеграла к объему параллелепипеда $IMAGE25$:
$IMAGE52$ (7)
Обозначим $IMAGE53$ объем параллелепипеда $IMAGE25$.
Таким образом, значение искомого интеграла можно выразить как произведение математического ожидания функции и объема n- мерного параллелепипеда $IMAGE25$:
$IMAGE56$ (8)
Следовательно, необходимо найти значение математического ожидания $IMAGE57$. Его приближенное значение можно найти произведя n испытаний, получив, таким образом, выборку $IMAGE58$ случайных векторов, имеющих равномерное распределение на $IMAGE25$. Обозначим $IMAGE60$ и $IMAGE61$. Для оценки математического ожидания воспользуемся результатом
$IMAGE62$, (9)
где $IMAGE63$,
$IMAGE64$,
$IMAGE65$ - квантиль нормального распределения, соответствующей доверительной вероятности $IMAGE66$.
Умножив двойное неравенство из (9) на $IMAGE67$ получим интервал для I:
$IMAGE68$. (10)
Обозначим $IMAGE69$ точечную оценку $IMAGE70$. Получаем оценку (с надежностью $IMAGE71$):
$IMAGE72$. (11)
Аналогично можно найти выражение для относительной погрешности $IMAGE73$:
$IMAGE74$. (12)
Если задана целевая абсолютная погрешность $IMAGE75$, из (11) можно определить объем выборки, обеспечивающий заданную точность и надежность:
$IMAGE76$. (13)
Если задана целевая относительная погрешность, из (12) получаем аналогичное выражение для объема выборки:
$IMAGE77$. (14)
1.3 Сплайн – интерполяция.
В данном программном продукте реализована возможность задавать дополнительные ограничения области интегрирования двумя двумерными сплайн – поверхностями (для подынтегральной функции размерности 3). Для задания этих поверхностей используются двумерные сплайны типа гибкой пластинки \4\.
Под сплайном (от англ. spline - планка, рейка) обычно понимают агрегатную функцию, совпадающую с функциями более простой природы на каждом элементе разбиения своей области определения. Сплайн – функция имеет следующий вид:
$IMAGE78$. (15)
Исходные данные представляют собой $IMAGE79$ троек точек $IMAGE80$.
Коэффициенты $IMAGE81$ и $IMAGE82$ определяются из системы:
$IMAGE83$, (16)
где $IMAGE84$,
$IMAGE85$
$IMAGE86$.
1.4 Алгоритм расчета интеграла
Реализованный алгоритм включает следующие шаги:
1) выбирается начальное значение $IMAGE87$, разыгрываются случайные векторы из $IMAGE88$ и определяются $IMAGE89$ и $IMAGE90$;
2) в зависимости от вида погрешности (абсолютная, относительная) определяется достигнутая погрешность; если она меньше целевой, вычисление прерывается;
3) по формулам (13) или (14) вычисляется новый объем выборки;
4) объем выборки увеличивается на 20%
5) переход к шагу 1;
6) конец.
2. ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ
2.1 Генератор псевдослучайных чисел применительно к методу Монте – Карло.
В любом алгоритме использующем метод Монте – Карло генератор псевдослучайных чисел играет очень важную роль. Степень соответствия псевдослучайных чисел заданному распределению является важным фактором проведения качественных статистических испытаний.
2.2 Алгоритм генератора псевдослучайных чисел
В программе реализован конгруэнтный метод генерации псевдослучайных чисел \3\:
$IMAGE91$, (17)
где $IMAGE92$=8192,
$IMAGE93$=67101323.
Авторский код, реализующий защиту от переполнения был, реализован на С++. Перед использование первые три числа последовательности удаляются. Для получении чисел из интервала (0,1) все числа делятся на $IMAGE93$.
2.3 Проверка равномерности распределения генератора псевдослучайных чисел.
Проверка равномерности распределения псевдослучайных чисел проводилась с помощью стандартного критерия χ2 \2\.
Были использованы 3 последовательности псевдослучайных чисел, определяемых стартовыми значениями 1, 1001, 1000000 длиной 300000.
Интервал (0,1) подразделялся на 50 равных интервалов и программно подсчитывались абсолютные частоты (рис. 1).
Рис. 1
$IMAGE95$
Результаты проверки приведены в Таблице 1.
Таблица 1
| | стартовое значение ГСЧ |
| | 1 | 1001 | 1000000 |
| хи-квадрат | 44.0533333333333 | 45.007 | |