Главная > Моделирование, обработка сигналов > Метод статистических испытаний (Монте-Карло) и его реализация на ЦВМ
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 14. Сопоставление метода статистических испытаний с обычными кубатурными формулами

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

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

Число операций существенно зависит от того, какую точность мы хотим получить, т. е.

Сравним этот способ с обычным методом вычисления интегралов.

Обычно используют кубатурные формулы вида

где точки -мерного куба.

Здесь количество операций равно и тоже зависит от требуемой точности

Естественно, при сравнении трудоемкости надо сопоставлять величины К и L при одинаковой точности Для этого нужно посмотреть, как зависят К и L от При одних значениях лучше метод статистических испытаний, при других выгоднее обычные кубатурные формулы.

Оценим сначала зависимость

В соответствии с (3.9)

Если вести речь о «максимальной» ошибке, то в данном случае можно принять распространенное правило «трех сигм». Тогда

Учитывая, что максимум величины равен 0,25, можно приближенно записать

Таким образом, величина имеет порядок

для любого числа измерений области интегрирования.

Сосчитаем теперь число операций для обычных кубатурных формул.

Рассмотрим квадратурную формулу для однократного интеграла:

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

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

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

Значит,

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

Здесь зависит от гладкости функции, число измерений.

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

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

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

Преимущества метода статистических испытаний обычно начинают сказываться при

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

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

Можно также указать на следующий, сравнительно просто доказываемый факт. Если «случайно» выбрать систему из N точек внутри -мерной области основываясь на равномерном законе распределения, то квадратурная формула

дает погрешность порядка где коэффициент а определяется гладкостью подынтегральной функции.

В заключение настоящего параграфа рассмотрим следующий пример.

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

В случае использования метода статистических испытаний для выполнения такой работы необходимо примерно операций, где N — число испытаний.

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

Результаты расчета представлены в таблице 2.

Таблица 2

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

<< Предыдущий параграф Следующий параграф >>
Оглавление