Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 40
Текст из файла (страница 40)
Однако и для этого случая критерий представляет интерес, так как он дает средство для исследования быстроты сходимости процесса. Рассмотрим подробнее процесс (3) при д, = д, = ... = д„ = д. Покажем, что за счет малого отклонения д от единицы почти всегда можно добиться уменьшения наибольшего модуля корней урзвнення (4) и, следовательно, получить процесс с более быстрой, сходимостью, чем процесс Некрасова., так что необходимым н достаточным условием сходимостн процесса (3) будет требование, чтобы все собственные значения матрицы (В+()Е) ~( — ВЯ вЂ” О)Ч) были по модулю меньше единицы.
Соб ственные значения этой матрицы, очевидно, являются корнями урав- нения 234 нтвглционныз методы гашения линейных систем [гл. ш Пусть д=1 — е, где з малое вещественное число. Тогда уравнение (4) равносильно уравнг~ ио г — а вн пи пш à — и 1 — ь и нав à — в га„а ... ави гпп~ [ Тз+ з (Й вЂ” 1 + ) з) ь) + Йе(. [ = О. (6) Здесь Т, = ),/.+ )„1Э + )7. Легко видеть, что, с точностью до малых 2-го порядка, справедлива следующая формула [А+ зВ [= [А [+ вар ВА, где А — матрица, союзная с матрицей А. Следовательно, уравнение (б) примет вид [Те[+ а [(и 1+)е)ЗРТ)То+ )гЗРЕТо[ = 0(еа). Принимая во внимание, что [Тз[= — О, получим, с точностью до малых 1-го порядка, что (1 — Хз) 8р Вт, (7) 8Р ВТо т 8Р Д)о Итак, число Л' =) + М, где )з определяется по формуле (7), является приближенным значением наибольшего по модулю корня уравнения (б).
Сравним модули )ю и ),'. Ясно, что [)7 [а '= [ )о [а -[- 2е Ке ()г) ) + е' [ й ['. Поэтому, при достаточно малом е, можно добиться того, чтобы [Л'[' был меньше [) [', если только Ке(М„) + О, При этом, если Ке()г)е) с.,О, следует взять е' О, т. е. прибегнуть к нижней релак- сации, если Ке(н)ч) ) О, то нужно взять а ( О, т. е. перейти к верхней релаксации. Формула (7) равносильна следующей формуле (1 "о)(Е' го )о) ((а)+7.)ггз )о) (8) Положим 1=)я+кз, где )з наибольший по модулю корень уравнения Некрасова [Г(,+Ю.+К [= О.
Тогда, с точностью до з', имеем =),,+()з — 1+)м)е, н уравнение (5), с точностью до малых 2-го порядка, перейдет в уравнение % 35! 235 наполнля ввллкслция где Хз ненулевой вектор, определенный из уравнения ТзХв = О, а 1', ненулевой вектор, определенный из уравнения Т,уз=- О. Векторы Х„ и ув определяются с точностью до скалярных множителей однозначно, если предположить, что ) простой корень уравнения ((Е + Ы+ Ас) =. О. Но, как можно показать, только в этом случае имеет смысл и формула (7).
Вопрос о выборе множителя с7, приводящего к процессу с наибольшей быстротой сходимости, в общем случае не решен. Для матриц 2-го порядка исчерпывающее исследование проведено А. 31. Островским (7!. Пусть Ненулевым корнем уравнения и, изс является, очевидно, )я.=и=- — '' =, так что для сходимости метода "ссим Некрасова необходимо и достагочно, чтобы ( и ~ ( 1. Для положительно-определенной матрицы А имеет место неравенство 0( и( 1. Применяя формулу (7), получим й = 2(1 — и), и)тс = 2и(! — и). Поэтому при 0(и(1 (з частности, для положительно-определенных матриц) верхняя релаксация (по крайней мере при малых е) дает более быструю сходимость, чем полная, а при — 1 ( и ( 0 более быстрая сходимость Судет прн нижней релаксации.
В той же работе А. М. Островского дано оспимальное значение для множителя д. Именно, 2 с7о= + причем соответствующее значение для модуля Л' есть ( сс! 1+Т'1 — и Отметим. что изменение быстроты сходимости при неполной релаксации может быть довольно значительным. Так, для 06 1 236 итевационные методы Решений линейных систем 1гл. И1 будем иметь при полной релаксации )о=,— =0.36. Оптимальная же 9 Б 10 неполная релаксация будет при )7 = —, причем соответствующее 1 значение ),' равно —,„=0.111... Для не положительно-определенных матриц Островским показано в той же работе, что при и ) 1 процесс (3) расходится при всех значениях () нз интервала(0.
2). Если же и . — 1, то процесс(3) будет 2 сходя(цимся при 0 ( 47 ( , так что область сходимости 1+а' ~и( процесса (3) при (7 й 1 будет шире. чем область сходимости процесса Некрасова. Для положительно-определенных матриц третьего порядка можно показать посредством довольно громоздких выкладок '), что Не (Ь„,) > О, так что верхняя релаксация (по крайней мере при малых о) приводит к более быстрой сходнмости, чем полная.
Таблица Ш. 8 Решение системы методом Некрасова с нижней релаксацией. 47= 0.8 Х(о) Х(1) Х(оо) Х(ш) Х(~) Х(41) 0.3745638 1.0384154 1.0390402 1.0391657 1.0391661 0.4149420 1Л810565 1.4821686 1.4823918 1.4823927 0.24 0.31936 0.0440084 0,0435748 0.0434877 0,0434874 — 1.2560832 — 1.2575067 — 1.2577924 — 1.2577935 Х(о) Х(ц Х(14) Х(1о) ОА340459 1.0391661 1.0391661 0.39754 0.0434866 00434873 0.4529715 1.4823932 1.4823928 0.33 — 1.2577939 — 1.2577935 1) Л. к. Фаддеев [3).
Таблица П1. й Решение системы методом Некрасова с верхней релаксацией. д = 1.1 ф 36! системы с квАаитРехдиАТОИАльными МАтРицлми '237 Таблица 7П. 70 Решение системы методом Некрасова с верхней релаксацией. д = 1.2 Х!0) 0.36 0.4! 856 0.4459930 1.039)1678 — 1.2577988 — 1.2577939 — 1.2577936 0.0434852 0.0434869 0.0434873 1.0391662 1.0391661 В табл. П1.8, П! 9 и ПП 1О приводятся результаты вычисления решения системы (9) 9 23 по иетоду Некрасова с неполной релаксацией при 27=0.8, д=!.1 и 7= 1.2. Сравнение этих таблиц с табл. !П.7 показывает.
что в данном примере верхняя релаксация дает лучший результат, чем полная. Отметим, что дальнейшее увеличение множителя релаксации приводит уже к худшему результату. Так, при )7=!.3 имеем Х)'е) = ( — 1.2577970, 0.0434871, 1.0391679, 1.4823915)', а результат, аналогичный Х!Ио табл. !П, 9, получается лишь при )2 = 26. $36.
Исследование итерационных методов для систем с квазитрехдиагональными матрицами В настоящем параграфе будет исследоваться быстрота сходимости метода простой итерации (процесса Якоби) и циклического релаксационного метода с постоянным множителем релаксации для систем с положительно-определенными квазитрехднагональными матрицами вида 12! Ж'! 1 2 2 где О,..., 77 — диагональные матрицы (быть может разных порядков), %'1, %'2, ..., В'„, ! — некоторые прямоугольные матрицы. Очевидно, что все диагональные элементы матрицы А положительны. Хо) Х!и) Х!!2) Хое) 0.4561382 1.4823963 1.4823930 1.4823928 238 итееьциониыв методы вешания линейных систем [гл.
щ Результаты, здесь излагаемые, принадлежат Янгу [2[. Всякая матрица А укаэанного вида обладает „свойством А" (Янг), состоящим в том, что номера строк и столбцов могут быть разбиты на два непересекающихся множества Р и с> так, что если а;у чс О и (Ф г, то (~Р и 1~ге или (~(э и у~Р. Именно, такими мно>кествами будут совокупности номеров строк, соответствующих нечетным клеткам В>, О,, ... с одной стороны и четным О,, О„...
с другой. Верно и обратное, что любая симметричная матрица, обладающая „свойством А", может быть приведена к квазитрехдиагональному виду за счет одновременного изменения нумерации строк и столбцов; достаточно, например, первые номера отдать множеству Р, последующие — множеству (). После такой перенумерации матрица примет вид (2) где В> и О,— диагональные матрицы, >г' — некоторая прямоугольная матрица. В частности, общая квазитрехдиагональная матрица может быть преобразована к виду (2) при О2 оя О, Оз )",)>= Е>аа Оглу '>р" > ~а ('з (если и> = 2л) 02 в> = Вяьг, ' 9 361 Огствмы с кВАзитРвхдиАГОИАльными мАтРицАми 239 Ю, В", рта (если гл = 2л + 1) еа - а аа-1 и зь .Системы с положительно-определенными матрицами, обладающими „свойством А", возникают, например, при решении некоторых уравнений в частных производных эллиптического типа разностными методами.
Установление нумерации, в которой матрица становится квазитрехлиагональной, связано с тем или другим естественным выбором нумерации узлов. Прежде всего заметим, что при исследовании сходимости метода простой итерации и релаксационных циклических методов с постоянным множителем релаксации для матргц с положительными диагональными элементами мы можем считать, без нарушения общности, что все диагональные элементы равны единице. Действительно, если В диагональная матрица, составленная из диа- 1 1 гонзльных элементов матрицы А, и А=В ' АВ -', то А имеетединичные диагональные элеиенты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
