Основы построения систем распознавания образов
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
>
y = g(x)
x
1
Рис.5.3.1.
Будем рассматривать две области на плоскости (x,y)
- область, заданная неравенствами
0<= x <=1
0<= y <=1
w - область, ограниченная кривой y = g(x) и ординатами x=0 и x = 1.
Площадь области равна единице S1=1, а площадь областиw2 = I.
Зададим в области равномерное распределение случайных точек. Это означает, что вероятность попадания точки с координатамиxi,yi в область равна 1, а в некоторую часть этой области - пропорциональна площади этой области независимо от ее расположения внутри .
Плотность заданного распределения вероятностей f(x,y) = 1
w
Таким образом, I = S2.
Если теперь мы располагаем возможностью имитировать случайные точки с координатами xi, yi в соответствии с заданной плотностью, то после N испытаний, подсчитав число тех из них (m), которые попали в область w, получим частость
Вспоминаем, что частота при N стремится к истинному значению, а в качестве приближенного значения интеграла следует использовать указанную частоту.
Подводя итог рассмотренному примеру с точки зрения введенного определения метода Монте-Карло, отметим, что
-решаемая задача относится к области вычислительной математики;
-для решения задачи формировалась случайная последовательность чисел как выборка значений из последовательности с равномерной плотностью распределения вероятностей, попадающих в областьw;
-искомая величина определялась как отнесение числа попаданий в область w к общему числу экспериментов.
Рассмотренных примеров уже вполне достаточно для того, чтобы пояснить данное в начале определение метода статистических испытаний. В то же время следует иметь в виду , что существует большое многообразие задач, для которых метод Монте-Карло является плодотворным, позволяя достигать инженерного результата там, где аналитические методы либо сложны, либо не дают ответа. В этом аспекте необходимо отметить такие области применения, как
-многомерные интегралы;
-теория обнаружения сигналов;
-обращение матриц и решение систем линейных алгебраических уравнений;
-некоторые краевые задачи;
-нахождение собственных значений и собственных функций и др.
5.3.2.Принципы получения случайных величин на ЭВМ
Датой рождения метода Монте-Карло принято считать 1949 г , когда в американском журнале ассоциации статистиков появилась статья Метрополиса и Улама “ Метод Монте-Карло”. Создателями метода считают Дж.Неймана и С.Улама. В Советском Союзе первые статьи о методе относятся к 1955-1956 годам.
Теоретические основы метода Монте-Карло известны уже давно. Более того, некоторые задачи статистики решались с использованием случайных выборок, то есть, фактически этим методом. Но так как моделировать случайные величины вручную - очень трудоемкая работа, широкое применение метода началось с появления вычислительных машин.
Само название “Монте-Карло” происходит от названия города в княжестве Монако, знаменитого своими игорными домами. Все дело здесь в том, что одним из простейших механических устройств для получения случайных величин является рулетка. Простейшая схема ее - вращающийся диск с цифрами, резко останавливающийся для определения цифры, на которую указывает неподвижная стрелка.
Пуская и останавливая рулетку и объединяя получаемые в каждом пуске цифры в группы заданного размера (например, пять), можно составить таблицу случайных цифр (в случае примера группирования - пятизначную). Таблица эта носит название таблицы случайных чисел, хотя правильнее было бы назвать ее таблицей случайных цифр. Самая большая такая таблица (RAND Corporation, 1955 г) содержит 1 000 000 цифр.
Составление таблиц случайных чисел - не такая простая задача. Если мы хотим иметь хорошую таблицу, то придется при разработке ее тщательно проверять, так как любое физическое устройство вырабатывает случайные числа отличающимися по распределению от равномерного.
Ну, а используются такие таблицы либо для ручного счета, что сегодня - редкость, либо при машинном применении приходится поступаться тем, что при вводе соответствующий файл потребует большой памяти в ущерб решаемым при этом задачам.
Для устранения этого недостатка казалось бы легче подключить рулетку к ЭВМ. Однако ясно, что быстродействие такого комплекса генерации случайных чисел будет исключительно низким. Поэтому в качестве генераторов случайных величин чаще используются шумы в электронных лампах. Например, здесь может быть предложен следующий алгоритм. Если за некоторый фиксированный промежуток времени t уровень шума превысил заданный порог четное число раз, то в разряд некоторого числа записывается единица, если нечетное - ноль.
Так как количество такого рода генераторов выбирают равным количеству разрядов упомянутого числа в ЭВМ, то во все эти разряды будут записаны нули и единицы. Каждый такт такой логической проверки всех генераторов дает одно полноразрядное число, равномерно распределенное в интервале [0,1].
Недостатки этого метода генерации:
1)Возможны неисправности электронных генераторов ?/p>