Диссертация (1150810), страница 11

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

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

[38, 39])22 =,2где = (, ), ∈ [0, 1], ≥ 0.(2.41)83Начальные и граничные условия примем в виде(0, ) = sin ,(, 0) = 0,(, 1) = 0.Введем на отрезке [0, 1] сетку 0 = 0, = 0 + ∆, = 1, . . . , + 1,+1 = 1 и заменим уравнение (2.41) на приближенные в точках сетки.˙ = 2−1 − 2 + +1, = 1, . . . , ,∆2(2.42)где = (, ). Начальные и граничные условия перепишутся в виде (0) = ( ), = 1, . . . , ,(2.43)0 () = 0, +1 = 0.(2.44)Таким образом исходная задача свелась к системе обыкновенных дифферен­циальных уравненийвида(2.1).Теперь,вводяобозначения = () = (1 , . . . , ) , запишем получившуюся систему в векторном виде(2.45)˙ = ,где – трёхдиагональная матрица × , имеющая следующую структуру⎛2⎜−2 /∆⎜ 2⎜ /∆2⎜⎜⎜⎜⎜⎜⎝0222 /∆202−2 /∆...2 /∆...2...2 /∆2 −22 /∆22 /∆22 /∆2−22 /∆2⎞⎟⎟⎟⎟⎟⎟.⎟⎟⎟⎠Далее полученную систему дифференциальных уравнений заменяем наравносильную систему интегральных уравнений.

Сделать это можно, напри­мер, следующим образом. Представим матрицу в виде суммы матриц841 +2 , где 1 представляет собой диагональную матрицу с диагональю мат­рицы , а матрица 2 = − 1 . Далее запишем равносильное интегральноеуравнениеZ() = 1 (− ) 2 ( ) + 1 (0)0или для покомпонентной записиZ−2(− )2 /Δ2 () = 222(−1 ( ) + +1 ( )) + −2 /Δ (0), = 1, .

. . , .2∆0Далее задача решается согласно схеме, описанной выше. Вообще говоря,построение оценки носит итеративный характер, который можно записать вследующем виде222 /∆2 −2 (−1 − )/Δ = −1, = 1, 2, . . . ,−1 , −1 , (−1 , )где 0 = ℎ(0 )/00 00 (0 ). В качестве переходной плотности рассмотрим усе­ченное экспоненциальное распределение22 /∆2 −2 (− ), (, ) =.1 − −22 /Δ2В этом случае итерационная процедура преобразуется к виду221 − −2 −1 /Δ, = 1, 2, . . .

, = −12−1 ,Известно (см., например, [3]), что если умножение на каждом шаге ите­рации происходит на величину меньшую по модулю единицы, то дисперсиятакой оценки будет конечной. Нетрудно проверить, что при выборе вероят­ности поглощения траектории цепи Маркова для каждого такой, чтовыполнено неравенство2 < −2−1 /Δ2,85умножение в итерационной схеме будет на величину по модулю меньшуюединицы. Следовательно дисперсия такой оценки будет конечной.Вернёмся к рассмотрению системы (2.45). Вообще говоря, можно былои обойтись без представления матрицы в виде суммы и сразу выписатьрешение() = (0).В данном случае проблемой является вычисление матричной экспоненты отматрицы с параметром .

Как известно (см., например, [40]), собственныечисла для имеют представление:42 = − 2 sin2, = 1, . . . , ,∆2( + 1)а собственные векторы() = sin, , = 1, . . . , .+1Для матрицы с известным спектром можно выписать (см., например, [25])следующее выражение для матричной экспоненты=∑︁ ℒ (),=1где ℒ () не зависят от и имеют следующий вид∏︀̸= ( − )ℒ () = ∏︀.(−)̸=В получившейся конечной сумме параметр уже стоит под обычной экспонен­той, а для оценки матриц ℒ (), которые со временем не меняются, требуетсяпостроение стохастического алгоритма.В рассматриваемом же случае можно вычислить матричную экспоненту еще проще.

