В.А. Ильин, Э.Г. Позняк - Линейная алгебра (6-е издание) (1113061), страница 36
Текст из файла (страница 36)
2'. Пусть теперь при р < 1 выполнены условия Самарского (6.21). докажем справедливость неравенства ()уь)(н < рь!)Ло()в. Положим Ль = р" $'ь. То~да, очевидно, Х„., — Кь = р""1гь„— р"~„= р""(1„! — 1„) — (! — р)р"1ь. Подставляя эти значения 7ь и 7ьт! — 7ь в равенство (6.15) и производя сокращение на р", получим для величин 1гь следующее соотношение: (6.22) т в котором В = рВ, А = А — — — В. ! — р т В силу условий (6.21) операторы В и А удовлетворяют условиям тА ) О, 2В > ТА. Из этих условий и из того, что уравнение (6.22) для 1Хь совершенно идентично уравнению (6.15) для Яь, в силу первого шага длЯ аз вытекает следУющаЯ оценка: (В\газ.!, 'Рь.ь!) < (В1ь, 1гь).
Из этой оценки в свою очередь, учитывая, что В = рВ, получим неравенство (В1гь,!, 1Гьь!) < ( В1гь, 1гь). Последовательное применение указанного неравенства для номеров к = О, 1, ... приводит нас к соотношению (В1Хь, 1гь) < (Вгш Цо), 164 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ ) гл. 6 а умножение последнего соотношения на ра" приводит к окончательной оценке ') (Вюю Яь) < йдь(ВХо, юо). Тем самым неравенство ~~Яь~~и < < р" ~~Яо~~в доказано. Доказательство теоремы 6.3 завершено.
В заключение применим теорему Самарского 6.3 для выяснения вопроса о выборе такого значения параметра т, при котором скорость сходимости является максимальной. Из доказанной в теореме 6.3 оценки ЕЯьян < р ~~2ояв вытекает, что эта задача сводится к нахождению такого значения т, при котором достигается минимальное значение функции р = р(т). Так как обе матрипы А и В симметричны и положительно определены, то существуют положительные постоянные Т1 и Тя такие, что справедливы неравенства у~В < А < .ТаВ. Будем считать, что постоянные т1 и тз в этих неравенствах нам заданы ). Сопоставляя только что написанные неравенства с условиями (6.21), мы получим, что минимальное значение р достигается при условии (! — р)!т = Ти (1+ р) (т = Тю откуда получаем оптимальное значение т = 2Ччч + Тз) и минимальное значение р, равное (Тя — Т1)г(Тя+Т1).
Частным случаем проведенного нами рассмотрения является явный метод простой итерации, изученный в п. 1. Для этого метода справедливы все полученные нами результаты. В следующих трех пунктах с помощью общего неявного метода простой итерации и теоремы Самарского 6.2 мы рассмотрим несколько наиболее употребительных итерационных методов и установим условия их сходимости. 3. Модифицированный метод простой итерации. Этот метод получается из общего неявного метода простой итерации в том случае, когда стационарный параметр т равен единице, а матрица В представляет собой диагональную матрицу Р, состоящую из элементов матрицы А, лежащих на главной диагонали, т.е.
В = Р, где аи О ... О О азз ... О (6.23) О О ... а„„ При этом, конечно, предполагается, что матрица А является симметричной и что все ее диагональные элементы аи, азю ...,а„„ являются положительными (последнее требование необходимо и достаточно для положительной определенности диагональной матрицы В = Р).
Из теоремы 6.2 сразу же вытекает, что для сходимости модифицированного метода простой итерации при любом выборе нуле- ') Мы учитываем, что Яь =' рьИИ Уэ =- Ъщ ) Постоянные Т~ и Т естественно назвать константами экзиеалеиглности матриц А и В. Для коммутирующих матриц А и В постоянные гп и Тз соответственно равны наименьшему и наибольшему собственным значениям задачи АХ = ЛВХ.
!65 МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ ного приближения достаточно, чтобы были выполнены два условия: 2Р>А,А>0. Теорема 6.1 позволяет выразить достаточное условие сходимости модифицированного метода простой итерации и в другой форме '): )(Š— Р 'Ай < 1 (6.24) (под нормой матрицы, как и выше, понимается операторная норма). Так как йŠ— Р !А)! = ))Р"!(Р— А))! = 'йР '(А — Р)й, то достаточное условие сходимости (6.24) можно переписать в эквивалентном виде 'йР !(А — Р)й < 1.
(6.25) Неравенство (6.25) позволяет получить различные достаточные условия сходимости модифицированного метода простой итерации. Прежде всего заметим, что если наряду с операторной нормой матрицы (6.2), которую мы, как н выше, будем обозначать символом ~~Ай, ввести так называемую сферическую норму этой матрицы, обозначаемую символом йАй,ф и определяемую равенством йАй,ф = и и 1!Л = [ 2 2' пз.~, то, как доказано в а4 гл.4 (см. формулу (4.28)), для з=!з=! любого вектора Х пространства Е" будет справедливо неравенство а) 'йАХ(! < йА)(,фйХ(!.
(6.26) Из (6.26) и (6.5) сразу же вытекает, что операторная и сферическая нормы матрицы связаны соотношением !!А~~ < ~(А~( ф. Таким образом, в силу (6.25) достаточное условие сходимости модифицированного метода простой итерации выражается неравенством ~~Р '(А — Рн,ф < 1, которое в развернутой записи имеет вид и, !!а! < 1. з=!1=! Заметим далее, что при определении операторной нормы (6.5) матрицы А мы исходили из обычной (так называемой сферической) нормы л! г " ! !!з вектора Х = ..., равной )~Х~( = ~ 2 ' ю~~ Ж з=! Часто вводят еще две нормы вектора Х: так называемую кубическую норму, определяемую равенством ~(Х~(, я = птах ~аз~, и так на!<!<и ') Мы учитываем, что в рассматриваемом случае вместо матрицы А следует взять матрицу А, определяемую формулой А =- В А н положить В = В, т =- 1 х! я -) В этом неравенстве под нормой вектора Х = ...
, 'понимается так м называемая сферическая норма !!Х!! = [2 л,~ =1 166 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ (гл. 6 и и !!А!!к в = п1ах 2 )а1.(, ()А)),к„= п1ах '! (а1!!. Дословное повторение проведенных выше рассуждений с заменой сферических норм соответственно кубическими и октаэдрическими приведет нас к достаточному условию сходимости модифицированного метода простой итерации, выраженному соотношением (6.25), в котором под нормой матрицы следует понимать соответственно ее кубическую или октаэдрическую операторные нормы.
Это приводит нас к следующим двум условиям, каждое из которых является достаточным для сходимости модифицированного метода простой итерации и < 1 (для1=1,2,..., и); аи У=1, Уф1 — < 1 (для 7' = 1, 2, ..., п). 1=1, 1~У 4. Метод Зейделя. Представим симметричную матрицу (6.2) в виде суммы трех матриц А = В + Л+ (7, где Π— диагональная матрица (6.23), а Л и (7 соответственно стра~о левая и строго правая матрицы, имеющие вид О О ...
О аз1 О ... О О а~ ... а~ О О ... аги О О ... О а„1 а ... О и удовлетворяющие условию! ' = (7. Метод Зейделя получается из общего неявного метода простой итерации в том частном случае, когда стационарный параметр т равен ') См., например. Крылов В.И., Бобков В.В., 7Нонастырный П.И. Вьшислительные методы высшей математики. — Минск; Вышэйшая школа, 1972. Т.1. С.!11-112. зываемую октаэдрическую норму, определяемую равенством !!Х!1„, = и ~!х1~. Если в определении (6.5) операторной нормы матрицы А 1=1 понимать под нормой вектора соответственно его кубическую или октаэдрическую норму, то соотношение (6.5) приведет нас к определению соответственно кубической и октаэдрической операторньгх норм матрицы А.
Можно доказать, что кубическая и октаэдрическая операторные нормы матрицы (6.2) следующим образом выражаются через элементы этой матрицы ') . !67 МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ единице, а матрица 8 равна сумме Р + 1. Таким образом, последова- тельные итерации в методе Зейделя определяются соотношением (В+ 1.)(Хьч! — Хь) + АХь = с. Докажем, что метод Зейделя сходится для любой симметричной и положительно определенной матрицы А. В силу теоремы 6.2 достаточно доказать, что для любой такой матрицы А выполнено условие (6.27) 2(Р+ Л) > А.
Для доказательства (6.27) заметим, что для любого вектора Х (2(Р + 1.)Х, Х) = (ВХ, Х) + (ВХ, Х) + ( 1.Х, Х) + (1 Х, Х) = = (РХ, Х) + (РХ, Х) + (ЬХ, Х) + (Х, 17Х) = = (ВХ, Х) + (АХ, Х). Таким образом, для доказательства неравенства (6.27) достаточно убедиться в положительной определенности матрицы В, но она сразу вытекает из того, что у положительно определенной и симметричной матрицы А все элементы, лежащие на главной диагонали, являются положительными ') . Сходимость метода Зейделя доказана. 5. Метод верхней релаксации.
Этот метод получается из общего неявного метода простой итерации в том частном случае, когда т = .= ы, В = Р+ ыЬ, а параметр ьа выбран так, чтобы являлось наименьшим наибольшее по модулю собственное значение матрицы су— ы(В+ шй) 'А, осуществляющей переход от ь-й итерации к (1с+ 1)-й. Докажем, что если матрица А является симметричной и положительно определенной, то для сходимости метода верхней релаксации достаточно, чтобы было вьтолнено условие О < ы < 2.
В силу теоремь! 6.2 для сходимости достаточно выполнение условий ш > О, 2(В + ый) > ыА. Второе из этих условий для любого вектора Х приводит к неравенству (2(Р+ ы1)Х, Х) > (ыАХ, Х). (6.28) Последнее неравенство эквивалентно каждому из неравенств в следу- ющей цепочке: (2РХ, Х) + (ыТ,Х, Х) + (ыЬХ, Х) > (ыАХ, Х), (2 — ы)(РХ, Х) + (ыРХ, Х) + (ы1 Х, Х) + (Х, ы1/Х) > (ыАХ, Х), (2 — ы)(ВХ, Х) > О. ') Достаточно заметить, что если у вектора Х и-я координата равна единице, а все остальные нулю, то (АХ, Х) = аьь > О. 168 итерационные метОды Решения линеиных систем (гл. 6 Из последнего неравенства и из положительной определенности Р заключаем, что (6.28) справедливо при 2 — ш ) О, т. е.
при ш < 2. Итак, доказано, что условия О < ш < 2 обеспечивают сходимость метода верхней релаксации. 6. Случай несимметричной матрицы А. В случае несимметричной матрицы А мы можем умножить матричное уравнение (6.1) слева на матрицу А' и заменить уравнение (6.1) уравнением АХ = г', в котором Р = А'Р', А = А'А, так что матрица А является симметричной и (как легко убедиться) положительно определенной. 7. Итерационный метод П.Л. Чебышева ').
Всюду выше при рассмотрении общего неявного метода простой итерации мы предполагали, что итерационный параметр т принимает одно и то же постоянное значение. Естественно возникает идея рассмотреть более общий случай, когда в указанном методе значения итерационного параметра зависят от номера и итерации. В таком случае последовательность итераций будет определяться не соотношением (6.13) ВХ" ' Х'+АХ = Тг т а более общим соотношением Вх -! — Ха+АХ, В твч! При этом, как и выше,  — некоторая легко обратимая квадратная матрица порядка и.
При таком выборе итерационной последовательности для погрешности Ув = Хь — Х итерационной схемы получится соотношение Я. — Я В вкы +АУЕ=О. ть., ! Предположим, что обе матрицы А и В симметричны и положительно определенны. Тогда, как уже отмечалось выше, найдутся положительные постоянные у! и уз такие, что Т!В < А < ТЕВ. Будем считать, что эти постоянные т! и та нам заданы и еще раз напомним, что эти постоянные равны соответственно наименьшему и наибольшему собственным значениям задачи АХ = ЛВХ. Оценим энергетическую норму погрешности 8 Уь 8 в. Напомним еще раз, что для симметричной и положительно определенной матрицы В существует симметричная и положительно определенная матрица ВПЕ такая, что ВПа ВПЕ = В. Как и выше, договоримся обозначать символом В е~в матрицу, обратную к матрице В!Уз. Для оценки нормы погрешности Уь сделаем замену, положив 2ь = = В Па)гь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
