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

Размещено на http://www.allbest.ru/

10

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Тульский государственный университет»

Кафедра прикладной математики и информатики

Пояснительная записка к курсовой работе

По курсу: «Численные методы»

На тему: «Вычисление интегралов методом Монте-Карло»

Автор работы: студент группы 520111 Кузнецова О.И.

Руководитель работы: профессор Горбачев Д.В.

Зав. кафедрой ПМиИ, В.И. Иванов

Тула 2013 г.



Содержание

Введение

1. Историческая справка

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

2.1 Детерминистический метод

2.2 Обычный метод Монте-Карло

2.3 Геометрический метод

3. Вычисление кратных интегралов в пространстве методом Монте-Карло

3.1 Обычный метод Монте-Карло

Заключение

Список литературы



Введение

Тема данной курсовой работы - это вычисление интегралов методом Монте-Карло. Иногда в прикладных задачах требуется найти значение интеграла, однако аналитически это не всегда удается. Чаще всего получается, что подынтегральная функция не имеет первообразной или не представима в виде элементарных функций, или известными методами невозможно или достаточно сложно найти его значение. Для этого мы обращаемся к численным методам вычисления интегралов, в которых одними из самых известных являются методы Монте-Карло.



1. Историческая справка

Сначала Энрико Ферми в 1930-х годах в Италии, а затем Джон фон Нейман и Станислав Улам в 1940-х в Лос-Аламосе предположили, что можно использовать связь между стохастическими процессами и дифференциальными уравнениями «в обратную сторону». Они предложили использовать стохастический подход для аппроксимации многомерных интегралов в уравнениях переноса, возникших в связи с задачей о движении нейтрона в изотропной среде. Идея была развита Уламом, который, по иронии судьбы, также как и Фокс боролся с вынужденным бездельем во время выздоровления после болезни, и, раскладывая пасьянсы, задался вопросом, какова вероятность того, что пасьянс «сложится». Ему в голову пришла идея, что вместо того, чтобы использовать обычные для подобных задач соображения комбинаторики, можно просто поставить «эксперимент» большое число раз и, таким образом, подсчитав число удачных исходов, оценить их вероятность.

Он же предложил использовать компьютеры для расчётов методом Монте-Карло. Появление первых электронных компьютеров, которые могли с большой скоростью генерировать псевдослучайные числа, резко расширило круг задач, для решения которых стохастический подход оказался более эффективным, чем другие математические методы. После этого произошёл большой прорыв и метод Монте-Карло применялся во многих задачах, однако его использование не всегда было оправдано из-за большого количества вычислений, необходимых для получения ответа с заданной точностью. Годом рождения метода Монте-Карло считается 1949 год, когда в свет выходит статья Метрополиса и Улама «Метод Монте-Карло». Название метода происходит от названия коммуны в княжестве Монако, широко известного своими многочисленными казино, поскольку именно рулетка является одним из самых широко известных генераторов случайных чисел. Станислав Улам пишет в своей автобиографии «Приключения математика», что название было предложено Николасом Метрополисом в честь его дяди, который был азартным игроком. В 1950-х годах метод использовался для расчётов при разработке водородной бомбы. Основные заслуги в развитии метода в это время принадлежат сотрудникам лабораторий ВВС США и корпорации RAND.

В 1970-х годах в новой области математики -- теории вычислительной сложности было показано, что существует класс задач, сложность (количество вычислений, необходимых для получения точного ответа) которых растёт с размерностью задачи экспоненциально. Иногда можно, пожертвовав точностью, найти алгоритм, сложность которого растёт медленнее, но есть большое количество задач, для которого этого нельзя сделать (например, задача определения объёма выпуклого тела в n-мерном евклидовом пространстве) и метод Монте-Карло является единственной возможностью для получения достаточно точного ответа за приемлемое время. В настоящее время основные усилия исследователей направлены на создание эффективных Монте-Карло алгоритмов различных физических, химических и социальных процессов для параллельных вычислительных систем.



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

