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

Его идея состоит в том, чтобы улучшить цикл Гаусса — Зейделя подходящим взвешенным усреднением значений х ьг . и х х лг длЯ метода ЗОВ = (1 — ы)х +ых ч.цд. Это приводит к следующему алгоритму: Алгоритм 6.5. Метод БОВл /агу=1 Фон „, ~ д — г п х тг . = (1 — ы)хтд+ — (б — ~ ь, а ах ч.ць — ~ з „, адзхт,ь~ епд /ог Эту формулу можно переписать в виде (г = 1,..., п) 1-1 и ад,х +цд+ы~~~ адзх +ге = (1 — ы)аПхтд — ы ~~~ азьхть+ыуы Ьтг ь=д+г или, снова используя обозначения уравнения (6.19), (Р— ыХ)х +г — — Я1 — ы)Р+ыП)х +ыб, или х ег = (Р— ыЬ) ((1 — ы)Р + ыУ)х + ы(Р— ыЬ) Ь = (1 — ыЬ) ~((1 — ы)1+ыУ)х +ы(1 — ы1) гР ''о : — Лзощ )х. +овощ 1 (6.21) В зависимости от значения ы, будем различать три случая: ы = 1 соответствует методу Гаусса — Зейделя, при ы ( 1 говорят о нижней релаксации, а при ы > 1 — о верхней релаксации.

Несколько упрощенный аргумент в пользу верхней релаксации состоит в следующем: если направление от х к х ь1 удачно в смысле продвижения к точному решению, то имеет смысл пройти по нему в ы(> 1) раз больший путь. В следующих двух разделах мы покажем, как выбрать оптимальное ы для модельной задачи.

Эта оптимальность опирается на использование красно- черного упорядочения. Алгоритм 6.6. Шаз метода ЯОВ(ы) для двумерного уравнения Пуассона при шахматном упорядочении: для всех белых узлов г, у (®) ит<-гдд (1 Ы)итзд+ ы(опь, г + о;+ц. +о Л 1+о цу+г + Ь Д.)/4 г епд /ог для всех черпых узлов г,у (ОВ) ите-ццу (1 ы)втяд+ Ы(ит-~ад-цд + От-~-1Л-Ь!О + От-~-1,Ц-1+ Отч-цЦ+1 + 1~ Л,)/4 г епд /от 298 Глава 6. Итерационные методы дли линейных систем 6.5.4.

Сходимость методов Якоби, Гаусса — Зейделя и ЗОН(ш) для модельной задачи Скорость сходимости метода Якоби для модельной задачи определить легко. Соответствующее расщепление имеет вид Тн„н = 41 — (41 — Тн„м), поэтому Из = (41) '(41 — Ти„и) = 1 — Ти„гг/4. Таким образом, собственными значениями матрицы И,р являются числа 1 — Л; ./4, где Л;,, — собственные значения матрицы Тн„иг я1 Л, =Л;+Л =4 — 2 соя +соя 1гг + 1 М + 1/ Наибольшее из чисел ~1 — Л; /4~ есть р(В,р), а именно, я р(В,т) = )1 — Лцд/4) = (1 — Ли,и/4( = соя - 1— г"г' + 1 2(У + 1) Я Заметим, что по мере роста М и ухудшения обусловленности Т спектральный радиус р(Вз) приближается к 1.

Поскольку на каждом шаге погрешность умножается на спектральный радиус, сходимость метода замедляется. Чтобы более точно оценить скорость сходимости, вычислим число т итераций Якоби, необходимых для уменьшения погрешности в е раз. Число т г должно удовлетворять условию (р(Вз))'" = е ~, или (1 — -(,г,—,)т)™ = е 2(м-~-ыг или гп - -~ — — О(Мз) = 0(п). Таким образом, число итераций пропорционально числу неизвестных. Поскольку на одном шаге метода требуется О(1) операций для перевычисления одной компоненты решения и 0(п) операций для перевычисления всех компонент, стоимость снижения погрешности в е раз (или в любое постоянное число раз, большее единицы) составляет О(пв).

Это объясняет элемент табл. 6.1, соответствующий методу Якоби. Отмеченная зависимость имеет общий характер: чем хуже обусловлена исходная задача, тем медленнее сходится большинство итерационных методов. Важными исключениями нз этого правила являются многосеточный метод и метод декомпозиции области; мы обсудим их позже. В следующем разделе мы покажем, что р(Воя) = р(Вз)Я = сояз —,', при условии, что переменные в уравнении Пуассона пронумерованы в соответствии с шахматным упорядочением (см. алгоритм 6.4 и следствие 6.1).

Иначе говоря, уменьшение погрешности на одном шаге метода Гаусса — Зейделя равно уменьшению на двух шагах метода Якоби. Это соотношение является общим для матриц, возникающих при аппроксимации дифференциальных уравнений посредством некоторых конечно-разностных схем. Оно также объясняет элемент табл. 6.1, относящийся к методу Гаусса — Зейделя: поскольку этот метод лишь вдвое быстрее метода Якоби, он имеет ту же сложность в смысле символа 0( ). При том же самом шахматном порядке пересчета мы покажем (см. алгоритм 6.6 и теорему 6.7), что при значении параметра релаксации 1 < аг = 2/(1+ гйп,е, ) < 2 справедливы соотношения соз ~+„2я 2 е РФяон( )) = .

