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

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

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

Обозна­чим через множество моментов времени, в которые происходит обновление .Разумно предположить, что в распределенной системе процессор, обнов­ляющий компоненту , не всегда имеет актуальную информацию по другимкомпонентам вектора . Поэтому в асинхронном случае допускается исполь­зование устаревшей информации. Этот факт можно записать в следующемвиде ( + 1) = (1 (1 ()), . . . , ( ())), ∀ ∈ ,где () – моменты времени, удовлетворяющие неравенству0 ≤ () ≤ , ∀ ∈ .(1.3)16Для всех моментов ∈/ считаем, что не обновляется ( + 1) = (), ∀ ∈/ .(1.4)Элементы множества следует рассматривать как индексы последова­тельности моментов реального времени, в которые происходит обновление.Процессорам, которые не обновляют компоненту не обязательно знатьмножество , так как этого не нужно для расчета итераций (1.3) и (1.4),и поэтому нет необходимости иметь в системе глобальное время.

Разницу( − ()) между текущим временем и временем (), когда процессором,обновляющем , в последний раз была получена информация о компоненте , может быть рассмотрена как задержка в передаче информации. Удобнорассматривать вычислительный процесс в данной ситуаций следующим об­разом: в момент ∈ процессор, закончивший предшествующие расчеты иготовый выполнить новые, получает посредством некоторого механизма вели­чины 1 (1 ()), . .

. , ( ()), а затем обновляет по формуле (1.3), при этомему совершенно не обязательно знать значения , 1 (), . . . , () и элементов , = 1, . . . , .Заметим, что такие итеративные методы для решения систем линейныхуравнений, как метод Якоби и метод Гаусса-Зейделя, являются частнымислучаями итерации (1.3). Для метода Якоби множества и моменты времени () определяются как = , () = , ∀, ∈ {1, . . .

, }, ∀ ∈ .Для метода Гаусса-Зейделя множества и моменты времени () определя­ются следующим образом = { ∈ | ( + 1) = 0},⎧⎨ () = − + , для < ,⎩ () = − + − , для ≥ .17Чтобы называть итерации (1.3) - (1.4) асинхронными необходимо доба­вить определенные условия на множества и моменты времени ().Множества являются бесконечными и для любой последовательно­сти { } ⊆ , стремящейся к бесконечности, выполнено lim→∞ ( ) = ∞для = 1, . . . , .Данное предположение гарантирует, что каждая компонента обновитсябесконечное число раз, а старая информация в конечном итоге выйдет изобработки.

В дальнейшем будем считать, что это предположение выполнено.После введения итераций (1.3) - (1.4) и сделанных относительно них пред­положений возникает вопрос – при каких условиях итерации сходятся к непо­движной точке оператора ? Достаточные условия (см. [16]) даёт следующаяТеорема 2.Если существует последовательность непустых множеств{()}, удовлетворяющих условиям∙ · · · ⊂ ( + 1) ⊂ () ⊂ · · · ⊂ (0) ⊂ ;∙ () ∈ ( + 1) для любого и ∀ ∈ (). Более того, если последо­вательность {()} такая, что () ∈ () для = 0, 1, .

. . , тогдакаждая предельная точка {()} является неподвижной точкой опе­ратора ;∙ Для любого ∈ {0, 1, . . . } существуют множества () ∈ , такиечто() = 1 () × 2 () × · · · × (),∙ начальное приближение (0) принадлежит (0),тогда каждая предельная точка последовательности {()}, определяемойасинхронными итерациями, является неподвижной точкой оператора .18Заметим, что первое и второе условия теоремы вместе подразумевают,что синхронные итераций := (), начинающаяся с некоторого начального из (0), сходятся к неподвижной точке оператора . Третье условие озна­чает, что если взять два произвольных элемента () и поменять в них -ыекомпоненты местами, то снова получатся элементы множества ().Далее ограничимся рассмотрением операторов вида : R → R .

