IV Канатников А.Н., Крищенко А.П. Линейная алгебра (Зарубин В.С., Крищенко А.П. - Комплекс учебников из 21 выпуска), страница 47

Уравнение (11.18) задает метпод верхней релаксации. К нему близок метод нижней релансации, который имеет уравнение х~+1 — х~ (Р+ыА».) + Ах = 6. (11.19) х~+' =-оЮ 'А х~+ + ((1-и)Е-ы0 'А».)х~+шВ '6. Как и метод Зейделя, методы верхней и нижней релаксации связаны с обращением матрицы, которое естественно встроено в вычислительную схему метода. В случае метода верхней релаксации преобразуем уравнение (11.18) к виду 11.4. Сходяиостьятерациохяихиетодое Записывая это уравнение в координатах, находим + а;1(1/о1 — 1)х; — ~~М а,ух1 + Ь,), 1= 1, и.

(11.20) 1=1+1 В методе нижней релаксации приведем уравнение (11.19) канонической формы к виду х + =-ооП ~А+х~+~+((1-1о)Š— 1оЭ 1А )х +1оП 1Ь и запишем в координатной форме: 1-1 х,. + = — Я аех +а11(Ц1о — 1)х; 1=1 а;ух~+ + Ь;), 1= 1, п. (11.21) Из (11.20) и (11.21) следует, что методы верхней и нижней релаксации различаются порядком вычислений. В методе верхней релаксации элементы столбца х~+1 вычисляются последовательно от первого к последнему (как в методе Зейделя), а в методе нижней релаксации, наоборот, — от последнего к первому.

11.4. Сходимость итерационных методов Итерационные методы решения систем линейных алгебраических уравнений (СЛАУ) наиболее детально разработаны в случае, когда мап1роца системы симметрическая подоэсип1ельно определенваа. Это объясняетсл тем, что такие системы часто встречаются в приложениях, причем они имеют значительные размеры, и прямые методы для таких систем теряют эффективность. 316 П. ИТЕРАЦИОННЫЕ МЕТОДЫ Отметим, что квадратную СЛАУ с невырожденной матрицей А легко преобразовать в эквивалентную систему с симметрической положительно определенной матрицей. Для этого т достаточно умножить систему Ах = Ь слева на матрицу А . Поскольку деФ А = бес А Ф О, то получающаяся прн этом СЛАУ А Ах = А Ь эквивалентна исходной СЛАУ, так как можно провести обратное преобразование, умножив полученную систему слева на матрицу (А ) 1. Матрица А А является симметрической: (А А) =А (А ) =А А.

Покажем, что она является и положительно определенной. т т Для этого рассмотрим квадратичную форму х А Ах. В силу свойств умножения матриц имеем х А Ах = (Ах) (Ах) = ~)Ах~)~ > О, где ~Я) — евклидова норма в линейном арифметическом пространстве К" со стандартным скалярным умножением. Последнее нестрогое неравенство превращается в равенство, если только столбец Ах является нулевым. Так как матрица А невырождена, существует обратная матрица А 1. Поэтому при Ах =О имеем х= Ех = (А |А)х = А ~(Ах) = А 10 = 0.

Переход от данной СЛАУ к эквивалентной ей системе с симметрической положительно определенной матрицей не всегда целесообразен. При таком переходе могут утрачиваться Ю свойства, которые были бы полезны при решении системы и которые не компенсируются приобретенными свойствами (симметричностью и положительной определенностью). Например, это наблюдается для разреженных матриц, отличительной особенностью которых является большое количество нулевых элементов. К недостаткам указанного перехода следует отнести н то, что он, как правило, приводит к увеличению числа обусловленности матрицы системы. Основой любого итерационного метода является сходимость итерационной последовательности по той или иной нор- 317 11.4.

Сходимость итералиоияьек методов ме, заданной в линейном пространстве. Мы рассмотрим линейное арифметическое пространство Й", норма в котором порождается стандартным скалярным умножением. Элементы линейного арифметического пространства будем записывать в виде столбцов. Если матрица А симметрическая, то запись А > О означает, что эта матрица положительно определена. Другими сионами, положительно определенной является квадратичнал ) форма х Ах, матрицей которой является А. Длл произвольной матрицы В мы также можем рассмотреть квадратичную форму х Вх. Матрицей этой квадратичной формы является В' = (В+В )/2. Если указанная квадратичная форма положительно определена, то мы будем говорить, что и матрица В (вообще говоря, несимметрическая) положительно определена и обозначать зто так: В > О. Рассмотрим одношаговый итерационный метод в канонической форме (11.5).

