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

Обсуждение этих методов можно найти и в ХЕТЫВ/Сещр1а1ез; там же даны их реализации. По заданному хо каждый из названных методов генерирует последовательность (х ), сходящуюся к решению А 'б системы Ах = б; при этом вектор х +1 несложно вычисляется по вектору х Определение 6.3.

Расщеплением матрицы А называется всякое представ- ление вида А = М вЂ” К, где матрица М невырожденнв. Всякое расщепление порождает итерационный метод следующим образом: из равенства Ах = Мх — Кх = б находим Мх = Кх+ Ь, или х = М гХх+ М ~о э— з Вх+с. Полагая хю+1 — — Вх +с, приходим к искомому итерационному методу. Определим условия его сходимости. Лемма 6.4. Пусть )) () — произвольная операторная норма ~т. е. йВИ' = гпахгйо ~~ф). Если Щ! < 1, то метод х„,+1 = Вх, + с сходится при любом хо Доказательство.

Вычитая равенство х = Вх+ с из х +г = Вхт+ с, получаем х .~1 — х = В(х — х). Отсюда ()х .ьд — х(( < ))В()((х — х!) < )Щ +')(хо — х)(. Правая часть сходится к нулю, так как !)Щ < 1. П Наш окончательный критерий сходимости опирается на приводимое ниже свойство матрицы В. Определение 6.4. Спектральным радиусом матрицы В называется число р(В) = шах)А~, где максимум берется по всем собственным значениям А втой матрицы.

293 6.5. Основные итерационные методы Лемма 6.5. Для любой операторной нормы справедливо неравенство р(В) < ЦВЦ. Для любой матрицы В и любого числа е > 0 найдется операторная норма Ц ° Цю такая, что ЦВЦ„< р(В) +е. Норма Ц Ц,„зависит от В и ». Доказательство. Покажем, что р(В) < ЦВЦ, какова бы ни была операторная норма. Пусть х — собственный вектор для числа Л, такого, что р(В) = Л; тогда ЦВЦ = тахгио )~ф > Я = Я = (Л! Построим теперь операторную норму Ц Цю такую, что ЦВЦ, < р(В) + е.

Пусть матрица Я 'ВЯ =,У имеет жорданову форму. Положим .Р, сйак(1, е, ег,..., е" ') . Тогда (т,)-'В(ВР,) = Р,-'т, Это «жорданова форма» с числом е над главной диагональю. Теперь с помощью векторной нормы ЦхЦ„= Ц(ЯР,) 'хЦ построим операторную норму ЦВхЦ* ЦВЦ„, = тах * Ц(ВР,)-'ВхЦ.

*Фо Ц(ЯР,) 'хЦ , ЦФР) 'ВФР.)рЦ ~~о ЦуЦ = ЦФР«) 'ВФР.)Ц < тах/Л,/+е = р(В) + е. П Теорема 6.1. Итерационный процесс х„,+1 —— Вх,„+ с тогда и только тогда сходится к решению системы Ах = о, каков бы ни был начальный вектор хо, когда р(В) < 1. Доказательство. При р(В) > 1 выберем хв так, чтобы хо — х был собственным вектором матрицы В для собственного значения Л, где )Л) = р(В). Тогда (х +1 х) — В(х х) ='''=В ~ (хо х) =Л +1(хо х), Глава б.

