Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 93
Текст из файла (страница 93)
(4) Выясним, как изменяются компоненты вектора ошибки в ВТ-процессе. С втой целью разобьем последовзтельность (2), определяющую процесс на „слова" так, чтобы каждое слово содержало букву В один раз и с нее начиналось. Например, ВВТТТ ВТ ВТ ВВ ТТ... = В(ВТТТ)(ВТ) (ВТ) В(ВТТ)... = = В,В,В, Взвгвз Здесь В,=ВТ... Т=ВТ, В,=В. Ясно, что у~ 1= Ву" ', если на й-м шзгу находится буква В и 1 РО 2Вуш-!1 уш-2) если на й-м месте находится буква Т. Рассмотрим, как влияет на вектор ошибки применение слова В,. Имеем уса ')=Ву(а)=т,(В) у(") уФ 1 2вуФ 1 Фю (2в, в) уы1 т (в) уйо у' '= 2ву~ + 1 — у~ +"=(2вт (в) — т,(в)) у1 1= т (в) у~ ' у'' ю=(2ВТ,(В) — Т,,(В)1 у1 1= Т,(В) 1' Здесь полиномы ТгЯ определяются рекуррентными соотношениями Тг(г) =2гтг-г(г) Гч-з(И) при начальных условиях Т Я=1, Т,(~) =1 и, следовательно, совпадают с полиномами Чебышева созт агссов1.
Таким образом, применение слова В, влечет за собой умножение компонент вектора ошибок на множители Т,(р,)...,, Т,(ег). Применение же последовательности из букв В и Т влечет за собой умножение каждой компоненты вектора ошибок на произведение значений в соответствующей точке полиномов Чебышева, отвечающих отдельным словам В,, из которых состоит определяющая последовательность (2). 576 [гл. >х унизвгсалънь>е Алгогиьмы Г!роцессы Абрамова являются частными случаями ВТ-процессов, в которых определяющие последовательности состоят нз слов В, В,, В,, В,, ....
Метод последовательных приближений записывается как ВВВВ...-процесс. Так же как в процессах Абрамова, применение слов с высокими номерами ускоряет убывание компонент, отвечающих лишь собственным значениям матрицы В, близким по модулю к единице. Поэтому целесообразно вначале работать только со словами В, вводя более длинные слова на последующих стадиях и возвращаясь к более коротким словам для погашения ошибок от округлений. Применим ВТ-процесс для нахождения решения системы (9) ф 23, 2 подготовленной с Г>= .,— ((3) э 31).
Применение слова В >» (ВТ)» В> (ВТТ): (ВТ)» Х= ( — 1.2577936, 0.0434873, 1.0391661, 1.4823926)'. Взятое слово состоит из 38 букв, так что для получения прибли>кения потребовалось вычисление 38 итераций. Как мы видели (9 31), метод последовательных приближений дал такую же точность при 75 итерациях. Слово В'» (В Т)' (В ТТ) ' (В ТТТ)' В> (В Т)» состоящее из 43 букв, дает Х=- ( — 1,2577945, 0.0434870, 1.0391667, 1.4823935)'. Это приближение хуже предыдущего.
Дополнив взятое слово еше буквзми ТВ ВТ, получим Х= ( — 1.2577936, 0.0434874, 1.039!662, 1.4823927)'. Более удачный выбор первого слова по сравнению 'со вторым объясняется тем, что обусловленность взятой системы такова, что пот необходимости прибегать к словам, более длинным, чем ВТТ. Рззумный выбор слова, управляющего ВТ-процессом, может быть осуществлен посредством следующего „ВТ-процесса с упрзвлением". По ходу этого процесса параллельно с последовательными прибли>кениями Х„должны вычисляться три системы вспомогательных вектеров — невязки гю векторы з„= Вг» и векторы зл — — 2зл — гл >.
Положим га~, = ВХ„+ а 2,+, — 2 (ВХа+ б) — Х„,. 9 91) овщив тгвхчлвнныв итвггщионныв пгоцвссы 677 Эти векторы получаются из вектора Х„применением В-шага и Т-шага. Вычисление векторов Е»», и Я~», не требует проведения итераций, ибо Е» „, — — Х»+г» 2» -г = 2(Х»+ г») — Х» Вычислим их невязки тл»„и тв»~,. Легко видеть, что ш„в, = Вг» = э» тв»„,= 2Вг„— г», — — 2㻠— г» .,— — э». Сравним нормы векторов г н э и положим Х»»,=Л»„, Х»-+г» (6) г» ю = в» если ~( э» ~~ ( )) л» ~), и Х»+, — — 2»,, — — 2 (Х„+ г„) — Х„, г»,-1 = Я» (6) ( — 1.2577936, 0.0434874, 1.0391661, 1А823928)', отличающееся от точного решения не более чем на 2 ° !О в каждой компоненте.
Невязки вычислялись непосредственно на 11, 16, 21, 26 н 31-и шагах. 9 91. Общие трехчленные итерационные процессы Изложенные выше ВТ-процессы и наилучший в смысле 1-го критерия алгорнфм укладываются в следующую общую схему трехчленных универсальных процессов '). Для решения системы Х= ВХ+ О ') Д. К. Фаддеев !21. 37 эвв, 974.
д. К. Фвлвввв в В. н. Фвлввввв если (/э»1~) /!л»~!. Затеи вычисляются векторы в =Вг и л =2э — г »+1 ».~-1 »->1 ».~.1 » и процесс продолжается дальше. Время от времени, для уменьшения ошибок округления, следует непосредственно вычислять невязку г„ »+1 по формуле г , = ВХ»в, + Π— Х„„ о а не по формулам (5) или (6). Применение ВТ-процесса с управлением к прежнему примеру привело к слову ВТВТВТВТВТВВТВВВТВТВВТВВТВВТВВВТВТ = = (ВТ)' В(ВТ) В'(ВТ)' В (ВТ) В (ВТ) В(ВТ) В'(ВТ)' (34 буквы), в результате получено приближение (гл.
~х ЬТ3 УНИВЕРСАЛЪНЫЕ АЛГОРИФМЫ с матрнцей В, собственные значения которой заключены в промежуток ( — 1, 1), строится, исходя из некоторого начзльного приближения Х ', последовательность приближений по формулам <21 ЛО> = ВХ1"'+ а Л' > — — (1+ „)(ВЛ"" '1+В) — „Х~ (2) (3) Первый шаг можно формально рассматривать протекающил2 по общей формуле (3), считая и,=О. Ясно, что если и„,г = О, то процесс, начиная с з+ 1-го ша. а, протекает так, как будто в-е приближение принято за начальное, и далее применяется процесс при и',=а,„, и,'=ив~в, .... В частности, циклическое повторение процесса с некоторыми иа, ..., а, равносильно применению единого процесса, в котором последовательность а„и,, ..., и„а,~о ...
состоит из циклически повторяющихся отрезков О, аа, ..., а,. В методе последовательных приближений все а2=0, в ВТ-процессзх последовательность а„ состоит нз нулей и единиц, в оптимальном процессе а„ = т,,(т) 2 та(т) Векторы ошибки в трехчленном процессе удовлетворяют соот- ношениям 'г'~ 1= Вг""' 'г'~ ~=(1+из)ВУ~" '1 — аз)Н Ю (12=2, 3, ...), так что „,<21 Р В),121 Теорема ЮТ.
1 Полиномы РА (1) удовлетворяют неравенствам ~РА(Г) ~ ( 1 ири — 1 (1 ( 1, — 1 (ав ( 1 (12 = 2. 3, ...). Догсозательство. Обозначим РА.(с) =Ф(Г, и,, ..., иь). При фиксированном 1 полипом Ф(1, а,, ..., иа) есть линейная функция от каждого из аргументов и,, и„. Поэтому при изменении параметров аа, ..., аа в кубе — 1 (оа(1, ....
— 1(аа(1 функция Ф(П ае, ..., а„) принимает экстремальные значения в одной из вершин куба, т. е. 1 Ф (1, иа,... иа)! ( ! Ф Иг, Ъ, ° ° ., 22) 1, гле еа= Ч 1, ..., ез — — +1. где Ра(1) последовательность полиномов, построенных по рекуррент- ~ным соотношениям Р,(1)= 1, Р,11) — 1, Ра(2) (1+«2)2~ 2 — 1(1) ивРА-2(~)' 9 91) ОвщнР ТРехч.ченные нтеРАцноннъи ПРОцессы 579 Покажем, что Р„(Г) = Ф(г, вв... ен) = Тв„(1) = сова„агссоз 7. причем чебышевский номер вн, каждого последующего полинома на единицу больше или на единицу меньше номера вн прсдшествуюшего. Действительно, это верно для 7е= О, (в=1, ибо Р (1)= ! =т (1), Р,(г)=1 = т,(г), Допустим, что это верно для полиномов Рн,(1) и Рн(1), т.
е. допустим, что Рн(Г)=Т (1) и РА. >(1)= Тв„>(1). Тогда Р„„, (Г) =(1+-в„,) 1Рн(1) — вн.>Рн > = =(1+ вн,) гТв (1) — в ..,Тнт> (Г). При в,, = — 1 получим Р„,, (Г)=Тана> (Г). При е„е, = 1 получим Р„„(Г)=2(Т (1) — Т,„з,(Г) = Т „(1). В обоих случаях полиномы Рн~>(1) и Рн(Г) оказались полиномами Чебышева с соседними номерами. Тем самым Р (Г) — Т (ТГ)+ — т (Т(), 2 г'а где 1+а Т= 2Т,— ° а = (Т вЂ” Р' Тв — 1 )в, Т„= сов й агссов в', мп (н+!) агссов г ~в~0 = в!и агссов Г 37в ! Рн (1) ( = ~ Ф (1, ав ° ..
ан) 1 ( ~ Рн (1) ! = ! Тв„(!) ) ( 1, что и требовалось доказать. Можно доказать, что если О ( ан ( а ( 1, то полиномы Рн(1) равномерно стремятся к нулю во всяком промежутке — Т (Г ( ( Т ( 1, так что трехчленный итерационный процесс в этих условиях будет сходящимся. Отметин некоторые интересные частные случзи трехчленных универсальных алгорифмов сверх указанных в начале параграфа. 1. Трехчленный алгорифм с постоянным а. Пусть а„= а. О ( а (1 при всех )в)~2. Тогда, как легко видеть, [гл.
1х 580 унивевсллъные Алгогнемы 1 1 Поэтому при — — (1 ( — имеем т !Рь(1И ( ' 11+,+, А)=( — 'и'Т' — 1) 1,1+,—, ) Таким образом, если все собственные значения матрицы В заключены в интервале 1 — —, — 1, процесс с постоянным аз=а == т/' =( — "„' ' — 1) сходится почти столь же быстро, как оптимальный процесс. 2. Универсальный алгорифм с полииомами Чебышева 2-го Л вЂ” 1 рода. Пусть а = —,. В этом случае а+1' 1 з1п (в+1) агссоз т 1 л -1- 1 мп агссоз г л -1-! есть полипом Чебышева второго рода, нормированный условием Очевидно, что последовательность Рь(1) равномерно стремится к нулю во всяком сегменте, внутреннем для промежутка ( — 1, 1), хотя сформулированное выше достаточное условие сходнмости здесь не выполнено.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
