Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 38
Текст из файла (страница 38)
Обозначим компоненты искомого вектора решения через х,, ..., х„. Одношаговый циклический процесс (часто называемый также методом Зейделя) напоминает процесс последовательных приближений с той разницей, что при вычислении й-го приближения для (-й компоненты учитываются вычисленные уже рзнее (с-е приближения для компонент х(ь), ..., х(ь(,.
Именно, вычисление последовательных приближений ведется по формулам (-1 о х®= ~~Р~д( х(а)+ ~(д( х(а 1+б( Х-г 1=1 (2) я (ВМЕСта Х(")=~дОХ(Ь 1>+о( В МЕтОдЕ ПОСЛЕдазатЕЛЬНЫХ Прнбпнжений). Одношаговый циклический процесс может быть истолкован двумя способами как разновидность обшего итерационного процесса. Именно, за один шаг процесса можно принять переход от вектора (х(а1, ..., х((ь)1, х(" '1, ..., х(„" 1>)' к вектору (х(Ю, ..., х1ь), х(ь — '), ..., х(ь-О)' (или от вектора (х(ь), ..., х(а))', к вектору (1 "" .) ('' х(ь+1), х(а), ..., х(„"1)'), или же за один шаг можно считзть результат применения полного цикла, т.
е. переход от вектора (х(а 1>, имеет следующий простой критерий сходнмости, Для сходимости процесса необходимо и достаточно, чтобы матрицы )с+5 и Й вЂ” 5 были положительно-определенными. Действительно, собственные значения матрицы В '5 вешествеины, так как )с положительно определена (теорема 11,14). Для сходи- мости процесса необходимо и достаточно, чтобы собственные зна— ь чения матрицы (ч 5 были по модулю меньше единицы, т.
е. заключены в интервале ( — 1, 1). Для этого же, в свою очередь, необходимо и достаточно, чтобы все собственные значения матриц Е+)с 5 и Š— В '5 были бы положительны. Это имеет место в том и только в том случае (теорема 11.16), если матрицы Рс(Е+(ч '5)=гт+5 и Й(Š— Й '5)=Й вЂ” 5 положительно-определенны.
й 321 221 ОДНОШАГОВЫЙ ЦИКЛИВЕСКИЙ ПРОЦЕСС ..., х!2-11)' к вектору (х121,..., х1Ю)'. В первом истолковании метод не будет стационарным, но будет циклическим. Именно, как легко видеть, в атом случае в качестве матриц, определяющих процесс, берутся, поочереди, матрицы еп, е„, ..., е„„, где (1) 0...0...0 0...1...0 0...0...0 (3) Х=ВХ+6 представим в виде Х = (М+ М) Х+ 6. (4) где ~!1 ~!2 ' ' ' 21!! О 522 , . ° 52„ 0 О ...
0 0 0 ... 0 0 . (5) 0 0 ...Ь„„ В зтих обозначениях формулы 1-1 и Х, =.~,Ь11Х, +~'.,51~Х! +д1 1-1 1-1 можно представить в матричной форме в виде Х!ю = МХ!ю + ИХ!~ '! + 6. Отсюда следует, что х'"'= (е — м)-' нх"-"-4- (е м)-'6. (6) Таким образом, один полный цикл одношагового циклического процесса для системы (4) оказывается равносильным одному шагу процесса последовательных приближений, примененного к системе Х=(Š— М) МХ+(Š— М) 6, которая равносильна исходной системе Х= (М + М) Х+ 6 и может быть получена из нее умножением слева на неособенную матрицу (Š— М) '.
Точнее, Н„!а-1!+! = ен Во втором истолковании процесс будет стационзрным. Исследуем его подробнее. Уравнение 222 итвглционныя методы ввшвния линвйных систем (гл. ш Из такого представ.чения процесса следует, что для его сходи. мости необходимо и достаточно, чтобы все собственные значения матрицы 2=(Š— М) '12' были по модулю меньше единицы.
Эти собственные значения являются корнями полинома ~ 5 — 1Е). Умно. жив обе части этого уравнения на ~ Š— М ( и воспользовавшись теоремой о произведении определителей двух матриц, мы преобразуем уравнение к виду ! 12' — (Š— М) Г ( = О или, в развернутой форме, к виду Ьп — т Ь„... Ьги Ь21" Ь22 т ' ' ' Ьйи (7) Таким образом, для сходимости одношагового циклического процесса необходимо и достаточно, чтобы все корни уравнения (7) были бы по модулю меньше единицы.
Обратимся теперь к рассмотрению одного достаточного условия сходимости одношагового циклического процесса. Именно, пусть !~В~)1= шах,~~~~ Ьг ~ <12 < 1. 1 1 1 ~1Х* Х("11~ < 12 ~~Х' Х1 — >~! (8) где в качеетве нормы векторов взята кубическая норма, т, е. шах (хг!. Покажем, что при этом условии одношаговый циклический процесс сходится, и для него имеет место несколько лучшая оценка.
Действительно, если х' = (х1, ..., х„)', то Х1 = ~ Ь;)Х1 + дг (1 = 1, ..., П). 21 (9) Вычитая из (9) равенства (2), получим $-1 и хз — хР=:~ Ьзз(х, — х,'")+ ,ч; ЬО (ху — х,'" ") 1=1 З=1 1-1 и ~,— ("'~ <~~Ь„~!,— ',"'!+Р~Ь„!~,—,"-ц 1. 2=1 У=1 (1О) Как мы видели, в этом случае для метода последовательных приближений имеет место оценка 223 % 82! одношаговый циклический пвоцасс Обозначим .У'!бц!=то (11) !!Х* — Хйо !! = шах ! х; — х1Ж ! = ! х; — х1Ю!. Обозначим тг шах =р . Тогда (12) !!Х' — Х< >!! <р !!Х* — Хгь- >!!. Р <Р.
Установим, что Действительно, рг+1 =Х!бу! <р з-г я,+ тг Фг(1 Рм тт) ) 0 ~а Тг , р, — , р, Отсюда Р) шах фг+ Т~) > шах т' = Р'. Здесь знак равенства возможен, только если шах,~, ! Ьц ! достиг у=1 гается прн 1 = 1 (или если ~, = О), и понижение оценки по сравнению с оценкой (8) будет наилучшим, если расположить уравнения в порядке возрастания .~ ~!Ь;~!, принимая за первое то уравнение, а-1 в котором зта сумма наименьшая. Однако одношаговый циклический процесс не всегда оказывается более выгодным, чем метод последовательных приближений.
Иногда одношаговый циклический процесс сходится медленнее процесса последовательных приближений. Воаможно даже, что одношаговый циклический процесс расходится, хотя метод последовательных приближений сходится. Области сходимости этих двух процессов различны и лишь частично перекрываются. Тогда из неравенства (!О) следует, что ! хг — х~ ~! < р; !!Х' — Х" !!+ Тг !!Х" — Х ' !!. ВзЯв длЯ 1 то значение 1е, пРи котоРом (х,— х(ы! достигает максимума, получии !,,Х Хро!! < тг !!Х Хг -о!! нбо 224 итеглционныв катоды вешания линейных систем (гл. ш Приведем примеры, показывающие различие областей сходимости одношагового циклического процесса и процесса последовательных приближений.
П ример 1. Пусть Тогда собственные значения матрицы В определяются нз уравнения (0.1 — ()(5 — Г)+5=0 и потому щах()ч~)1. Процесс последовательных приближений расходится. Образуем матрицу Г 5 — 5 Я=(Š— М) ')тГ= ~ 5 — 4.9 Собственные значения этой матрицы определяются из уравнения гз — О.0+0,5= 0. Очевидно, шах))ч! ( 1. Одношаговый циклический процесс сходится. П ри мер 2. Пусть ) 23 — 5 Собственные значения матрицы В определяются из уравнения — (2,3 — 1)(2.3+1)+5 = Ге — 0.29 = 0; шах )Л, ! ( 1. Процесс последовательных приближений сходится. Нетрудно проверить, что в этом случае одношаговый циклический процесс расходится.
Действительно, 2.3 — 5 5 = (Š— М) 51 = и собственные значения втой 2.3 — 7.3 матрицы по модулю больше единицы. Одношаговый циклический процесс теоретически тождественен с процессом последовательных приближений, примененным к надлежащим образом подготовленной данной системе и это обстоятельство было нами использовано для получения условий сходимости процесса. Однако фактически при проведении процесса вычислительная схема не совпадает с вычислительной схемой эквивалентного процесса последовательных приближений и, в чзстности, вычисление „подготзвлизающей матрицы" Н=(Š— М) ' не должно быть осуществлено.
Это обстоятельство н заставляет выделить одношаговый циклический процесс как самостоятельный итерационный метод. В качестве примера найдем решение системы (14) 9 30, приведенной к виду х, = 0.22х, + 0.02хз+ 0.12хз+ 0.14х, + 0.76 х, = 0.02х, + 0.14хз+ 0.04хз — 0.06х,-+ 0.08 хз = О. 12х, + О. 04ха+ О. 28х, + О. 08х, + 1. 12 л, =- О.! 4х, — 0.06хз+ 0.08ха+ 0.26х, + 0.68. ОДНОШ2ГОВЫй ЦИКЛИЧВСКИй ПГОЦВСС $32! Достаточные условия сходимости одношагового циклического процесса. очевидно, выполнены. В качестве начального приближения берем вектор свободных членов.
Последовательные приближения помещены в табл. Ш.б. Таблица Ш. 5 Вычисление решения системы одношаговым циклическим процессом Х(0) = а 0.68 0.76 1.12 Таблица Ш.б Вычисление решения системы одношаговым циклическим процессом Х(О) О 0.68702290 0.53435515 0.22900763 .0.38167939 Х(О Х (20) Хо в Х(40) Х(40) 0.86327494 1.4810254 1.4821242 1.4823907 1.4823927 0.24074649 0.0439969 0,0435866 0.0434880 0.0434873 — ОА0557078 — 1.2560487 — 1.2574501 — 1.2577909 — 1.2577935 0.65379631 1.0383844 1.0390124 1.0391650 1.0391661 Сравнивая найденные последовательные приближения с решением системы, найденным по методу единственного деления (см.
9 30), мы видим. что четырнадцатое приближение дает решение с точностью 15 эвв. 074. д. к. Фвддеев в в. н. Фаддеева Х(') Х(2) Х(4) Х(4' Х (2) Х(в) Х(2) Х(в) Хой Х (1О) Х(го Х(!2) Х(") Х(14) 1,1584 1,3?30 1.4683 1,5080 1.5242 1.5307 1.5333 1.5343 1 5346)9 1.53485 1,53492 1.534947 1.5349579 1а5349622 0.1184 0,1208 О. !213 0.1216 0.12!8 0.1219 О. 1219 0.1220 0.12201 0.12201 0.12201 0,122009 0.1220094 0.1220010 1.63!7 1.8379 1.9204 1.9533 1.9665 1.9717 1.9738 1.9746 1.97493 1.97507 !.97512 1.975141 1.9751507 1.9751041 1.1424 1.3090 1.3723 1.3969 1.4066 1.4104 1.4118 1.4125 1.41278 1.41289 1.41293 1А12945 1.4129513 1.4129538 226 итввлционныв матоды ввшания линейных систам [гл. ш 5 33.
Метод Некрасова. Так же как в методе последовательных приближений, данную систему АХ=В можно подготавливать к виду, удобному для применения одношагового циклического процесса различными способами. Наиболее употребительной является модификация одношагового циклического процесса, параллельная методу простой итерации. Необходимое и достаточное условие сходимости этой модификации циклического одношагового процесса впервые было найдено П. А.
Некрасовым' ), что дает право называть ее методом Некрасова, Система АХ=с записывается в виде анх<= — ~~< а< ха — ж< аох)+Л „< а=< щ или, что то же самое, в виде < — 1 в а<) ч-ч а<) у< .Ла а« у л < ан а ам ' а-< а-<а< и последовательные приближения определяются по формулам «- и <а) ~~ а<) <<о ч,т ао <а о г< аан а а~а ан лн (2) Необходимые и достаточные условия сходимости этой модификзцин процесса легко получаются из приведенных выше необходимых и достаточных условий сходимости в общем случае. Действительно, выбранная подготовка системы АХ= с к виду Х= — ВХ.+ 0 основана на предварительном умножении системы на диагональную матрицу Р '=(а«, ..., а„,) '.
Следовательно, В= — Р 'А. Обозначим О а„... агв О О ... аа„ О О ... О ам О ... О (3) О О ... О а<н а„а ... О <) П. А. Некрасов 11!. до трех единиц шестого знака. Одношаговый циклический процесс в рассматриваемом примере сходится быстрее, чем процесс последовательных приближений (см.
тзбл. !П. 1, П!. 2 и П!. 3). То же заключение будет, верно и в применении к системе (3) 3 31, что видно из сравнения табл. Ш.4 н табл. !П.б, в которой дается решение упомянутой системы циклическим одношаговым процессом. й зз] 227 мвтод нзквьсовь Тогда так что в прежних обозначениях М= — 7) 'Л, Аг= — О ')с, Характеристический полинам ! — (О+ ь) ' Р.
— (Е ) матрицы — (О+й) "Я после умножения на ] — (О+й)] принимает зид [)с + (О+ Е)1[. Следовательно, для сходимости метода Некрасова необходимо и достаточно, чтобы все корни уравнения (уравнение Некрасова) ап! аж ... а„, аз 1! а,~! ... азь =0 (4) а„,г аг! ... а„„г были бь| по модулю меньше единицы, Большое количество достаточных признаков сходимости метода дано в переписке П. А. Некрасова и Мемке.') В частности, достаточными признаками являются признаки 1, !1, !', !1' $30. В случае, если матрица А из коэффициентов системы АХ=У симметрична или эрмитова, существует еще одно важное условие сходимости метода Некрасова. Именно, если матрица А положительно определена, то метод Некрасова для системы АХ= Р сходится.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
