Методы Монте-Карло для параллельных вычислений

Серия
Суперкомпьютерное 
Образование

Координационный совет
Системы научно-образовательных центров
суперкомпьютерных технологий

Председатель Координационного совета
В. А.  Садовничий,
ректор МГУ имени М. В.  Ломоносова,
академик

Заместители председателя совета
Е. И.  Моисеев,
декан факультета вычислительной математики и кибернетики
МГУ имени М. В.  Ломоносова, 
академик

А. В.  Тихонравов,
директор Научно-исследовательского вычислительного центра
МГУ имени М. В.  Ломоносова, 
профессор

Члены совета

В. Н. Васильев, ректор Санкт-Пе тер  бургского национального исследовательского госу дар ственного университета инфор ма ционных технологий, механики 
и оптики, чл.-корр. РАН, профессор; В. Г. Захаревич, ректор Южного федерального университета, профессор; Н. Н. Кудрявцев, ректор Московского физико-технического института, чл.-корр. РАН, профессор; Г. В. Майер, 
ректор национального исследовательско го Томско го государственного университета, профессор; А. А. Фаткулин, проректор по науке и инновациям 
Дальневосточного федерального университета, профессор; Е. В. Чупрунов, 
ректор националь ного исследовательского Ниже городского го су дарственного 
университета, про фессор; А. Л. Шестаков, ректор национального исследовательского Южно- Уральского государственного университета, профессор; 
В. Н. Чубариков, декан механико-математического факультета МГУ имени 
М. В. Ломоносова, профессор; М. И. Панасюк, директор Научно-ис сле дова тельского института ядерной физики МГУ имени М. В.  Ломоно сова, профессор; Вл. В. Воеводин, заме ститель директора Научно-исследо ва тель ского 
вычислительного центра МГУ имени М. В.  Ломоносова, исполнительный директор 
НОЦ «СКТ-Центр», член-корреспондент РАН.

Издательство Московского университета
2013

Нижегородский гоударственный университет 
им. Н. И. Лобачевского

Методы Монте-Карло 
для параллельных 
вычислений

А. В. Зорин, М. А. Федоткин

Допущено 
УМО по классическому университетскому образованию 
в качестве учебного пособия для студентов высших учебных заведений, 
обучающихся по направлениям ВПО 
010400 «Прикладная математика и информатика» 
и 010300 «Фундаментальная информатика 
и информационные технологии»

© А.В.Зорин, М.А.Федоткин, 2013 
© Издательство Московского университета, 2013
ISBN 978-5-211-06530-7

Зорин А. В., Федоткин М. А. 
Методы Монте-Карло для параллельных вычислений: Учебное пособие / Предисл.: В. А. Садовничий. – М.: Издательство Московского университета, 2013. – 192 с., ил. – (Серия «Суперкомпьютерное образование»)

ISBN 978-5-211-06530-7

З 86

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

УДК 007 (075) 
ББК 32.973.2

УДК 007 (075) 
ББК 32.973.2
З 86

Уважаемый читатель!

Вы держите в руках одну из книг серии «Суперкомпьютерное образование», выпущенную в рамках реализации проекта комиссии Президента 
РФ по модернизации и технологическому развитию экономики России 
«Со здание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного программного обеспечения». Инициатором издания выступил Суперкомпьютерный консорциум университетов России.
Серия включает более 20 учебников и учебных пособий, подготовленных ведущими отечественными специалистами в области супер ком пьютерных технологий. В книгах представлен ценный опыт преподавания 
супер компьютерных технологий в таких авторитетных вузах России, как 
МГУ, ННГУ, ТГУ, ЮУрГУ, СПбГУ ИТМО и многих других. При подготовке изданий были учтены рекомендации, сформулированные в Своде знаний и умений в области суперкомпьютерных технологий, подготовленном 
группой экспертов Суперкомпьютерного консорциума, а также международный опыт.
Современный уровень развития вычислительной техники и методов 
математического моделирования дает уникальную возможность для перевода промышленного производства и научных исследований на качественно новый этап. Эффективность такого перехода напрямую зависит 
от наличия достаточного числа высококвалифицированных специалистов. Данная серия книг предназначена для широкого круга студентов, 
аспирантов и специалистов, желающих изучить и практически использовать параллельные компьютерные системы для решения трудоемких вычислительных задач.

Издание серии «Суперкомпьютерное образование» наглядно де мон стрирует тот вклад, который внесли участники Суперкомпьютерного консорциума университетов России в создание национальной системы подготовки высококвалифицированных кадров в об ласти суперкомпью терных 
технологий, а также их четкое понимание ответственности за подготовку 
высококвалифицированных специалистов и формирование проч ного научного фундамента, столь необходимого для эффективного использования суперкомпьютерных технологий на практике.

Ректор Московского университета,
Президент Суперкомпьютерного консорциума 
университетов России,
академик РАН  В. А. Садовничий

Оглавление

Предисловие
10

Часть I. Основные понятия и методы
12

Глава 1. Модели и системы параллельных вычислений
13
1.1
Параллельные вычисления с общей памятью . . . . . . .
13
1.2
Параллельные вычисления с разделенной памятью
. . .
18

Глава 2. Генераторы псевдослучайных чисел
21
2.1
О генераторах псевдослучайных чисел . . . . . . . . . . .
21
2.2
Линейный конгруэнтный генератор . . . . . . . . . . . . .
25
2.3
Векторный линейный конгруэнтный генератор . . . . . .
27
2.4
Обобщенный генератор Фибоначчи с запаздыванием
. .
30
2.5
Векторный обобщенный генератор Фибоначчи с запаздыванием
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
2.6
Методы перетасовывания и комбинации . . . . . . . . . .
35
2.7
«Вихрь Мерсенна»
. . . . . . . . . . . . . . . . . . . . . .
37
2.8
Методы получения псевдослучайных последовательностей с равномерным распределением для параллельных
вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
2.9
Некоторые реализации генераторов для параллельных
вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . .
44