2.1 Детерминистический метод

Пусть в пространстве на задана функция , причём , хотя бы один раз. Смысл метода состоит в аппроксимации до элементарных фигур разбиения. Разобьём на n частей, т.е. :

где - длина приращения при равномерном распределении. Рассмотрим два случая: когда элементарные фигуры - трапеции, и когда - прямоугольники.

Трапеции:

где S - площадь под графиком, - площади разбиений графика, которые аппроксимируем до трапеций.

Пример: численно вычислить интеграл

Решение

Сначала вычислим интеграл с помощью формулы Ньютона-Лейбница.

Пусть n=5, то

интеграл пространство вычисление математический

Из полученного результата мы видим, что при разбиении на 5 частей, с точностью до мы получаем исходный результат, что говорит об актуальной применимости детерминистического метода Монте-Карло при разбиении на трапеции.

Прямоугольники:

где S - площадь под графиком, - соответственно площади разбиений графика на прямоугольники с избытком и недостатком.

Пример: численно вычислить интеграл



Решение

Сначала вычислим интеграл с помощью формулы Ньютона-Лейбница.

Пусть n=5, то

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

2.2 Обычный метод Монте-Карло

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

Рассмотрим случайную величину p, заданную на промежутке . Очевидно, что тоже случайная величина. Тогда запишем формулу для её математического ожидания:

случайной величины p, причём

Разобьём на n частей, т.е. :

где - длина приращения при равномерном распределении. Тогда математическое ожидание можно оценить следующим образом:

Пример: численно вычислить интеграл

Решение

Сначала вычислим интеграл с помощью формулы Ньютона-Лейбница.

Пусть n=5, то

Пусть n=10, то

Из полученного результата мы видим, что при увеличении разбиений в два раза, точность результата приблизилась к настоящему на 0.205. При увеличении разбиений результат приблизится к исходному достаточно быстро, с точностью до можно получить уже при n=50.

2.3 Геометрический метод

Пусть в пространстве на задана функция , причём , хотя бы один раз и на имеет . Разобьём на n частей, т.е. :

где - длина приращения при равномерном распределении. Поместим область, ограниченную и осью абсцисс в прямоугольник со сторонами , где d и c - точки на оси ординат, причём Разобьём на k частей, т.е. :

где - длина приращения при равномерном распределении. При данных разбиениях и получили (n+1)(k+1) точек. Рассмотрим способ нахождения площади под графиком функции при данном распределении точек. Так как эта площадь есть какая-то часть площади прямоугольника, то скажем, что эта часть есть вероятность попадания этих точек в саму область под графиком функции и на её границу. Пусть попавших точек будет m, где , тогда

где - площадь прямоугольника.

Пример: численно вычислить интеграл

Решение

Сначала вычислим интеграл с помощью формулы Ньютона-Лейбница.

Пусть n=3, k=2, c=0, d=4, то

- площадь выбранного прямоугольника,

(n+1)(k+1) = 12 - общее количество точек,

Разбиение : 2, , , 4, разбиение : 0, 2, 4, тогда получаем точки (2,0), (2,2), (2,4), (,0), (,2), (,4), (,0), (,2), (,4), (,0), (,2), (,4), из них попадают в область (2,0), (2,2), (,0), (,2), (,0), (,2), (,0), (,2) - 8 точек, тогда

Из полученного результата мы видим достаточно большую погрешность, погрешность до достигается при достаточно большом количестве точек, например 9000, где n=100, k=900. Это показывает, что данный метод не очень удобен из-за достаточно медленной сходимости.



3. Вычисление кратных интегралов в пространстве методом Монте-Карло

3.1 Обычный метод Монте-Карло

Пусть в пространстве задана функция , где , причём , хотя бы один раз, где , - компактное множество, - ограничена и сверху, и снизу. Требуется вычислить интеграл

