Диссертация (Стохастические и асинхронные методы решения систем уравнений (с приложениями к задачам финансовой математики))

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиДмитриев Алексей ВалерьевичСтохастические и асинхронные методырешения систем уравнений (с приложениями кзадачам финансовой математики)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Метод Монте-Карло и асинхронные итерацииПри использовании параллельных или распределенных алгоритмов необ­ходимо координировать действия различных процессоров, другими словами,необходимо наличие некоторого управляющего алгоритма. Принцип действияуправляющих алгоритмов существенно различается для синхронных и асин­хронных алгоритмов. Для синхронных алгоритмов процесс управления удоб­но представить в виде этапов, в течении которых каждый процессор долженсовершить ряд вычислений на основе данных, полученных от других про­цессоров на предыдущих этапах.