В.А. Ильин, Э.Г. Позняк - Линейная алгебра (1152751), страница 36
Текст из файла (страница 36)
з=!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ь = = В Па)гь. При такой замене соотношение для погрешности Яь переходит в следующее соотношение для Ра! )хме ! = ( Š— тач ! С) )ьн (й = О, 1, 2, ...), ') Пафнутий Львович Чебышев (1821-1894) — великий русский математик и механик. !69 МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ где через С обозначена матрица вида С = В 'гаАВ 'гз. Убедимся в том, что квадрат обычной нормы вектора 1ГЕ равен квадрату энергетической нормы вектора гзя. В самом деле, [[Ъ'~[[~ = (\ '~, Ъ'~) = (В'~~Я, В'~~7) = (ВЛЫ Я~) = [[У~[[~~. Таким образом, для оценки энергетической нормы ль достаточно оценить обычную норму Ую Оценим норму [[Уь[[.
Прежде всего заметим, что из неравенств у1(ВХ, Х) < (АХ, Х) < "Гз(ВХ, Х) с помощью замены Х = = В 'УЕУ получаются неравенства у|(У, У) < (СУ, У) < уз(У, У). Последние неравенства эквивалентны тому, что гп Е < С < уаЕ. Поскольку, кроме того, матрица С = В 'У АВ 'г~ симметрична, то все собственные значения этой матрицы вещественны и расположены на отрезке [тн тз). Последовательно записывая соотношение Уьч1 = = (Š— тьэ~С)ГЕ для номеров я = О, 1,..., мы придем к следующему равенству: Ь'ь = П ( Š— тз С) Уо, у=! из которого сразу же вытекает, что [[Уа[[ < П (Е тус) [[10[[ з=| Но тогда из Равенства [[Уя[[ = [[Ха[[в вытекает, что [[Ел[[в < 9ь[[Яо[[в, где чь = П(Š— Т,С) .
Следовательно, итерационный процесс схоу=! дится при условии, что последовательность (дь) стремится к нулю, причем тем быстрее, чем меньше величины дь. Поскольку каждое значение чь является функцией параметров гн тш ..,, Ть, возникает задача построения оптимального набора итерационных параметров из условия минимума чь для фиксированного к.
Перейдем к решению этой задачи. Предположим, что все собственные значения Л, матрицы С лежат на заданном сегменте [Тн тз). Учитывая симметрию матрицы С, мы приходим к следующей задаче оптимизации: найти пцп чь(тн тш.,., гь) = 1п1 = пн1п П(Š— т С) = ппп ~ гпах П(1 — т Л,) Поскольку все Л, лежат на отрезке [тн тз], то расширяя область, по которой берется максимум, мы получим, что ппп Чь(тн тш..., ть) < ппп гпах П(1 — ТД 1П1 1П1 1 ш<гау2 170 итн лционныв мвтоды гашения линейных систем [гл. 6 Полученная огрубленная задача имеет более простое решение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