+,„1 — для больших М. (1+ я1п — ',)я М+ 1 299 б.б. Основные итерационные методы Они контрастируют с равенством р(В) = 1 — О( — ~т) для матриц Вг и Воз. Указанное значение ы оптимально, т. е. оно минимизирует р(Вз<цц ~). При таком выборе ы метод ЗОВ(ы) приблизительно в 1»' раз быстрее, чем методы Якоби и Гаусса — Зейделя. Действительно, если у шагов ЗОВ.(ы) уменьшают погрешность в такой же мере, как й шагов методов Якоби и Гаусса — Зейделя, то (1 — ф)" — (1 — й)', откуда следует, что 1 — + 1 — -~-, илн й — у«У. Это снижает сложность метода ВОЩы) с 0(пг) до 0(из7г), как и показано в табл.

6.1. В следующем разделе для некоторых конечно-разностных матриц будет указан общий метод выбора значения ы, минимизирующего р(Взощ )). 6.5.5. Волее подробно о критериях сходимости методов Якоби, Гаусса — Зейделя и БОК(ог) Мы дадим ряд критериев, гарантирующих сходимость названных методов.

Первый критерий прост для проверки, но не всегда применим; в частности, он не применим к модельной задаче. Затем мы укажем несколько более сложных критериев, накладывающих более сильные условия на матрицу А, но зато дающих больше информации о сходимости. Эти более сложные критерии «скроены по мерке» матриц, возникающих при дискретизации некоторых дифференциальных уравнений с частными производными, таких, как уравнение Пуассона. Приведем сводку результатов данного раздела: 1.

Если А — матрица со строгим диагональным преобладанием по строкам (см. определение 6.6), то методы Якоби и Гаусса — Зейделя сходятся, причем второй метод сходится быстрее (теорема 6.2). Строгое диагональное преобладание по строкам означает, что модуль каждого диагонального элемента в А больше суммы модулей прочих элементов той же строки. 2. Указанный результат не приложим к нашей модельной задаче, поскольку в ней строгое диагональное преобладание не имеет места. Поэтому мы предполагаем более слабую форму диагонального преобладания (определение 6.11), но накладываем условие, называемое неразложимосгнью, на характер расположения ненулевых элементов в А (определение 6.7), что позволяет нам доказать сходимость методов Якоби и Гаусса — Зейденя.

Второй метод снова сходится быстрее (теорема 6.3). Этот результат применим к модельной задаче. 3. В случае метода ВОЩЕ) мы показываем, что неравенство 0 < и < 2 необходимо для сходимости (теорема 6.4). Если, к тому же, А — положительно определенная матрица (что имеет место в модельной задаче), то неравенство 0 < ы < 2 и достаточно для сходимости (теорема 6.5).

