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

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

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

[2]) следующаяТеорема 5.Если – -сжимающий оператор на замкнутом множестве ⊆ R и () ⊆ , тогда произвольные асинхронные итерации сходятсяк единственному решению системы (1.1).24Таким образом, если обычный (синхронный) процесс +1 = ( ), = 0, 1, . . . сходится, а оператор не удовлетворяет условиям теоремы 5,то, по крайней мере, асинхронные итерации некоторого вида обязательно рас­ходятся. Можно попытаться исправить положение, осуществляя после неко­торой группы асинхронных итераций определенное количество синхронных,которые уменьшают ошибку (частичная синхронизация).В статье [14] был приведен пример линейной системы вида = + ,при решении которой методом асинхронных итераций в некоторых случаяхможно наблюдать расходимость метода.

Для получения аналогичного резуль­тата для нелинейной системы (1.1) достаточно рассмотреть оператор сле­дующего вида: () = 10−2 2 + + ,(1.10)где операция возведения в квадрат поэлементная.Рассмотрим теперь задачу нахождения корня некоторого оператора : R → R :() = 0.Будем искать решение методом хорд( + 1) = () − (()),где – заданная обратимая матрица, а (0) – заданный начальный вектор.Нетрудно видеть, что метод хорд – это метод простых итераций для опера­тора − , и для нахождения неподвижной точки этого оператора могутиспользоваться асинхронные итерации.

Такой оператор , при котором про­стые итерации для оператора − сходятся, а асинхронные итерации внекоторых случаях расходятся, может быть найден из выражения − () = (),25где оператор из (1.10). Таким образом искомый оператор выглядит следу­ющим образом() = −1 ( − ()).Расходимость асинхронных итераций продемонстрирована на рисунке 1.4.Рис.

1.4. Расходимость асинхронных итерацийЕсли же корень оператора ищется при помощи метода Ньютона+1 = − ′ ( )−1 ( ),26то на каждой итерации необходимо решать систему линейных уравнений′ ( ) = ( ) или эквивалентную ей систему = ( − ′ ( )) + ( ).Применение метода асинхронных итераций для решения последней системыпри некоторых условиях может привести к расходимости. Так, например, ес­ли взять () = 0.52 + + , то при 0 = (1, 1, . .

. , 1) необходимо будетрешить систему = + (0 ), при решении которой методом асинхроннойитерации можно наблюдать расходимость.Приведенные выше примеры свидетельствуют о том, что существуюттакие нелинейные операторы для которых простые (синхронных) итерациисходятся к их неподвижной точке, в то время как асинхронные итерациимогут и расходится. Возможным компромиссным решением как и в линейномслучае может быть использование последовательности групп асинхронныхитераций и затем синхронных. Число итераций и , при которых будетнаблюдаться сходимость зависит в общем случае от свойств оператора .Будем далее рассматривать алгоритм, который после каждых асин­хронных итераций, использует обычных.

Очевидно, существует такое ,при котором этот комбинированный итерационный процесс будет сходиться,но медленнее, вообще говоря, чем процесс, полностью синхронизированный.Поэтому наш подход имеет смысл, если асинхронные итерации существеннодешевле, чем синхронные.Пусть (), = 0, 1, 2, . . . – последовательность асинхронных итерацийдля системы (1.1), а ̃︀ – её решение. Пусть – липшицевый оператор на ∈ R с липшицевой матрицей , но при этом не является сжимающим,то есть 1 (||) > 1.

Рассматривая оператор ( + )̃︀ − ̃︀, не умаляя общностиможно считать, что ̃︀ = (̃︀) = 0. Полагая = ̃︀ в неравенстве (1.9), условиелипшица для оператора приобретет вид | ()| ≤ ||, ∀ ∈ .Лемма 2.При сделанных выше предположениях относительно оператора27 выполняется неравенство(1.11)‖()‖ ≤ ‖‖ ‖(0)‖для = 0, 1, 2, . . . .Доказательство. Проведем доказательство по индукции. Для = 0 имеем‖(0)‖ = ‖‖0 ‖(0)‖,и, следовательно, база индукции доказана. Пусть теперь (1.11) выполненодля всех ≤ . Покажем, что (1.11) выполняется при = + 1. Согласноопределению асинхронных итераций, если ∈ , то ( + 1) = (1 (1 ()), .

. . , ( ()))а если ∈/ , то ( + 1) = ().Если ( + 1) = (), то в силу предположения индукции выполнено| ( + 1)| ≤ ‖()‖ ≤ ‖‖ ‖(0)‖ ≤ ‖‖+1 ‖(0)‖.Если ( + 1) = (1 (1 ()), . . . , ( ())), то в силу липшицевости опе­ратора выполнено| ( + 1)| =| (1 (1 ()), . . .

, ( ()))|≤∑︁ | ( ())| ≤=1≤ ‖‖‖(1 (1 ()), . . . , ( ()))‖.По определению асинхронных итераций () ≤ , = 1, . . . , , то по пред­положению индукции| ( + 1)| ≤ ‖‖‖(1 (1 ()), . . . , ( ()))‖ ≤≤ ‖‖‖‖ ‖(0)‖ ≤ ‖‖+1 ‖(0)‖.28Следовательно, | ( + 1)| ≤ ‖‖+1 ‖(0)‖ при любом , и лемма доказана.Теперь легко доказать следующую теорему для класса нелинейных опе­раторов, описанных выше.Теорема 6.Если итерационный процесс состоит из последовательностигрупп асинхронных итераций и затем синхронных, то при достаточно(︁ )︁ +‖‖большом он сходится. При этом сходится не медленнее чем , где < 1 – параметр геометрической сходимости итераций (1.2) к решению(1.1).Таким образом, для определенного класса вычислительных устройствметод частичной синхронизации и в нелинейном случае может служить удоб­ным инструментом.

