Основы построения систем распознавания образов
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
µй может быть несколько. При таком разделении функций исчезает сложность разрабатываемых моделей. Этим, в частности, объясняется деление системных моделей на функциональные и комплексные. И если функциональные модели предназначаются для испытаний функционирования сложной системы в различных ситуациях, то комплексные обеспечивают:
-отработку и отладку программного обеспечения сложной системы;
-оценку характеристик отдельных средств и получение исходных данных для полной оценки системы.
Л Е К Ц И Я 5.3
Метод статистических испытаний
(метод Монте-Карло)
5.3.1. Основное определение
Из рассмотрения принципов построения моделей сложных систем следует, что при упрощениях модели и замене блоков, описывающих, как правило, воздействия на систему и ее части, эксперимент на системной модели сложной системы достаточно часто приобретает случайный характер. Случаен в силу этого и выходной эффект системы от запуска модели к запуску. Для проведения моделирования в таких условиях наиболее приемлемым является метод моделирования, основанный на статистических испытаниях, так называемый метод Монте-Карло.
Приемлемость указанного метода обусловливается тем, что
1)расчет оценок выходных параметров осуществляется с использованием достаточно простых алгоритмов обработки.
2)просто и точно определяется необходимый объем моделирования из условия достижения заданной точности оценок выходных показателей.
3)методика организации экспериментов на модели достаточно проста и хорошо программно реализуема.
В этом легко убедиться на простых примерах. А пока рассмотрим определение.
Метод статистических испытаний (метод Монте-Карло) состоит в решении различных задач вычислительной математики путем построения для каждой задачи случайного процесса с параметрами, равными искомым величинам этой задачи..
Рассмотрим простейшие примеры.
А. Пусть необходимо определить вероятность Pч того, что суммарное число попаданий при стрельбе в “десятку” мишени при 10 выстрелах - четно.
Известно, что если вероятность попадания в “десятку” при одном выстреле равна p , то искомая вероятность согласно биномиальному закону распределения вероятностей вычисляется так:
Здесь - число сочетаний из 10 по 2k.
Если предварительно подсчитать все числа сочетаний при k=0…5 или использовать готовую таблицу сочетаний, то вычисления Pч по указанной формуле потребуют 26 операций.
Вместо такого расчета можно было бы экспериментально выполнить N серий стрельб по 10 выстрелов и определить из их числа количество серий nч , в которых число попаданий в “десятку” - четное. Тогда при достаточно большом N имеем
Однако при таком подходе для получения достоверными в оценке Pч двух знаков после запятой потребуется около 10 000 серий по 10 выстрелов.
Оказывается, что ЭВМ позволяет выполнить решение указанной задачи третьим способом.
Как известно многие языки программирования имеют в составе стандартных функций датчик случайных чисел, позволяющий формировать случайную последовательность равномерно распределенных чисел на интервале [0,1].
Поэтому вместо выстрела по мишени достаточно выбрать из датчика указанное число со значением x и проверить выполнение неравенства x<p. Если оно выполнено, то это соответствует попаданию в “десятку” с вероятностью p. Покажем это.
Действительно вероятность попадания случайной величины в интервал [0;p] равна
,
где w(x) - плотность распределения вероятности
В нашем случае имеем дело с равномерным распределение на единичном интервале, то есть w(x) = 1. Поэтом P0;р = p.
Выбираем теперь серии из 10 чисел x. Если при этом число “попаданий” (выполнения неравенства x<p) будет четным, считаем серию удачной.
При N таким образом имитированных серий получим также, как и в прямом эксперименте со стрельбами
Однако в отличии от этого прямого эксперимента результат будет получен здесь на современной ЭВМ не более чем за 10 с.
Таким образом задача в рассмотренном случае была решена (согласно определению метода Монте-Карло) путем построения случайной последовательности с параметром, равным искомой величине Pч. Эта последовательность была построена следующим образом:
-формирование на первом этапе равномерно распределенной последовательности на интервале [0,1] ;
-формирование на втором этапе новой случайной последовательности (N серий) группировкой полученных на первом этапе значений в серии по 10;
-формирование на третьем этапе искомой случайной последовательности путем выборки из последовательности серий второго этапа размера N таких, в которых неравенство x<p выполняется четное число раз.
Количество серий третьего этапа формирования и определяет частость
которая при N стремится к искомой величине Pч .
Б.Еще один пример, но из области непосредственного применения метода Монте-Карло к вычислению интегралов.
Пусть необходимо вычислить
При этом будем считать, что 0<=x<=1 и 0<= g(x) <=1 , то есть вся функция лежит в единичном квадрате.
Такое ограничение не влияет на общность задачи, так как любой интеграл заменой переменных и изменением масштаба может быть приведен к рассматриваемому.
Y
1