3. 1. Метод статистических испытаний. 1 страница

МГУПИ Военная кафедра

Грама В.С.

3.1. МЕТОД СТАТИСТИЧЕСКИХ ИСПЫТАНИЙ.

3.1.1. Общее представление о методе.

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

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

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

Теорема Бернулли:

Если проводиться N независимых испытаний, в каждом из которых некоторое событие A происходит с вероятностью P, относительная частота появления события при сходится по вероятности к P, т.е. при любом

Теорема Чебышева:

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

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

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

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

Сущность метода статистических испытаний заключается в следующем:

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

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

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

- случайные входные параметры.

Искомая величина выражается через числовые характеристики выходных параметров некоторой вероятностной модели.

Блок-схема моделирующего алгоритма вычисления значения функционала представлена на рис. 3.1.1

Рис. 3.1.1

Этапы вычисления функционала:

1. Задаются детерминированные входные переменные .
2. Проводится серия из N испытаний .

Количество испытаний N выбирается исходя из заданной точности и достоверности вычислений.

В каждом i-ом испытании:

* с помощью датчиков случайных чисел подчиненных простому (ПЗР) или заданному (ЗЗР) закону распределения моделируются значения случайных параметров .

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

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

Количество испытаний N выбирается исходя из требуемой точности и достоверности результата.

3. После всех испытаний методами математической статистики определяются оценки числовых характеристик выходных параметров и, соответственно, оценка искомой величины , при этом .

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

Пример1. Исследуется стохастическая система, выходной параметр которой , где - детерминированный входной параметр, а - случайный параметр, закон распределения которого задан.

Необходимо методом статистических испытаний определить математическое ожидание случайной величины .

Данная задача является вероятностной. Искомая величина - , т.е. выражена через математическое ожидание выходного параметра.

Определение приближенного значения величины состоит в следующем:

- задается значение параметра ;

- проводится серия из , в каждом из которых с помощью ДСЧ

с ЗЗР получаем некоторое значение СВ - , и определяем

значение ;

- на основании полученной выборки значений

вычисляется оценка искомой величины

.

Пример 2: Необходимо вычислить площадь произвольной области s, расположенной внутри единичного квадрата (рис. 3.1.2).

Рис. 3.1.2.

Границы области описаны аналитически:

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

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

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

Если моделировать случайную точку () равномерно распределенную в единичном квадрате, то вероятность попадания её в область будет численно равна площади области :

Таким образом, эквивалентная вероятностная модель вычисления площади области будет иметь вид:

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

По результатам N испытаний , где - количество точек, попавших в область .

Особенности метода СИ:

1. Вычислительный процесс метода СИ не является детерминированным, т.е. является случайным.

2. Возможность применения метода для решения задач, не сформулированных в виде уравнений или формул.

3. Метод применим только в том случае, если возможно построение вероятностной модели процесса.

4. Метод является своего рода сходящимся; чем больше проведено испытаний, тем вероятнее получение точного результата.

5. Эффективное применение метода возможно при использовании ЭВМ.

6. Для решения задач методом СИ необходимо иметь последовательности случайных чисел подчиненным разным законам распределения.

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

- последовательности случайных чисел равномерно распределенных в интервале [0,1];

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

3.1.2. Точность метода статистических испытаний.

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

не отклонится результат с заданной вероятностью, т.е.

(1)

- истинное значение параметра;

- оценка искомого параметра;

e - заданная абсолютная погрешность (точность);

a - заданная вероятность (достоверность).

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

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

Пусть: X - некоторая СВ,

A - некоторое событие,

- истинное значение параметра ( или ),

- оценка искомого параметра ( или ).

P(A): Введем СВ Тогда оценка вероятности появления некоторого события А имеет вид:

M[X]: Задана СВ X Оценка математического ожидания некоторой СВ X имеет вид:

где -значение СВ X, которое она принимает в каждом i-ом испытании (). Таким образом можно записать:

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

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

Поэтому для достаточно большого N имеет место соотношение:

(2),

или

Для определения по заданному a решается уравнение

,

где erf - табличная функция (функция ошибок):

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

Из выражений (1) и (2) следует, что для заданной точности e с достоверностью a должно выполняться неравенство

(3)

Вычислим значение через известное :

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

.

P(A): если значение P известно, то

M[X]: - задано

Окончательно получаем, что для вычисления оценок M[X] и P(A) с требуемой точностью и достоверностью необходимое количество испытаний должно быть:

, (4) - при вычислении M[X]:

, (5) - при вычислении P(A).

Если искомая величина W выражается одновременно через M[X] и P(A) и при этом для вычисления должно быть проведено испытаний, а для вычисления - испытаний, то количество испытаний для вычисления W должно выбираться таким, чтобы обеспечить данные точность и достоверность вычисления и одновременно.

