Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 46
Текст из файла (страница 46)
В книге Кнут (1969), с. 130, доказано, что Х, и Х, — независимые случайные величины, имеющие нормальное распределение Л( (О,1). Незначительная модификация этого метода была опубликована в виде программы языка АЛГОЛ 60 (Пайк (1965)). Значительно более быстрые методы можно найти в статье Арене, Дитер (1972).
Родственный, но иной метод описан в отчете Форсайт (1972); случайная нормально распределенная величина получается здесь в среднем за 4.036 обращения к подпрограмме с)КА)т)Р плюс несколько сравнений. УПРАЖНЕНИЯ 10.1 Если х — случайная величина с нормальным распределением Аг(0,1), а г — некоторая константа. то можно показать, чта вероятность того, что х меньше г (обозначаемая через Р (хч г]), равна Р(к < г)= ! е ги»3! 1' 2л = —,' (1+-1 — '. ), Пусть М вЂ” большое целое число, например !О 000. Выработайте М случай.
иых чисел к; вз распределения Аг(0.1), пользуясь подпрограммой ())сд)ч(у и схемой Бокса — Мюллера, описанной в а 10.3. Храните их в памяти машины а виде массива. Пусть г принимает значения от — 3.0 до 3.0 с шагом 0.2. Для каждого г выведите на печать и сравните две величины: (число тех хо которые 1 <г)гМ и — (1-!. ег((г()«2)). Значения функции ег1 можно вычислять любым 2 из методов, изложенных в упр. 1.1, 6.1 и 6.1. Попробуйте поэкспериментиро- вать с различными начальнымн значениими для ())!А)»().
Если у вас достаточ- но машинного времеви, испытайте большие значения М 10.2. Возьмите два датчика случайных чисел — ()йА!«0 и )(А(ч00; при- мените критерий у' к распределению троек по 1000 ящиков, упомянутому в й 1О 1 Чтобы применение при~ария у' имело смысл, необходимо, чтобы каждая тройка использовала трн «свежих» случайньш числа; не пытайтесь включать одно и то же число в различные тройки. 10 3 С помощью метода Монте-Карло найдите плошадь круга радиуса ! 10.4. Используя метод Монте-Карла, найдите объем области четырехмер.
ного евклидова пространств, описываемой следующими неравенствами: 0" х, <1, О. 'кг 1, 0::л»<,1, 0 х«1, на + х'+х, '+х, '<0.7, х, + з(п х«0 8, к,х» ~ Одй 1о. выплвоткл случлцных чмснл 10.5. В книге Кнут (1969) обсуждается ряд тестов для проверки эффективности датчика случайных чисел. Используя по вазможности больше из этих тестов, попытайтесь определить качество случайных чисел, вырабатываемых подпрограммой ()((АХ)З на вашей машине. 10.6. Зта задача связана со случайными блужданиями по решеткам одного, двух и трех измерений. Случайное блуждание есть последовательность единичных шагов, где каждый шаг производится в направлении одной из координатных осей и нее возмпжные направлении равновероятны. Например, в двумерном случае при старте из точки с пелочисленными координатами (х, у) единичный шаг с одинаковой вероятностью приведет в одну из четырех соседних — (к+1, у), (х — 1, у), (х, 9+1), (х, у — 1).
В одномерном случае возможных соседей два, а в трехмерном — шесть. Подпрограмму () ВАМ)Р можно использовать, чтобы экспериментальна определить приближевные ответы на следующие вопросы относительно случайных блужданий, исходящих из начала координат. (а) В случае одномерного блуждания: Каково ожидаемпе число попаданий в некоторую фиксированную ненулевую точку до первого возвращения в начало координат? Зависит ли это число от расположения точки? (б] В случае двумерного блуждания: Существует лн конечная граница для ожидаемого числа шагов до первого возвращения в начало координат? (в) В случае трехмерного блуждания: Какова вероятность возвращения в начало координат? Для некоторых из этих вопросов получение даже двух верных цифр в ответе стоит очень большого машинного времени.
Для всех известны аналитические решения. См. книги Феллер (1950) или Спикер (!964). Ваша программа будет содержать два больших целых числа: М вЂ” число выполняемых случайных блужданий и У вЂ” максимальное число шагов в одном блуждании. Если в данном блуждании произведено Ж шагов, то считается, что оно не вернется в начало. Проверьте вашу программу при относительно малых значениях М и У; затем проведите счет для больших .
качений. Было бы желательно исследовать влияние М и Ф на результаты, но это потребует очень много машинного времени. Абрамовиц, Стигаи (ред.) (АЬгапюшйг М., 51ейип 1.) (1964) НаибЬоой о1 гпабгешаБса( 1ипс(гоня, йгарйи аиб шайсшэбса! 1аЫ я Уйаз( п»91оп, (). С. (Русский перевод: Абрамознц М, Стиган И. Сираво шик по специальным функциям.— Ми Наука, 1973.) Алберг, Нильсон, Усаш (АЫЬегй Н. 3., Н(Воп Е. Ы., »Уа1«(т 3. 1..) (1967) ТЬе 1(тсогу о1 яр(шея апб (Ье(г арр)!сабоп, Ыетч Уог1». Лсабсги(с Ргезы (Русский перевод: Ллберг 3(х<., Нильсон Э., Уолш Дж.
Тсо. рня сплайнов и ее приложения. Пер, с англ.— Ми Мир, 1972 ) Лноннм (1966)»(). 5. А. я1апдагб Гог1гап», (15АБХ3.9 — !966. ПпНеб 5(а1ея о1 Л~иеггса 5(апбагЫя !пя1йи1е. Арене, Литер (Айиепз 3. Н., 0(е1ег 13.) (1972) Соигри1ег ше(Ьодя 1ог яашр1(пй 1гош йе ехроиепЬа) апг1 погша) б)я1г(Ьи1)опя, Сотт. АСМ, 1б, 873 — 882.
Браун, Контэ (Вгогчп К. М, Соп1е 5. Ес) (1967) ТЬе яо(и!юп о1 ыпш(1аиеоиз пои!гневя ейиа1(оия, Ргсс. 22пд Ыа1гг>па( Сои1егеисе о1 АСМ, 111 — 1!4. Брент (Бгеп! 9. Р.) (!973) А!богБ(ипя (ог гп(пгпгиаБои вбйои( г(епчаычея. Епй(ечгооб С(г((я, Ы. 3 .: Р ген В се. На Б. Булирш, Стоэр (Ви((гзсб К., 5(оег 3.) (1966) )9игпепса( 1геа(гпеп1 о( огг!(пату 611!егеп((а( ейиаНопя Ьу ех1гаро1абоп гпсйобы 7(итог. Ма!й., 8, 1 — 13. Вендрофф ()уеибго(1 В.) (1966) ТЬеоге1йа( пшпеыса) аиа(уыя Метч Уог(г: Лсадеш(с Ргеаь (1969) Е(гя( рппс(р(ея о! пигиемса) апа1уыя: Аи ипдегйгабив(е 1ех( ((сагйпй, Мазы. Лбйзоп-учев(еу. Вильде (%3Ые Гд 3.) .
(1964) Ор1ипигп яеейпй пге1(гойя. Ещ1еэчоод СИ(з, )4. 3: РгепПсе-Най Гарднер (СгэМпсг М ) (!961) МвйегпаБса1 риаз)ея апд бтегыопя. 1(ев Уогйи 5(сиоп апб бсбия1ег. (Русский перевод: Гарднер М. Математические головолоьгкэи и развлечгния Пер с англ.— М.: Мир, 1971.) Гихл, Мюррэй (СВ( Р. Е., Миггау %.) (1974) Мипэег са( шейобз 1ог сапз1гагпеб ор1~ш(ка1юп Неж Уог!и Лсвбепцс Ргсаь (Руссг нй перевод: Численные методы условной ог.тимизации Редакторы Ф.
Гилл и У. Мюррэй. Пер с англ,— М.. Мнр, !977,) Гилл. Мюррэй, Питфнлд (Сбб Р. Е., Миггау 97„Р(!!геЫ Р. А ) (1972) ТЬе (игр(егпеп1абои о1 (чго йиая(-Ь(еэч(ои а1бомйпи 1ог ипсопз1гыи пей ор(йиза1юп, РМАС 11 Мабопа( РЬуыса! ЕаЬсга1огу Гилпин (С()р(п М. Е.) (1972) ЕимсЬеб ргеб(с1ог-ргеу яуз1епэя: 1Ьеоге1~са! Май!йу, 5сгепге, 177, 99« о94 Гнлгберт 1Н(1Ьег1 17.) (1894) Е)п бе 1га«хит Виог(с бея Еейепдге'ясйеп ро()и низ, Асга 7Еаг(г., 18, 1бб — 190, 272 СписОк литеРатуРЫ Гир (Сгеаг С таг.) (1971) Мшпепса| !п!Иа) ча|ие ргоЫегпь |п огб!пагу Ййегепйа) сйиайопз. Еп61егчооб С!ИВ, Ы йп Ргеп1гее-Най.
Голуб, Райнш (Оо1иЬ О. Н., )|е~пзсЬ С.) (!9?1) 5!пйи1аг ча|ие бесошром1юп апд |еаМ зйиагез ю|пйоп, !п 3. Н. %!!Ыпьоп апд С )(е!пьсЬ (ебз.), НапбЬоой 1ог аи1овайс соврЫайоп, чо1. 11: Ыпеаг а!6еЬга. Нейе!Ьегй: 5рг!пйег. Грэг, Стьюарт (Огайя 'т)г. В . 5!еьчаг! (э % ) (1976) Л ЫаЫе чаггап1 о1 1Ье аесап1 ше1Ьоб 1ог ьо1чшй поп|шеаг ейиайопь, 5?АМ .1. Митег. Ала1., 13, 889 — 903.
Данниг (Пап!юй О. В.) (1963) Ыпеаг ргойгапппшй апб ех1епз!опь. Рппсе|оп, 14. 3л Рппсс1оп Упшегя1у Ргею. (Русский перевод: Данииг Дж. Б. Линейное программирование, его применения и обобщения. Пер. с англ.— Мл Прогресс, 1966.) Деккер (()е)сйег Т. Л) (!969) Р!пбшй а хего Ьу веапз о1 ьиссеьжче Ипеаг !и!егро)айоп, |п В. Бе|оп апб Р. Неппс~ (ебь.), Сопь1гисйче азрес1ь о1 !Ье |ипдавеп1а| !Ьеогегп а1 а!Ее!эта. )(ечг УогЫ Ууйеу-1п1егьс)енсе.
(1971) Л йоайпй-ро~п! 1ес!гп(йие 1ог ех1епдшй !Ье ачайаЫе ргесмюп, Мотет, Май., !8, 224 — 242. Дженкинс, Трэуб (ЗепЫпь М. Л., ТгаиЬ 3. Г.) (1972) легок о1 а совр1ех ро|упопна!, А|йоггйнп 419, Сотт. АСМ, !5, 97 — 99. Джойс ()оусе Тэ. С ) (1971) 5игчеу о1 ех1га|эо|айоп ргосеюеь ш пшпепса| апа!ушь, 51АМ ??ю1ещ 13, 435 — 490. Дэвис (Вачв Н.
Т.) (1962) |п|гобисйоп 1о поп|всат ййегепйа! эпб ш(ейга! ейиайопз. )(ечг Уогв Розог. Келлер (Кейег Н. В.) (1968) Мипэепса| гпе!Ьобь 1ог Ичо-ро!п1 Ьоипбагу ча1ие ргоЫепж. %а!1- Ьаш, Мазал Ошп?В1а~збей. Кнут (Кпи16 О. Е.) (1969) 5епнпивепса| а!бог!(Ьвь. ТЬе аг1 о1 соври!ег ргоЕгапипшй, чо|.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
