Б.П. Демидович, И.А. Марон - Основы вычислительной математики (1132358), страница 82
Текст из файла (страница 82)
А именно, по способу построения, для Рнс. 84. последовательности (у„) будет справедливо предельное соотношение ь ц„„(л, ь) (4) л-но П и где ен (а, Ь) — число элементов конечной подпоследовательности у,) ..;, у„, принадлежащих произвольному промежутку (а, Ь). В частности, полагая аз 1 р(у)==а ' Уъ этим способом получим каноническую нормально распределенную (гауссову) случайную последовательность (у„), соответствующую случайной велячине У с математическим ожиданием л4У=О н дисперсией .0У=1. Линейное преобразование я„=ау„+с (л=1, 2, ...) дает нормально распределенную случайную последовательность (г„), соответствующую случайной велнчине Е, для которой математическое ожидание МУ=с и дисперсия ЮЕ=оа.
МЕТОД МОНТЕ-КАРЛО $3. Способы получения случайных чисел [гл, хчп Для выработки случайных чисел можно использовать результаты случайныхфизическнх процессов(например, бросание игральной кости, вращение рулетки, вспышки в счетчике Гейгера, шум при электрических передачах н т. и.). Имеются также готовые таблицы случайных чисел (см., например, (7], [8)). Строго говоря, при пользовании механическими приспособлениями для получения случайных чисел нет абсолютной уверенности, что мы имеем дело со случайными событиями с заданным распределением вероятностей.
Поэтомуполученныйматериалобычно подвергается статистической «проверке на случайность>. В этом смысле надежнее употреблять случайные числа из таблиц, где такая проверка уже проделана; однако использование таблиц случайных чисел для решения задач на электронных цифровых машинах часто связано с серьезными неудобствами [9).
Для решения задач методом Монте-Карло обычно требуется весьна большое количество случайных чисел. Эти числа практически наиболее удобно получаются с помощью слеииальиык датчиков случайных чисел, подключаемых к машине. Действие этих датчиков регулируется случайными физическими процессами (например, радиоактивным распадом, шумами в электронных лампах и 'т. п,) [9). Так как воспроизводство случайных чисел, отвечающих данной теоретической модели, есть процесс весьма тонкий н сложный, то на практике часто ограничиваются получением так называемых лсевдослучайиык чисел, в основных чертах похожих на соответствующие случайные. Источниками (датчиками) псевдослучайных чисел служат достаточно сложные математические алгорифмы. В дальнейшем под термином «случайное число» мы будем понимать как случайные, так и псевдослучайные числа, если различие между ними не имеет существанного значения.
Укажем некоторые простые приемы получения случайных чисел, в обобщенном смысле, равномерно распределенных на отрезке [О, 1). Для простоты будем предполагать, что эти числа представляют собой правильные десятичные дроби с фиксированным количеством десятичных знаков после запятой, например г (г-разрядные десятичные дроби), т. е. могут быть записаны в виде (1) где а, ([=1, 2, ..., г) — цифры этого числа, принимающие значе- нияО, 1,2,3,4,5,6,7,8,9.
Для составлении таблицы случайных чисел вида (1), равномерно распределенных на (О, 1), достаточно указать способы получения цифр а, с соблюдением следующих условий: * а) сс есть случайная выборка из системы чисел 0 — 9, причем все указанные значения равновероятны; 639 % 3) СПОСОБЫ ПОЛУЧЕНИЯ СЛУЧАЙНЫХ ЧИСЕЛ б) выбор предыдущей цифры и~ никоим образом не влияет на выбор последующей а;+,. Для получения а-разрядного случайного числа такая выборка производится з раз. Система выбора, удовлетворяющая условиям а) н б), практически может быть реализована многими способами. Рассмотрим некоторые нз них.
1. В урну опускают десять одинаковых перенумерованных шаров с номерами 0 — 9. Из урны последовательно извлекается шар и записывается его номера. После каждого извлечения шар возращают в урну н перед каждым следующим тнражом все шары в урне перемешиваются. 2. Одновременно бросают две игральные кости. Если лд н л — числа выпавших очков(л„ лт = 1, 2; 3, 4, 5, 6) соответственно на первой н второй костях (костя должны быть различаемыми), то очередная цифра а случайного числа берется равной остатку от деления суммы 6(лд — 1)+лз на 1О, где л,л.,6, т. е. а есть целое неотрицательное число, меньшее 10, удовлетворяющее сравнению"), 6(л — 1)+па=а(шоб 10).' (2) Если лд — 6, то кости перебрасываются.
Из формулы (2) вытекает, что цифра сг с равной вероятностью может принять любое значение от 0 до 9(см, [71). 3. Берется г-разрядное целое число. Число возводится в квадрат н выбираются средние з его разрядов; затем процесс повторяется. Если г достаточно велико, например г ~ 10, то выбираемые разряды могут быть приняты за наборы элементов а-разрядных псевдослучайных чисел [31. Для получения последовательности псевдослучайных чисел можно также использовать умножение многозначного числа на постоянный множитель н извлечение средних разрядов или возведение многозначного числа в квадрат и прнведенне результата по модулю некоторого достаточно большого простого числа.
4. Псевдослучайная последовательность [л„) вырабатывается с помощью процесса [101 лл 2 пл~ где и =1, и„ь =:5" и„(шоб2ш). 5. Используется десятичное разложение положительного нррацнонального числа '"=0 ()т[)А " 1. "=ре+(ы) где ра †цел часть числа ы н (ы) — его дробная часть. *) Запнсь а=Ь(шов Ь) (а, Ь, Ь вЂ” целые числа) обозначает, что разность 'а — Ь делится без Остатка на Ь. (гл. хтд! 640 метод монти"нагло Для получения случайной последовательности (х„) полагают: х„= (лв) (л = 1, 2,...).
Если требуется случайная последовательность, состоящая из г-разрядных чисел, то в числах (лв) ограничиваются соответствующими разрядамн. Для решения некоторых задач нужно иметь несколько случайных последовательностей (х!!>) (хои) (хдм)) В етом случае выбирают лд линейно независимых положительных иррациональностей в„в„..., в„и полагают: х!в=(лвь) (8=1, 2, '., лд; и=1, 2, ...). Можно также взять одну равномерно распределенную случайную последовательность (х„) и произвести из нее лд выборок: (хы х„+„ х,„+„ (х„х е, ...
хз +„...), Таблица 76 Случайные числа, равномерно расоределениме на отрезке [О, 1) 0,66674 0 99279 0,24202 0,940!О 0,60981 0,65339 0,93382 0,05758 0,00336 0,88222 0,11578 0,93045 0,93011 0,42844 0,52906 0,35483 0,09393 0,30304 0,55186 0,64003 0,57705 0,71618 0,737! 0 0,70131 0,16961 0,0946! 0,99602 0,69962 0,31311 0,27004 0,13094 0,35193 0,64560 0,64559 . 0,68008 0,98585 0,52103 0,91827 0,07069 0,13928 0,20514 0,00! 88 0,55709 0,86977 0,31303 0,53324 0,43166 0,26275 0,05928 0,66289 (х, хе, х,„, ...1, беря числа не подряд, а через лд элементов.
Очевидно, таким образом, мы будем иметь в равномерно распределенных подпоследовательностей.. С помощью этих и других методов составлены таблицы случайных чисел. В таких таблицах обычно даются случайные десятичные цифры; из них легко можно конструировать случайные числа определенного разряда. Для примера приводим часть одной из таблиц (см.(7!) пятиразрядных случайных чисел (таблица 76). $4) вычнсляния каатных интяггллов мятодом монти-клгло 641 В 4. Вычисление кратных интегралов методом Моите-Карло Пусть функция у=)(хт ха ° ° ° х ) непрерывна в ограниченной замкнутой области о и требуется вычислить ш-кратный интеграл у = ~ ~ ...
~'7(хы хю ..., х ) Лх, г(ха ... с(х . (1) (а) Геометрически число 1 представляет собой (пг+1)-мерный объем прямого цилиндроида") в пространстве Ох х ... х„у, построенного на основании о и ограниченного сверху данной поверхностью У у ГФ у=)(х), где х=(х„х„ ..., х ) (рис. 85).
Преобразуем интеграл (1) так, чтобы новая область интегрирования целиком содержалась внутри единичного гв-мерного куба. Пусть область Я расположена в лг-мерном параллелепипеде а; -хг(А~ (2) (Е=1, 2, ..., ш). Сделаем замену переменных хг — — а; +(Аг — а,)$,. (3) (1=1, 2, ..., т). Рис. 85. Тогда, очевидно, гл-мерный параллелепипед (2) преобразуется в ш-мерный единичный куб 0($,(1 (1=1, 2, ..., т) (4) и, слеловательно, новая область интегрирования а, которая находится по обычным правилам, будет целиком расположена' внутри этого куба (рис. 86). Вычисляя якобнан преобразовании будем иметь: Ад — аь О ... О О Аа — а, ... О Р(хмхю ...,х,) Р(6о С ° ° Фт) О О ... Ащ — аж =(А,— ат)(Аа — а,) ...
(А„— а ). *) Точнее, алгебраический объем, где предполагается, что части' цнлиидроида, расположенные выше гнперплоскости Окали ..., х„„имеют' положительную меру, а ниже — отрицательную. 642 (гл. хтп мвтод монти-кьгло Таким образом, 1 = К ... ~Р($„ $„ ..., $.)с%, %, ... 6., (а) где Рф,, $ю ..., $„)=(А,— а,)(А,— а,) ... (А„— а„)х х1(а +(А — ат)Кы аз+(Аз — аз)Я„..., а„+(А — а )Я ).
Введя обозначения (5) Ф=Й $з," $) (уа = а~,а~, запишем интеграл (5) короче в следующем виде: 1=)~ ... ~Р($)()а. (5') (О) Мы укажем два способа вычисления интеграла (5') методом случайных испытаний. Пе р в ы й способ. Выбираем лч равномерно распределенных на отрезке (О, () последовательностей случайных чисел: $(0 Ц)) ф()) зь(з) з(х) з(з) ьь[пв) зь(ию) ф(м) Точки М((ь(('), Я) )...„$( )) ((=), 2, ...) можно рассматривать Рис.
86. Рнс. 87. как случайные. Выбрав достаточно большое число Ф точек М, М... „М)г,' йроверяем, какие из них принадлежат области а $4) Вычисление кРАтных интеГРАлОВ методом монте-карло 643 (первая категория) и какие не принадлежат ей (вгорал категория). Пусть (рис. 87) 1) М!Ео при !=1, 2, ..., а (6) и 2) МЯ и при 1 = л+ 1, а -1- 2, ..., ))у (6') (для удобства мы здесь изменяем нумерацию точек!).
Заметим, что относительно границы Г области о следует заранее договориться, причисляются лн граничные точки или часть их к области и, или не причисляются к ней. В общем случае при гладкой границе Г вто не имеет существенного значения; в отдельных случаях нужно решать вопрос с учетом конкретной обстановки. Взяв достаточно большое число и точек М, Еп, приближенно можно положнтьл уср =,~~~! г (М!) ! с=! отсюда искомый интеграл выражается формулой ! =-У,ра= о 2;г'(М!), 1=1 где под и понимается ш-мерный объем областя интегрирования о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
