В.А. Ильин, Э.Г. Позняк - Линейная алгебра (4-е издание) (1113059), страница 36
Текст из файла (страница 36)
Из доказанной в теореме 6.3 оценки 12а(з ~ ра(ле)з вытекает, что эта задача сводится к нахождению такого значения т, при котором достигается минимальное значение функции р = р (т). Так как обе матрицы А и В симметричны и положительно определены, то существуют положительные постоянные у, и у такие, что справедливы неравенства Т,В ~ А ~ уаВ. Будем считать, что постоянные у, и у, в этих неравенствах иам заданыее). Сопоставляя только что написанные неравенства с условиями (6.21), мы получим, что минимальное значение р достигается при условии (! — р)/т = у„(1+ р)/т = у„откуда получаем оптимальное значение ч = 2/(у, + тз) и минимальное значение р, равное (у, — у,)/(уз+ у,). Частным случаем проведенного нами рассмотрения является явный метод простой итерации, изученный в п.
1. Для этого метода справедливы все полученные нами результаты. В следующих трех пунктах с помощью общего неявного метода простой итерации и теоремы Самарского 6.2 мы рассмотрим несколько наиболее употребительных итерационных методов и установим условия их сходнмости. 3. й(одифицнрованный метод простой итерации. Этот метод получается из общего неявного метода простой итерации в том частном случае, когда стационарный параметр т равен единице, а матрица В представляет собой диагональную матрицу Р, состоящую из элементов матрицы А, лежащих на главной диагонали, т. е. В *= Р, где Ггл.
а 172 итерационные методы При этом, конечно, предполагается, что матрица А является симметричной и что все ее диагональные элементы ам, ааа, ..., а„„ являются положительными (последнее требование необходимо и достаточно для положительной определенности диагональной матрицы В = Р). Из теоремы 6.2 сразу же вытекает, что для сходимости моди. фицированного метода простой итерации при любом выборе нулевого приближения достаточно, чтобы были выполнены два условия 2Р > А, А ) О.
Теорема 6.1 позволяет выразить достаточное условие сходи- мости модифицированного метода простой итерации н в другой форме: 1В - Р-аА) ~ 1«) (6.24) (под нормой матрицы, как и выше, понимается операторная норма). Так как 1Š— Р тАП =ЦР т (Р— А)Д = ПР ' (А — Р)ь то достаточное условие сходимости (6.24) можно переписать в эквивалентном виде 1Р '(А — Р)) ( 1. (6.25) Неравенство (6.25) позволяет получить различные достаточные условия сходимости модифицированного метода простой итерации.
Прежде всего заметим, что если наряду с операторной нормой матрицы (6.2) (которую мы, как и выше, будем обозначать символом 1А1) ввести так называемую сферическую норму этой матрицы, обозначаемую символом 1А),ф и определяемую равен- Г " 1ыт СтВОМ 1А(сф =~ ~~ ~~ аСу~, тО, КаК дОКаэаНО В Э 4 ГЛ. 4 (СМ. Е 1у 1 формулу (4.28)), для любого вектора Х пространства Е" будет справедливо неравенство *ь) )АХ)! ~~А)сф)Х). (6.26) Из (6.26) и (6.5) сразу же вытекает, что операторная н сферическая нормы матрицы связаны соотношением 1А1~ '1А)~ф, Таким образом, в силу (6.25) достаточное условие сходимости модифицированного метода простой итерации выражается нера- ') Мы учитываем, что в рассматриваемом случае вместо матрицы А следует ваять матрицу А, определяемую формулой А= В тА и положить В = )), т = !. кс еч) В этом неравенстве под нормой вектора Х = ° ° ° поиимается так «в ч 1 па иаамваемая сферическая норма 1Х1= ~ ~~ к~~~ с=1 а !! итердциОнные метОды Решения линеЙных систем 173 венством 1Р-! (А — Р)!еа (1, котоРое в РазвеРнУтой записи имеет вид ~~р, ~~),— ! с.!.
о)! 1 /~! Заметим далее, что при определении операторной нормы (6.5) матрицы А мы исходили из обычной (так называемой с ф е р и1л!1 е ~1/т ч е с к о й) нормы вектора Х = ~" ~, равной ~ Х ! = ~ ~ х>~ ! 1 Часто вводят еще две нормы вектора Х: так называемую к уб и ч ес к у ю н ор му, определяемую равенством 1Х~ о гпах~х!), и так называемую октаэдрическую нор!ч!че и м у, определяемую равенством !Х1онт ~~ )х1~.
Если в опреде- ! 1 ленин (6.5) операторной нормы матрицы А понимать под нормой вектора соответственно его кубическую или октаэдрическую норму, то соотношение (6.5) приведет нас к определению состветственно кубической и октаэдрической операторных норм матрицы А. Можно доказать, что кубическая и октаэдрическая операторные нормы матрицы (6.2) следующим образом выражаются через элементы этой матрицы е): а л 1А~ а=п!ах ~ !а!1~, 1А1,„,=шах ~1а!1~. !с!е ! ! !Ю!<а!-! Дословное повторение проведенных выше рассуждений с заменой сферических норм соответственно кубическими и октаэдрическими приведет нас к достаточному условию сходимости модифицированного метода простой итерации, выраженному соотношением (6.25), в котором под нормой матрицы следует понимать соответственно ее кубическую или октаэдрическую операторные нормы.
Это приводит нас к следующим двум условиям, каждое из которых является достаточным для сходимости модифицированного метода простой итерации ! — '~ ! «-! (ДЛЯ ! = 1> 2> ...> и)> ! та> и ~~)~ ~л!! ~«'! (для /=1, 2, ..., и). ! ! >е>! ') См., например, книгу: В. И. Крылов, В. Б. Бобков иП. И. Монастырный.
Вычислительные методы высшей математики, том 1. — Минск: Вышайшаа школа, 1972, с. 111 — 112. итар»ционныв мвтоды 174 4. Метод Зейделя. Представим симметричную матрицу (6.2) в виде суммы трех матриц А = Р + Е + (?, где Р— диагональная матрица (6.23), а Ь и У соответственно строго левая и строго правая матрицы, имеющие вид 0 а1» ...
ага О 0 ... оса 0 0 ... 0 0 0 ... 0 а, О ... О ат а„е ... 0 Р= е) Достаточно заметить, что если у вектора Х»-в координата ревев единице, з все остальные нулю, то (АХ, Х) а»» > О. н удовлетворяющие условию Е' = Р. Метод Зейделя получается кз общего неявного метода простой итерации в том частном случае, когда стационарный параметр т равен единице, а матрица В равна сумме Р + Ь. Таким образом, последовательные итерации в методе Зейделя определяются соотношением (Р + Ц (Х»+с — Х») + АХ» = Р.
Докажем, что метод Зейделя сходшпся для любой симметричной и положительно определенной матрицы А. В силу теоремы 6.2 достаточно доказать, что для любой такой матрицы А выполнено условие 2(Р+ Е) >А. (6.27) Для доказательства (6.2?) заметим, что для любого вектора Х (2 (О+ Е) К, Х) = (РХ, Х) + (ОХ, Х) + (ЕХ, Х) +(ЕХ, Х) = =(РХ, Х)+(РХ, Х)+(ЕХ, Х)+ (Х, иХ) = = (РХ, Х) + (АХ, Х). Таким образом, для доказательства неравенства (6.27) достаточно убедиться в положительной определенности матрицы О, но она сразу вытекает из того, что у положительно определенной и симметричной матрицы А все злементы, лежащие на главной диагонали, являются положительными *).
Сходимость метода Зейделя доказана. 5. Метод верхней релаксации, Этот метод получается из общего неявного метода простой итерации в том частном случае, когда ч = са, В = Р + вЕ, а параметр со выбран так, чтобы являлось наименьшим наибольшее по модулю собственное значение матрицы Š— со (О + соЕ) ' А, осуществляющей переход от й-й итерации к (й+ 1)-й.
Докажем, что если матрица А является симметричной и положительно определенной, то для сходимости метода верхней релаксации достаточно, чтобы было выполнено условие О < со < 2. В силу теоремы 6.2 для сходимости достаточно выполнение условий со > О, 2 (О + соЕ) > саА. й 1) ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ 176 В х»" х» +АХ»=Р, т (6.13) а более общим соотношением В ~«~ » +АХ»= Р.
При этом, как и выше,  — некоторая легко обратимая квадратная матрица порядка и. При таком выборе итерационной последовательности для погрешности л» = Х» — Х итерационной схемы получится соотношение В е ° — г»+А2,=0. т»«т (6.15*) «) Пафнутий Львович Чебышев (182! — 1З94) — велнкнй русский математик и механик. Второе из этих условий для любого вектора Х приводит к неравенству (2 (0 + ш1.) Х, Х) > (»1АХ, Х). (6.28) Последнее неравенство эквивалентно каждому из неравенств в следующей цепочке: (20Х, Х) + (шт,Х, Х) + (ш1.Х, Х) > (ШАХ, Х), (2 — ш) (0Х, Х) + (ш0Х, Х) + (шт'.Х, Х) + + (Х, 1аУХ) > (ШАХ, Х), (2 — ш) (0Х, Х) > О.
Из последнего неравенства и нз положительной определенности 0 заключаем, что (6.28) справедливо при 2 — ш > О, т. е. при о1 < 2. Итак, доказано, что условия О < а < 2 обеспечивают сходимость метода верхней релаксации. 6. Случай несимметричной матрицы А. В случае несимметричной матрицы А мы можем умножить матричное уравнение (6.1) слева на матрицу А' и заменить уравнение (6.1) уравнением АХ = Р, в котором Р = А'Р, А = А'А, так что матрица А является симметричной и (как легко убедиться) положительно определенной. 7.
Итерационный метод П, Д. Чебь1шева "). Всюду выше прн рассмотрении общего неявного метода простой итерации мы предполагали, что итерационный параметр т принимает одно и то же постоянное значение. Естественно возникает идея рассмотреть более общий случай, когда в указанном методе значения итерационного параметра зависят от номера й итерации.
В таком случае последовательность итераций будет определяться не соот- ношением [гл, е 176 итал»ционныя мвтоды Предположим, что обе матрицы А и В симметричны н поло- жительно определенны. Тогда, как уже отмечалось выше, най- дутся положительные постоянные у, н у, такие, что у,В ~ А ч:у»В. Будем считать, что этн постоянные у, и у, нам заданы и еще раз напомним, что эти постоянные равны соответственно наимень- шему и наибольшему собственным значениям задачи АХ = ХВХ. Оценим энергетическую норму погрешности )2»(в. Напомним еще раз, что для симметричной и положительно определенной матрицы В существует симметричная и положительно определенная матрица Вп» такая, что Вп» Вн' = В. Как н выше, договоримся обозначать символом В-н' матрицу, обратную к мат- рице Вп'.
Для оценки нормы цогрешности Е» сделаем замену, положив Е» = В-и'У». Прн такой замене соотношение для погрешно- сти Е» переходит в следующее соотношение для У». У»+,—— (Š— ч»+,С) У» (й=О, 1, 2, ...), где через С обозначена матрица вида С = В-и» А В-ц'. Убе- димся в том, что квадрат обычной нормы вектора У» равен квад- рату энергетической нормы вектора 2». В самом деле, 1У, )'=(У„У,) =(В"г, Вп'г) =(Вг„, г„) =)2„!Д. Таким образом, для оценки энергетической нормы Е» достаточно оценить обычную норму У». Оценим норму(У»1. Прежде всего заметим, что из неравенств у, (ВХ, Х) ~ (АХ, Х) ( у, (ВХ, Х) с помощью замены Х = = В-'/» ° У получаются неравенства т, (1', У) ~ (С)', У) < ( у, (1', У).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