Рас­смотрим следующую норму на R‖‖ = | |,где = (1 , 2 , . . . , ) ∈ R и > 0, = 1, . . . , .Если теперь рассматривать сжимающие отображения с параметром сжа­тия < 1 и положить в определении асинхронных итераций = R, = 1, . . . , , а также = R , то согласно теореме 2, чтобы показать, чтоасинхронные итерации сходятся к неподвижной точке * оператора , нужнопостроить последовательность множеств {()}. Определим их следующимобразом() = { ∈ R | ‖ − * ‖ ≤ ‖(0) − * ‖ }.Нетрудно проверить выполнение условий теоремы.Далее будут использовать следующие нормы:∙ для вектора = (1 , .

. . , ) :‖‖ = max | |,1≤≤(1.5)∙ для матрицы = ‖ ‖,=1 :‖‖ = max1≤≤∑︁=1| |.(1.6)191.1.1. Система линейных уравненияРассмотрим случай, когда () = + ,где = ‖ ‖,=1 – заданная матрица, ∈ R – заданный вектор правыхчастей. В этом случае выполняется поиск такого * , что* = * + .Асинхронные итерации (1.3)-(1.4) для системы линейных уравнений будутиметь вид ( + 1) =∑︁, ( ()) + , ∈ ,=1(1.7) ( + 1) = (), ∈/ .В работе [1] было доказано, что хаотические релаксации, которые явля­ются частным случаем асинхронных итераций, для системы линейных урав­нений сходятся к решению системы тогда и только тогда, когда 1 (||) < 1.В [16] было получено обобщение этого результата для случая асинхронныхитераций.Теорема 3.Пусть матрица такая, что − обратима.

Тогда следую­щие утверждения эквивалентны1. 1 (||) < 1;2. Для любого начального (0), для любого ∈ R , для любых множеств , удовлетворяющих условиям из определения асинхронных итера­ций, для любого выбора переменных () таких, что − 2 < () < ,последовательность, порождаемая асинхронными итерациями (1.7),сходится к ( − )−1 .20Таким образом, если обычный (синхронный) процесс сходится –|1 ()| < 1, но 1 (||) > 1, то по крайней мере асинхронные итерации некото­рого вида обязательно расходятся. В этом случае можно попытаться испра­вить положение, осуществляя после некоторой группы асинхронных итера­ций определенное количество синхронных, которые уменьшают ошибку (ча­стичная синхронизация).Будем далее рассматривать алгоритм, который после каждых асин­хронных итераций, использует простых.

Очевидно, существует такое ,при котором этот комбинированный итерационный процесс будет сходиться,но медленнее, вообще говоря, чем процесс, полностью синхронизированный.Поэтому наш подход имеет смысл, если асинхронные итерации существеннодешевле, чем синхронные.Оценка возможной получаемой выгоды существенно зависит от вида мат­рицы и в общем случае может быть достаточно грубой. По-видимому, наи­более эффективным здесь может быть численный эксперимент. Тем не менеемы докажем лемму, которая указывает границы роста ошибки в асинхронномслучае при 1 (||) > 1.Пусть (), = 0, 1, 2, .

. . – последовательность асинхронных итерацийдля системы = + ,а̃︀ – её решение. Тогда () можно представить в виде () = ̃︀ + ∆(), где∆() – последовательность асинхронных итераций для системы = .Лемма 1.Если для матрицы выполнено |1 ()| < 1 и 1 (||) > 1, то‖∆()‖ ≤ ‖‖ ‖∆(0)‖для = 0, 1, 2, . . .

.(1.8)21Доказательство. Проведем доказательство по индукции. Для = 0 имеем‖∆(0)‖ = ‖‖0 ‖∆(0)‖,и, следовательно, база индукции доказана. Пусть теперь (1.8) выполнено длявсех ≤ . Покажем, что (1.8) выполняется при = + 1. Согласно опре­делению асинхронных итераций, если ∈ , то∆ ( + 1) =∑︁, ∆ ( ()),=1а если ∈/ , то∆ ( + 1) = ∆ ().Пусть ∆ˆ – вектор длины 2, такой что ∆ˆ = ∆ ( + 1), ∆ˆ+ = 0 при ∈ и ∆ˆ = 0, ∆ˆ+ = ∆ ( + 1) при ∈/ . Обозначим вектор̃︁ . Для ∆ˆ̃︁ и ∆() справедливо ра­, ∆(∆1 (1 ()), . .

. , ∆ ( ())) за ∆венство⎛∆ˆ=⎝1002⎞⎛⎠⎝̃︁∆⎞⎠,∆()где 1 , 2 – матрицы на . При ∈ -ая строка матрицы 1 равняется -ой строке матрицы , а при ∈/ -ая строка матрицы 1 состоит изнулей. 2 – диагональная матрица, для которой -й элемент диагонали равен0, если ∈ , и равен 1 в противном случае.Заметим, что ‖∆ˆ‖ = ‖∆( + 1)‖, ‖1 ‖ ≤ ‖‖, и в силу того, что‖‖ ≥ |1 (||)| > 1, выполнено неравенство ‖2 ‖ ≤ ‖‖.

