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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиДмитриев Алексей ВалерьевичСтохастические и асинхронные методырешения систем уравнений(с приложениями к задачамфинансовой математики)01.01.07 – Вычислительная математикаАВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата физико-математических наукСанкт-Петербург – 2017Работа выполнена на кафедре статистического моделированияматематико-механического факультета Санкт-Петербургскогогосударственного университета.доктор физико-математических наук,Научный руководитель:профессор ЕРМАКОВ Сергей МихайловичОфициальные оппоненты: доктор технических наук,профессор ШИЧКИНА Юлия Александровна,Санкт-Петербургский государственный элек­тротехнический университет «ЛЭТИ»доктор физико-математических наук,СИМОНОВ Николай Александрович,старший научный сотрудникИнститута вычислительной математики иматематической геофизики СО РАНСанкт-Петербургский государственный поли­Ведущая организация:технический университет Петра ВеликогоЗащита состоится «»2017 г.

вчасов на заседаниидиссертационного совета Д 212.232.49 при Санкт-Петербургском государ­ственном университете, расположенном по адресу: 198504, Санкт-Петер­бург, Петергоф, Университетский пр., 28.С диссертацией можно ознакомиться в библиотеке им. Горького Санкт-Петер­бургского государственного университета, расположенной по адресу 199034,Санкт-Петербург, Петергоф, Университетская наб., д.7/9.Автореферат разослан «»2017 г.Ученый секретарь диссертационного совета,доктор физ.-мат.

наук, проф.Чурин Ю.В.Общая характеристика работыАктуальность работы.При решении многих прикладных задач фи­зики, биологии, финансовой математики и других дисциплин зачастую неудаётся найти их явное решение. По этой причине возникает необходимостьиспользования приближенных методов, после применения которых исходнаязадача часто сводится к решению систем уравнений большой размерности.Решение таких задач в силу их сложности целесообразно проводить намногопроцессорных системах, что налагает определенные ограничения накласс используемых алгоритмов.

Такие алгоритмы должны обладать свой­ством параллелизма и эффективно использовать ресурсы вычислительныхсистем. Алгоритмы, пригодные для использование на многопроцессорных си­стемах, можно разделить на два типа: синхронные и асинхронные.При использовании параллельных алгоритмов так или иначе возникаетнеобходимость координировать действия процессоров.

В случае синхронныхалгоритмов эта координация осуществляется путем разделения алгоритмана общие для всех процессоров этапы. На каждом этапе процессоры произ­водят ряд операций, зависящих от результатов вычислений на предыдущихэтапах. Переход к следующему этапу осуществляется только после того, каквсе процессоры выполнили назначенные им в рамках этапа операции. Обменрезультатами вычислений между процессорами, другими словами – синхро­низация, происходит в конце этапа. Некоторые процессоры при этом могутбыстрее других справляться с теми операциями, которые назначены им натекущем этапе, и в результате будут, простаивая, ожидать завершения этапа.В асинхронных алгоритмах нет этапов общих для всех процессоров, аесть свои собственные этапы для каждого процессора.

Процессорам разреша­ется вычислять быстрее и совершать больше итераций, чем могут совершитьдругие процессоры. Тот факт, что такие алгоритмы эффективно загружаютсистему и имеют потенциальное преимущество в скорости, делает их объек­том исследования.Так например, в работах [4], [5] были предложены асинхронные вариантыметода простых итераций для решения систем уравнений. В этих работах при­3ведены достаточные условия, при которых асинхронные итерации сходятся крешению задачи, однако эти условия довольно ограничительные, и, как былопоказано в диссертации, в некоторых случаях удаётся построить асинхронныеалгоритмы, гарантирующий сходимость и при более слабых условиях.Естественными свойствами асинхронности обладают также многие раз­новидности метода Монте-Карло для решения систем уравнений. Исследова­нию вопроса применения метода Монте-Карло посвящено достаточно многоработ различных авторов (см., например, работы С.М.

Ермакова, Г.А. Ми­хайлова, Дж. Холтона и др.).Цель диссертационной работы:∙ исследование метода асинхронных итераций для задач, не удовлетворя­ющих достаточным условиям сходимости, указанным в [4], [5];∙ построение оценок метода Монте-Карло для решения систем уравненийс использованием многопроцессорных систем, исследование вопросов ихстохастической устойчивости;∙ построение оценок метода Монте-Карло, обладающих свойством асин­хронности, для решения систем обыкновенных дифференциальных урав­нений большой размерности;∙ применение разработанных алгоритмов для численного решения задачинахождения цены американского опциона.Методы исследования.В работе применяются методы статистическо­го моделирования, теории вероятностей, функционального анализа, линейнойалгебры и общая теория методов Монте-Карло.