Так как множество - компакт, то впишем его в n-мерный параллелепипед P с осями, параллельными осям координат. Зададим его двумя вершинами - самой младшей и самой старшей координатами и , причём . Очевидно, что объём P можно выразить следующим образом:

Доопределим подынтегральную функцию следующим образом:

тогда исходный интеграл перепишем следующим образом:



Рассмотрим n-мерный вектор, имеющий равномерное распределение в параллелепипеде P, , тогда значение подынтегральной функции от случайного вектора будет выражаться как математическое ожидание следующим образом:

случайного вектора p, причём

Разобьём параллелепипед P на векторы классом разбиений

Причём установим между номерами разбиений взаимно однозначное соответствие между номерами разбиений в классе разбиений.

Тогда математическое ожидание можно оценить следующим образом:



Заключение

В данной работе рассмотрены методы численного вычисления интегралов с помощью метода Монте-Карло в пространствах и . В пространстве были рассмотрены детерминистический, обычный и геометрический методы. Получены следующие выводы: наиболее хорошая сходимость у детерминистического метода, а наиболее плохая - у геометрического метода. Ввиду слабой сходимости геометрического метода не актуально рассматривать его в пространстве . Также отмечено, что существенным отличием метода Монте-Карло от близких по характеру изучаемых в классической вычислительной математике является необходимость моделирования вероятностных распределений.



Список литературы

В.А. Зорич «Математический анализ», из-во МГУ, 2007г, 1447стр.

Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков «Численные методы» из-во МГУ 2007г,630стр.

А.Н. Колмогоров, С.В. Фомин «Элементы теории функций и функционального анализа», из-во МГУ, 2007г, 530 стр.

http://ru.wikipedia.org/wiki/%CC%E5%F2%EE%E4_%CC%EE%ED%F2%E5-%CA%E0%F0%EB%EE

С.М. Ермаков «Метод Монте-Карло в вычислительной математике», С-П. 2009г, 65 стр.



Приложения

Текст программы «Вычисление интеграла методом Монте-Карло»

#include <math.h>

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include<clocale>

void main()

{

setlocale(LC_CTYPE, "");

srand((unsigned)time(NULL));

printf("Функция: z=(8*x*sin(x)+7*x*y^3*cos(y)^2))/cos(x-y)^(1/2)\n");

float Zmax=0;

for(float x=0;x<=1;x=x+0.01)

{

for(float y=0;y<=1;y=y+0.01)

{

if(Zmax<(float)(8*x*sin(x)+7*x*pow(y,3)*pow(cos(y),2))/pow(cos(x-y),1/2))

{

Zmax=(float) (8*x*sin(x)+7*x*pow(y,3)*pow(cos(y),2))/pow(cos(x-y),1/2);

}

}

}

float SumINTEGR=0;//Сумма интегралов за 10 опытов

for(int i=1;i<=10;i++)

{

float X,Y,Z;// Рандомные точки

int HIT=0;// Число попаданий точек в искомый объем под поверхностью функции

float INTEGR=0;//Значение интеграла

for(float N=1;N<=183065;N++)

{

X=(float)(rand()%101)/100;

Y=(float)(rand()%101)/100;

Z=(float)(rand()%1001)/100;

if(Z<=(8*X*sin(X)+7*X*pow(Y,3)*pow(cos(Y),2))/pow(cos(X-Y),1/2))

{

HIT=HIT+1;

}

}

INTEGR=(float)HIT/183065*10;

SumINTEGR=SumINTEGR+INTEGR;

}

float averINTEGR=SumINTEGR/10;// Среднее значение интеграла в 10 случаях

printf("Значение интеграла - %f\n", averINTEGR);

printf("Z максимальное - %f",Zmax);

getch();

}



Результат работы программы

- приближенное значение найдено для целевой абсолютной погрешности 0.0001.

Размещено на Allbest.ru

...