Тогда справедливонеравенство⃦⎛⃦⎛⎞⎛⎞⃦⎞⃦⃦⃦⃦⃦̃︁̃︁⃦ 1 0⃦⃦⃦∆∆⎝⎠⎝⎠⃦ ≤ ‖‖ ⃦⎝⎠⃦ .‖∆( + 1)‖ = ⃦⃦⃦⃦⃦⃦ 0 2⃦ ∆() ⃦∆() ⃦̃︁ , ∆() )‖ = |∆ ′ (′ )| для некоторого натурального ′ ≤ иПусть ‖(∆221 ≤ ′ ≤ . Так как ′ < , в силу предположения индукции будет выполнено⃦⎛⎞⃦⃦⃦̃︁⃦⃦∆⃦⎝⎠⃦ ≤ ‖∆(′ )‖ ≤ ‖‖′ ‖∆(0)‖ ≤ ‖‖ ‖∆(0)‖,⃦⃦⃦ ∆() ⃦а следовательно,‖∆( + 1)‖ ≤ ‖‖+1 ‖∆(0)‖,и лемма доказана.Теперь легко доказать следующую теорему.Теорема 4.Если итерационный процесс состоит из последовательностигрупп асинхронных итераций и затем синхронных, то при достаточно(︁ )︁ +‖‖большом он сходится.

При этом сходится не медленнее чем для произвольного , удовлетворяющего неравенству |1 ()| < < 1.Доказательство. Из леммы 1 следует, что за асинхронных итераций ошиб­ка может возрасти не более чем в ‖‖ раз. Поскольку |1 ()| < 1, то для∀ > 0, такого что < 1 − |1 ()|, найдется такое 0 , что для ∀ ≥ 0 будетвыполняться неравенство ‖ ‖ < (|1 ()| + ) < 1. Обозначим (|1 ()| + )за .

Нетрудно видеть, что |1 ()| < < 1. Норму ошибки после + ите­раций ( асинхронных и синхронных) можно оценить следующим образом:‖∆( + )‖ ≤ ‖ ‖‖‖ ‖∆(0)‖ < ‖‖ ‖∆(0)‖.При достаточно большом имеем ‖‖ < 1, что и доказывает первую частьтеоремы.Мы видим, что за + итераций ошибка уменьшается в ‖‖ раз.Такой результат мы имели бы при геометрической сходимости с параметром, если бы + = ‖‖ . То есть=1( ‖‖ ) +(︂= что доказывает вторую часть теоремы.‖‖)︂ +,23Теорема 4 даёт соотношение на количество асинхронных и синхронныхитераций для систем линейных уравнений вида (1).

В алгоритмах, где чере­дуются асинхронных и синхронных итераций, и при выбранном соотно­шении и итерации сходятся к искомому решению, будем называть сумму+периодом асинхронности.Перейдем теперь к рассмотрению болееобщего случая.1.1.2. Система нелинейных уравненийОпределение 2.Оператор из R в R называется липшицевым (в лите­ратуре (см. [20]) также встречается название n-липшицевый) операторомна ⊆ R , если существует неотрицательная матрица такая, что| () − ()| ≤ | − |, ∀, ∈ ,(1.9)где операция взятия модуля применяется покомпонентно и неравенствовыполняется для всех компонент.Матрицу из определения 2 будем называть липшицевой матрицей опе­ратора .Определение 3.Оператор из R в R называется сжимающим (в ли­тературе (см. [20]) также встречается название n-сжимающий) операто­ром на ⊆ R , если он липшицев на и для его липшицевой матрицы выполнено 1 () < 1, где 1 () — первое собственное число матрицы .Для сжимающих операторов справедлива (см.

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

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