Соболь И.М. Численные методы Монте-Карло (1973)

517.8+ 518 С 54 УДК 519.2 Численные методы Моите-Карло, И. М Со. боль. ! лавная релакция физико-математической литературы изд-ва «Наука», !973. Книга возникла из курса, который автор неоднократно читал в Московском инженерно.физическом институте, где у слушателей предполагалось знш<омство с теорией вероятностей в весьма ограниченном объеме (соответствующем программе втузов). На атом уровне удалось рассмотреть важнейшие разделы теории методов Моите- Карло.

В книге эти разделы изложены значительно полнее, имеется лгного примеров, подобраны упражнения. Многие результаты излагаются впервые. Книга рассчитана на студентов втузов, инженеров, научных работников. Она будет особенно полезной специалистам по вычислительной и прикладной математике. Книга содержит 73 рис., бпбл. 185 наев. © Издательство «Наука», !973. 0224 †!857 942!92Н73 ОГЛАВЛЕНИЕ Предисловие ° Ф Введение Г л а в а 1. Получение случайных велнчнн на ЭВМ 4 1.

Тргг способа получения случайных величин й 2. Псевдослучайные числа . 4 3. Статистическая проверка случайных чисел . Упражнения к главе 1 Г л а в а 2. Преобразования случайных величин . $ 1. Метод обратных функций (основной прием моделнровання случайных величин) 4 2. Моделирование многомерных случайных величин . $ 3. Преобразования вида 5=9(уь ут) .

4 4. Преобразования вида 5=я(уг, ..., уч) . Гг 5. Методы отбора Упражнения к главе 2 Г л а в а 3. Вычисление интегралов $1. Общий метод оценки математических огкпданвй . $ 2. Простейший метод Монте-Карло для вычисления интеграла й 3. Важнейшие способы построения хороших оценок (способы уменьшения дисперсии) й 4. Интегралы, зависящие от параметра Упражнения к главе 3 Г л а в а 4.

Вычнсленне интегралов (сложные оценки) . $1. Методы Монте-Карло с повышенной скоростью схо. димости 6 2. Случайные квадрвтурные формулы й 3. Использование смещенных оценок . Упражнення к главе 4 Г л а в а 5. Решение линейных уравнений 5 1. Интегральные преобразования . 2. Неоднородные интегральные уравнения 3. Пример: рассеяние частиц . $4. Однородные интегральные уравнения . $5. Решение линейных алгебраических систем Упражнения к главе 5 , . .

. . . . , . ° )ь 7 (О 1О 49 30 42 44 44 53 61 70 74 83 86 86 93 100 !23 13! 135 135 143 151 159 161 161 171 182 185 193 207 Оглдвле!нге 292 292 298 308 Гл а в а 5. Моделирование естественных процессов... 210 $ 1. Моделирование путем пьпжацпн . . . .

. . 21! $ 2. Моделирование свободного пробега . . . . . 22! й 3 Использование статистических весов . . . . . 23! 9 4. Статистические веса и интегральные уравнения . . 247 Упражнения к главе 6.....,,... 251 Гл а в а 7. Неслучайные точки в алгоритмах Монте-Карло 253 Гз 1, Конструктивная размерносгь алгоритмов МонтеКарло............. 254 9 2. и-мерные псевдослучайные точки . . . , .

. 259 ф 3. Поиски «универсальных» псевдослучайных чисел . , 270 $4. Проверка псевдослучайных чисел с детерминистиче. ской точки зрения . . . . . . . . . . 274 Упражнения к главе 7 . . . . . . . , . , 277 Г л а в а 8. Некоторые другие задачи . . . . . , , 279 Гз 1.

Интерполирование фувкпнй от большого числа переменных . . . . . . . . . . . , 279 й 2. Простейший случайный повск...... 281 й 3. Решение уравнения Лапласа...,... 284 4. Вычисление ввнеровских интегралов . . . . . 287 Приложения !. Вспомогательное неравенство П. Таблицы Литература Указатель . ПРЕДИСЛОВИЕ Книга эта возникла из курса, который я в течение ряда лет читал в Московском инженерно-физическом институте, но довольно сильно отличается от него: все вопросы изложены здесь значительно полнее.

Основной материал, предназначенный для общего курса методов Монте-Карло, содержится в главах 1, 2, 3, 6, 7, исключая мелкий шрифт. Предполагается, что читатель знаком с теорией вероятностей в сравнительно небольшом объеме, примерно соответствующем программе по выс. шей математике для втузов *). За последнее десятилетие сфера приложений методов Монте-Карло необычайно расширилась. Методы МонтеКарло используются для расчета задач физики (перенос излучения и вещества, ядерная физика, статистическая физика и др.), радиотехники, теории массового обслуживания, теории надежности, химии, биологии, экономики (оптимизация, управление, сетевое планирование и др.), теории автоматов, аэродинамики, гидрологии— перечислить все невозможно. В книге рассмотрены почти все наиболее важные вопросы, связанные с применением методов Монте-Карло, и можно надеяться, что она будет полезна специалистам, использующим эти методы, независимо от области приложений.

По мнению автора, современный курс методов Монте-Карло обязательно должен содержать хотя бы краткое изложение детерминистического подхода к методам Монте-Карло, так как использование так называемых детерминированных псевдослучайных чисел позволяет во многих задачах увеличить скорость сходимостп (1/Лп-е вместо 1/~М), не нарушая структуры вычислительного алгоритма. Этим вопросам посвящена глава 7. '1 В лекции для инженеров-физиков следует включать также ряд вопросов из главы 6. певдисловнв Обычно преобразования случайных величин излага.

