Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 41
Текст из файла (страница 41)
Быстрота сходимости метода простой итерации обусловливается наибольшим модулем собственных значений матрицы В = Š— В А. Быстрота сходимостн релаксационного цик— ! лического метода с постоянным множителем релаксации д определяется наибольшим модулем собственных значений матрицы Е, = ~В+ 9С>-'< — ~ — ~ж~, где В, Л и гг диагональная, поддиагональная и наддиагональная части 1 1 матрицы А.
Для матрицы А=В ' АВ ' диагональная, поддиаго- 1 1 нальная и наддиагональная части будут, соответственно, Е, В ' ЕВ 1 1 В з гсВ Я . Поэтому 1 В=Š— Е А=Š— В зАВ =Ва (Š— В 'А)  — Вз гтВ з -1 1 1 Е,=И+,В-' — "-) (..;, — КВ-а)= 1 1 1 1 =ВаР+9Е~- ВУВ Д вЂ” д — два . 240, итвгяционныв мктоды гвп1вния линвйных систвм [гл. гн Е1 К1 1 2 А= '1г" Е м — 1 21 где Е,, Е,, ..., Ем †единичн матрицы.
Если все надлиагональные клетки квазитрехдиагональной матрицы умножить на некоторое число а, а все полдиагональные на обратное число а ', то определитель матрицы не изменится. Действительно, ясно что Е)1 а 1Ф 1 аК1 С2 . аК ~-112", 0 Е11 Ф", О, Ег аЕ2 а2и — 1Е 21— Е, аз аяг-1Е 22 откуда непосредственно следует справедливость сказанного. Это свойство квазитрехдиагональной матрицы позволяет связать характеристический полином матрицы 5 с характеристическим поли- Таким образом, матрицы В и Я~, построенные исходя из матрицы А, подобны матрицам В и Зч и, следовательно, их собственные значения соответственно совпадают.
Это замечание позволяе~ при исследовании указанных методов лля положительно-опрелеленных квазитрехдиагональных матриц ограничиться рассмотрением иатриц вида ф Зб) системы с квлаитввхдиагонлльными млтеицлми 241 номом матрицы В.(Мы считаем диагональные элементы матрицы А еди- ничными). действительно. ~ 1Š— В,~ = 1,~(Е+ д1.) — (Š— дŠ— да~ ~ = (1+д — !) Е1 д)Р, 6?%", (1+ д — 1)Е 4~'пь-~ Гдй"~, (~+ д — 1) Е, д)~' г ~' д )/ г Ф'', (г+ д — 1) Е г+д — 1 Š— 2 „~ —,,"Е~ г+д — 1~ где Г(Г) есть характеристический полином матрицы В=Š— А= 16 Змц Вгь и. а„Фаллеев еюв. Н.
Фааавевч (1-+д — 1) Е, д')г( Ф', дУ'1 (Р', (1+ д 1) Е2 Г+д — 1 )/ ~- Я3 — »Е» Ж»» »к» — ГЕа е( — г)= (р', — ГЕ„ тЕ» — Ж'» — Ф", »Е, '=( — 1)" е(т) в' ж-» т-» и = ( — 1)" Следовательно, Г(Г)=Ге-аа(Г» — с,)(Г» — са)... ( — сь). (4) Здесь и — число пар ненулевых корней полинома Р(г). Так как матрица В симметрична, то все корни полинома Е(т) вещественны. Поэтому с, 0; са>0; ...; с„)0.
Положим с.=-1»'., 1=1, 2..., л; р; ) О. Таким образом, собственными значениями матрицы В являются 0 (кратности а — 2в) и ~- 1»», ~- р, ..,, + ра, Нулевой корень может отсутствовать при четном и. Так как матрица А = Š— В положительно определена, все числа 1 + р; '" О, откуда р; ( 1. Следовательно, в наших условиях метод простой итерации сходится. Быстрота сходимости определяется наибольшим»из чисел ро которое мы обозначим через 1». Характеристическим полиномом матрицы Ва в силу . (3) и (4) является (т) уцНаР( +Ч ) Д~( +Ч ) оа~ »а — аа та а=» = (~+ — 1)"-" Ц Иг+ ~ — 1) — уКг1.
1» В частности, при 4= 1 (метод Некрасова) Р» (Г) = Г" Ц (1 — 1»Я»). Его корнями являются 0 (кратности и — й) и числа р',, рвам ..., ра Отсюда мы заключаем, Что метод Некрасова сходится вдвое быстрее. чем метод рростой итерации 242 итеглционныв мвтоды вишвния линейных систвм [гл. ш Полипом Г(т) обладает свойством Р( — г) =( — 1)" Г(Г). действительно..
в 36) систамы с кваэитввхдилтоилльными мАтРицАми 243 Выясним теперь вопрос о наиболее целесообразном выборе множителя релаксации д. Нулевым собственным значениям матрицы В соответствуют собственные значения матрицы 54, равные 1 — д. Собственным значениям +и; соответствуют два собственных значения матрицы 5 .
определяемые из квадратного уравнения УУ+ у — 1)а — уаз'-.Г = О. Корни этого уравнения суть а Ргуь у Р-,.ва — 44 — ', 4 2 При О ( д.( . =д, эти корни будут вещественными и 2 1+ У) — Р'-,'. положительными, причем болщпим нз них является При д; ( д ( 2 корни становятся комплексными и нх модули равны д — 1. На плоскости д, Г кривая третьего порядка 1У+ у — 1)' — уаИ,'Г = О имеет двойную точку при д.=О, У= — 1 и выпуклую петлю в полосе О (д (д,, касающуюся прямой у=О при д=1 и прямой д=д; при г:= дс — 1. Так как каждая прямая, параллельная оси д, пересекает кривую не более чем в лвух точках, то прямая г'= 1, проходящая через двойную точку, более не пересекает кривую. Поэтому петля кривой пеликом расположена ниже прямой У = 1.
и верхняя часть ММ петли опускается при изменении д от О до до Таким образом, график модуля большего из двух корней, соответствующих дзнному рь имеет вид, изображенный сплошной линией на рис. 1. При возрастании ра точка М сдвигается вправо, а участок кривой Мйу поднимается. Таким образом, наибольшее по модулю собственное значение матрицы Яч соответствует р. Наивыгоднейшим значением множителя релаксации, очевидно, является 2 1+ау — Р' Интересно отметить, что при таком выборе множителя релаксации все собственные значения, матрицы В- становятся по модулю я 244 итввьционныв методы ьвшвния линвйных систем [гл. ш равными о — 1= . Действительно, нулевым корням ма- 1+У1 — ь трицы В соответствуют корни о — 1, корням +ро при и; ( И, соответствуют пары сопряженных комплексных корней, равных по модулю о — 1, и, наконец, для +Ро при р»= — и, оба корня совпадают и равны о — 1.
При д(д (2 по тем же соображениям все собственные значения матрицы В» по модулю равнгя о — 1. Рис. 1. График зависимости от о наибольшего модуля собственных значения матрицы Я» имеет в точке о = о резкий минимум с верти- и кальнои касательной слева и касательной справа, образующей угол— 4 с осью абсцисс. Поэтому при отклонении о ото должно получаться реакое уменьшение быстроты сходимости, особенно при отклонении в сторону уменьшения. В заключение заметим, что установленная связь между собственными значениями матриц В и 5» сохраняется для любой квазитрехдиагональной матрицы с единйчными дизгональными блоками, без предположения о симметрии и положительной определенности. 5 37.
Теорема сходимости Теорема 37.е. Если в процессе неполной (или полной)релаксации для системы с положительно-определенной матрицей выполнены условия: а) последовательность ведущих индексов го..., 1ь, ... имеет интервал повторяемости, т. е. в каждом отрезке длины 1ь„о ., Гь+~ этой последовательности присутствуют хотя йы по одному разу все числа 1, 2, ..., и; 0 371 245 тзогема сходимости Ь) мнозкители релаксации удовлетворяют условию в(«7ь( (1 — е при О(в(1, то процесс сходится к решению системы.
Более того, существует число 0, О(0(1 такое, чт, !Л вЂ” Х(ь)( (0ь. Доказательство. Пусть процесс решения системы АХ= Р происходит по формуле г (ь -1) Х" =Х +«7ь ' е(„=Х +тье;л, (ь) (ь-О «ь (1-О а«„«, где (Ь вЂ” 1) г, ь тв — — а а«ь «) 12) 2 — «) Положительные числа — а ограничены сверху и снизу, так ь «) (ь()« ь что существуют такие константы 71 и Тю что т,т'-„* (7(х( ')) — Дх(ы) ( т, Р. Так как ряд из положителы)ых членов „1„71Х~ )) — 71Х( )), оче- 1«=1 Ш видно, сходитсЯ, то сходащимса бУдет и Рад ~~.', Т,тгь, а вместе с ним ь-ь и ряд ~ ть и, следовательно,тв -+ О.
Так кзк компонента г« век- (1«-1) к-о тора невяаки отличается от т„ограннченныч сверху и снизу множителем —, мы устанавливаем, что г; -+ О. Таким образом„ а«ь «, (Й-1) (( 1) компонента вектор» невязки с номером, равным номеру компоненты приближения, меняющейся на следующем шагу, стремится к нулю. Для сходимости процесса достаточно показать, что и все остальные компоненты вектора незязки стремятся к нулю при «0-+ сю.
Пусть Е любое натуральное число, 1 (1 ( и и пусть к ) 1. Обозначим через Й( номер последнего шага. предшествующего )г-му, при Здесь через (ь обозначен номер компоненты, изменяемой на Ь-м шагу процесса. Пусть 7"(Х~ )) есть значение функции ошибки на 0-м шагу, )'( ) вектор ошибки на к-м шагу. (ь) Тогда .(Ь вЂ” 1) 2 (4) 246 итвглционныв мвтОды гашения линвйных систем [гл. ш котором менялась 1-я компонента приближения.
В силу условна о существовании промежутка повторяемости длины 1 имеет место (ь — 1) неравенство 0 (й — й; . 1. В силу доказанного г, -+О, Имеем далее Оценим последнее слагаемое, Лля этого предварительно оценим г — г ~, где гл (й. Имеем (а) о«ь) ))г~ ~ — г"~ ~~=(тле;а)=та. Следовательно, 1у — г ~~ ( ~~ !т,1, «=««««ч и потому ) г — г 1 = ! А() ) — У~~~) / ()~А)),~~ ~! лс„!. =и «« Отсюда ь !г~ — г1 с )! (~г~ — г1 4 ')~ ()~А(! «=Ф.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
