Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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

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

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

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

Выполнил:

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

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

Были использованы 3 последовательности псевдослучайных чисел, определяемых стартовыми значениями 1, 1001, 1000000 длиной 300000.

Интервал (0,1) подразделялся на 50 равных интервалов и программно подсчитывались абсолютные частоты (рис. 1).

Рис. 1

Результаты проверки приведены в Таблице 1.

Таблица 1

Следовательно, равномерность распределения не отвергается на уровне 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

ПРИЛОЖЕНИЕ 1

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов курсовой работы