Диссертация (1150810)
Текст из файла
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиДмитриев Алексей ВалерьевичСтохастические и асинхронные методырешения систем уравнений (с приложениями кзадачам финансовой математики)01.01.07 – Вычислительная математикаДИССЕРТАЦИЯна соискание ученой степеникандидата физико-математических наукНаучный руководительдоктор физико-математических наук,профессорЕрмаков Сергей МихайловичСанкт-Петербург – 20172СодержаниеВведениеГлава 1.. .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3. . . .8Метод Монте-Карло и асинхронные итерации1.1.Асинхронные итерации . . . . . . . . . . . . . . . . . . . . . . . 141.2.Алгоритмы метода Монте-Карло1.3.Численные эксперименты . . . . . . . . . . . . .
. . . . . . . . . 50Глава 2.. . . . . . . . . . . . . . . . . 28Глава 2. Решение систем обыкновенных дифференциальных уравнений методом Монте-Карло. . . . . . . . . . . . 562.1.Частные случаи . . . . . . . . . . . . . . . . . . . . . . . . . . . 592.2.Случай полиномиальной нелинейности . . . . . . .
. . . . . . . 632.3.Общий случай . . . . . . . . . . . . . . . . . . . . . . . . . . . . 802.4.Асинхронные релаксации . . . . . . . . . . . . . . . . . . . . . . 862.5.Численные эксперименты . . . . . . . . . . . . . . . . . . . . . . 89Глава 3.лоОценка Американских опционов методом Монте-Кар. . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . 953.1.Основы опционов . . . . . . . . . . . . . . . . . . . . . . . . . . 963.2.Модель Блэка-Шоулса . . . . . . . . . . . . . . . . . . . . . . . 983.3.Метод подвижной границы . . . . . . . . . . .
. . . . . . . . . . 993.4.Метод штрафной функции . . . . . . . . . . . . . . . . . . . . . 1043.5.Численные эксперименты . . . . . . . . . . . . . . . . . . . . . . 115Заключение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119Литература. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . 1213ВведениеАктуальность работы.При решении многих прикладных задач физики, биологии, финансовой математики и других дисциплин зачастую неудаётся найти их явное решение. По этой причине возникает необходимостьиспользования приближенных методов, после применения которых исходнаязадача часто сводится к решению систем уравнений большой размерности.Решение таких задач в силу их сложности целесообразно проводить намногопроцессорных системах, что налагает определенные ограничения накласс используемых алгоритмов. Такие алгоритмы должны обладать свойством параллелизма и эффективно использовать ресурсы вычислительныхсистем.
Алгоритмы, пригодные для использование на многопроцессорных системах, можно разделить на два типа: синхронные и асинхронные.При использовании параллельных алгоритмов так или иначе возникаетнеобходимость координировать действия процессоров. В случае синхронныхалгоритмов эта координация осуществляется путем разделения алгоритмана общие для всех процессоров этапы. На каждом этапе процессоры производят ряд операций, зависящих от результатов вычислений на предыдущихэтапах.
Переход к следующему этапу осуществляется только после того, каквсе процессоры выполнили назначенные им в рамках этапа операции. Обменрезультатами вычислений между процессорами, другими словами – синхронизация, происходит в конце этапа. Некоторые процессоры при этом могутбыстрее других справляться с теми операциями, которые назначены им натекущем этапе, и в результате будут, простаивая, ожидать завершения этапа.В асинхронных алгоритмах нет этапов общих для всех процессоров, аесть свои собственные этапы для каждого процессора.
Процессорам разрешается вычислять быстрее и совершать больше итераций, чем могут совершитьдругие процессоры. Тот факт, что такие алгоритмы эффективно загружают4систему и имеют потенциальное преимущество в скорости, делает их объектом исследования.Так например, в работах [1], [2] были предложены асинхронные вариантыметода простых итераций для решения систем уравнений. В этих работах приведены достаточные условия, при которых асинхронные итерации сходятся крешению задачи, однако эти условия довольно ограничительные, и, как былопоказано в диссертации, в некоторых случаях удаётся построить асинхронныеалгоритмы, гарантирующий сходимость и при более слабых условиях.Естественными свойствами асинхронности обладают также многие разновидности метода Монте-Карло для решения систем уравнений.
Исследованию вопроса применения метода Монте-Карло посвящено достаточно многоработ различных авторов (см., например, работы С.М. Ермакова [3–6], Г.А.Михайлова [7–9], Дж. Холтона [10–12] и др.).Цель диссертационной работы:∙ исследование метода асинхронных итераций для задач, не удовлетворяющих достаточным условиям сходимости, указанным в [1], [2];∙ построение оценок метода Монте-Карло для решения систем уравненийс использованием многопроцессорных систем, исследование вопросов ихстохастической устойчивости;∙ построение оценок метода Монте-Карло, обладающих свойством асинхронности, для решения систем обыкновенных дифференциальных уравнений большой размерности;∙ применение разработанных алгоритмов для численного решения задачинахождения цены американского опциона.Теоретическая и практическая ценность.Полученные результатыявляются математически обоснованными и могут успешно применяться для5решения широкого класса задач, так или иначе сводящихся к решению систем уравнений, на многопроцессорных вычислительных системах.
Полученные теоретические результаты могут послужить основой для дальнейших исследований асинхронных детерминированных и стохастических асинхронныхметодов.На защиту выносятся следующие основные результаты и положения:построен алгоритм метода Монте-Карло с частичной синхронизацией для решения систем уравнений вида = + ,(1)при выполнении условий |1 ()| < 1 и 1 (||) > 1, где 1 (·) – наибольшеепо модулю собственное число матрицы, а || – матрица, составленная из модулей элементов матрицы . Получены достаточные условия стохастическойустойчивости предложенного алгоритма и оценен период асинхронности.Модифицирован метод асинхронных итераций для решения задачи (1)при условии |1 ()| < 1 и 1 (||) > 1.
Получены оценки периода асинхронности.Получены и формально описаны оценки метода Монте-Карло, обладающие свойством асинхронности, для решения систем обыкновенных дифференциальных уравнений большой размерности. Получены достаточные условияих стохастической устойчивости.Построены асинхронные оценки метода Монте-Карло для нахождениястоимости американского опциона, исследованы условия их стохастическойустойчивости.Апробация работы. Основные результаты диссертации докладывалисьи обсуждались на семинарах кафедры статистического моделирования математико-механического факультета СПбГУ, а также на международных конференциях:6∙ Seventh International Workshop on Simulation, Римини, Италия, Май21-25, 2013;∙ Ninth IMACS Seminar on Monte Carlo Methods, Аннеси-ле-Вьё, Франция,Июль 15-19, 2013.РаботанаддиссертациейбылаподдержанагрантомРФФИ№ 14-01-00271-а.Научная новизна.Все основные результаты диссертации являются новыми.Публикации.По теме диссертационной работы опубликованы работы[13], [14] и [15] в научных изданиях, включенных в Перечень рецензируемыхнаучных изданий, рекомендованных ВАК.
В статье [13] Ермаковым С.М. была поставлена задача и предложен метод её решения, а реализация метода,получение оценок метода Монте-Карло, исследование их свойств и проведение численных экспериментов полностью выполнено диссертантом. В статье[14] соискателем были доказаны лемма 1 об оценке погрешности при использовании асинхронных итераций и теорема 1 о сходимости метода частичнойсинхронизации, предложены оценки метода Монте- Карло в случае частичнойсинхронизации, сформулированы и доказаны теоремы 3 и 4 о достаточныхусловиях стохастической устойчивости предложенных методов. В статье [15]соискателем был построен пример расходимости асинхронных итераций дляслучая нелинейной системы, были сформулированы и доказаны лемма 2 обоценке погрешности при использовании асинхронных итераций для нелинейных систем уравнений и теорема 6 о сходимости метода частичной синхронизации в случае нелинейных систем уравнений.Личный вклад автора.Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы.
Подготовка к публикации полученных результатов прово7дилась совместно с соавторами, причем вклад диссертанта был определяющим.Структура и объем диссертации.Диссертация состоит из введения,3 глав, заключения и библиографии. Общий объем диссертации 125 страниц,из них 120 страницы текста, включая 20 рисунков. Библиография включает52 наименования на 5 страницах.8Глава 1Метод Монте-Карло и асинхронные итерацииПри использовании параллельных или распределенных алгоритмов необходимо координировать действия различных процессоров, другими словами,необходимо наличие некоторого управляющего алгоритма. Принцип действияуправляющих алгоритмов существенно различается для синхронных и асинхронных алгоритмов. Для синхронных алгоритмов процесс управления удобно представить в виде этапов, в течении которых каждый процессор долженсовершить ряд вычислений на основе данных, полученных от других процессоров на предыдущих этапах.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