ются как справочный материал: различные способы моделирования экспоненциальных величин, различные способы моделирования нормальных величин и т. д. Вместо этого в главе 2 построена общая классификация преобразований, используемых для моделирования различных случайных величин. На первый взгляд принцип этой классификации может показаться формальным. Но полностью его роль выясняется в главе 7 в связи с введенным в книге понятием конструктивной размерности алгоритмов Монте-Карло.

Нередко при изложении методов Монте-Карло много места уделяют способам решения задач линейной алгебры. Однако такие способы редко применяют на практике, где, как правило, используют более быстро сходящиеся численные методы линейной алгебры. Поэтому в главе 5 излагаются в первую очередь способы решения линейных интегральных уравнений; и лишь в $ 5 этой главы как частный случай рассмотрены алгебраические системы.

В главе 6 рассмотрены различные способы введения статистических весов. Эти способы позволяют, отправляясь от естественного процесса, строить модели для расчета, более выгодные, чем имитация процесса (см. мелкий шрифт, стр. 9). Устанавливается связь этих приемов с методами вычисления интегралов и решения интегральных уравнений. Главы 4 и 8 выходят за рамки общего курса. В главе 4 указаны наиболее интересные и, вероятно, наиболее перспективные направления исследований методов вычисления интегралов, а в главе 8 рассмотрены некоторые задачи других типов. Таким образом, эти главы как бы иллюстрируют возможности развития методов Монте-Карло «вглубь» и «вширьж Упражнения предназначены в первую очередь для того, чтобы сообщить читателю дополнительные сведения.

Я пользуюсь случаем, чтобы выразить свою призна. тельность Н. Н. Чепцову, многолетний контакт с кото. рым повлиял на мои взгляды на методы Монте-Карло. И. Соболь ВВЕДЕНИЕ 0.1. Методы Монте-Карло. Общепринятого определения методов Монте-Карло пока нет. Назовем методами Монте-Карло численные методы решения математических задич при помощи моделирования случайных величин ").

При таком определении приходится к методам Монте-Карло причислить некоторые другие методы, как, например, стохастические приближения или случайный поиск, которые по традиции рассматриваются отдельно. Однако специалисты, занимающиеся этими вопросами, нередко сами называют свои приемы методами МонтеКарло. В то же время в определении подчеркивается что: а) речь идет о численных методах (и конкурировать они могут с классическими численными методами, а не с аналитическими методами решения задач); б) решать методами Монте-Карло можно любые математические задачи (а не только задачи вероятностного происхождения, связанные со случайными величинами!, Название «Моите-Карло» произошло от города Монте-Карло (княгкество Монако), известного своим казино, ибо одним из простейших приборов для генерирования случайных чисел служит рулетка.

Официальной датой рождения методов Монте-Карло считают !949 год, когда появилась статья под заглавием «Метод Монте. Карло» (159]. Возникновение метода связывают обычно с именами Дж. Неймана, С. Улана, Н. Метрополиса, а также Г. Кана и Э, Ферми; все онн в 40-х годах работали в Лос-гтламосе (США).

Необходимо сразу же подчеркнуть, что теоретические основы ') Можно добавить: «н статистической оценки нк карактернстнк». вваанив методов Монте-Карло были известны значительно раньше. Более того, фактически такие методы не раз исполь. зовались для расчетов в математической статистике. Однако до появления электронных вычислительных машин (ЭВМ) методы Монте-Карло не могли стать универсальными численными методами, ибо моделирование случайных величин вручную — весьма трудоемкий процесс. Развитию методов Монте-Карло способствовало бурное развитие ЭВМ. Алгоритмы Монте-Карло (как правило, обладающие небольшой связностью) сравнитель.

но легко программируются и позволяют рассчитывать многие задачи, недоступные для классических численных методов. Так как совершенствование ЭВМ продолжается, есть все основания ожидать дальнейшего развития методов Монте-Карло и дальнейшего расширения области их применения. 0.2. Общий курс методов Монте-Карло. Важнейший прием построения методов Монте-Карло — сведение задачи к расчету математических ожиданий, Более подробно: для того чтобы приближенно вычислить некогорую скалярную величину а, надо придумать такую случайную величину $, что йй$=а; тогда, вычислив АГ независимых значений $ь ..., йи вели° ° чины $, можно считать, что аж (1/АГ) (ф,+ ...

+$„). Пример. Требуется оценить объем Ун некоторой ограниченной пространственной фигуры 6. Выберем параллелепипед П, содержа- нгий б, объем которого Уп известен (рнс. !). ° ° Выберем Ф случайных точек, равномерно рас° пределениых в П, и обозначим через йг' коли. честно точек, попавших в 6. Если гу велико, ° то, очевидно, Ф': Фж Уо ~ Уп, откуаа полу- чаем оценку Рис.

1, Уа = Уп(~ ~гУ) В этом примере случайная величина в равна Уп, если случайнан точка попадает в б, и й равна нулю, если точка попадает в П вЂ” О. Нетрудно проверить, что математическое оигиданне Ый= У, а среднее арифметическое (1УгУ) (й + " + й ) =- У К(гч) введение Легко видеть, что существует бесконечно много случайных величин $ таких, что ййеь=а.