Автореферат (1150809)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов диссертации