Диссертация (1150810), страница 5
Текст из файла (страница 5)
В противном случае с ростом будет наблюдаться экспоненциальный рост дисперсии.Теперь для заданного вектора = (1 , . . . , ) введем оценки = ()32и * = * () такие, чтоE = (ℎ, +1 ),E * = ( ( )+1 , ℎ).Оценки и * строятся на траекториях цепей Маркова (, ) и (, ) длины + 1 и выражения для них имеют вид=ℎ0 0 ,1 . . . ,+1 +1,0 0 ,1 .
. . ,+1(1.18)* =0 1 ,0 . . . +1 , ℎ+1.0 0 ,1 . . . ,+1(1.19)Как и ранее дисперсии оценок (1.18), (1.19) вычисляются просто, учитывая, что выражения для вторых моментов имеют вид(︃E 2 =(︃E( * )2 =2(︂2ℎ,( )2(︂)︂+1( )2)︃2 ,)︂+1)︃, ℎ2 ,где операции возведение в квадрат векторов и матриц, как и деление матрицы на матрицу и вектора на вектор, выполняются поэлементно. Поведениедисперсии, также как и для оценок (1.14), (1.15), с ростом определяетсяпервыми собственными числами матриц 2 / и ( )2 / .Таким образом, при помощи пар оценок , и * , * для заданного вектора и натурального может быть получена оценка вектора∑︀+1 + =0 .
Поручая моделирование цепей Маркова и вычисление оценок по ним разным процессорам, мы вновь получим асинхронный алгоритм.1.2.3. Оценки суммы ряда НейманаОценки (1.14), (1.18) и (1.15), (1.19) могут служить основой алгоритмовс частичной синхронизацией для получения решения системы (1.12) без огра33ничений вида (1.13). Алгоритмы состоят в последовательном вычислении оценок векторов (), где () связаны соотношением(0) = , () = ( − 1) +−1∑︁ ,(1.20)=0( + 1) = () + , .
. . , ( + ) = ( + − 1) + , = 1, + 2, 2 + 2, . . .(1.21)или соотношением(0) = , () = +1 ( − 1) +∑︁ , = 1, 2, . . .(1.22)=0для некоторого фиксированного натурального . Первый случай соответствует частичной синхронизации, когда после асинхронного алгоритма следуют синхронные, аналогично описанному выше подходу для асинхронныхитераций. Если устремить к бесконечности, то () в (1.20) – (1.22) будетстремиться к искомой сумме∑︀∞=0 .При использовании метода Монте-Карло оценками векторов () будутслучайные векторы Ξ() = (1 (), . . . , ()) . Скалярное произведение(ℎ, ()) может оцениваться с помощью оценок вида (1.14), (1.18). В этомслучае оценкой для (ℎ, ()) будет(Ξ( − 1)) + + (ℎ, ).Или оценок вида (1.15), (1.19) и в этом случае (ℎ, ()) будет оцениваться как * (Ξ( − 1)) + * + (ℎ, ).В каждом случае берется среднее из некоторого количества реализацийоценок. Оценка всех компонент () может быть получена, если полагать ℎравным векторам с одной из компонент равной 1 и остальными равными 0.При этом во многих случаях интерес представляет оценка () для ≤ < +∞ (разностные схемы).34Заметим, что один и тот же вектор ( в (1.22) и −1 в (1.20)–(1.21)) оценивается на каждой итерации, поэтому можно организовать алгоритм такимобразом, чтобы оценка этого вектора уточнялась с каждой новой итерацией,используя оценки с предыдущих шагов итераций.Особый интерес представляет задача оценки ковариации случайных векторов, возникающих при использовании метода Монте-Карло для оценкипоследовательности векторов итерационного процесса.
Ковариация вектораΞ() с ростом может оставаться ограниченной, а может экспоненциальнорасти. В последнем случае алгоритм будет стохастически неустойчивым, чтоделает невозможным его применение на практике.Рассмотрим теперь итерационный процесс () c начальным вектором(0) и(1.23)() = ( − 1) + , = 1, 2, . . . ,где – матрица ×, а – вектор длины . Пусть при каждом вычислениеслагаемых в правой части (1.23) происходит с помощью рандомизированнойпроцедуры.
Таким образом, вместо последовательности () возникает последовательность случайных векторов Ξ() = (1 (), . . . , ()) , = 0, 1, 2, . . .с начальным вектором Ξ(0), связанных соотношением(1.24)Ξ() = B Ξ( − 1) + D()где B = ‖, ‖,=1 – случайные матричные операторы, D() – случайныевекторы.ПриэтомдлялюбогонатуральноговыполненоEΞ() = () = (1 (), . . . , ()) , EB = , ED() = .Следующая лемма определяет характер поведения ковариации векторовошибок ℰ() = Ξ() − ().Лемма 3.Пусть случайные операторы B , векторы D() и Ξ() независимыв совокупности при любых = 0, 1, 2, . .
. и < , в том смысле, что случайные величины 1 , 2 , 3 , где 1 – произвольный элемент оператора B , 2 –35произвольный элемент D(), 3 – произвольный элемент Ξ(), независимыв совокупности. Тогда для матрицы ковариации вектора ℰ() справедливосоотношение ℰ() = ⊗ ℰ( − 1) + E(∆ ⊗ ∆ ) ℰ( − 1)+(1.25)+ E(∆ ⊗ ∆ )(( − 1)( − 1) ) + (),где ∆ = B − , () = D() − , – операция векторизации матрицы,а ⊗ – операция кронекеровского произведения матриц.Доказательство. Подставим в (1.24) выражения для B , D() и Ξ():() + ℰ() = ( + ∆ )(( − 1) + ℰ( − 1)) + + ().Поскольку () подчинен (1.23), получим выражения для ℰ() и ℰ() :ℰ() = ℰ( − 1) + ∆ ( − 1) + ∆ ℰ( − 1) + ()(1.26)иℰ() = ℰ( − 1) + ( − 1) ∆ + ℰ( − 1) ∆ + () .(1.27)Далее необходимо перемножить правые и левые части равенств (1.26), (1.27)и вычислить математическое ожидание от всех членов получившегося равенства.
При этом стоит отметить, что математические ожидания многих слагаемых правойчастибудутравнынулю.Так,например,E∆ ℰ( − 1)( − 1) ∆ = 0 в силу того, что ℰ( − 1) не зависит от ∆ иEℰ() = 0. Учитывая эти соображения, имеемℰ() = ℰ() + E(∆ ℰ( − 1)∆ )++ E(∆ ( − 1)( − 1) ∆ ) + ().Если столбцы матриц ℰ() составить в один столбец длины 2и то же самое проделать с матрицей ℰ( − 1), то получившиеся векторы36будут связаны соотношением(︀)︀ ℰ() = ( ⊗ ) ℰ( − 1).Теперь, применяя такую операцию векторизации к матрицам ℰ(),ℰ( −1), ( − 1)( − 1) и (), получим (1.25), что и доказывает лемму.Из леммы 3 можно вывестиСледствие 1.Для стохастической устойчивости алгоритма (1.24) необходимо и достаточно, чтобы модуль первого собственного числа матрицы ⊗ + E(∆ ⊗ ∆ ) был меньше единицы.Известно (см., например, [25, 26]), что собственными числами ⊗ являются () (), , = 1, .
. . , . Заметим также, что ‖ ⊗ ‖ = ‖‖2 .Для удобства введем следующие обозначения: ℳ = E(∆ ⊗ ∆ ),ℬ = ⊗ + ℳ и = E(∆ ⊗ ∆ )(( − 1)( − 1) ) + (). Тогдавыражение для ковариации из леммы 3 примет вид ℰ() = ℬ ℰ( − 1) + .Элементы матрицы ℳ имеют порядок 1/ , где – количество моделируемых траекторий на -ой итерации, то есть ℳ =1′ ℳ ,где ℳ′ –матрица с элементами, не зависящими от .Лемма 3 и следствие из нее позволяют сделать определенные выводы относительно стохастической устойчивости рандомизированных процедур дляитерационных процессов (1.20)–(1.21) и (1.22).Теорема 7.Если |1 ()| < 1, и на каждой итерации (1.20)–(1.21) вычисления осуществляются при помощи метода Монте-Карло, то для любогонатурального существует такое ′ , что для ∀ > ′ , = 1, 2, .
. . , где37 – количество моделируемых траекторий цепи Маркова для оценки ()в (1.20)–(1.21), рандомизированный итерационный процесс (1.20)–(1.21) будет стохастически устойчивым.Доказательство. Рассмотрим (1.20) и заметим, что матрица из Леммы 3равна , при этом в явном виде матрица не известна и оценивается припомощи метода Монте-Карло. Учитывая, что ‖ℬ ‖ ≤ ‖‖2 +1′ ‖ℳ ‖,нормуковариации ошибки после вычисления (1.20) методом Монте-Карло можнооценить как‖ ℰ()‖ ≤ (‖ ‖2 +1‖ℳ′ ‖)‖ ℰ( − 1)‖ + ‖ ‖.Согласно (1.21) последующие итераций ковариация ошибки будет изменяться в соответствии с ℰ( + 1) = ( ⊗ +1ℳ′ ) ℰ() + +1 .+1Так как |1 ()| < 1, то |1 ( ⊗ )| = 21 () < 1 и существует такое ′ , что1для ∀+1 > ′ первое собственное число матрицы ⊗ + +1ℳ′ по модулю будет меньше единицы.
Тогда, согласно следствию 1, рандомизированныйитерационный процесс будет стохастически устойчивым.Оптимальный выбор параметров , , ′ из теоремы 7 зависит от матрицы , вида оценок и свойств многопроцессорной системы. Как видно, придостаточно большом ′ предложенная процедура соответствует случаю частичной синхронизации в детерминированном случае, за исключением того,что на каждом шаге итерации возникает случайная ошибка. Помимо очевидного увеличения числа моделируемых траекторий ′ дисперсия случайнойошибки может быть уменьшена путем применения различных техник уменьшения дисперсии (см.
[4, 7, 27]). Важно заметить, что если количество процессоров больше порядка системы, то часть процессоров при использовании38асинхронных итераций будет простаивать, так как для расчета одной компоненты очередной итерации используется не более одного процессора. Использование метода Монте-Карло в тех же условиях позволяет эффективноиспользовать все имеющиеся процессоры, равномерно распределяя по ниммоделируемые траектории цепей Маркова.Похожую теорему можно сформулировать для (1.22).Теорема 8.Если |1 ()| < 1, и на каждой итерации (1.22) вычисленияосуществляются при помощи метода Монте-Карло, то для любого натурального существует такое ′ , что для ∀+1 > ′ , где – количествомоделируемых траекторий цепи Маркова для оценки () в (1.22), рандомизированный итерационный процесс (1.22) будет стохастически устойчивым.Доказательство.
При применении метода Монте-Карло для вычисления очередного () в выражении (1.22) ковариация ошибки, согласно лемме 3, будетизменяться следующим образом ℰ() = ( ⊗ +1ℳ′ ) ℰ( − 1) + .Сделанное предположение о матрице , а именно |1 ()| < 1, означает, чтовыполнено неравенство |1 ( )| = |1 ()| < 1. Модуль первого собственного числа матрицы ⊗ равен |1 ()|2 . Этот факт позволяет заключить,что для любого натурального существует такое ′ , что для ∀+1 > ′ модуль первого собственного числа матрицы ⊗ +1′+1 ℳбудет меньшеединицы.
А это в свою очередь согласно следствию 1 означает, что процедура вычисления (1.22) методом Монте-Карло будет стохастически устойчивой.При использовании (1.22) и метода Монте-Карло может быть построенстохастически устойчивый алгоритм. Он будет обладать большей асинхрон39ностью чем алгоритм, построенный на основе (1.20)–(1.21), но у такого алгоритма при равном числе моделируемых траекторий ковариация оценок будетбольше.Полученные результаты для систем линейных уравнений дают представление о периоде асинхронности применения последовательного метода МонтеКарло.1.2.4. Система нелинейных уравненийОсновные принципы и идеи применения метода Монте-Карло к решениюнелинейных уравнений можно найти, например, в [3, 4, 28].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