Дело в том, что матрица является симметрической веще­ственной матрицей и, следовательно, допускает представление = Λ ,86где матрица – ортогональная матрица, столбцами которой являются соб­ственные векторы () матрицы , а Λ – диагональная матрица с собствен­ными числами матрицы на диагонали. Известно (см., например, [25]), чтодля произвольной обратимой матрицы выполнено равенство −1= −1 .В рассматриваемом случае в силу того, что = −1 , верно следующее = Λ .Обозначив матрицу за = {, },=1 , нетрудно выписать выражения дляэлементов матрицы :, =∑︁ sin=1sin.+1+1Так же просто можно выписать собственные числа матрицы , которыеполучаются взятием экспоненты от собственных чисел матрицы , а именно 2− 4sin2Δ2=2(+1), = 1, .

. . , .Заметим, что для любого > 0 выполнено неравенство < 1.Любопытно отметить, что, решая одну задачу, мы столкнулись с другой, неменее интересной – оценкой матричной экспоненты от матрицы, зависящейот параметра.2.4. Асинхронные релаксацииКак отметалось в начале главы, часть повествования будет уделена ме­тоду асинхронных итераций или иначе – асинхронных релаксаций.87Рассмотрим динамическую систему, состоящую из взаимосвязанныхподсистем. Пусть () = (1 (), . . . , ()) ∈ R – вектор состояния системы, () ∈ R – вектор состояния подсистемы в момент времени , =∑︀=1 .Предполагается, что задано начальное состояние (0) для каждой из подси­стем, а сама система описывается дифференциальными уравнениями вида () + ( , ) = (, ) + (), = 1, .

. . , ,(2.46)где ( , ), (, ), () – заданные функции, образы которых лежат вR . В такой постановке за динамику подсистемы отвечают функции , а завзаимосвязь между системами функции .Применение асинхронных методов для решения таких систем было рас­смотрено в [41] и [16]. Суть предложенных методов заключается в том, чтоподсистемы распределяются между процессорами и поиск решения выпол­няется при помощи итераций. На каждом шаге итераций для -ой подсисте­мы предполагается наличие некоторого приближения искомого решения.

Этоприближение подставляется в правую часть -ого уравнения в (2.46), послечего решается получившееся дифференциальное уравнение. Решение -огоуравнения даст таким образом новое приближение, после чего процесс повто­ряется до тех пор пока не будет выполнен критерий остановки алгоритма.Рассмотрим линейный случай уравнения (2.46)∑︁, () () + (), = 1, . . . , , () + () () ==1(2.47)где () и , () – матрицы размерности × и × соответственно.Будем далее предполагать, что все элементы матриц (), , () и векто­ров () являются непрерывными и ограниченными функциями на [0, ∞).Это предположение обеспечивает существование и единственность решенияуравнения (2.47) при любом начальном условии.88Обозначим за множество непрерывных на интересующем нас интер­вале времени ([0, ] или [0, ∞)) функций (), которые согласуются с началь­ными условиями задачи (2.47).

Пусть = 1 × 2 × · · · × . Определимотображения : → следующим образом. Для функций () ∈ , = 1, . . . , пусть () = (1 (), . . . , ())является решением дифференциального уравнения∑︁ () + () () =, () () + ()=1(2.48)с начальным условием (0) = (0). При сделанных предположениях относи­тельно матриц (), , () и вектора () уравнение (2.48) имеет единствен­ное решение, принадлежащее .

Как обсуждалось в предыдущих разделах () имеет следующее представлениеZ () = − () ( )[︃∑︁]︃, () ( ) + ( ) + − () (0),(2.49)=10гдеZ () = ( ).0Теперь, после того как определены функции , = 1, . . . , , определена ифункция : → такая, что = (1 , 2 , . . . , ). Пусть * () – решениесистемы (2.47), удовлетворяющее начальным условиям. Тогда * () удовле­творяет интегральному уравнениюZ* () = − () ( )0[︃∑︁]︃, ()* ( ) + ( ) + − () (0),(2.50)=1и, как не трудно видеть из уравнения (2.49), является неподвижной точкойоператора .89Далее можно воспользоваться математическим аппаратом первой гла­вы. Считаем, что итерационный процесс начинается с функций () ∈ ,а функция обновляет компоненту в рамках одного процессора.