Численные экспериментыпроводились в статистическом пакете R совместно с программной реализа­цией на языке С.Научная новизна.Все основные результаты диссертации являются но­выми.Теоретическая и практическая ценность.Полученные результатыявляются математически обоснованными и могут успешно применяться для4решения широкого класса задач, так или иначе сводящихся к решению си­стем уравнений, на многопроцессорных вычислительных системах. Получен­ные теоретические результаты могут послужить основой для дальнейших ис­следований асинхронных детерминированных и стохастических асинхронныхметодов.Апробация работы.Основные результаты диссертации докладывалисьи обсуждались на семинарах кафедры статистического моделирования мате­матико-механического факультета СПбГУ, а также на международных кон­ференциях:∙ Seventh International Workshop on Simulation, Римини, Италия, Май21-25, 2013;∙ Ninth IMACS Seminar on Monte Carlo Methods, Аннеси-ле-Вьё, Франция,Июль 15-19, 2013.РаботанаддиссертациейбылаподдержанагрантомРФФИ№ 14-01-00271-а.Публикации.По теме диссертационной работы опубликованы работы[1], [2] и [3] в научных изданиях, включенных в Перечень рецензируемыхнаучных изданий, рекомендованных ВАК.

В статье [1] Ермаковым С.М. бы­ла поставлена задача и предложен метод её решения, а реализация метода,получение оценок метода Монте-Карло, исследование их свойств и проведе­ние численных экспериментов полностью выполнено диссертантом. В статье[2] соискателем были доказаны лемма 1 об оценке погрешности при исполь­зовании асинхронных итераций и теорема 1 о сходимости метода частичнойсинхронизации, предложены оценки метода Монте-Карло в случае частичнойсинхронизации, сформулированы и доказаны теоремы 3 и 4 о достаточныхусловиях стохастической устойчивости предложенных методов. В статье [3]соискателем был построен пример расходимости асинхронных итераций дляслучая нелинейной системы, были сформулированы и доказаны лемма 2 обоценке погрешности при использовании асинхронных итераций для нелиней­ных систем уравнений и теорема 6 о сходимости метода частичной синхрони­зации в случае нелинейных систем уравнений.5Структура и объем диссертации.Диссертация состоит из введения,3 глав, заключения и библиографии.

Общий объем диссертации 125 страниц,из них 120 страницы текста, включая 20 рисунков. Библиография включает52 наименования на 5 страницах.Содержание работыВ диссертации рассматривается задача нахождения неподвижной точки(1) = (),где=–(1 , 2 , . . . , )вектор-столбецнеизвестных, = (1 (), 2 (), . . . , ()) – оператор из R в R .

В основе предлагаемыхв диссертации методов лежит метод простой итерации ( + 1) = (()), = 1, . . . , ,(2)где (), = 0, 1, . . . – последовательность векторов из R . При выполненииопределенных условий (см. [6]) на оператор итерации (2) сходятся к непо­движной точке оператора .Во введенииобоснована актуальность диссертационной работы, сфор­мулирована цель и аргументирована научная новизна исследований, показанапрактическая значимость полученных результатов.В первой главепроизводится исследование асинхронных итераций иметода Монте-Карло для решения систем уравнений. В начале первой главыдается обзор встречающихся в литературе результатов, связанных с введени­ем и использованием метода асинхронных итераций для решения различныхзадач.В первом параграфе даётся определение асинхронных итераций, форму­лируются известные и полученные автором результаты.Предположим, что множество = {0, 1, 2, .

. . } – это множество момен­тов времени, в которые одна или несколько компонент вектора обновля­ются согласно (2) некоторым процессором распределенной вычислительной6системы. Обозначим через множество моментов времени, в которые про­исходит обновление .В многопроцессорной системе процессор, обновляющий компоненту ,не всегда имеет актуальную информацию по другим компонентам вектора, поэтому в асинхронном случае допускается использование устаревшей ин­формации.

Этот факт можно записать в следующем виде ( + 1) = (1 (1 ()), . . . , ( ())), ∀ ∈ ,где () – моменты времени, удовлетворяющие ∀ ∈ неравенству0 ≤ () ≤ , = 1, . . . , .Для всех моментов ∈/ считаем, что не обновляется (+1) = ().Разница ( − ()) между текущим временем и временем (), когдапроцессором, обновляющем , в последний раз была получена информацияо компоненте , рассматривается как задержка в передаче информации.Отсутствие задержек, связанных с ожиданием других процессоров, спо­собствует эффективной загруженности всей системы, однако может привестик расходимости таких итераций.Для систем линейных уравнений = + (3)1 (||) < 1(4)известно (см. [4]), что условиеявляется необходимым и достаточным для сходимости асинхронных итерацийпри любых начальных условиях.Автором исследуются линейные системы, не удовлетворяющие условию(4).

Согласно указанному результату, если обычный (синхронный) процесссходится – |1 ()| < 1, но 1 (||) > 1, то по крайней мере асинхронныеитерации некоторого вида обязательно расходятся.В диссертации предлагается использовать алгоритм с частичной синхро­низацией, который после каждых асинхронных итераций, использует 7обычных. Получены оценки сверху скорости сходимости этого комбинирован­ного процесса. Имеет местоТеорема 1.Если итерационный процесс состоит из последовательностигрупп асинхронных итераций и затем синхронных, то при достаточнобольшом он сходится.