Глава 3. Моделирование случайных величин и векторов с
произвольным законом распределения
46
3.1
Моделирование дискретных случайных величин . . . . .
46
3.2
Моделирование непрерывных случайных величин . . . .
51
3.3
Моделирование случайных векторов . . . . . . . . . . . .
59

7

3.4
Моделирование случайных векторов с помощью многомерных цепей Маркова . . . . . . . . . . . . . . . . . . . .
70

Глава 4. Приближенное вычисление определенных интегралов методом Монте-Карло
74
4.1
Геометрический метод Монте-Карло . . . . . . . . . . . .
74
4.2
Метод математического ожидания . . . . . . . . . . . . .
77
4.3
Сравнение точности геометрического метода и метода математического ожидания. Мера трудоемкости . . . . . . .
81
4.4
Способы уменьшения дисперсии
. . . . . . . . . . . . . .
83
4.5
Метод Монте-Карло в параллельных вычислениях . . . .
87

Часть II. Примеры решения прикладных задач
101

Глава 5. Решение уравнений телеграфного типа
102
5.1
Пуассоновский процесс и его моделирование
. . . . . . .
102
5.2
Связь функционалов от пуассоновского процесса с дифференциальными уравнениями
. . . . . . . . . . . . . . .
106
5.3
Решение уравнений телеграфного типа методом МонтеКарло . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
110

Глава 6. Имитационное моделирование
118
6.1
Методы имитационного моделирования систем массового
обслуживания . . . . . . . . . . . . . . . . . . . . . . . . .
118
6.2
Оптимизация системы массового обслуживания в классе
алгоритмов разделения времени с переналадками
. . . .
126

Глава 7. Моделирование распространения зондирующего
излучения в многослойных биологических тканях
147
7.1
Постановка задачи на физическом уровне . . . . . . . . .
148
7.2
Алгоритм моделирования распространения зондирующего излучения в многослойных биологических тканях
. .
149
7.3
Результаты численных экспериментов . . . . . . . . . . .
155

Глава 8. Обзор задач, решаемых методом Монте-Карло
159
8.1
Приближенное вычисление интегралов Римана высокой
размерности
. . . . . . . . . . . . . . . . . . . . . . . . . .
159
8.2
Задача о приближенном решении линейного неоднородного интегрального уравнения . . . . . . . . . . . . . . . .
159

8

8.3
Решение задач Коши и граничных задач для основных
уравнений математической физики . . . . . . . . . . . . .
160
8.4
Вычисление континуальных интегралов . . . . . . . . . .
161
8.5
Линейное интерполирование функций многих переменных 162
8.6
Оценка абсолютного экстремума функций многих переменных . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
162
8.7
Численное решение стохастических дифференциальных
уравнений Ито . . . . . . . . . . . . . . . . . . . . . . . . .
162
8.8
Вычисление справедливой цены опционов . . . . . . . . .
163
8.9
Имитационное моделирование реальных систем
. . . . .
165
8.10 Картографирование и локализация для роботов . . . . .
166
8.11 Задачи математической статистики . . . . . . . . . . . . .
167

ПРИЛОЖЕНИЕ. Векторные вычисления
168

Обзор источников
176

Список алгоритмов
178

Предметный указатель
179

Литература
185

9

Предисловие

Идея использования случайных чисел многократно возникала в
умах математиков в разных странах и в разные времена. Одно из первых упоминаний о методе решения задачи с помощью случайных чисел
историки науки относят к 1876 году, когда статистик Эраст Лайман де
Форест использовал метод обратной функции для экспериментального исследования поведения остатков при сглаживании временного ряда. В работах отечественных ученых метод обратной функции носит
имя преобразования Н.В. Смирнова [10]. Еще ранее швейцарский астроном Рудольф Вольф в серии статей 1849–1850 годов использовал физический датчик случайности — натурный эксперимент — для оценки
по методу наименьших квадратов вероятности пересечения тонкой иглой одной из параллельных линий, нанесенных на плоскость (точное
решение задачи было получено ранее французским естествоиспытателем Ж. Бюффоном). Термин «метод Монте-Карло» восходит к другому
замечательному математику Станиславу Уламу, который использовал
датчик псевдослучайных чисел на только что появившейся электронной
вычислительной машине для моделирования ветвящихся процессов при
ядерном распаде. По его словам, название процедуры обязано присутствию в ней «. . . своеобразного элемента везения — получения случайных чисел, с которыми играют в соответствующие игры» (С. Улам, в
своей книге воспоминаний «Приключения математика», 1976). Отсюда
следует, что первые применения метода Монте-Карло относились как к
сфере интересов классических численных методов, так и к сфере имитационного моделирования реальных процессов (в физике).
Дальнейшее развитие метода статистического испытания неразрывно связано с развитием вычислительной техники. Рост быстродействия позволил генерировать выборки большого объема для получения оценок исследуемых характеристик — с заданной надежностью и
за приемлемое время. Соответственно расширилась сфера применений
методов Монте-Карло [9, 10, 11, 12, 13, 17, 19, 29, 30, 36, 41].
В настоящее время исследователям в области прикладной математики становятся доступны вычислительные системы параллельного
действия. Оказывается при этом, что методы Монте-Карло позволяют получать высокую эффективность использования параллельных вычислительных процессов. Причина эффективности в том, что большую
часть времени занимает генерирование и обработка независимых копий некоторой случайной величины. Пусть имеется K вычислительных

10