Пред­полагается, что уравнение (2.48) решается с заданной точностью некоторымчисленным методом, природа которого на данном этапе не важна.В [16] было показано, что при сделанных предположениях относительноматриц (), , () и векторов () асинхронные итерации для оператора ,начинающиеся с некоторой непрерывной функции, удовлетворяющей началь­ным условиям, сходятся равномерно на [0, ], < ∞ к решению системы(2.47).На каждом шаге асинхронных релаксаций необходимо решать системудифференциальных уравнений (2.48).

В данном случае дополнительная воз­можность распараллеливания видится в применении метода Монте-Карлоописанного ранее в этой главе. Уместно в такой ситуации будет говорить окомбинации двух методов – метода Монте-Карло и асинхронных релаксаций.2.5. Численные экспериментыВ качестве примера использования метода Монте-Карло для решения си­стем обыкновенных дифференциальных уравнений с полиномиальной нели­нейностью рассмотрим матричное уравнения Риккати= () + 1 () + 2 () + (), (0 ) = 0(2.51)где – матрица неизвестных размерности × , (), 1 (), 2 (), () –заданные матрицы, зависящие от , размерности × . Уравнение Риккатииграет важную роль в вариационном исчислении и в квантовой теории поля.В модельном примере будем считать матрицы (), 1 (), 2 (), (), независящими от времени.90Система (2.51) естественным образом приводится к векторной форме, врезультате чего получится система из 2 уравнений.Результаты моделирования приведены на рисунках 2.3 - 2.6.

На рисунках2.3 и 2.5 приведены графики точного решения (черная сплошная линия) дляотдельных компонент решения и серия оценок метода Монте-Карло для этихкомпонент. На рисунках 2.4 и 2.6 изображены норма ошибки (синим цветом)и ее доверительные интервалы (красным цветом).Решение систем обыкновенных дифференциальных уравнений методомМонте-Карло можно условно разделить на два этапа. Первый этап заключа­ется в переходе от исходной системы к равносильной системе интегральныхуравнений. Второй этап состоит собственно в применении метода Монте-Кар­ло для нахождения решения получившейся системы интегральных уравне­ний.

В основе предложенного метода лежат оценки, построенные на ветвя­щихся траекториях, которые удобно представлять как процесс рождения/­гибели частиц. Такое представление сразу же подключает аппарат теориислучайных процессов, что несомненно является полезным при формальномописании траекторий, порождаемых такими процессами, и их свойств. Пред­ложенные оценки являются несмещенными и простыми для реализации, од­нако имеют некоторые ограничения. Условия на сходимость мажоритарногоитерационного процесса налагает ограничения на интервал интегрирования.Такое препятствие может быть преодолено использованием последовательно­го метода Монте-Карло, однако его применимость, а именно стохастическаяустойчивость, как мы видели, зависит от свойств вблизи искомого реше­ния. Другое ограничение связано с тем, что алгоритм метода Монте-Карлоподходит для задач с полиномиальной нелинейностью, но, как известно, вприкладных задачах нередко встречаются задачи с произвольной нелинейно­стью.

В этом случае можно попытаться свести задачу к уже решенной, при­близив нелинейный оператор оператором с полиномиальной нелинейностью,91Рис. 2.3. Серия оценок первой компонентыне забывая при этом, что в результате такой замены возникает дополнитель­ная погрешность.Предложенные оценки метода Монте-Карло, как отмечалось выше, до­вольно просты в реализации и легко адаптируются для использования напараллельных вычислительных системах.

Метод релаксаций для решения си­92Рис. 2.4. Оценка ошибки для первой компонентыстем обыкновенных дифференциальных уравнений является связкой с идея­ми и методами первой главы, которая открывает дополнительные возможно­сти для асинхронного решения задач на многопроцессорных системах.93Рис. 2.5. Серия оценок пятой компоненты94Рис. 2.6. Оценка ошибки для пятой компоненты95Глава 3Оценка Американских опционов методомМонте-КарлоОценка опционов является одной из важных задач финансовой матема­тики, и разрешению этой проблемы посвящено множество работ [42–46].

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

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