Очевидно, другие методы линеаризации, метод Ньютона,например, допускает также частичную синхронизацию.1.2. Алгоритмы метода Монте-КарлоМетод Монте-Карло зачастую без особого труда адаптируется к исполь­зованию на многопроцессорных вычислительных системах. Рассмотрим осо­бенности его применения для решения систем уравнений, начав со случаялинейных систем.1.2.1. Система линейных уравненийВ этом разделе будут рассматриваться системы линейных алгебраиче­ских уравнений вида = + ,для которых сходится метод простых итераций.(1.12)29Известны различные алгоритмы метода Монте-Карло для решения си­стемы вида (1.12) (см., например, [4, 7, 23]). Мы будем рассматривать про­стейшие алгоритмы, состоящие в оценивании сходящегося ряда Неймана(ℎ, )̃︀ = (ℎ,∞∑︁ )=0с помощью выбранной соответствующим образом оценки – оценки на траекто­риях моделируемой цепи Маркова. Здесь ℎ – заданный вектор, а ̃︀ – решениесистемы (1.12).

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

Альтернативой является запоминаниепромежуточных результатов (синхронизация).Предлагается в случае 1 (||) > 1, “дешевых” асинхронных алгоритмови относительно “дорогих” синхронных, как и в случае асинхронных итера­ций использовать смешанный алгоритм с частичной синхронизацией.

Как иранее, будем рассматривать подход, в котором чередуются асинхронные исинхронные алгоритмы. Для формального исследования такого комбиниро­ванного алгоритма мы подробно рассмотрим схемы оценивания частичных30сумм ряда Неймана в асинхронном и синхронном случаях.1.2.2. Оценки частичных сумм ряда НейманаРассмотрим аналог схемы Неймана-Улама для нахождения частичнойсуммы ряда Неймана =∑︁ ,=0где ∈ N задано. Случай = ∞ подробно изучен в литературе [3]. Случайконечного требует некоторой модификации стандартных рассуждений.Пусть ℎ – заданный вектор, ℎ = (ℎ1 , . . .

, ℎ ) . Алгоритм предполагаетзадание стохастической матрицы = ‖ ‖,=1 , удовлетворяющей условиямсогласования:(a) , > 0, если , ̸= 0, и распределение = (1 , . . . , ) такое, что > 0,если ℎ ̸= 0, или(б) , > 0, если , ̸= 0, и распределение = (1 , . . . , ) такое, что > 0,если ̸= 0.Также зададим вектор = (1 , . . . , ) , такой что > 0, = 1, . .

. , и∑︁ = 1.=1Введем случайную величину , распределенную по закону⎛⎝1 ... 1 . . . ⎞⎠,и рассмотрим случайные величины=ℎ0 0 ,1 . . . −1 , ,0 0 ,1 . . . −1 , (1.14)* =0 1 ,0 . . . , −1 ℎ,0 0 ,1 . . . −1 , (1.15)31где 0→1→···→ соответствует цепи Маркова (, ), а0 → 1 → · · · → – цепи Маркова (, ).Легко проверить, чтоE = (ℎ,∑︁ ) = (ℎ, ),=1∑︁ ( ) , ℎ) = (, ℎ).E = (*=1Столь же просто вычисляются дисперсии оценок (1.14), (1.15), если учесть,чтоE 2 =∑︁∑︁=1 0 ,1 ,...E( * )2 =∑︁ℎ20 20 ,1 . .

. 2−1 , 2=...,,001−1=1∑︁=1 0 ,1 ,...(︃20 21 ,0 . . . 2 ,−1 ℎ2=...,,001−1=1)︂ 2 (︂ℎ ∑︁ 2,2)︃,(1.16)=1(︃(︂)︂ 2∑︁( )2 ( )2ℎ,=1)︃,(1.17)где операции возведение в квадрат векторов и матриц, как и деление матри­цы на матрицу и вектора на вектор, выполняются поэлементно. В дальней­шем будет отдельно оговариваться использование подобных операций надматрицами и векторами.

Оценкой всех компонент может быть вектор = (1 , . . . , ) , где , = 1, . . . , получаются из (1.14), если полагать ℎравным вектору с -ой компонентой равной единице и остальными равныминулю.Как видно из (1.16) и (1.17) поведение дисперсии с ростом определяет­ся первыми собственными числами матриц 2 / и ( )2 / соответственно.Так, если выполнено 1 (2 /) < 1 и 1 (( )2 /) < 1, то соответствующиедисперсии будут ограничены при стремлении к бесконечности.

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

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