Если значение вероятности P(A) и среднеквадратичное отклонение заранее неизвестны, требуемое количество испытаний N в общем случае определяется методом подбора.

Определение N методом подбора.

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

и проверяется выполнение соответственно условия (4) или (5).

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

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

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

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

Сущность способа: в выражение (5) для определения количества испытаний N, подставляется максимальное значение функции Из рис. 3.1.13 видно, что

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

Рис. 3.1.13

3.1.3 Моделирование последовательностей случайных чисел с простым законом распределения.

3.1.3.1 Последовательности случайных чисел и способы их формирования.

Для решения задач методом статистических испытаний необходимо иметь последовательности случайных чисел (СЧ), подчиненных различным законам распределения.

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

Описывая (характеризуя) последовательность СЧ необходимо указывать следующие ее основные характеристики:

Ряд распределения.

Дифференциальный закон распределения f(x).

Интегральный закон распределения F(x).

Математическое ожидание M[X].

Дисперсию D[X].

Основным (простым) законом распределения случайных чисел, используемых в методах статистических испытаний, является закон равномерного распределения случайных чисел в интервале [0,1].

Последовательность СЧ X называется равномерно распределенной в интервале [0,1], если плотность распределения вероятностей f(x) определяется как:

.

В этом случае функция распределения F(x) имеет вид:

.

Математическое ожидание M[X] и дисперсия D[X] соответственно равны:

Существуют различные способы получения случайных чисел:

* генерирование случайных чисел специальными датчиками

(механическими, физическими);

* табличное задание случайных чисел;

* аналитический способ получения случайных чисел

(программные датчики случайных чисел).

К простейшим механическим датчикам относятся: бросание монеты, извлечение пронумерованных шаров из урны, “рулетка” и т. д.

Например, результат каждого бросания монеты можно рассматривать, как двоичный знак некоторой бесконечной двоичной дроби. Так как вероятность таким появления 0 или 1 одинакова, то полученное число будет распределено равномерно в интервале [0,1].

Механические датчики могут быть применены при расчетах вручную и не пригодны для ЭВМ.

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

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

В 1927 году Леонард Типпет опубликовал таблицы, содержащие свыше 40000 случайных цифр, произвольно взятых из отчета

з

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

Первую такую машину в 1939 году использовали М. Дж. Кендалл и Б. Бебингтон - Смит при создании таблиц, включающих 100000 случайных цифр.

В 1955 году компания RAND Corporation опубликовала таблицы с 1 млн. случайных чисел, полученных другой такой машиной.

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

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

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

Рис. 3.1.4

Если несколько генераторов работают параллельно, то в каждом такте будет вырабатываться k-разрядное двоичное число.

Недостатки физических датчиков:

* трудность осуществления контроля за их работой в процессе решения задачи,

* невозможно воспроизвести повторно одну и ту же последовательность случайных чисел.

* Наибольшее распространение получил аналитический способ формирования последовательностей случайных чисел, то есть случайные числа вырабатываются на ЭВМ программным способом с помощью какого-либо рекурентного соотношения. При этом каждое число , вырабатываемое программным ДСЧ, образуется из предыдущего в результате вычислений.

* Получаемая при этом последовательность чисел, не являясь случайной, может удовлетворять различным статистическим критериям, т. е. вести себя как случайная. Такие числа называются псевдослучайными (ПСЧ).

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

* Рассмотрим основные характеристики ПСЧ с квазиравномерным законом распределения.

* В ЭВМ с длинной машинного слова - k ПСЧ представляются в виде:

* ,

* где принимает значения 0 или 1 с одинаковой вероятностью , при этом:

* , тогда

* ,

* .

* Заметим, что и при , то есть с увеличением количества разрядов мантиссы чисел x закон распределения асимптотически приближается к равномерному.

* 3.1.3.2 Аналитические методы получения последовательностей псевдослучайных чисел.

*

* Изобрести простой качественный датчик ПСЧ не так легко. Можно разработать сложный алгоритм, который, казалось бы, должен обеспечить достаточно сложную последовательность чисел. Однако при практической реализации этого алгоритма на ЭВМ, выясняется, что это совсем не так.

* Рассмотрим некоторые методы получения последовательности ПСЧ.

*

* Метод середины квадратов.

* Берется k-разрядное число (k кратно четырем), возводится в квадрат и выбирается k средних разрядов. В результате получается первое псевдослучайное число. Затем это число берется в качестве исходного и действия повторяются для получения второго псевдослучайного числа и т. д.

Дата добавления: 2015-09-30