Реферат: Вычисление интегралов методом Монте-Карло

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИЙУНИВЕРСИТЕТ

ФАКУЛЬТЕТИНФОРМАТИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

КУРСОВАЯРАБОТА

ВЫЧИСЛЕНИЕИНТЕГРАЛОВ МЕТОДОМ МОНТЕ — КАРЛО

Выполнил:

Руководитель:

Саратов, 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