4. Чтобы дать количественное сравнение методов Якоби, Гаусса — Зейделя и ВОЩЕ), сделаем еще одно предположение о позициях ненулевых элементов в А. Соответствующее свойство называется свойством А (определение 6.12) и равносильно требованию, чтобы граф матрицы был деудольным. По существу, свойство А означает, что переменные можно пересчитывать, пользуясь красно-черным упорядочением. При наличии свойства А справедлива простая алгебраическая формула, связывающая собственные значения матриц Вт, Вс«з и Взощ > (теорема 6.6); это позволяет нам срав- зоо Глава 6. Итерационные методы для линейных систем нить скорости сходимости методов. Эта формула также дает возможность вычислить оптимальное ы, обеспечивающее наиболее быструю сходимость метода ЗОВ(ы) (теорема 6.7).

Определение 6.6. Матрица А имеет строгое диагональное преобладание по строкам, если ~аи~ ) 2 ~1~а;,~ для всех«. Теорема 6.2. Для матрицы А со стпрогим диагональным преобладанием по строкам методы Якоби и Гаусса — Зейделл сходятпся. При э«лом ЛВоээь» < ((Вэ)~ < 1. Доказательство. Снова используя обозначения уравнения (6.19), запишем Вэ = 1+ 0 и Впэ = (1 — Ь) 1У. Мы хотим доказать, что 'ОВоэО„= ()(Воз)ей, < )((Вэ(е(! = 'ОВэ() (6.22) где е = (1,... 1]т — вектор, состоящий из единиц.

Неравенство (6.22) заведомо будет верно, если мы сможем доказать более сильное покомпонентное неравенство /(Š— Е) 1Ц е = ~Впэ~ е < ~Вэ~ е = (Щ+ /Ц) е. (6.23) Так как )(1 — Е) 'Ц.е < )(1 — Е) (.)Ц. е и — 1 Ь1 (Ц.е '=о ь-1 < ~ ~Щ' )Ц е 1=0 =(1 — Щ) )Ц е по неравенству треугольника поскольку Гп = О по неравенству треугольника поскольку Щ" = О, то неравенство (6.23) будет выполняться, если мы сумеем установить еще более сильное покомпонентное неравенство (1 — Щ) .

(Ц е < (Щ+ (Ц) е. (6.24) Все элементы матрицы (1 — Щ) 1 = 2 ,'",: Щ' неотрицательны, поэтому нера- венство (6.24) будет справедливо, если мы докажем, что (Ц е<(1 — Щ) (Щ+)Ц).е=(Щ+)Ц вЂ” ٠— Щ )Ц) ° е, О < (٠— Щг — Щ Щ) е = Щ. (1 — ٠— !Ц) е. или (6.25) Неравенство !)Воз)(, < !)Вэ(! означает, что в задаче, наихудшей для метода Гаусса — Зейделя, погрешность снижается за один шаг не меньше, чем в задаче, наихудшей для метода Якоби.

Оно не гарантирует, что для любой конкретной системы Ах = б метод Гаусса — Зейделя сходится быстрее метода Якоби; «случайно» может оказаться, что на каком-то шаге ошибка в методе Якоби меньше. 201 6.5. Основные итерационные методы В силу неотрицательности элементов матрицы Д, неравенство 16.25) будет верно, если доказать, что 0 < (1 — Д вЂ” (Ц) е, илн (Вз) е = Щ+ (Ц)е < е. (6.26) Наконец, неравенство (6.26) верно, так как, по предположению, !))Вз) е() РЛ =р<1. П Аналогичный результат справедлив, если А имеет строгое диагональное преобладание по столбцам (т. е.

Ат имеет строгое диагональное преобладание по строкам). Читатель легко проверит, что этот простой критерий не приложим к модельной задаче. Поэтому нам придется ослабить предположение о строгом диагональном преобладании. Для этого потребуется учесть теоретико-графовые свойства матрицы. Определение 6.7. Матрица А называется неразложимой, если не суще- ствует матрицы-перестановки Р, такой, что РАрт и гг Мы вскоре увидим, как это определение связано с теорией графов. Определение 6.8. Ориентированный граф представляет собой конечное множество узлов, соединенных конечным числом ориентированных ребер, т. е. стрелок, ведущих из одного узла в другой. Путь в ориентированном графе — зто последовательность узлов пг,...,п вместе с ребрами, направленными из каждого и; в п;+ы Петлей н зывается ребро, ведущее из данного узла к нему самому.