Xreferat.com » Рефераты по математике » Вычисление интегралов методом Монте-Карло

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

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


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


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


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


Выполнил:

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


Саратов, 2009

СОДЕРЖАНИЕ


ВВЕДЕНИЕ

1. МАТЕМАТИЧЕСКОЕ ОБОСНОВАНИЕ АЛГОРИТМА ВЫЧИСЛЕНИЯ ИНТЕГРАЛА

1.1 Принцип работы метода Монте – Карло

1.2 Применение метода Монте – Карло для вычисления n – мерного интеграла.

1.3 Сплайн – интерполяция

1.4 Алгоритм расчета интеграла

2. ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

2.1 Генератор псевдослучайных чисел применительно к методу Монте – Карло.

2.2 Алгоритм генератора псевдослучайных чисел

2.3 Проверка равномерности распределения генератора псевдослучайных чисел.

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


ВВЕДЕНИЕ


Целью данной работы является создание программного продукта для участия в конкурсе, проводимом группой компаний «Траст» по созданию программных разработок. Для реализации было выбрано следующее технической задание:

Задание 12 Вычисление интегралов методом Монте – Карло.

Цель:

Реализация генератора случайных чисел для метода Монте – Карло.

Сравнение равномерного распределения и специально разработанного.

Вычисление тестового многомерного интеграла в сложной области.

Продукт:

Программный код в виде функции на языке С++ или Fortran .

Тестовые примеры в виде программы, вызывающие реализованные функции.

Обзор использованной литературы.

Для реализации данного технического задания был выбран язык 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 Алгоритм расчета интеграла


Реализованный алгоритм включает следующие шаги:

выбирается начальное значение Вычисление интегралов методом Монте-Карло, разыгрываются случайные векторы из Вычисление интегралов методом Монте-Карло и определяются Вычисление интегралов методом Монте-Карло и Вычисление интегралов методом Монте-Карло;

в зависимости от вида погрешности (абсолютная, относительная) определяется достигнутая погрешность; если она меньше целевой, вычисление прерывается;

по формулам (13) или (14) вычисляется новый объем выборки;

объем выборки увеличивается на 20%

переход к шагу 1;

конец.

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).

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Бережная Е. В., Бережной В. И. Математические методы моделирования экономических систем. – М.: Финансы и статистика, 2001. – 368 с.

Мюллер П., Нойман П., Шторм Р. Таблицы по математической статистике. – М.: Финансы и статистика, 1982. – 278 с.

Теннант-Смит Дж. Бейсик для статистиков. – М.: Мир, 1988. – 208 с.

Baranger J. Analyse numйrique. Hermann, 1991.

Маделунг Э. Математический аппарат физики. Справочное руководство. М.: Наука, 1968., с.287.

В.Е. Гмурман Теория вероятностей и математическая статистика – М.: Высшая школа, 2003

ПРИЛОЖЕНИЕ 1


ЛИСТИНГИ ОСНОВНЫХ ФУНКЦИЙ

Листинг 1 Функция расчета интеграла


void integral ()

{

// вычисление интеграла методом Монте – Карло


// размерность области интегрирования

unsigned d_int=fun_dim;


//----- 3 d график --------------------------------------------------------


// максимальное число троек

unsigned plot_dim_max=10000;


// матрица троек

pmatd xyz,xyz_tmp;


if (d_int==3) xyz=new matd(plot_dim_max,3);


//-------------------------------------------------------------------------


// индикатор относительной погрешности

mcres.relok=Read1double("error_type.txt");


// целевая погрешность

mcres.dlt_int=Read1double("error_value.txt");


// номер стандартного значения доверительной вероятности (начиная с 0)

int nome_int=Read1double("error_omega.txt");


// ГСЧ

unsigned long b=m_rng*m_rng-d_rng,c,r,i,PSChunk;


// "росток" ГСЧ

mcres.rng_seed=Read1double("rng_seed.txt");


pmatd fun_b, fun_A, con_b, con_A, con_U, con_v,

a_int, b_int, ba_int, x_int, xyz_top, xyz_bottom;


unsigned j,ii,jj,con_ok;


struct date dat;

struct time tim;


pspl2d sp_top,sp_bottom;


// квантили нормального распределения

double omegas_int[6]={0.9,0.95,0.99,0.999,0.9999,0.99999};

double zs_int[6]={1.64485362695147,1.95996398454005,2.5758293035489,

3.29052673149191, 3.89059188641317, 4.4171734134667};

mcres.omega_int=omegas_int[nome_int];

mcres.z_int=zs_int[nome_int];


double fun_cd,con_wd,fu_int,con_sum,sum1_int,sum2_int;

// вид интегрируемой функции

// 0 - постоянная

// 1 - линейная

// 2 - квадратичная

mcres.fun_type=Read1double("fun_kind.txt");


// вид системы ограничений

// 0 – отсутствуют (весь параллелепипед)

// 1 - линейные

// 2 - квадратичное

// 3 – сплайн - поверхности

mcres.con_type=Read1double("con_type.txt");


// загрузка параметров интегрируемой функции

switch (mcres.fun_type)

{

case 2: fun_A=new matd("fun_A.txt");

case 1: fun_b=new matd("fun_b.txt");

case 0: fun_cd=Read1double("fun_c.txt");

}


// загрузка параметров ограничений

switch (mcres.con_type)

{

case 3: // сплайн - поверхности

// верхняя

xyz_top=new matd("xyz_top.txt");


// нижняя

xyz_bottom=new matd("xyz_bottom.txt");


// двумерная интерполяция

sp_top=new spl2d(xyz_top);

sp_bottom=new spl2d(xyz_bottom);

break;

case 2: // квадратичная функция ограничений

con_U=new matd("con_U.txt");

con_v=new matd("con_v.txt");

con_wd=Read1double("con_w.txt");

break;

case 1: // линейные ограничения

con_b=new matd("con_b.txt"); con_A=new matd("con_A.txt");

}


// объемлющий параллелепипед

a_int=new matd("con_xmin.txt");

b_int=new matd("con_xmax.txt");

// разность границ параллелепипеда

ba_int=new matd;

ba_int=&(*b_int - (*a_int));


// аргумент интегрируемой функции

x_int=new matd(d_int,1);


//объем объемлющего параллелепипеда

mcres.V0_int=1;

for (j=1; j <= d_int; j++)

{

if (_p(ba_int,j,1) <= 0)

{

DbBox("Нижняя граница объемлющего параллелепипеда выше верхней для

координаты ",j);

goto clean_exit;

}


mcres.V0_int=mcres.V0_int*_p(ba_int,j,1);

}


// начальный объем выборки

mcres.n1_int=10000;


// основной цикл для достижения заданной точности


// число итераций, потребовавшихся для достижения заданной точности

mcres.n_ite=0;


getdate(&dat); gettime(&tim); mcres.t_start=dostounix(&dat,&tim);


WaitForm->Show();


while (1)

{

mcres.n_ite++;


WaitForm->Edit1->Text=mcres.n_ite;

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: