Диссертация (1150810), страница 14
Текст из файла (страница 14)
То есть далее считаем, что−1 ( + ℰ ) ≈ ( ) + ′ ( )ℰ . Положим также (^− )= ( − )−1 + ,где = 0. Равенство (3.16) перепишется + ℰ = (( − )−1 + )( (+1 ) + ′ (+1 )ℰ+1 ).Учитывая, что удовлетворяет (3.12), получим для ℰ следующее выражениеℰ = (+1 ) + ( − )−1 ′ (+1 )ℰ+1 + ′ (+1 )ℰ+1(3.17)и соответственно для ℰ , заметив прежде, что ′ – диагональная матрица иследовательно ( ′ ) = ′ ,ℰ = (+1 ) + ℰ+1 ′ (+1 )(( − )−1 ) + ℰ+1 ′ (+1 ) .(3.18)Теперь необходимо перемножить левые и правые части равенств (3.17) и(3.18) соответственно и вычислить математическое ожидание всех членов получившегося равенства.
При этом стоит отметить, что математическое ожидание многих слагаемых в правой части равны нулю. Так, ′ (+1 ) ) = 0 в силу того, что ℰ+1не зависит от и( (+1 )ℰ+1ℰ+1= 0. Учитывая эти соображения, получим(ℰ ℰ ) = ( − )−1 ′ (+1 )(ℰ+1 ℰ+1)(( − )−1 ′ (+1 )) ++( ′ (+1 )ℰ+1 ℰ+1 ′ (+1 ) ) + ℱ+1 ,где матрица ℱ+1 объединяет слагаемые, не зависящие от ℰ+1 . Далее получимℰ = ( − )−1 ′ (+1 )ℰ+1 (( − )−1 ′ (+1 )) +′′+ ( (+1 )ℰ+1 (+1 ) ) + ℱ+1 .(3.19)112Теперь было бы удобно привести получившееся равенство к виду = +1 + , где , +1 , – векторы, а – матрица. Согласно определению операции умножения матриц, из (3.19) имеем −1‖,=1‖,−1 −1⃦⃦ −1⃦ ∑︁ ∑︁⃦+10 ,1 1 ,2 3 ,2 ⃦=⃦+1 =1 2 =10 ,3 =1−1 −1⃦⃦ −1⃦ ∑︁ ∑︁⃦+10 ,1 1 ,2 3 ,2 ⃦+ ⃦+ ℱ+1 ,1 =1 2 =1(3.20)0 ,3 =1где , – элементы матрицы ( − )−1 ′ (+1 ), , – матрицы ℰ и , –матрицы ′ (+1 ).
В силу того, что матрица ′ диагональная, элементы ′ (+1 ) будут иметь вид: , = ′ , , где ′ – элемент диагонали матрицы ′ , a , – элементы матрицы . Если теперь ввести мультииндекс = (, )принимающий ( − 1)2 значений от (1, 1) до ( − 1, − 1), то равенство(3.20) перепишется( −1, −1)‖ ‖=(1,1)⃦⃦ ∑︁⃦+1 ⃦=⃦0 ,1 3 ,2 ⃦+=(1 ,2 )⃦ ∑︁⃦⃦+1 ⃦′ ′+⃦(0 ,1 3 ,2 )1 2 ⃦ + ℱ+1 .(3.21)=(1 ,2 )Теперь вытянем матрицу ℰ в столбец и будем рассматривать далее ‖ ‖как вектор длинны ( − 1)2 , тогда последнее равенство (3.21) перепишетсяв искомой нами форме‖ ‖ = ( + )‖+1 ‖ + ℱ+1 ,(3.22)где = ‖0 ,1 3 ,2 ‖, = ‖′1 (0 ,1 3 ,2 )′2 ‖ – матрицы ( − 1)2 × ( − 1)2 ,0 , 1 , 2 , 3 меняются от 1 до − 1. Покажем, что собственные векторы есть , , = 1, . .
. , − 1, где – собственный вектор-столбец матрицы( − )−1 ′ , а собственные числа есть , , = 1, . . . , − 1, где –113собственные числа матрицы ( − )−1 ′ . Пусть , – собственные векторы ( − )−1 ′ и , – соответствующие им собственные числа.
Вытянемматрицу = в один столбец и рассмотрим – вектор длинны ( −1)2−1)⃦( −1,⃦( −1, −1)⃦ ∑︁1 2 ⃦0 ,1 3 ,2 ⃦. = ⃦(1 ,2 )=(1,1)(0 ,3 )=(1,1)(3.23)Правую часть можно мыслить как матрицу ( − 1) × ( − 1), а именно−1 −1⃦⃦ −1⃦ ∑︁ ∑︁1 2 ⃦0 ,1 3 ,2 ⃦= ( − )−1 ′ (( − )−1 ′ ) =⃦0 ,3 =11 =1 2 =1= (( − )−1 ′ )(( − )−1 ′ ) = .Если снова растянуть в столбец, получим = . Что и требовалось доказать.
Рассмотрим теперь матрицу . В действительности представляет собой произведение ℳˆ , где ˆ – диагональная матрица с диагона( −1, −1)лью ‖′ ′ ‖(,)=(1,1) , а элементы матрицы ℳ есть ковариации вектора, составленного из элементов матрицы погрешностей . Элементы матрицы ℳимеют порядок 1/ , где – количество независимых траекторий на слое сномером . Оценим ′ , выражение для которого имеет вид(︂)︂1∆′ =1−1 + 2 2 ∆ + ∆(,+1 + − + ∆)2найдем условие на ∆, при котором разность, стоящая в скобках, больше нуля1−∆∆≥1−≥0(,+1 + − + ∆)2( − )2откуда получаем условие( − )2.(3.24)∆ ≤Таким образом норма матрицы ′ меньше единицы при ∆ из (3.24).
Учитывая малость и то, что ≥ , это условие на ∆ является несущественным.Заметим, что вообще говоря, матрица ′ зависит от момента времени, поэтому в действительности ′ = ′ .114Из (3.22) и вышесказанного следуют следующие утверждения:Утверждение 1.Для стохастической устойчивости алгоритма (3.15) необходимо и достаточно, чтобы максимум из модулей первых собственныхчисел матриц ℒ +1′ ℳ , = − 1 . . . 1 при любых натуральных былменьше единицы.Утверждение 2.Если первые собственные числа матриц ( − )−1 ′ помодулю строго меньше единицы, то существует такой набор , = −1, . . .
1, что при всех > алгоритм (3.15) будет стохастическиустойчивым.В силу того, что норма матрицы меньше единицы, то матрица ( −)−1допускает следующее представление−1( − )=∞∑︁ ,0 = .(3.25)=0При фиксированном ∆ и малых ∆ будет выполнено ( − )−1 ≈ + . Изэтого следует следующее утверждениеУтверждение 3.Если max ((( + )′ )) < 1, где (·) – спектральныйрадиус, то существует такой набор , = − 1, . .
. 1, что при всех > алгоритм (3.15) будет стохастически устойчивым.Таким образом получены достаточные условия применимости и стохастической устойчивости алгоритма метода Монте-Карло для решения задачнахождения цены Американских опционов методом штрафной функции.Важным замечанием является то, что метод Монте-Карло обладает свойством естественного параллелизма. Если число испытаний 1 такое, что алгоритм стохастически устойчив (дисперсия не растет экспоненциально), томожно осуществить 2 моделирований с 1 повторениями каждое на разныхпроцессорах и результат осреднить.1153.5.
Численные экспериментыНиже приведены результаты решения систем (3.12) методом Монте-Карло и детерминированным методом. Расчеты производились для следующихпараметров: = 0.75, ∞ = 100, = 100, = 700, ≡ 0.15, ≡ 0.055, =35, = 0.001, = 2. На графиках изображена цена опциона в зависимостиот ценны акции в момент времени = 0. Количество моделируемых траекторий: 1000 – для рисунка 3.1, 5000 – для рисунка 3.2, 9000 – для рисунка3.3.116Рис.
3.1. Оценка стоимости опциона. Кол-во траекторий – 1000117Рис. 3.2. Оценка стоимости опциона. Кол-во траекторий – 5000118Рис. 3.3. Оценка стоимости опциона. Кол-во траекторий – 9000119ЗаключениеПри решении систем уравнений большой размерности, к которым нередко сводятся прикладные задачи, неизменно упоминаются многопроцессорныесистемы, являющиеся важным инструментом быстрого поиска решения такихсистем уравнений.
Координирование действий процессоров при этом является одним из ключевых вопросов. Асинхронные алгоритмы могут значительноупростить координацию и одновременно с этим эффективно использовать доступные вычислительные ресурсы. Исследованию таких алгоритмов, а именно методу Монте-Карло и методу асинхронных итераций, для решения системуравнений и было посвящено диссертационное исследование.В диссертации построен алгоритм метода Монте-Карло с частичной синхронизацией для решения систем уравнений вида = + ,(3.26)при выполнении условий |1 ()| < 1 и 1 (||) > 1, где 1 (·) – наибольшеепо модулю собственное число матрицы, а || – матрица, составленная из модулей элементов матрицы .
Получены достаточные условия стохастическойустойчивости предложенного алгоритма и оценен период асинхронности.Модифицирован метод асинхронных итераций для решения задачи (3.26)при условии |1 ()| < 1 и 1 (||) > 1. Получены оценки периода асинхронности.Получены и формально описаны оценки метода Монте-Карло, обладающие свойством асинхронности, для решения систем обыкновенных дифференциальных уравнений большой размерности. Получены достаточные условияих стохастической устойчивости.120Построены асинхронные оценки метода Монте-Карло для нахождениястоимости американского опциона, исследованы условия их стохастическойустойчивости.Полученные результаты позволяют решать широкий спектр прикладныхзадач из различных областей науки, предоставляя при этом возможность эффективно использовать многопроцессорные вычислительные системы, что вобстановке непрерывного развития вычислительной техники выгодно выделяет исследованные в диссертации методы и алгоритмы.
Кроме того, указанныетеоретические результаты могут послужить основой для дальнейших исследований асинхронных методов вычислений.121Литература1. Chazan D., Miranker W. Chaotic relaxation // Linear Algebra and its Applications. 1969. Vol. 2, no. 2. P. 199–222.2. Baudet G. M. Asynchronous Iterative Methods for Multiprocessors // J.ACM. 1978. Vol.
25, no. 2. P. 226–244.3. Ермаков С.М. Метод Монте-Карло и смежные вопросы. Москва: Наука,1975. С. 472.4. Ермаков С.М. Метод Монте-Карло в вычислительной математике (Вводный курс). Невский Диалект, Бином. Лаборатория знаний, 2009. С. 192.5. Ермаков С.М. Параметрически разделимые алгоритмы // Вестник СПбГУ, Сер.1, вып. 4,. 2010. С.
25–31.6. Ермаков С.М., Михайлов Г.А. Статистическое моделирование. М.:Наука,1982. С. 296.7. Михайлов Г.А., Войтишек А.В. Численное статистическое моделирование. Методы Монте-Карло. Академия, 2006. С. 368.8. Михайлов Г.А. Оптимизация весовых методов Монте-Карло. М.:Наука,1987. С. 240.9. Михайлов Г.А. Весовые методы Монте-Карло. Новосибирск: Изд-во СОРАН, 2000.
С. 248.10. Halton J. H. A retrospective and prospective survey of the Monte Carlomethod // SIAM Review. 1970. Vol. 12, no. 1. P. 1–63.11. Halton J. H. Sequential Monte Carlo techniques for the solution of linearsystems // Journal of Scientific Computing. 1994. Vol. 9, no. 2. P. 213–257.12212. Halton J. H. Sequential Monte Carlo techniques for solving non-linear systems // Monte Carlo Methods and Applications.2006.Vol. 12, no. 2.P.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
