Случайный выбор как правило сводится к проблеме получения случайных чисел, равномерно распределенных на отрезке Действительно, пусть на отрезке•[0,1 случайным образом выбрано число Тогда число а + (b-a)m. будет случайно выбранным на заданном отрезке [а,Ь]. Следовательно, для случайного выбора точки θ в n-мерном параллелепипеде (1) достаточно получить n случайных чисел 0£m. £1 и затем проинтерпретировать числа аk + (bk – ak)mk как набор координатточки.θ.
Существует много таблиц, представляющих собой последовательность случайных равномерно распределенных на отрезке[0,1] чисел. Эти таблицы можно вводить в ЭВМ и хранить на магнитных носителях в виде файлов для многоразового использования
В настоящее время наиболее удобным и распространенным способом получения случайных чисел является вычисление их на ЭВМ по специальному алгоритму (обычно хранимому его разработчиками в секрете). Числа, получаемые таким путем, называются псевдослучайными, так как, строго говоря, они не являются случайными. Хороший алгоритм вырабатывает псевдослучайные числа, обладающие статистическими свойствами вполне случайных чисел.
Следует иметь ввиду, что для любого алгоритма рано или поздно наступает критический момент, после которого он начинает циклически выдавать одну и ту же подпоследовательность псевдослучайных чисел.. С этого момента генерируемые им числа становятся непригодными для использования в методе Монте-Карло. Неопределенность наступления такого момента является органическим изъяном метода получения, случайных чисел с помощью алгоритмов. Качество алгоритма псевдослучайных чисел проверяется специальными тестами. Хорошим можно считать алгоритм, который надежно выдает не менее 100000 равномерно распределенных псевдослучайных чисел без циклических повторов.
В языках программирования псевдослучайные числа генерируются специальной функцией - датчиком псевдослучайных чисел. Однократный вызовэтой функции позволяет получить очередное псевдослучайной число. Перед первым вызовам функции обычно выполняется оператор инициализации датчика псевдослучайных чисел. Если инициализации не провести, то функция-датчик будет генерировать одну и ту же последовательность псевдослучайных чисел при разных запусках программы.. Это можег быть удобно при отладке программы. При использовании оператора инициализации функция выдаетразные последовательности чисел при разных запусках программы.
Функция-датчик генерирует числа, равномерно распределенные в полуинтервале 0£θ < 1. Это значит, что -функций выдает числа, не совсем равномерно распределенные на отрезке [0,1] (так как значение 0=1 невозможно; эта несимметричность объясняется особенностями представления чисел в ЭВМ) Однако, это обстоятельство может привести лишь к ошибке, на много порядков меньшей, чем та точность, которую реально позволяет достичь метод Монте-Карло. В различных языках и их версиях оператор инициализации датчика и сам датчик псевдослучайных чисел записываются по разному.
| MSX –бейсик, Бейсик УКНЦ | Паскаль | |
| Оператор инициализации датчика Функция -датчик псевдослучайных чисел | A = RND(-TIME) RND(1) | Randomize Random |
В качестве иллюстрации приведем программу на языке Бейсик, позволяющую вычислить интеграл от функции
(8) - 
по области, заданной неравенствами
10 A=RND (-TIME)
20 I=1 TO 100
30 J=1 TO 100
40 X1!=7RND(1)
50 X2!=-4+14RND(1)
60 X3!=-8+14RND(1)
70 X4!=1+8RND(1)
80 IF (X4!-5)2+(X1!-4)2>16 THEN 130
90 IF X1!2+(X2!-3)2+(X3!+1)2>49 THEN 130
100 F!=X1!+X2!X2!+(X3!X4!)2
110 S1!=S1!+F!
120 S2!=S2!+F!F1
130 NEXT J
140 PRINT «Проведено»; I*100; «испытаний.»
150 NEXT I
160 PRINT «Сумма значений f равна»; S1
170 PRINT «Сумма ее квадратов равна»; S2
Программа проводит 10000 испытаний. Чтобы можно выло слепить за ходом вычислений, после каждых 100 проведенных испытаний на экран выдается соответствующее сообщение. В результате программа выдает сумму 10000 случайных значений функции и сумму квадратов этих же значений. Для ускорения работы программы в ней использованы переменные одинарной точности, позволяющие вести вычисления с 6 значащими цифрами. Этой точности вполне достаточно, так как погрешность метода Нанте-Карло будет заведомо больше.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1Некая информационная служба решила выяснить методом выборочного опроса мнение(совершеннолетних) жителей г. Костромы о законе по приватизации жилья. Было предложено опросить по одному жильцу из каждого жилого дома (предлагалось выбирать из списка жильцов первого по алфавиту, достигшего совершеннолетия). /Будет ли такой опрос носить случайный характер? Почему?
2. Формула оценки точности метода Манте-Карло (6) имеет характерное отличие от аналогичных оценок для квадратурных формул. Какое?3.
3 Оценка точности по формуле (4) является априорной или апостериорной? Почему?
Указание. Примите во внимание метод нахождения σ по формуле (5).
4. Для вычисления одномерных интегралов метод Монте-Карлр нецелесообразно использовать. Почему? Почему квадратурные формулы оказываются удобнее и дают более точный результат?
5. Какие преимущества имеет метод Монте-Карло перед квадратурными формулами при вычислении многомерных интегралов? (Назовите два основных преимущества.)
6.Пусть некоторый генератор псевдослучайных чисел выдает последовательность чисел, в целом равномерно распределенных по отрезку [0.1), но обладающих одной специфической особенностью: нечетные члены последовательности явно чаще оказываются в первой половине отрезка, а четные члены – во второй его половине. К каким неприятностям может привести использование этого генератора в методе Монте-Карло?
Указание. Попробуйте придумать пример, когда вычисление объема методом Монте-Карло с использованием этого генератора приведет к грубой ошибке.
7.Предположим, некоторый алгоритм генерации псевдослучайных чисел дывает 10000 чисел, а затем их циклически повторяет. Каковы, на ваш взгляд, могут быть последствия применения такого алгоритма или интегралов методом Монте-Карло с использованием скажем 100000?
8. При вычислении объемов методом Монте-Карло оценка точности по формуле (4) может оказаться неверной. Причины могут быть разные, например:
1. допущена ошибка в программе;
2. очень мало число испытаний (точек);
3. объем области на много порядков меньше объема параллелепипеда… А еще какие причины вы можете назвать?