Построение систем распознавания образов (стр. 21 из 36)
-многомерные интегралы;
-теория обнаружения сигналов;
-обращение матриц и решение систем линейных алгебраических уравнений;
-некоторые краевые задачи;
-нахождение собственных значений и собственных функций и др.
5.3.2.Принципы получения случайных величин на ЭВМ
Датой рождения метода Монте-Карло принято считать 1949 г , когда в американском журнале ассоциации статистиков появилась статья Метрополиса и Улама “ Метод Монте-Карло”. Создателями метода считают Дж.Неймана и С.Улама. В Советском Союзе первые статьи о методе относятся к 1955-1956 годам.
Теоретические основы метода Монте-Карло известны уже давно. Более того, некоторые задачи статистики решались с использованием случайных выборок, то есть, фактически этим методом. Но так как моделировать случайные величины вручную - очень трудоемкая работа, широкое применение метода началось с появления вычислительных машин.
Само название “Монте-Карло” происходит от названия города в княжестве Монако, знаменитого своими игорными домами. Все дело здесь в том, что одним из простейших механических устройств для получения случайных величин является рулетка. Простейшая схема ее - вращающийся диск с цифрами, резко останавливающийся для определения цифры, на которую указывает неподвижная стрелка.
Пуская и останавливая рулетку и объединяя получаемые в каждом пуске цифры в группы заданного размера (например, пять), можно составить таблицу случайных цифр (в случае примера группирования - пятизначную). Таблица эта носит название таблицы случайных чисел, хотя правильнее было бы назвать ее таблицей случайных цифр. Самая большая такая таблица (RAND Corporation, 1955 г) содержит 1 000 000 цифр.
Составление таблиц случайных чисел - не такая простая задача. Если мы хотим иметь хорошую таблицу, то придется при разработке ее тщательно проверять, так как любое физическое устройство вырабатывает случайные числа отличающимися по распределению от равномерного.
Ну, а используются такие таблицы либо для ручного счета, что сегодня - редкость, либо при машинном применении приходится поступаться тем, что при вводе соответствующий файл потребует большой памяти в ущерб решаемым при этом задачам.
Для устранения этого недостатка казалось бы легче подключить рулетку к ЭВМ. Однако ясно, что быстродействие такого комплекса генерации случайных чисел будет исключительно низким. Поэтому в качестве генераторов случайных величин чаще используются шумы в электронных лампах. Например, здесь может быть предложен следующий алгоритм. Если за некоторый фиксированный промежуток времени Dt уровень шума превысил заданный порог четное число раз, то в разряд некоторого числа записывается единица, если нечетное - ноль.
Так как количество такого рода генераторов выбирают равным количеству разрядов упомянутого числа в ЭВМ, то во все эти разряды будут записаны нули и единицы. Каждый такт такой логической проверки всех генераторов дает одно полноразрядное число, равномерно распределенное в интервале [0,1].
Недостатки этого метода генерации:
1)Возможны неисправности электронных генераторов шума, приводящие к пропаданию равновероятности нулей и единиц, что требует постоянных проверок и ремонта.
2)Невозможно повторение случайной последовательности чисел, полученной в одном эксперименте, для проверки работы программы ЭВМ.
Поэтому такого рода датчики применяются в специализированных ЭВМ для решения задач методом Монте-Карло.
Для универсальных ЭВМ такие датчики - слишком дорогостоящее оборудование, так как в таких ЭВМ прибегают к расчетам с использованием случайных чисел достаточно редко. Но чтобы не исключить полностью такую возможность здесь лучше использовать так называемые псевдослучайные числа.
Генерация псевдослучайных чисел осуществляет сама машина в соответствии со специальными стандартными функциями, предусматриваемыми в ее математическом обеспечении.
Можно вообще не интересоваться, как эти числа получаются. Указанные стандартные функции неоднократно проверяются разработчиками и качество их гарантируется. Однако сама постановка вопроса “получение псевдослучайных чисел” на ЭВМ вызывает недоумение. Ведь все, что делает машина, должно быть заранее запрограммировано. Поэтому хотелось бы понимать, откуда появляется случайность. Кроме того, без понимания особенностей псевдослучайных последовательностей, хотя бы поверхностного, трудно говорить иногда о их разумном использовании.
Что же такое псевдослучайные числа?
Числа, получаемые по какой-либо формуле и имитирующие значения случайной величины, называются псевдослучайными.
Под словом “имитирующие” подразумевается, что эти числа удовлетворяют ряду требований так, как если бы они были значениями случайной величины.
Первый алгоритм для получения псевдослучайных чисел был предложен Дж.фон Нейманом в 1951 г. Он получил название метода середины квадратов. . Существо его заключается в следующем.
Пусть задано произвольное 4-значное целое число n1= 9876.
Возведем его в квадрат и получим 8-значное число n12 = 97535376.
Выберем 4 средние цифры из этого числа и обозначим n2= 5353.
Затем снова возведем его в квадрат n22 = 28654609 и выберем 4 средние цифры. В результате получим n3 = 6546.
Продолжая указанные рекуррентные действия будем иметь
n4 = 8501; n5 = 2670; n6 = 1289 и т.д.
В качестве псевдослучайных значений предлагалось использовать
gк = 10 -4 *n к ,
то есть:
0.9876; 0.5353; 0.6546; 0.8501; 0.2670; 0.1289 и т.д.
Таков самый простой алгоритм, обладающий отдельными недостатками, на которых не будем задерживать внимание. Главное то, что они заставили в последующем обратиться к более сложным алгоритмам. Но схема получения псевдослучайных чисел осталась фактически неизменной: очередное значение получается из предыдущего или предыдущих.
Рассмотрение теории вопроса и других алгоритмов не входит в планы нашего курса, но нам необходимо знать один важный вывод из соответствующих разделов, имеющий практическое значение:
рекуррентно получаемые псевдослучайные последовательности обладают периодом, величина которого зависит главным образом от разрядности представления чисел в машине.
С точки зрения теории вероятностей - это плохо. Однако там, где длины генерируемых последовательностей удовлетворяют потребителя, появляется такое достоинство как возможность отработки программного обеспечения сложных систем при одних и тех же последовательностях.
Ну, а рекуррентность получения псевдослучайных последовательностей и определенный период позволяют повторять генерацию последовательности любое число раз, что невозможно для физических датчиков случайных чисел и что так важно для отладки специфических программ.
В целом достоинства методов получения псевдослучайных чисел заключаются в следующем:
1) на получение каждого числа затрачивается всего несколько простых операций, в результате чего скорость генерирования случайных чисел имеет тот же порядок, что и скорость работы ЭВМ.
2) программы получения псевдослучайных чисел чрезвычайно компактны в силу простоты рекуррентных соотношений.
3) любое псевдослучайное число может быть легко воспроизведено.
4) последовательность псевдослучайных чисел достаточно один раз аттестовать, а затем постоянно использовать в сходных задачах без опасения изменения характеристик.
Л Е К Ц И Я 5.4
Метод статистических испытаний
(продолжение)
5.4.1. Моделирование независимых случайных событий
Возможность генерации псевдослучайных чисел, равномерно распределенных на интервале [0,1], открывает широкие возможности для статистического моделирования вообще во всех его приложениях.
Наиболее важным в задачах статистических испытаний представляется моделирование независимых случайных событий. Здесь существо задачи состоит в том, что необходимо воспроизвести случайное событие А, наступающее с вероятностью p.
Если для этого воспользоваться квазиравномерной последовательностью, то интересующая вероятность в общем виде может рассматриваться как результат интегрирования соответствующей плотности распределения вероятностей
где z - некоторый пока неопределенный предел; fрр(x)- плотность вероятностей равномерно распределенных чисел.
Но для равномерного распределения на интервале [a,b] имеем
Для чисел равномерных на интервале [0,1] будем иметь
f рр(x)= 1 и соответственно
Отсюда очевидно z = p.
Тогда понятно, что реализация события А с вероятностью p осуществляется тогда, когда равномерно распределенные числа на интервале [0,1] попадают в его часть [0,p].
Следовательно, процедура моделирования появления случайного события А должна состоять в генерации случайных чисел R 4i 0 и сравнении их с величиной p : Ri <= p
Выполнение неравенства соответствует наступлению события А.
Рассмотренные соображения распространяются на моделирование полной группы событий . A1,A2,…,Am , наступающих с вероятностями p1,p2 ,…,pm, для которых естественно определено:
p1 + p2 +…+ pm = 1.
Здесь, используя ту же квазиравномерную последовательность, можем записать условия наступления любого события As из представленной группы:
Тогда действительно:
