Вычисление интегралов методом Монте-Карло
Краткое сожержание материала:
3
САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ИНФОРМАТИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
КУРСОВАЯ РАБОТА
ВЫЧИСЛЕНИЕ ИНТЕГРАЛОВ МЕТОДОМ МОНТЕ - КАРЛО
Выполнил:
Руководитель:
Саратов, 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. ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ
Сущность метода Монте-Карло и моделирование случайных величин
Исследование способа вычисления кратных интегралов методом Монте-Карло. Общая схема метода Монте-Карло, вычисление определенных и кратных интегралов....
Метод Монте-Карло и его применение
Некоторые сведения теории вероятностей. Математическое ожидание, дисперсия. Точность оценки, доверительная вероятность. Доверительный интервал. Нормал...
Алгоритм интегрирования методом Монте-Карло для определенного интеграла
Некоторые сведения теории вероятностей. Математическое ожидание, дисперсия. Точность оценки, доверительная вероятность. Сущность метода Монте-Карло. Г...
Метод статистических испытаний Монте-Карло
Определение площади фигуры аналитическим методом (с помощью вычисления определенного интеграла) и методом статистических испытаний Монте-Карло. Постро...
Моделирование траекторий нейтронов при расчете реакторов методом Монте-Карло
Описана техника моделирования траекторий нейтронов на ЭВМ, применяемая в многогрупповых расчетах реакторов методом Монте-Карло, а также в расчетах с д...