Автореферат (1150809), страница 2

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

Текст из файла (страница 2)

При этом сходится не медленнее,чем процесс с(︁ )︁ +для произвольногогеометрической сходимостью с параметром ‖‖ , удовлетворяющего неравенству |1 ()| < < 1.В алгоритмах, где чередуются асинхронных и синхронных итераций,и при выбранном соотношении и итерации сходятся к искомому решению,будем называть сумму + периодом асинхронности.В диссертации получено обобщение теоремы 1 на случай нелинейныхсистем (1), для которых сходится метод простой итерации, но при этом неявляется -сжимающим (см.

[5]).Во втором параграфе исследуются алгоритмы метода Монте-Карло длярешения систем вида (1) и линейных систем (3), для которых |1 ()| < 1, но1 (||) > 1.Как известно (см. [7]), при условии (4) возможно вычисление решениялинейной системы (3) при помощи асинхронного алгоритма метода Монте­Карло.

То есть на различных процессорах моделируются траектории цепиМаркова, и вычисляются оценки на них, после чего оценки, полученные навсех процессорах, усредняются. Таким образом, условия несмещенности оце­нок метода Монте-Карло и сходимости асинхронных итераций совпадают, начто было обращено внимание в работе [8].Как было показано в [7], нарушение условия (4) и использование асин­хронного алгоритма приводит к стохастической неустойчивости – экспонен­циальному росту дисперсии. Эта трудность, вообще говоря, может быть пре­одолена за счёт увеличения вычислительной работы, но её экспоненциальныйрост делает алгоритм нереализуемым.

Альтернативой является запоминаниепромежуточных результатов – синхронизация.Предлагается в случае 1 (||) > 1 использовать смешанный алгоритм счастичной синхронизацией. В диссертации доказывается лемма, являющаяся8обобщением леммы из [7], которая описывает поведение ковариации случай­ной ошибки с ростом числа итераций.Рассматривается итерационный процесс () c начальным вектором (0)и(5)() = ( − 1) + , = 1, 2, . . .

,где – матрица × , а – вектор длины . Пусть при каждом вычисле­ние слагаемых в правой части (5) происходит с помощью рандомизированнойпроцедуры. Таким образом, вместо последовательности () возникает после­довательность случайных векторов Ξ() = (1 (), . . .

, ()) , = 0, 1, 2, . . .с начальным вектором Ξ(0), связанных соотношением(6)Ξ() = B Ξ( − 1) + D()где B = ‖, ‖,=1 – случайные матричные операторы, D() – случайныевекторы.ПриэтомдлялюбогонатуральноговыполненоEΞ() = () = (1 (), . . . , ()) , EB = , ED() = .Следующая лемма определяет характер поведения ковариации векторовошибок ℰ() = Ξ() − ().Лемма 1.Пусть случайные операторы B , векторы D() и Ξ() незави­симы в совокупности при любых = 0, 1, 2, .

. . и < , в том смысле,что случайные величины 1 , 2 , 3 , где 1 – произвольный элемент опера­тора B , 2 – произвольный элемент D(), 3 – произвольный элемент Ξ(),независимы в совокупности. Тогда для матрицы ковариации вектора ℰ()справедливо соотношение ℰ() = ⊗ ℰ( − 1) + E(∆ ⊗ ∆ ) ℰ( − 1)++ E(∆ ⊗ ∆ )(( − 1)( − 1) ) + (),(7)где ∆ = B − , () = D() − , – операция векторизации матрицы,а ⊗ – операция кронекеровского произведения матриц.Доказанная лемма позволяет оценить период асинхронности алгоритмаметода Монте-Карло с запоминанием.9Можно предложить разные оценки метода Монте-Карло, реализующиепредложенный подход с чередованием синхронных и асинхронных методов.Автором приводится ряд простых в реализации оценок для решения системы(3) при условиях |1 ()| < 1, но 1 (||) > 1 и исследуются их свойства.Доказываются теоремы, гарантирующие их стохастическую устойчивость.Во второй части параграфа рассматриваются методы Монте-Карло длярешения нелинейных систем размерности ∈ N, уравнениями в которой яв­ляются полиномы степени, не превосходящей > 0, следующего вида∑︁ = 1 1 .

. . , = 1, . . . , ,(8)=(1 ,..., )где – заданные константы, = (1 , . . . , ) – вектор с целочисленны­ми неотрицательными компонентами, для которых выполнено неравенство∑︀=1 ≤ .Оценки метода Монте-Карло для решения системы (8) строятся на вет­вящихся траекториях, которые интерпретируются как процесс эволюции по­пуляции частиц. Для формального описания результатов в диссертации ис­пользуется развитый математический аппарат теории ветвящихся процессов(см., например, [9]).В диссертации построены несмещенные оценки решения системы (8) иисследованы их свойства. Как и в случае с линейными системами процессвычисления оценки решения без труда распараллеливается путем распреде­ления моделируемых ветвящихся траекторий по разным процессорам.Первая глава заканчивается серией численных экспериментов, демон­стрирующих работу предложенных оценок и алгоритмов.Результаты первой главы опубликованы в работах [2], [3].Во второй главерезультаты первой главы обобщаются на случай боль­ших систем обыкновенных дифференциальных уравнений.Рассматривается система обыкновенных дифференциальных уравненийпервого порядка размерности ∈ N, записанная в векторной форме˙ = (, ),10(9)где = () = (1 (), 2 (), .

. . , ()) – искомая вектор-функция, ∈ R, (, ) = (1 (, ), 2 (, ), . . . , (, )) – оператор из R+1 в R . C заданнымначальным условием (0 ) = 0 .Относительно функций (, ), = 1, . . . , предполагается, что они непре­рывны на области определения. Точно так же будет предполагаться, что част­ные производные (, 1 , . . . , ), , = 1, . . . , существуют и непрерывны на области определения.Система дифференциальных уравнений (9) заменяется на эквивалент­ную систему интегральных уравненийZ() =(10)(, )(, ( )) + (),0где (, ) – матричная функция, (, ()), () – заданные вектор-функции.После такого преобразования система интегральных уравнений (10) решаетсяметодом Монте-Карло.Дальнейшее исследование системы (10) разбивается на две части: перваяпосвящена интегральным уравнениям с полиномиальной нелинейностью, авторая – уравнениям, которые приближаются полиномами.Первая часть содержится во втором параграфе.