Если метод стационарный то он определяется частным случаем канонической формы У+1 и В + Ах = б, 11е1В ~ О. (11.22) т Для такого метода верна следующая теорема о сходимости. Теорема 11.3 (теорема А.А. Самарского). Если А— симметрическая положительно определенная матрица, т > О и матрица В удовлетворяет условию  — О,бтА > О, то итера ционная последовательность для итерационного метода (11.22) сходится. ф Сформулированнал теорема 11.3 позволяет получить легко проверяемые условия сходимости для конкретных итерационных методов. Следствие 11.1. Пусть А — симметрическая положительно определенная матрица порядка и с диагональным преобла- 318 П. ИТЕРАЦИОННЫЕ МЕТОДЫ данием, т.е. для ее элементов ау выполняются неравенства ан > ~ (а; (, 1=1,п.

3Ф~ (11.23) Тогда итерационная последовательность метпода Якоба схо- ди гся. м Метод Якоби является частным случаем канонической формы (11.22) стационарного итерационного метода при т = 1, В = Р. Поэтому условие теоремы 11.3 для этого метода имеет вид 2Р— А > О. Покажем, что это условие выполняется, если матрица А имеет диагональное преобладание, т Оценим квадратичную форму х Ах, учитывал, что а; = а;. для симметрической матрицы А: т х Ах= ~~> аух;ху < ~~> )аО()х;))х~(< и и и < — ~~) )а; ((х~+х~~) = — ~~) (а; )х3+ — ,') (а1у~х~д = 2 ',3=~ 1,1=1 ~,у=1 1 2 1 )аО)х; + — ~~~ (ад,)х; = ау=1 АЗ=1 и и = — ~~Г Цоу~+(аИох; = ~ (ад)х;.

1о=1 Из (11.23) немедленно следует, что у матрицы А с диагональным преобладанием диагональные элементы ан положительны. Поэтому при х ф О и и и х Ах= ~~) (аО)х; =~х~Яа1у(+он) <2~ х~ан=2х Рх. з,у=1 1=1 бф1 М1 Следовательно, х (2Р— А)х > О при х ф О и условия теоремы А.А. Самарского выполнены. ~ 319 П.4. Сходимоеть итераииоииых методов Следствие 11.2. Если А — симметрическая положительно определенная матрица, то итерационная последовательность метода верхней релаксации сходится при 0 < ш < 2. м Метод верхней релаксации получается из канонической формы (11.22) стационарного метода при В = Р+ юА, т = м. Для симметрической матрицы А имеем А = А+.

Значит, квадрат т тичные формы х А х и х А» х совпадают, так как у них одна и та же матрица 0,5(А + А+). Учитывая зто, преобразуем условие теоремы 11.3: х ( — 0,5тА)х=х ((Р+иА ) — О,йо(Р+А +А» ))х= =(1 — 0,5ш)х Рх+О,Ьа(х А х — х А+х) =(1 — 0,5ш)х Рх. У симметрической положительно определенной матрицы все диагональные элементы положительны (см. следствие 8.3). Это значит, что диагональная матрица Р положительно определена.

Следовательно, х ( — О,бтА) х = (1 — 0,5ш)х Рх > 0 прим < 2 ихО. Если и >О, то и т>0. Согласно теореме11.3, при 0 < ш < 2 итерационная последовательность метода верхней релаксации сходится. ° При ш = 1 метод верхней релаксации превращается в мееаод Зейделл. Иэ следствия 11.2 сразу получаем следующее утверждение. Следствие 11.3. Если А — симметрическая положительно определенная матрица, то итерационная последовательность метода Зейделя сходится. Для метода простой итерации теорема 11.3 дает условие сходимости, более сложное для проверки. Следствие 11.4. Если А — симметрическая положительно определенная матрица, то итерационная последовательность 320 Ы. ИТЕРАЦИОННЫЕ МЕТОДЫ метода простой итерации сходится при 0 < т < 2/Л ~„, (11.24) где Л вЂ” наибольшее собстеенное значение матрицы А. м Метод простой итерации (11.16) получается из канонической формы (11.22) стационарного метода в случае В = Е.

Условие теоремы 11.3 для этого метода имеет вид Š— 0,5тА > О, т > О. Матрица Š— 0,5тА симметрическая, Поэтому она положительно определена тогда и только тогда, когда положительны все ее собственные значения (см. 8.6). Покажем, что каждому собственному значению р матрицы 1 — р Š— 05тА соответствует собственное значение Л = 2 — ма! т трицы А.

Пусть х — собственный вектор матрицы Š— 0,5тА, отвечающий собственному значению р, т.е. (Š— 0,5тА)х = рх. 1-Р Тогда х — 0,5тАх = рх, откуда Ах = 2 — "х. Следовательно, х — собственный вектор матрицы А, при этом собственное 1-Р значение равно Л = 2 — ". Выразив отсюда р, находим р = т = 1 — 0,5тЛ. Собственное значение р матрицы Š— 0,5гА положительно, если для соответствующего ему собственного значения Л матрицы А выполняется неравенство 1 — 0,5гЛ > О, или Л < 2/т. Отсюда вытекает, что если максимальное собственное значение Л „матрицы А меньше 2/г, то все собственные значения матрицы Š— 0,5тА положительны и эта матрица является положительно определенной.

Согласно теореме 11.3, итерационная последовательность метода простой итерации сходится, если Л <2/т. > Условия сходимости типа (11.24) можно получить для произвольного стационарного метода. Теорема 11.4. Для сходимости итерационной последовательности стационарного метода, заданного канонической формой (11.22), при любом начальном приближении необходимо 11.5. Скорость скодиностн стационарных методов 321 и достаточно, чтобы все корни характеристического уравнения матрицы Т = Š— тВ 1А были по модулю меньше единицы. Отметим, что в теореме не требуется, чтобы матрица А СЛАУ была симметрической. Достаточно лишь, чтобы и А, и В были невырожденными матрицами.