Сущность метода Монте-Карло

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

Рассмотрим  независимых случайных величин распределения которых совпадают с распределением . Если достаточно велико, то, согласно центральной предельной теореме, распределение суммы будет приблизительно нормальным с параметрами . Из (1.6) следует, что .

Последнее соотношение перепишем  в виде:

     (1.7)

Это соотношение даёт и  метод расчёта  , и оценку погрешности.

В самом деле, найдём значений случайной величины . Из (1.7) видно, что среднеарифметическое этих значений будет приближенно равно . С большой вероятностью погрешность приближения не превосходит величины . Эта погрешность стремится к нулю с ростом . На практике часто используют не оценку сверху , а на вероятную ошибку, которая приближенно равна Именно такой обычно порядок фактической погрешности расчёта, которая равна

.

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

Таблицы случайных чисел  используют предпочтительно при  расчётах вручную. Определяющую роль в этом играют два факта: 1) при использовании ЭВМ легче и удобней воспользоваться генератором случайных чисел, получаемых тут же, чем загружать из памяти значения таблицы, которая к тому же, будет занимать там место. 2) При подсчёте вручную нет необходимости использовать ЭВМ, так как часто необходимо выяснить лишь порядок искомой величины.

 

2.1 Генераторы случайных  чисел

 

Генераторы случайных  чисел анализируют какой-либо процесс, доступный для них (шумы в электронных  лампах, скачки напряжения) и составляют последовательность из 0 и 1, из которых  составляются числа с определёнными разрядами, однако такой метод получения случайных величин имеет свои недостатки. Во-первых, трудно проверить вырабатываемые числа. Проверки приходится делать периодически, так как из-за каких-либо неисправностей может возникнуть так называемый дрейф распределения (нули и единицы в каком-либо из разрядов станут появляться не одинаково часто). Во-вторых, обычно все расчёты на ЭВМ проводятся несколько раз, чтобы исключить возможность сбоя. Но воспроизвести те же самые случайные числа невозможно, если их только не запоминать по ходу счёта. А если запоминать, то снова появляется случай таблиц.

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

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

Первый алгоритм для получения  псевдослучайных чисел был предложен  Дж. Нейманом. Он называется методом середины квадратов.

Пусть задано 4-значное число  . Возведём его квадрат. Получим 8-значное число . Выберем 4 средние цифры этого числа и положим .Далее и т.д.

Но этот алгоритм не оправдал себя, так как получается слишком  много малых значений. Поэтому  были разработаны другие алгоритмы. Наибольшее распространение получил  алгоритм, называемый методом сравнений (Д. Лемер): определяется последовательность целых чисел , в которой начальное число задано, а все последующие числа вычисляются по одной и той же формуле

 при        (1.8)

По числам вычисляются псевдослучайные числа

          (1.9)

Формула (1.8) означает, что  число  равно остатку, полученному при делении на , такой остаток называют наименьшим положительным вычетом по модулю Формулы (1.8), (1.9) легко реализовать на ЭВМ.

Достоинства метода псевдослучайных  чисел довольно очевидны. Во-первых, на получение каждого числа затрачивается  всего несколько простых операций, так что скорость генерирования  случайных чисел имеет тот  же порядок, что и скорость работы ЭВМ. Во-вторых, программа занимает не так много места в памяти. В-третьих, любое из чисел  может быть легко воспроизведено. В-четвёртых, необходимо лишь один раз проверить «качество» такой последовательности, затем её можно много раз безбоязненно использовать при расчёте однотипных задач.

Единственный недостаток метода – ограниченность количества псевдослучайных чисел, так как  если последовательность чисел  вычисляется на ЭВМ по формуле вида

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

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

Допустим, что необходимо получать значения случайной величины , распределённой в интервале , с плотностью . Докажем, что значения можно находить из уравнения

 т.е. выбрав очередное значение , надо решить уравнение (1.10) и найти очередное значение .

Для доказательства рассмотрим функцию

.

Из общих свойств плотности (1.2), (1.3) следует, что

Значит, функция  монотонно возрастает от 0 до 1, и любая прямая , где , пересекает график в одной единственной точке, абсциссу которой мы и принимаем за . Таким образом, уравнение (1.10) всегда имеет одно и только одно решение.

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

Поэтому, если принадлежит интервалу , то принадлежит интервалу , и наоборот. Значит

Так как  равномерно распределена в , то

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3 Практическая часть

     3.1Задание

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

 

3.2 Алгоритм интегрирования методом Монте-Карло для определенного интеграла

Предположим, требуется вычислить  определённый интеграл 

