Участник:Grachovamc/Вычисление кратного интеграла методом Монте - Карло.: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === Метод Монте-Карло — об…»)
 
Строка 21: Строка 21:
 
* определяется число <math>M</math> точек, координаты которых попали под график функции;
 
* определяется число <math>M</math> точек, координаты которых попали под график функции;
 
* искомая площадь равна <math>S\frac{M}{N}</math>.
 
* искомая площадь равна <math>S\frac{M}{N}</math>.
−
 
+
Далее данный алгоритм повторяется N раз, после чего результаты испытаний усредняются. Для достижения наибольшей точности число N должно быть достаточно большим.
−
Для малого числа измерений интегрируемой функции производительность Монте-Карло интегрирования гораздо ниже, чем производительность детерминированных методов. Тем не менее, в некоторых случаях, когда функция задана неявно, а необходимо определить область, заданную в виде сложных неравенств, стохастический метод может оказаться более предпочтительным.
 
−
 
 
−
Очевидно, что точность вычислений можно увеличить, если область, ограничивающая искомую функцию, будет максимально к ней приближена. Для этого необходимо использовать случайные величины с распределением, форма которого максимально близка к форме интегрируемой функции.
 
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 +
Таким образом, вычислительным ядром последовательной реализации данного алгоритма является многократное проведение одинаковой последовательности действий по определению площади под графиком функции.
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
 +
Согласно описанию вычислительного ядра алгоритма в качестве макровершины можно взять последовательность действий, использующуюся для определения площади под графиком функции и представленную в рамках математического описания алгоритма.
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
 +
Пусть интегрируемая функция имеет следующий вид
 +
 +
[[Файл:0_step.png]]
 +
 +
Последовательность исполнения метода следующая. В цикле осуществляется выполнение последовательности действий:
 +
 +
1. Функция ограничивается прямоугольником площадью <math>S</math>
 +
 +
[[Файл:1_step.png]]
 +
 +
2. В прямоугольнике случайным образом выбираются координаты <math>N</math> точек
 +
 +
[[Файл:3_step.png]]
 +
 +
3. Определяется число <math>M</math> точек, координаты которых попали под график функции
 +
 +
[[Файл:4_step.png]]
 +
 +
4. Искомая площадь вычисляется согласно формуле <math>S\frac{M}{N}</math>
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
 
=== Информационный граф ===
 
=== Информационный граф ===

Версия 00:06, 22 октября 2017

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

Годом рождения метода Монте-Карло считается 1949 год, когда в свет выходит статья Метрополиса и Улама «Метод Монте-Карло»[1]. Название метода происходит от названия города в княжестве Монако, широко известного своими многочисленными казино, поскольку именно рулетка является одним из самых широко известных генераторов случайных чисел.

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

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

Рассмотрим использование метода Монте — Карло для задачи вычисления кратных интегралов.

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

Для определения этой площади можно разбить отрезок, по которому производится интегрирование, на подотрезки, подсчитать площадь под графиком функции на каждом из них и сложить. И если предположить, что в случае функции одной переменной достаточно разбиения на 50 подотрезков и, соответственно, 50 вычислений значений функции, то в случае функции [math]n[/math] переменных количество подотрезков и вычислений значений функции возрастает до [math]50^n[/math]. При размерности функции больше 10 задача становится очень громоздкой. Поскольку пространства большой размерности встречаются во многих задачах, необходимо иметь метод решения, вычислительная сложность которого бы не столь сильно зависела от размерности. Именно таким свойством обладает метод Монте-Карло.

1.2 Математическое описание алгоритма

При использовании метода Монте — Карло для определения площади под графиком функции применяется следующий стохастический алгоритм:

  • функция ограничивается прямоугольником площадью [math]S[/math], в случае [math]n[/math] переменных [math]n[/math] — мерным параллелепипедом;
  • в данном прямоугольнике случайным образом выбираются координаты [math]N[/math] точек;
  • определяется число [math]M[/math] точек, координаты которых попали под график функции;
  • искомая площадь равна [math]S\frac{M}{N}[/math].

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

1.3 Вычислительное ядро алгоритма

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

1.4 Макроструктура алгоритма

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

1.5 Схема реализации последовательного алгоритма

Пусть интегрируемая функция имеет следующий вид

0 step.png

Последовательность исполнения метода следующая. В цикле осуществляется выполнение последовательности действий:

1. Функция ограничивается прямоугольником площадью [math]S[/math]

1 step.png

2. В прямоугольнике случайным образом выбираются координаты [math]N[/math] точек

3 step.png

3. Определяется число [math]M[/math] точек, координаты которых попали под график функции

4 step.png

4. Искомая площадь вычисляется согласно формуле [math]S\frac{M}{N}[/math]

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. ↑ N. Metropolis, S. Ulam The Monte Carlo Method, — J. Amer. statistical assoc. 1949 44 № 247 335—341.
  2. ↑ Соболь И. М. Метод Монте-Карло. — М.: Наука, 1968. — 64 с. — (Популярные лекции по математике). — 79 000 экз.
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Grachovamc/Вычисление_кратного_интеграла_методом_Монте_-_Карло.&oldid=23199