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

Определение 6.9. Ориентированный граф 0(А) матрицы А — зто граф с уз- лами 1, 2,..., и, где из узла 1 в узел у ведет ребро в том и только том случае, если ай ф О. Пример 6.1. Матрица имеет направленный граф Определение 6.10. Ориентированный граф сильно связен, если в нем существует путь, ведущий из любого узла г' в любой узел 11 Сильно связной компонентой ориентированного графа называется подграф (т. е. подмножество узлов вместе с соединяющими их ребрами), который сильно связен, но не может быть вложен в больший сильно связный подграф.

А= [ 2 — 1 — 1 2 — 1 — 1 2 — 1 ~ — 1 2 302 Глава б. Итерационные методы для линейных систем Пример 6.2. Граф примера 6.1 сильно связен. Пример 6.3. Матрица имеет ориентированный граф Поскольку в этом графе нет пути из произвольного узла в узел 1, он не является сильно связным. Узлы 4,5 и 6 образуют сильно связную компоненту, так как для любого из них существует путь, ведущий в любой другой узел. О Пример 6.4.

Граф модельной задачи сильно связен. По существу, этот граф имеет вид с той оговоркой, что каждое ребро сетки представляет два ребра графа (по одному в каждом направлении); кроме того, не показаны петли. О Лемма 6.6. Длл того чтобы матрица А была неразложима, необходимо и достаточно, чгпобы граф 0(А) был сильно свлзен. Доказательство. Если А = ~ 1 — разложимая матрица, то, очевид- ~ Аы А1г 22 но, не существует способа достичь узлов, соответствующих блоку Аы, из узлов, соответствующих Агг, т.

е. граф С(А) не будет сильно связен. Точно так же, если 0(А) не является сильно связным графом, перенумеруем строки (и столбцы) матрицы так, чтобы первые номера приобрели узлы некоторой сильно связной компоненты. Тогда матрица РАРт приобретет верхний блочнотреугольный вид. П Пример 6.5. Матрица А примера 6.3 разложима, О Определение 6.11. Матрица А имеет слабое диагональное преобладание по строкам, если (аи) > ~ г~г ~ась~ длл всех 1 и хотя бы длл одного 1 имеет место строгое неравенство. зоз 6.5. Основные итерационные методы Теорема 6.3.

Пусть матрица А неразложима и имеет слабое диагональное преобладание по строкам. Тогда методы Якоби и Гаусса — Зейделя сходятся, причем р(Впз) < р(Вз) < 1. Доказательство этой теоремы см. в [249]. Пример 6.6. Матрица модельной задачи имеет слабое диагональное преобладание и неразложима, но не имеет сильного диагонального преобладания. (Диагональные элементы равны 4, а суммы модулей внедиагональных элементов равны 2, 3 либо 4.) Таким образом, методы Якоби и Гаусса — Зейделя сходятся для модельной задачи. О Хотя факты, приведенные выше, показывают, что при определенных условиях метод Гаусса — Зейделя быстрее метода Якоби, в общем случае такой результат не верен. Существуют несимметричные матрицы, для которых метод Якоби сходится, а метод Гаусса — Зейделя расходится, а также матрицы,,аля которых сходится метод Гаусса — Зейделя, но расходится метод Якоби [249].

Исследуем теперь сходимость метода ЗОВ(аз) [249]. Напомним определение метода: Взоя( ) = (1 — ыЕГ ((1 — ы)1+ОП). Теорема 6.4. Имеет место неравенство р(Взощ >) > ]ы — 1]. Поэтому не- равенство О < ы < 2 необходимо для сходимости метода. Доказательство. Запишем характеристический многочлен матрицы Взощ„~ в виде у(Л) = с1ес(Л1 — Взощ 1) = бес((1 — ыЬ)(Л1 — Взояь,,1)) = бег((Л + ив 1)1 — ыЛЬ вЂ” ыП); тогда ~р(О) = ~ДЛг(Взоя~ 1) =~йесйы — 1)1) =+(ы 1)" г=1 откуда п1ах; ]Лг(Взощ„>)] > ]ы — 1]. 'Теорема 6.5. Если А — симметричная положительно определенн и матрица, то р(Взощ >) < 1 для всех О < ы < 2, поэтому метод ЗОЩез) сходитсл для всех О < ы < 2.