Итерационные методы для линейных систем и эта последовательность не сходится к нулю. При р(В) < 1 нужно, опираясь на лемму 6.5, выбрать операторную норму так, чтобы выполнялось неравенство )Щ„< 1, а затем применить лемму 6А, устанавливающую сходимость метода. П Определение 6.5. Скоростью сходимости процесса х +г = Вх + с наэыеаетсл число г(В) = — 1ойш р(В). ПосколькУ 1ойш ((х — х)(, — 1окго ~(х л — х)~„> г(В) + 0(е), то г(В) имеет смысл приращения числа верных десятичных знаков в приближенном решении за одну итерацию.

Чем меньше р(В), тем выше скорость сходимости, т. е. тем больше число верных десятичных знаков, вычисляемых за итерацию. Теперь нашей целью будет выбор расщепления А = М вЂ” К, удовлетворяющего следующим условиям: 1. произведения Вх = М "Кх и с = М 'б должны легко вычисляться; 2. число р(В) мало. Эти конфликтующие условия нужно сбалансировать. Например, выбор М = 1 хорош для установки 1), однако условие р(В) < 1 может в этом случае не быть выполнено. С другой стороны, выбор М = А и К = 0 хорош для установки 2), но, скорей всего, плох для 1). Разбиения для методов, обсуждаемых в данном разделе, используют следующие общие обозначения: если А не имеет нулевых диагональных элементов, то пишем А=Р— Х вЂ” О=Р(1 — Х вЂ” ХХ), (6.19) где Р— диагональ матрицы А, матрица — Х есть нижняя строго треугольная часть в А, причем РХ, = Х, а — О есть верхняя строго треугольная часть в А и РХХ = О.

6.5.1. Метод Якоби Метод Якоби можно описать как циклический обход уравнений с изменением текущей переменной г так, чтобы гзе уравнение удовлетворялось точно. В обозначениях уравнения (6.19), расщепление для метода Якоби можно представить как А = Р— (Х + О). Полагая Вг = Р '(1 + О) = Ь+ ХХ и ст = Р 'б, можем описать шаг метода формулой х +~ — — Втх +от. Чтобы убедиться, что эта формула соответствует нашему первому описанию метода, заметим, что из нее следует Рх +~ — — (Х+ О)х +Ь, или аИх +~ — — — Х „а яхт в+ 5, или аях +~ +~ ь .а эх ь=б.. Алгоритм 6.1.

Шаг метода Якоби: Хогг'=1 акоп Хт-Ы 1 = —,(бд ~ Ьг. адххт,г) епд Хог В специальном случае модельной задачи реализация алгоритма Якоби упрощается. Будем работать непосредственно с уравнением (6.10) и обозначать 295 6.5. Основные итерационные методы через н 1 значение решения в сеточном узле е,у на шаге тп. Тогда, 1чсание метода Якоби принимает следующий вид: Алгоритм 6.2. Шаг я«енгода Якоби для двумерного уравнения Пуассона: 1ог 1 = 1 1о Ю ~от ~ = 1 ео Ат о т11 =(о; 1д+н оь1 +и 1 1+о «г~ь1+Ь ~«1)/4 г епд 1аг епд 1ог Иными словами, на каждом шаге новое значение и,, получается «усреднениеме значений соседних компонент и числа 6~11 .

Отметим, что все новые значения н +1; могут вычисляться независимо друг от друга. Действительно, алгоритм 6.2 можно записать одной строкой Ма11аЪ'а, если и «.1,;, хранятся в квадратном массиве Р, содержащем дополнительные первую и последнюю строки и первый и последний столбцы, заполненные нулями (см.

вопрос 6.6). 6.5.2. Метод Гаусса — Зейделя Мотивация этого метода такова: поскольку на гчм шаге цикла в методе Якоби имеются уточненные значения первых 1 — 1 компонент решения, их можно использовать при суммировании. Алгоритм 6.3. Шаг метода Гаусса — Зейделя: ~ог1=1 гоп 1 — 1 — агйх +1,й й=1 агйх Е й=д+1 1 ет«11 е перееычеееенные е етерые е епд 1ог Для целей последующего анализа мы хотим записать этот алгоритм в ви- ДЕ Хы«1 = ВаЗХ«е + СПЗ. ДЛЯ ЭТОГО ЗаМЕтИМ, Чта ФОРМУЛУ аЛГОРИтМа МОЖНО переписать как 1 1« а;йх „., й — — — ~~1 а.йх в+Ь .

(6.20) й=1 й =у+ 1 Теперь, используя обозначения уравнения (6.19), перепишем (6.20) как (Р— Р)Х Э1 = УХы + Ь, ИЛИ х + — — (Р— Х) Ох +(Р— Е) 'Ь вЂ” (г г) 1Пх + (г г) 1р 1Ь = Все.ех + сстз. Как и в случае метода Якоби, обсудим, как следует реализовать метод Гаусса — Зейделя для нашей модельной задачи. В принципе, реализация очень похожа с тем исключением, что нужно следить, какие переменные приобрели новые значения (им соответствует индекс гп + 1), а какие сохранили прежние значения (они помечены индексом т).

Однако, в зависимости от принятого 296 Глава 6. Итерационные методы для линейных систем порядка обхода сеточных узлов «',у, будут получаться различные (и одинаково законные) реализации метода Гаусса — Зейделя. Не так в методе Якоби, где порядок перевычисления переменных не существенен. Например, если вначале (прежде всех прочих и,азу) перевычисляется значение о а ы то все соседние значения по необходимости старые. Но если переменная и 11 перевычисляется последней, то все соседние значения необходимо новые, поэтому для и будет получено иное (чем в методе Якоби) значение.

В действительности, возможны столько реализаций метода Гаусса — Зейделя, сколько существует способов упорядочить ааат переменных (а именно, Хт!). Два из этих упорядочений представляют особый интерес. Первое из них — это упорядочение, показанное на рис. 6.4; оно называется естнестпвенным упорядочением.

Второе упорядочение называется шахматным (или черно-белым). Его важность для нас состоит в том, что наиболее сильные результаты о сходимости, устанавливаемые в равд. 6.5.4 и 6.5.5, опираются на это упорядочение. Чтобы описать его, рассмотрим «шахматное» раскрашивание сеточных переменных, показанное на рисунке: узлы, помеченные символом ®, соответствуют черным квадратам шахматной доски, а узлы, помеченные символом ®, соответствуют белым квадратам.

При шахматном упорядочении белые узлы нумеруются прежде, чем черные. Заметим, что смежны с каждым белым узлом лишь черные узлы. Поэтому, если вначале перевычисляются компоненты из белых узлов, используются только старые значения из черных узлов. Затем, когда перевычисляются компоненты из черных узлов, которые смежны лишь с белыми узлами, будут использоваться лишь новые значения из этих белых узлов. В результате алгоритм принимает следующий вид.

Алгоритм 6.4. Шаг метпода Гаусса — Зейделя для двумерного уравнения Пуассона при красно-черном упорядочении: для всех белых узлов «, у' (Ю) ите-цад = ~от,а — Пу + ит,аэ-цд + ит,а 4-1 + аат,авж» + Л а«ау)/4 2 епд /ог для всех черных узлов а, з (®) ит.~-пад = (от+па-цу + отец««-Ку + иапэ-ца,у — 1 + иапч-ца,усю + 5 УИ)/4 епд /ог 297 6.5. Основные итерационные методы 6.5.3. Последовательная верхняя релаксация Этот метод будем обозначать через ЗОВ(ы), где ы — параметр релаксации.