Рассматриваются систе­мы интегральных уравнений с полиномиальной нелинейностью видаZ () =∑︁(0,...,0) (, )1 1 ( ) . . . ( ) + (), = 1, . . . , , (11)0 =(1 ,..., )где { = (1 , . . . , )} – векторы с целочисленными неотрицательными ком­понентами, для которых выполнено неравенство∑︀=1 ≤ .Оценки метода Монте-Карло решения системы (11) строятся на ветвя­щихся траекториях, интерпретируемых как процесс эволюции популяции ча­стиц, в котором продолжительность жизни каждой частицы является случай­ной величиной.11Подобные ветвящиеся процессы описываются например в [9] и [10].

От­личительной особенностью рассматриваемого ветвящегося процесса будет то,что время имеет обратный ход. Другими словами, частица, родившаяся в мо­мент времени > 0 , погибнет в момент времени из промежутка [, 0 ].В диссертации получены оценки решения системы (11), являющиеся несме­щенными и простыми для реализации. Однако условия на сходимость мажо­ритарного итерационного процесса налагают серьезные ограничения на ихиспользование. Такое препятствие можно преодолеть за счет уменьшения ин­тервала интегрирования и использования последовательного метода Монте­Карло с запоминанием.Вводится сетка с шагом ∆ на отрезке [0 , ]: 0 = 0 , +1 = + ∆, =1, . .

. , − 1, а = . Такая процедура есть не что иное, как синхронизация,а выбор ∆ зависит от вида оператора.Далее применяется алгоритм метода Монте-Карло последовательно длякаждого , где начальным условием для уравнения будет результат алго­ритма для момента −1 . С ростом дисперсия оценки может экспоненци­ально расти, что при большом числе итераций может привести к стохастиче­ской неустойчивости.

В диссертации показывается, что поведение ковариацииошибки метода с ростом определяется линейным операторомexp⎧ ⎨ Z (, * ( ))⎩⎫⎬,⎭−1где * () – точное решение задачи (11), (, * ( )) – матрица Якоби для по, а операция интегрирования поэлементная. Далее формулируются и дока­зываются достаточные условия стохастической устойчивости предложенногопоследовательного метода Монте-Карло.В третьем параграфе рассматривается системы (10), которые с любойзаданной точностью могут быть приближены системами с полиномиальнойнелинейностью. В результате такой замены возникает дополнительная по­грешность, оценка которой приводится в диссертации.Вторая глава завершается серией численных экспериментов, в которыхпредложенными методами решается матричное уравнение Риккати, играю­12щее важную роль в вариационном исчислении и в квантовой теории поля,= () + 1 () + 2 () + (), (0 ) = 0где – матрица неизвестных размерности × , (), 1 (), 2 (), () –заданные матрицы, зависящие от , размерности × .В третьей главеметод Монте-Карло применяется для решения задачиоценки стоимости американского опциона, которая является одной из труд­ных задач в теории опционов.

Показывается применимость результатов пер­вой главы.В первом параграфе приводятся основные сведения про опционы и ихвиды. Во втором параграфе описывается уравнение Блэка-Шоулза, на основекоторого строятся методы оценки американского опциона 2 2 2 ++ − = 0,22 где — время, — цена акции, = (, ) — цена опциона, — постояннаяволотильность, — безрисковая ставка.В качестве методов оценки стоимости американских опционов в диссер­тации рассматривается метод подвижной границы (см. [11]) в третьем пара­графе и метод штрафных функций (см.

[11]) в четвёртом параграфе.Параллелизм методов Монте-Карло, используемых для нахождения це­ны опциона, исследуется для однофакторных моделей, однако это обстоятель­ство не является существенным ограничением при переносе предлагаемыхметодов на многофакторные модели.Для уравнений в частных производных, полученных после примененияметода штрафных функций или метода подвижной границы, на их областиопределения вводится сетка, и применяется метод конечных разностей.

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

По­лученные результаты позволяют решать широкий спектр прикладных задачиз различных областей науки, предоставляя при этом возможность эффек­тивно использовать многопроцессорные вычислительные системы.Список публикаций1. Дмитриев А.В., Ермаков С.М. Параллельный Монте-Карло метод оценкиамериканских опционов // Вестник СПбГУ, Серия 1, Выпуск 1. 2013.С. 72–82.2. Дмитриев А.В., Ермаков С.М.

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

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