Дж. Деммель - Вычислительная линейная алгебра, страница 82

Это обстоятельство делает привлекательным применение итерационных методов крыловского подпространства, таких, как метод СС (равд. 6.6), поскольку в них матрица Я используется лишь в произведениях с векторами. Число матрично-векторных умножений в методе СС зависит от числа обусловленности матрицы Я. Оказывается (и в этом состоит особая привлекательность метода декомпозиции области!), что Я гораздо лучше обусловлена, чем исходная матрица А (ее число обусловленности растет как 0(гУ), а не как 0(Мг)), а потому метод СС сходится быстро ~116, 205). В более общем случае имеется и ) 2 подобластей, разделенных границами (см. рис.

6.21, где подобласти разделены жирными линиями). Если пронумеровать последовательными числами узлы каждой подобласти и лишь затем называется дополнением Шура ведущей главной подматрицы, содержащей бло- ки Аы и Агг. Следовательно, можно написать 366 Глава б.

Итерационные методы для линейных систем граничные узлы, то получим матрицу вида (6.62) Снова эту матрицу можно факторизовать, факторизуя независимо друг от уга диагональные блоки Ан, а затем формируя дополнение Шура Я = др А~+1 ат1 — 2,'1 1А; „,А,; Асат1. а т В том случае, если имеется более чем один граничный сегмент, Я обладает структурой, которую можно использовать для предобуславливания.

Так, если внутренние узлы каждого граничного сегмента занумерованы прежде, чем узлы на пересечении таких сегментов, то возникает блочная структура, схожая со структурой матрицы А. Диагональные блоки в Я устроены слож- 1/2 но, но их можно аппроксимировать матрицей Т~, допускающей эффективное обращение посредством метода и'и Т [36, 37, 38, 39, 40]. Мы можем резюмировать достижения в теории метода следующим образом: при подходящем выборе предобуславливателя для матрицы Я можно добиться, чтобы число шагов алгоритма СС не зависело от числа 1т' граничных узлов [23Ц.

6.10.2. Методы с перекрытием Мы говорили в предыдущем разделе о методах без перекрышия, потому что области, соответствующие узлам диагональных блоков Аи, были непересекающимися, что приводило к блочно-диагональной структуре, показанной в уравнении (6.62). В данном разделе мы допускаем пересечение областей, иллюстрируемое рисунком.

Как увидим, это позволит нам построить алгоритм, сравнимый по скорости с многосеточным методом, но применимый к более широкому кругу задач. Прямоугольник на рисунке, граница которого указана пунктиром, обозначим через Й1, а квадрат с границей, проведенной сплошной линией, через Й2. Узлы пронумерованы таким образом, чтобы первые номера получили узлы из Й1, а последние — из Й2, при этом средние номера будут присвоены узлам из пересечения Й1 П Й2. 368 Глава б. Итерационные методы для линейных систем Теперь у нас достаточно обозначений для того, чтобы описать два основных алгоритма декомпозиции области с перекрытием.

Простейший из них называется (по причинам, связанным с его историей) аддитивным методом Шварца, но с равным основанием может именоваться блочными итерациями Якоби с перекрытием вследствие своей схожести с (блочным) методом Якоби из равд, 6.5 н 6.6.5. Алгоритм 6.18. Аддитивный метод Шварца для пересчета приближенного решения х; системы Ах = 5 в более точное приближение хг+1.

т; = Ь вЂ” Ах; /" вычислить невявну»/ х1.»1 = О хита, = х;а, + Аа~ н . га, /" модифицировать решение на й1 "/ хг+цп» = х;чцп» + Аа|о, гп, /" модифицировать решение на йг "/ Этот алгоритм можно записать одной строкой следующим образом: В словесном описании алгоритм работает так: поправка Аа,' а, га, соответствует решению уравнения Пуассона только на области й1, при этом используются граничные условия, зависящие от предыдущего приближенного решения х;, в узлах П, 14, 17, 18 и 19. Аналогично интерпретируется поправка Ап' а гп„ использующая граничные условия, зависящие от х,, в узлах 5 и 6. В данном случае, й; суть прямоугольники, поэтому для определения поправок Аа1п гги можно применить любой из ранее описанных быстрых алгоритмов, например многосеточный метод.

Поскольку аддитивный метод Шварца является итерационным, нет необходимости решать задачи на областях й; точно. Действительно, адлитивный метод Шварца обычно используется квк предобуславливатель для методов крыловского подпространства типа алгоритма сопряженных градиентов (см. равд. 6.6.5). В обозначениях разд. 6.6.5 предобуславливатель М описывается формулой М-1 пыо1 Если бы й» и йг не пересекались, матрица М ' упростилась бы к блочно- диагональному виду ~»„8 О что соответствует блочным итерациям Якоби. Однако, как мы знаем, метод Якоби сходится не слишком быстро, потому что иинформация» о решении передается нз одной области в другую через границу между ними довольно медленно (см.

обсуждение в начале разд. 6.9). Но если пересечение двух областей составляет достаточно большую часть каждой из них, информация будет распространяться со скоростью, достаточной для того, чтобы обеспечить быструю сходимость. Разумеется, пересечение не должно быть слишком велико, 369 6.10. Декомпозиция области поскольку это сильно увеличило бы работу.