Рассмотрим случайную  величину  , равномерно распределённую на отрезке интегрирования  . Тогда   также будет случайной величиной, причём её математическое ожидание выражается как 
, где   — плотность распределения случайной величины  , равная   на участке  .

Таким образом, искомый интеграл выражается как 
.

Но матожидание случайной величины   можно легко оценить, смоделировав эту случайную величину и посчитав выборочное среднее.

Итак, бросаем   точек, равномерно распределённых на  , для каждой точки   вычисляем  . Затем вычисляем выборочное среднее:  .

В итоге получаем оценку интеграла: 

Точность оценки зависит  только от количества точек  .

 

3.3 Вычисление кратных интегралов

 

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

Первый способ.

Пусть требуется вычислить  кратный интеграл

      

по области  G, лежащей в мерном единичном кубе

 

Выберем равномерно распределённых на отрезке последовательностей случайных чисел

 

Тогда точки  можно рассматривать как случайные, равномерно распределённые в мерном единичном кубе.

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

  

где под понимается мерный объём области интегрирования. Если вычисление объёма затруднительно, то можно принять , и для приближенного вычисления интеграла получим:

  

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

Второй  способ.

Если  функция  , то интеграл можно рассматривать как объём тела в мерном пространстве, т.е.

 

  

 

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

Если в области  , то введя новую переменную , получим

 где область  лежит в единичном мерном кубе   Возьмём равномерно распределенных на отрезке случайных последовательностей

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

 

 

3.4 Описание пользовательского  интерфейса

 

Первая программа вычисляет пять интегралов с подынтегральными функциями x^2+2x+1,ln(x),log10(x),cos(x),sqrt(x).Пользователь задает верхнюю и нижнюю границу интегрирования и вводит количество случайных величин:

Рисунок 1 «Пример вычисления определенных интегралов»

      Листинг программы представлен в Приложении А.

Вторая программа вычисляет  двойной интеграл. Пользователь задает раницы интегрирования по х в интервале [0,1] и количество испытаний. Границы интегрирования по y заданы в программе: 0<y<2x-1:

Рисунок 2 «Пример вычисления двойного интеграла»

    Листинг программы представлен в Приложении Б.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

Процесс выполнения данной работы представлял большой интерес  и послужил хорошей возможностью для приобретения новых знаний и  навыков, а также закрепления  уже полученных.

Были рассмотрены основные свойства метода Монте-Карло и создана  программа, показывающая возможности  данного метода при использовании  ЭВМ.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы

1. Бусленко Н.П. Метод статистического моделирования – М.: Статистика, 1970. – 112 с.
2. Демидович Б.П., Марон И.А. Основы вычислительной математики. - М.: Наука, 1966. – 664 с.
3. Ермаков С.М. Метод Монте-Карло и смежные вопросы – М.: Наука, 1975–472 с.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение А

Листинг программы для определенных интегралов

package monte;

import java.util.Random;

import java.lang.Math;

import java.util.Scanner;

public class Monte {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

Random ran = new Random();

 int a, b,N,m;

double k,j,n,n1,n2,n3,n4,I,I1,I2,I3,I4,X,j1,j2,j3,j4; n=0; n1=0; n2=0; n3=0; n4=0;

 System.out.println("нижняя граница интеграла:");

a = sc.nextInt();

 System.out.println("верхняя граница интеграла:");

b=sc.nextInt();

 System.out.println("количество случайных величин:");

 N=sc.nextInt();

m=N;

 while (N>0)

{

k=ran.nextFloat();

X=a+(b-a)*k;

j=X*X+2*X+1;

n=n+j;

j1=Math.log(X);

n1=n1+j1;

j2=Math.log10(X);

n2=n2+j2;

j3=Math.sqrt(X);

n3=n3+j3;

j4=Math.cos(X);

n4=n4+j4;

N--;

}

I=(b-a)*(n/m);

I1=(b-a)*(n1/m);

I2=(b-a)*(n2/m);

I3=(b-a)*(n3/m);

I4=(b-a)*(n4/m);

System.out.println("оценка интеграла c подынтегральной функцией x^2+2x+1: "+I);

System.out.println("оценка интеграла c подынтегральной функцией log(x): "+I1);

System.out.println("оценка интеграла c подынтегральной функцией log10(x): "+I2);

System.out.println("оценка интеграла c подынтегральной функцией sqrt(x): "+I3);

System.out.println("оценка интеграла c подынтегральной функцией cos(x): "+I4);

}

}

 

 

 

 

 

 

 

 

Приложение Б