Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 90
Текст из файла (страница 90)
отвечающих близким к нулю собственным значениям, так как д(О) = 1. Это совершенно естественно, так как наличие близких к нулю собственных значений матрицы А свидетельствует о плохой обусловленности системы. Выбор полинома й(г) (а вместе с ним н п(Г)) можно осуществлять, применяя другой критерий, основанный на сравнении компонент вектора ошибки Г с компонентами невязки г=Р— АХ=Аг' приближения Х. Пусть г=б,и,+ ... +б„и„.
Тогда п [гл. ~х УНИВЕРСАЛЬНЫЕ АЛГОРНФМЫ у =-'"-д(л,)и,+ ... +',.д(л„)и„= =б,( —,' — Д(),,)) и,+ ... +Ь„( — „' — Д(Л„)) и„. (4) При этом подходе естественным становится такой выбор полинома Ь(О, чтобы его значения на промежутке (О, М) возможно менее 1 отклонялись от значений функции —. Оба указаш<ых критерия по существу близки друг другу. Именно.
выполнение одного нз них влечет выполнение, в большей нли меньшей степени, второго. Однзко второй критерий предъявляет более сильные требования к подавлению компонент, отвечающих малым собственным значениям. действительно, если — — Ь(ЛД~ < о (о ) О), ~й()ч) ~=~1 — Л,.Д(),г), <бЛг то (б) Х=ВХ+О, Первым критерием целесообразно руководствоваться в тех случаях, когда пользование формулой (1) является элементарным шагом в итерационном процессе, ибо множители за~ухания при проведении нескольких шагов итерационного процесса просто перемножаются.
Если же формула (1) применяется всего лишь один раз, то имеет смысл руководствоваться вторым критерием, если есть основания предполагать, что компоненты исходной невяэкн (например, свободного члена с') имеют коэффициенты одного порядка в своем разложении по собственным векторам. В случае, если о распределении собственных значений матрицы А имеются какие-либо дополнительные сведения, можно ставить вопрос о наилучшем выборе полинома л (Е) данной с~висни в смысле первого или второго критерия. Так, если известно, что все собственные значения заключены в промежутке (лт, М), то наилучшим в смысле первого критерия будет полином л (г), наименее отклоняющийся от нуля на промежутке (т, М), нормированный условием д (О) = 1, наилучшим в смысле второго критерия будет полипом л(~), наименее 1 отклоняющийся от — в том же промежутке.
Ниже мы рассмотрим универсальные алгорифмы, основанные на осуществлении такого выбора. Для системы, подготовленной к виду 557 $84! пРием л. А. люстеРникА при условии, что все собственные значения матрицы В лежат в промежутке ( — 1, 1), один шаг универсального алгорифма производится по формуле х' = Х+У(В) (ВХ+ а — Х(, (6) Векторы ошибки двух соседних приближений в этом случае связаны соотношениеи 1" = — У' +)(В)(В>' — У) = ( †( — В)г(В))'г' = е(В)!', где е(г>= 1 — (! — !)>'(1).
Таким образом, здесь иоанном е(>) должен удовлетворять требованию е(1) = 1. Множителями затухания будут значения е(р,), ..., е(р„), где ро ..., р„собственные значения матрицы В. Критериями для выбора полинома е(г) или поли- нома )'(!) являются, во-первых, возможно малое отклонение от нуля значений полинома е(г) на промежутке ( — 1, !), нормированного условием е(1) = 1, или, во-вторых, возможно малое отклонение 1 полинома 7'(>) от функции 1 на том же промежутке.
й 84. Прием Л. А. Люстерннка для ускорения сходнмостн метода последовательных приближений прн решении системы линейных уравнений ') При решении системы Х= ВХ+ 6 методом последовательных приближений в самом ходе процесса получается некоторая информация о расположении собственных значений матрицы В.
Именно, если наибольшее цо модулю собственное значение р, матрицы В оторвано от остальных собственных значений, то оно может быть практически определено из отношений одноименных компонент векторов Х вЂ” А . (л 1) Д) и Х' > — Х> >. Действительно, Х> ) — Х' '=В (Х,— Хе), Х =В (Х,— Хз), где Х„начальное приближение. Зная и,, можно уничтожить коэффициент лри собственном векторе (>1 в векторе ошибки, исходя от приближения Х, уже попо строенного методом последовательных приближений. Для этого до- А) — >А 11> статочно взять, при переходе от Х' ' к следующему приближению Х в качестве полинома г (г) константу †.
действительно, соотРР1 1 1 Р1 ветствующий полипом е'>(г) равен ! — —, так что е( >(р,)=>>. !Е) 1 — Г и Р.1 Последний шаг тогда будет осуществлен го форму.че Х( "о=Х1 >-+- — — (ВХы> — !-Π— Х( )) = 1) Л. А. Л ю с т е р н и к > Ц :558 [ГЛ. (Х УНИВВРСАЛЬНЫВ АЛГОРИФМЫ где Х( )=ВЛ +)т есть следующее за Х( ) приближение метода (в) 1) (в) (а) последовательных приближений.
Если метод последовательных приближений проводится по фор- муле то формула (!) приобретает еще более простой вид Х(ат1) Х(а)+ 1 Вва 1- и, (2) Х( ) = (1.53490847, 0.12200958, 1.97509985, 1.41289889)'. Вычислим — †(0.00005656, О, 0.00005656, 0.00005656)'. Таким образом, Х(') = (1.534965, 0.122010, 1.975156, 1.412955)'.
Указанное решение совпадает с точностью до ! ° 10 с найденным по методу Гаусса. Отношения 7-й и 6-й итераций дают (9 53) для р, значение р) = ОА792. Так как Х()= (1.52533. 0.12201, 1.96551, 1.40333)' — †(0.00962, 0.00002, 0.00963, 0.00960)', 'Х(1) = (1.53495, 0.12203, 1.97514, 1.41293)'. Иа табл, Ш. 1 видно, что Х(') ближе к точному, чем Х(ы). Компоненты вектора ошибки для приближений, найденных по формулам (1) и (2), будут, очевидно, иметь порядок О() )Га(~), где ра следующее за р, по величине модуля собственное значение матрицы В. Проиллюстрируем описанный прием на примере 9 30.
На основе табл. 1И.! в 9 53 (пример 3) было определено р1=0А800 из отношений компонент 14-й и 13-й итераций вектора б=(0.76, 0.08, 1.12, 0.68)' матрицей В. Из той же таблицы $85) пОдАВление пги помощи полиномов низших степеней 55У Прием Люстерннка может быть применен н к цинлическому одношаговому процессу, ибо этот метод, применяемый к системе Х= ВХ+ О, равносилен методу последовательных приближений для некоторой эквивалентной системы. $ 85.
Подавление компонент при помощи полиномов низших степеней Рассмотрим в свете идеи подавления компонент приемы подготовки системы АХ=В с положительно-определенной матрицей А к применению метода последовательных приближений. Для системы, подготовленной к виду Х= Х+ И 1Р— АХ) = = гс — ИА) Х+ ИГ, формула метода последовательных приближении будет Хно = Х1 и+ И(à — АХ~ 1).
В этом случае коэффициентами затухания будут значения 1 — И)ч при 1=1, ... а. Все коэффициенты затухзния. очевидно, будут меньше единицы, и. 1 М следовательно, процесс будет сходящимся, если — ) —,, т. е И 2 2 И ( — 1рис. 15). Быстрота затухания компонент на разных частях М Рнс. 15. промежутка 1гн, М) будет различной и наибольшая быстрота, оче- 1 / 1 видно, будет в зоне, примыкающей к точке — 1если И) — ), илн и1 М)' 1 А на правом конце промежутка ~если И ( — ). Наиболее медленное затухание будет на правом конце промежутка, если И ( — — , 1 М -Г Ач 1 и на левом, если И ) .
Ясно, что для ускорения процесса. М+т последовательных приближений целесообразно время от времени. 1 ! брать И = — или И = †, соответственно, если одно из этих чисел М известно. Именно в этом и состоит описанный выше прием Люстерника в применении к подготовленной системе Х = ВХ+ Ат при  —  — ИА„ Аг = ИГ.
ббо [гл. )х УНИВЕРСАЛЬНЫЕ АЛГОРИФМЫ Действительно, собственнымн значениями рч матрицы В являются как раз коэффициенты затухания р; = 1 — Ь)ч. Наибольшим из них по модулю будет р, = ! — ЬМ или в, = 1 — йгн. Один шаг при 1 Ь = — дает М Х" "=Х'"'+ — ' (Р— АХ")) М мли, переходя к матрице В, = Х( ') -+ — [сг — (Š— В) Х~ '~] = Рг Х!Ус) + ВХ + 0 Х Х)А) [ 1 [Х(а 1!) Х(А)) 1 — Рг 1 — Р) К такому же результату мы придем, если наибольшим собственным значением матрицы В окажется 1 — Ьт, и мы положим на й+1-м 1 шагу )) = —. Довольно эффективный прием подавления компонент мы получим, если будем изменять константу 1) от шага к шагу так, чтобы корень — полинома я (1) = 1 — 1)АГ двигался по промежутку 1А) Ьь ( М вЂ”, Л!) справа налево.
При этом зона эффективного подавления 2 компонент вектора ошибки будет передвигаться, накрывая, в конце концов, весь промежуток. Если мы захотим быстро подавлять компоненты собственных векторов, принадлежацгнх собственным значениям, лежащим в проМт 2 Гмежутке (О. —,[, то нам придется брать )1) =, что, однако, будет А) ' приводить к возрастанию компонент, отвечающих собственным значениям, близким к М.
Если же стремиться строить процесс так, чтобы ни на одном шагу не происходило увеличения каких-либо компонент, то для дальнейшего сдвига зоны наиболее эффективного подавления компонент влево нужно обратиться к полиномам высших степеней. Рассмотрим грубую схему выбора полиномов а)А)(т) невысоких степеней г. обслуживающих значительную часть проне)кутка (О, М), с постепенным сдвигом зоны наиболее эффективного подавления компонент справа налево (метод „утюга", см.
рис. 16). Как мы уже /М видели, промежуток ( —, М) хорошо обслуживается полиномами 'т 2 первой степени. Известно, что из всех полиномов данной степени а, удовлетворяющих требованиям д,(О) = 1 и [п„(1) [ ( 1 при О <! ~~ М, наиболее ф 85) подавление пеи помощи полиномов низших степеней 561 соз з агссоз М вЂ” 2Е Наименьший корень этого полинома равен 1»=Майна 4, так что 4а ' Рис. 16.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
