Методы Монте-Карло

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

. (*)

Рассмотрим один из простых вариантов метода Монте-Карло, который можно интерпретировать как статистический метод прямоугольников (рис. 4.17).

Рис. 4.17. Пример метода Монте-Карло (вариант 1 – статистический метод прямоугольников).

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

. (4.17)

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

Формула (4.17) непосредственно обобщается на кратные интегралы

,

где – объем области интегрирования.

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

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

,

откуда

.

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

,

что в итоге приводит к соотношению

,

которое совпадает с формулой (4.17).

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

приводится к виду ,

где на отрезке .

Для вычисления интеграла генерируются пары значений , , случайных величин x и y, равномерно распределенных на отрезке , которые можно рассматривать как координаты точек в единичном квадрате (рис. 4.18).

Рис. 4.18. Пример метода Монте-Карло (вариант 2).

При равномерном распределении точек в квадрате за приближенное значение интеграла принимается отношение количества точек , попавших под кривую или на нее, к общему числу испытаний (точек)

.

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

Рис. 4.19. Пример метода Монте-Карло (вариант 3).

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

.

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

Вопросы для самопроверки

1. Объясните геометрический смысл определенного интеграла, дайте определение интегральной суммы, приведите примеры.

2. Запишите формулу Ньютона-Лейбница и перечислите возможные причины ограниченности ее использования на практике.

3. С чем связано появление погрешности вычисления интегралов в численных методах интегрирования?

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

5. Поясните основную идею методов Ньютона-Котеса.

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

7. Поясните основную идею методов наивысшей алгебраической точности.

8. Поясните основную идею методов Монте-Карло.

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

10. Дайте определение узлов и шагов интегрирования, приведите примеры методов Ньютона-Котеса.

11. Запишите формулу левых прямоугольников для постоянного и переменного шагов интегрирования, поясните принцип ее выведения.

12. Запишите формулу правых прямоугольников для постоянного и переменного шагов интегрирования, поясните принцип ее выведения.

13. Запишите формулу средних прямоугольников для постоянного и переменного шагов интегрирования, поясните принцип ее выведения.

14. Приведите геометрические примеры погрешности для методов левых, правых и средних прямоугольников.

15. Объясните принцип замены подынтегральной функции полиномом первой степени.

16. Запишите формулу трапеций для постоянного и переменного шагов интегрирования, приведите геометрический пример.

17. Объясните принцип замены подынтегральной функции полиномом второй степени.

18. Запишите формулу Симпсона для вычисления определенных интегралов.

19. Объясните принцип определения значений коэффициентов полинома второй степени, используемого для замены подынтегральной функции.

20. Объясните принцип оценки погрешностей методов Ньютона-Котеса.

21. Дайте определение главного члена погрешности и порядка метода интегрирования, приведите примеры.

22. Объясните принцип вычисления интеграла с заданной точностью.

23. Дайте определение адаптивных алгоритмов и объясните принцип определения в них длины шага интегрирования.

24. Объясните принцип вычисления определенных интегралов от разрывных функций, приведите геометрические примеры.

25. Объясните принцип вычисления несобственных интегралов с бесконечной границей интегрирования, приведите геометрический пример.

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

27. Объясните принцип вычисления двойных интегралов по прямоугольной области интегрирования с помощью формул методов Ньютона-Котеса, приведите пример.

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

29. Поясните принцип выведения формулы Симпсона для вычисления двойного интеграла по прямоугольной области интегрирования.

30. Запишите формулу Люстерника для вычисления двойного интеграла по области нтегрирования, представляющей собой единичный круг, приведите геометрический пример.

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

32. Какова идея вычисления определенного интеграла методами Монте-Карло?

33. Объясните сущность первого варианта метода Монте-Карло.

34. Объясните сущность второго варианта метода Монте-Карло.

35. Объясните сущность третьего варианта метода Монте-Карло.

36. В чем заключается особенность численного интегрирования с использованием полиномов различных степеней?

37. Почему метод средних прямоугольников неприменим для численного интегрирования таблично заданных функций?

38. Каковы преимущества формулы Симпсона по сравнению с формулой трапеций и следствием чего являются данные преимущества?

39. Запишите формулу Симпсона для случаев деления исходного отрезка интегрирования на четное и произвольное количество частичных отрезков.

40. Запишите оценки погрешностей различных методов Ньютона-Котеса, проведите их сравнение.