Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 92
Текст из файла (страница 92)
Для полинома Т,(() легко вычислить коэ Рфнциенты, что даст возможность использовать схему п. 5 9 86. Олнако при пользовании этой схемой происхолит значительное уничтожение значащих цифр. Несколько лучшей оказывается схема п. 6 6 86, использующая корни полинома Т,(Г). ОчевИдно, что эти корни равны е;= — сов, (1= 1, ..., 5). 1 (рл — 1) я 25 При пользовании этой схемой приближение Х, получится как последний член послеловательности 2, =Л,,+ ' (ВЛ,, +Π— Л,,) (1=1, ..., 5), начинающейся с 7ч= Хе. Ясно, что при таком способе построения Х, нужно заранее фиксировать значение 5.
Сходимость процесса обеспечивается циклическим повторением. Для уменьшения влияния ошибок округления следует располагзть корин е в порядке их убывания, так как процесс наиболее чувствителен к ошибкам округления на тех шагах, где е близко к единице. Г1окажем ход процесса на примере системы (9) 9 23, принимая зз М и и трехзначные приближения к наибольшему и наименьшему собственным значениям матрицы - системы, именно М = 2.322 и и = 0.242. Эго дает гг = 0.78003!20, так что 0 21996880 — 0 32761310 — 0 42121685 — 0.51482059 В = 0'327613!О 0'21996880 0'24960998 0'34321373 — 0.42121685 — 0.24960998 0.2!996880 — 0.17!60686 — 0.51482059 — 0.34321373 — 0.17160686 0.2!996880 О = (0.23400936, 0.39001560, 0.54602184, 0.70202808)',.
(гл. !х 570 униаввсальныв Алговиемы Далее 7 = 1.2326923, а = 0.26204959. Имеем й 88. Универсальный алгорифм, наилучший в смысле второго критерия Пусть для системы Х= ВХ+О известно, что все собственные 1 1т значения матрицы В лежзт в промежутке ( — —, — ! при 7 ) 1. т т Универсальный алгорифи будет нзилучшим в смысле второго крите- рия, если определяющий его полипом 7(1) будет полиномом, наименее 1 г 1 11 отклоняющимся от на промежутке ! — —, — !.
Очевидно, что 1 — Г т' 77' 7(г)=7г(71), где Р(г) есть полипом, наименее уклоняющийся от 1 функции — нз промежутке ( — 1, 1). 7 †Полипом степени э — 1, удовлетворяющий последнему требованию, был известен еще Чебышеву. Именно, Р,,(1)= — —,— !т,(1) — 2У ат,я+от,,(г)~1+ где а=(7 — У7а — 1), Т,(1) =сова агссоа1.
Таким образом, л 7,,(г)=- — —, (Т,(тг) — 2У пТ,,(тг)+пТ, а(71)~. В работе М. К. Гавурина [1], впервые предложившего такой выбор полинома 7'(1). рекомендуется вычислить коэффициенты полинома 7(г) и затем искать Решение как линейнУю комбинацию вектоРов Ваге согласно схеме п. 4, а) 9 86. При больших степенях г происходит сильное уничтожение значащих цифр. Х, — 0.23400936 Ха — 0.64639927 Хз 1 2463278 Хо — 1.2571934 Хш — 1.2577816 Մ— 1. 2577930 Хаа — 1. 2577936 0.39001560 0.03264644 0.0430531 0.0436358 0.0434862 0.0434873 0.0434873 0 0.54602184 0.52125464 1.0292!17 1.0389835 1.0391543 1.0391655 1.039!661 0 0.70202808 0.75775989 1А685821 1.4821027 1.4823759 1.4823918 1.4823926 $88] ллгогием, нлилячший в смысле втового кгитвгия 57! Значительно более удобнзя вычислительная схема получается, если перейти к полиному е,(С).
Имеем е, (С) = 1 — (1 — С) с,, (С) = в р ~Т1(СС) 2 ]С о Тв-~ Ю+ оТа-а(]С)1- Положим е,(С) = я ае,(С) =,, ~Т,(СС) — 2 ]С аТ,, (тС)+аТ, (Я~. Полиномы Тс("СС) связаны рекуррентным соотношением Тс (; С) = 2 С С Тс, (СС) — Тс - а (С С) с коэффициентами, не зависящими от номера полинома. Поэтому любая комбинация нескольких соседних полиномов Чебышева связана соотношениями такого же вида. В частности, ес(С) = 2уСес,(С) — е;,(С). Умножив на еа и переходя к полиномам е;(С), получим ес(С) = 2(']с ЯСес, Я вЂ” вес аЯ=(1+а) Се;, Я вЂ” ае; аЯ, — '1 а+ г' а-~ ибо 2С] а=21 а = — 1+а.
При этом е,(С)=( ) (С вЂ” 1)+1, еяЯ=Се,Я+ (С вЂ” !). Таким образом, последовательные приближения можно вычислять пэ рекуррентным соотношениям х (1+2)(вх 1+6) охС 2 (согласно п. 8 $ 86), начиная с начальных приближений Х, и Хгн которые вычисляются по формулам х, =- х+( ' -'-" )е (вх+ а — х) Ха = Вхг + 0+ - (ВХ+ б Х). При численном осушествлении алгорифма, наилучшего в смысле 2-го критерия, нужно располагать такой же информацией о расположении собственных значений матрицы коэффициентов, как и при пользовании алгорифмом, наилучшим в смысле 1-го критерия. Мы покажем ход процесса на примере системы (9) $23, подготовленной так же, как на стр, 669. (гл. )х УНИВЕРСАЛЬНЫЕ АЛГОРИФМЫ Здесь а = 0.26204959. Имеем Хо 0 Х, 0.6844342 Х, — 1.5527282 Хй — 0.7490792 Ха 1 2636344 Х>4 1 2571287 Х, — 1.2578043 Х„ — 1.2577941 Х,а — 1.2577935 0 1.1407237 — 0.4096498 0.3334810 0.0348866 0 2.0533026 0.6343461 1.6324174 1 4668835 0 1.5970131 0.3597126 1.1875589 1.02669 ! 7 0.0438702 0.0434744 0.0434870 0,0434875 1.0393853 1.0391495 1.0391660 1.0391665 1.4826318 1 48237!9 1.4823925 1.4823930 й 89.
Прием А. А. Абрамова ддя ускорения сходимости метода последовательных приближений при решении систем линейных уравнений У Х(4йй) . 2Х(й 2 Х(й), (2) где Х< '+ ' второе последовательное приближение, построенное из Х( ' (йей) <й> т. е. Х<4-,4> ВХ(йь))+ О Х'й4 0 = ВХпч+ О. (3) Таким образом, В;шаг требует применения двух В-шагов и составления одной линейной комбинзции. Далее, В;шаг заключается в построении приближения Х< + ' по =' (й 4-4) формуле дна+4> 2Х<ййй> Х<й> (4) где Х<й+ получается из Х ' двукратным применением Ва-шага.
(йе4) (й) А. А. Абрзмовым 11] предложен следующий прием ускорения сходнмости процесса последовательных приближений для системы, записанной в виде Х=ВХ+О, где  — мзтрица, все собственные значения которой вещественны и лежат в промежутке ( — 1, 1).
Врел)я от времени нормальное течение процесса последовательных приближений, происходящего по формуле Х<"' = ВХ'"-'>+ О, (1) применение которой мы для краткости будем называть В-шагои, прерывается одним или несколькими более сложными Ва-шагами, В;шагзми, к описанию которых мы переходим. В;шаг заключается в построении приближения Х Ф по фор(йьй) и ле 573 9 891 пгивм А. А. АБРАМОВА Аналогично определяются В;шаг, В„-шаг и т.
д. Как правило, при практических вычислениях следует ограничиться употреблением лишь В, Вз В,, В„-шагов, чередуя их друг с другом в некоторой последовательности. Из описания следует, что вычислительная схема процесса Абрамова почти не сложнее вычислительной схемы классического метода последовательных приближений. Объем же вычислений для процесса В 'В,'В *В ' (т. е.
процесса, состоящего из )зр В-шагов, )г, В;шагов н т. д.) лишь немного больше, чем объем вычислений при й,+ + 2н, + 4па + 8йа шагах процесса последовательных приближений. Поясним теперь, почему применение процесса Абрамова дает лучший результат по сравнению с эквивалентным по объему вычислений результатом, полученным по методу последовательных приближений. Для этой цели вычислим множители затухания в компонентзх векторов ошибки для отдельных шагов процесса Абрамова. Ясно, что У' + '=ВУ~ 1' ~ ' ~ = 2у1 ' ~ — уно = (2Ва — Е) уно = Взуйо = Т, (В) уыо 1' = (2В~ — Е)У = В4У = Тз (В,) 1 = Тч(В) У Здесь полиномы Т,(1), Т,(1), ...
суть не что иное, как полиномы Чебышева Т, (1) = соз г агссоз А Это очевидно для з = 2, для з = 4, 8, ... это верно в силу известного соотношения Т„(1) = Т, (Т, (1) ). На рис. 20 даны графики функций гз и !Т,(1)(=(21з — 1(, на рис. 21 графики функций гь и ~ Т,Я~, на рис. 22 графики функций ! Т.', (Г) ! и ~ Т, (1) ~. Рассмотрение этих графиков позволяет сравнить множители затухания компонент в разложении вектора ошибки для почти эквивалентных по объему вычислений двух В-шагов и одного Ва-шага (рнс. 20), четырех В-шагов и одного В -шага (рис. 21) и, наконец.
двух В;шагов и одного Вч-шага (рис. 22). Именно из рис. 20 мы видим, что два В-шага выгоднее одного В; 1 шага при 0 (1 ч., = 0.58. Но один В;шаг значительно выгод- У 3 нее двух В-шагов при 1) =. Поэтому „подавив" достзточно коме' 3 поненты вектора ошибки для собственных знзчений из промежутка 574 1гл. гх УНИВЕРСАЛЬНЫЕ АЛГОРИфмы 0 ( 1 ( = методом последовательных приближений, следует перейти 1 -тг 3 к В;шагам. Далее, В;шаг оказывается более выгодным, чем два Вз-шага для промежутка 0.89(1( 1 (рис.
22). Из рис. 21 следует также, что один В4-шаг выгоднее четырех В-шагов для промежутка 0.86 (1(1. Поэтому применение В4-шагов следует начинать после того, как В и В;шагами уже подавлены компоненты вектора ошибки для промежутка 0 (1(0.89. Рис. 20. Ряс. 21. Рис. 22 Время от времени следует возвращаться к низшим шагам, для подавления накопившихся ошибок округления на компонентах, отвечающих малым собственным значениям. Мы не приводим здесь численного примера, так как метод Абрамова укладывзется как частный случай в группу ВТ-процессов, имеющих более единообразную вычислительную схему.
ф 90. ВТ-процессы Метод Абрамова может быть несколько обобщен без усложнения вычислительной схемы. Именно, процесс Абрамова можно рассматривать как частный случай „ВТ-процессов", которые заключаются в следующем. Пусть лана система Х = ВХ+ 0 с матрицей В, имеющей вещественные собственные значения, расположенные в интервале г — 1.
1). Пусть далее дана последовательность букв В и Т, начинающаяся с буквы В. Например, ВВ ТТТ ВТ ВТ ВВ ТТ .. В соответствии с этой последовзтельностью строим последовательные приближения Х~1, Х, АМ 1, ..., задавшись начальным приближением Х11 произвольно. Приближение Хг 1 строим следующим <41 ро ВТ-пвоцвссы 575 ф 901 образом: если в последовательности (2) на и-м месте находится буква В, то полагаем Хгю = ВХ(ь-11+ О. (3) Если же на и-м месте находится буква Т, то полагаем Хы1 = 2 (ВХ~" '1+ б~ — Хы '1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