В частности, сходится метод Гаусса — Зейделя, для которого ы = 1. Доказательство. Примем сокращение Взоя(„> = В и, используя обозначения уравнения (6.19), положим М = ш 1(Р— ыХ). Проведем доказательство в два этапа: 1. определим матрицу сг = А г(2М вЂ” А) и покажем, что 91Лг(сг) > О для всех г; 2. покажем, что В = (сг — 1) (сг + 1) ', откуда будет следовать, что ]Л;(В)] < 1 для всех 1. Чтобы доказать 1), заметим, что с1х = Лх влечет за собой (2М вЂ” А)х = ЛАх, или х'(2М вЂ” А)х = Лх*Ах. Складывая последнее равенство с сопряженным к нему, получим х'(М + М' — А)х = ЯЛ(х'Ах). Отсюда ЯЛ = х*(М + М'— А)х/х*Ах = х'(~ — 1)Рх(х'Ах > О, поскольку матрицы А и (~ — 1)Р положительно определены. 304 Глава б. Итерационные методы для линейных систем Чтобы доказать 2), заметим, что (Π— 1ИО + 1) ' = (2А гМ вЂ” 21) (2А 'М) ' = 1 — М 'А = В.

По теореме о спектральном отображении (вопрос 4.5) ЦО) 1 Р1Л~О) 1)г + РЦО))г г/г Л®) + 1 (лЛ(О) + 1)'+ (ОЛ(О))г Вместе теоремы 6.4 и 6.5 означают, что для симметричной положительно определенной матрицы А метод ВОЯ(~) сходится тогда и только тогда, когда 0 < аг < 2. Пример 6.7. Матрица модельной задачи симметрична и положительно определена, поэтому ВОЩьг) сходится для 0 < ы < 2. О Для окончательного сравнения вычислительных затрат в методах Якоби, Гаусса — Зейделя и ВОЯ(ы) в применении к модельной задаче наложим на А еще одно теоретико-графовое условие, часто возникающее при дискретизации некоторых типов дифференциальных уравнений с частными производными, например уравнения Пуассона.

Это условие позволит нам вычислить р(Воз) и р(Взощ ~) как явные функции от р(Яз). Определение 6.12. Матрица Т имеет свойство А, если существует матрица-перестановка Р, такая, что РТРт 11 1г где Ты и Тгг — диагон льные матрицы. Другими словами, множество узлов графа С(А) может быть представлено как Я~ О ог, где, иск«ючая петли, нет ребер, соединяющих два узла из Яг либо два узла из ог, такой граф С(А) назе«вается двудольным. Пример 6.8. Шахматное упорядочение для модельной задачи.

Оно было введено в разд. 6.5.2 с помощью иллюстрируемого рисунком «шахматного» изображения графа модельной задачи: черные узлы, помеченные как О~, принадлежат подмножеству оы а белые, помеченные как ®, — подмножеству ог. Как было отмечено в разд. 6.5.2, каждое уравнение модельной задачи связывает значение в узле сетки со значениями в соседних узлах слева, справа, 305 6.5. Основные итерационные методы сверху и снизу, окрашенных иначе, чем центральный узел. Иначе говоря, узлы типа ® не связаны между собой непосредственно, как и узлы типа О. Поэтому, если вначале пронумеровать белые узлы, а затем черные, то матрица приобретет форму, требуемую определением 6.12.

Так, для сетки 3 х 3 получим следуюшую матрицу: Предположим теперь, что матрица Т имеет свойство А. Тогда (обозначая диагональные блоки Тн через Р;) можем записать РТрт Р1 Тгз Рз ΠΠΠ— Тш Определение 6.13. Положим Лз(а) = аЬ+ 1У. Тогда Лз(1) = Вз есть итерационная матрица метода Якоби. Предложение 6.2. Собственные значения матрицы Кз(а) не зависят от а.

Доказатиельство. Матрица имеет те же собственные значения, что и подобная ей матрица Определение 6.14. Для произвольной матрицы Т положим Т = Р— Х вЂ” П и Лз(а) = аР ~Х+ 1Р 10. Если собственные значения матрицы Кз(а) не зависят от а, то Т называют согласованно упорядоченной матарицей. 306 Глава б.

Итерационные методы для линейных систем Легко показать, что если Т имеет свойство А (как, например, в модельной задаче), то матрица РТРт будет согласованно упорядоченной для матрицы- перестановки Р, такой, что блоки Тм и Т22 в РТР = ~ 7, 7, суть диат ( 7ы Т12 21 22 тональные матрицы. Однако из свойства согласованной упорядоченности, вообще говоря, не следует, что матрица имеет свойство А. Пример 6.9.

Всякая блочно-трехдиагональная матрица .01 А1 В1 А„ В„1 17„ согласованно упорядочена, если блоки .0; являются диагональными матрицами. О При наличии согласованной упорядоченности справедливы простые формулы, связывающие собственные значения матриц В,1, Воз и Взощ„л [249]. Теорема 6.6. Пусть А — согласованно упорядоченная матрица и ш ~ О.

Тогда верны следующие утверждения: 1. собственные значения матрицы В,л расположены ~ парами; 2. если р — собственное значение матарицы В л и (Л + ш — 1)2 = Лшгрг, (6.27) то Л вЂ” собственное значение матрицы Взощ„11 3. обратно, если Л ~ О являеплся собственным значением матрицы Взощ р то число р, определяемое уравнением (б.з7), есть собственное значение матрицы Ву. Доказательство.