При построении хорошего метода декомпозиции области целью является выбор подобластей и их пересечений, гарантирующий быструю сходимость при выполнении по возможности меньшей работы. Ниже мы вернемся к вопросу о том, каким образом сходимость зависит от размера перекрытия. Из обсуждения в разд. 6.5 мы знаем, что метод Гаусса — Зейделя обычно эффективнее метода Якоби. Это же справедливо для рассматриваемой ситуации: блочный метод Гаусса — Зсйделя с перекрьлтием (чаще называемый мультипликатпивны.м методом Шварца) нередко оказывается вдвое более быстрым, чем адлитивные блочные итерации Якоби (т.

е. здцитивный метод Шварца). Алгоритм 6.19. Мультипликативный метод Шварца длл перссчгтпа при- ближенного решения х1 системы Ах = Ь: гп, = (Ь вЂ” Ах1)п, /г вычислить невязку для х, на области Й1 "/ л-1 х1+л и, — — х;и, +Ап 11, гп, /* псрсвычислить решение на Й1 "/ Х1Ьл П,П = Х1 010, гп, = (Ь вЂ” АХ1ьт)п, /* вычислить нсвязку для хг л на области Йг "/ л-1 ХЬЬ1 ц~ — Х1л 1 П + ~П П ' Гоь /" пгргвычислить решение на Йг г/ хьь1 010, = хг+1 010, (2) (2') (3) (4) (4') Заметии, что строки (2') и (4') не требуют перемещения данных, если хг+1 и х1э1 записьлваются на место прежнего вектора х,.

В этом алгоритме, как и в алгоритме 6.18, вначале решается уравнение Пуассона на Й1, использующее граничные данные, зависящие от х1. Затем решается уравнение Пуассона на Йг, но теперь используются только что пересчитанные граничные данные. И этот алгоритм может быть применен в качестве предобуславливателя для методов крыловского надпространства. На практике используется большее, чем 2, число подобластей Йь Причинами могут быть более сложная геометрия основной области, наличие многих независимых параллельных процессоров, позволяющее независимо решать подзадачи А01п,гп„или просто желание сделать подзадачи А„1„гп, малыми и дешево решаемыми. Приведем краткое изложение теоретического анализа сходимости этих методов для модельной задачи и подобных ей дифференциальных уравнений с частными производными. Пусть Ь вЂ” шаг сетки.

Теория предсказывает число итераций, необходимых для сходимости, как функцию от Ь при Ь, стремящемся к нулю. В случае двух областей Й1 и Йз указанное число итераций не зависит от Ь, если пересечение Й1 П Йз составляет ненулевую долю всей области Й1 11 Йг. Это привлекательное свойство, напоминающее о многосеточном методе, скорость сходимости которого также не зависела от шага сетки Ь. Однако в стоимость одной итерации входит точное решение подзадач на Й1 н Йг, что может быть сравнимо со стоимостью ре1пения исходной задачи.

Следовательно, задачи на Й1 и Йз должны решаться очень дешево 1как это было в 370 Глава б. Итерационные методы для линейных систем ! Рис. 6.21. Грубая и более точная дискретизации Ь-обрезной области. разобранном выше примере с Т-образной областью), чтобы общая стоимость не была слишком высока. Предположим теперь, что имеется много областей Пь каждая размера Н » Ь. Иначе говоря, можно представлять себе П; как элементы грубой сетки с шагом Н, включающие в себя дополнительно некоторые ячейки мелкой сетки, находящиеся за границей крупной ячейки 1это показано пунктирной линией на рис. 6.21).

Пусть число б < Н измеряет степень перекрытия подобластей, и пусть все три величины Н, б и Ь стремятся к нулю таким образом, чтобы доля перекрытия 6(Н оставалась постоянной, причем Н » Ь. Тогда число итераций, необходимых для сходимости, растет как 1~Н, т. е. не зависит от шага Ь мелкой сетки. Это близко к соответствующему свойству многосеточного метода, но хуже его, так как число итераций многосеточного метода постоянно и работа на одно неизвестное, выполняемая в нем, равна 0(1). Для достижения такой же производительности нужна еще одна идея, которая (что, возможно, не является удивительным) похожа на идею многосеточного метода.

Используем приближение Ан задачи на сетке с шагом Н как предобуславливатель грубой сетки в дополнение к предобуславливателям мелкой сетки Ап) и . Для описания алгоритма нам потребуются три матрицы. Пусть, во-первых, Ан — матрица модельной задачи, дискретизованной с крупным шагом Н. Во-вторых, нам нужен оператор суженил В, который бы преобразовывал невязку с мелкой сетки в функцию на грубой сетке. По существу, это тот же оператор, что и в многосеточном методе (см. разд. 6.9.2). Наконец, нужен оператор интерполяции для интерполирования значений с грубой сетки на мелкую.