Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 91
Текст из файла (страница 91)
для последовательных полиномов Чебышева наименьшими корнями будут М вЂ” 0.147М гз= 4 М 0.067М, ... 2 — ггЗ »» —, М. 16»з М 2 — )'2 «г= ««в 2 ' ' 4 Поэтому за счет полиномов второй степени мы можем расширить зону действия метода от — до 0.147 М, за счет полнномов третьей М 2 степени расширить ее до 0.067М и т. д. Таким образом, для матрип с обусловленностью, меньше чем 15, можно ограничиться лишь полиномами до третьей степени включительно.
Пели»он чееншеба Рис. 17. Выбор полиномов первой степени можно осуществить, например, гМ так. На промежутке 1 — . М ) возьмем точки а, = М ) а, ) ... ( 2 ... > а > —, и положим у®(1)= 1 — —, й=О,..., р,. (рис. 17) М в Р ав 36 за», зг«д. К. Ф»дд»«»» в, н, Фалд««»» близким к нулю наименьшим корнем обладает полинам Чебышева для промежутка (О, М), т.
е. полинам 562 [гл. ~х УНИВЕРСАЛЬНЫЕ АЛГОРИФМЫ Затем, для построения полиномов второй степени выберем после- М довательность точек Ьз = —, ) Ь, ) ... ) Ьр, — — 0.147М и положим е — ме !аь!(Е)=1 — —,, (Д=р,-)-1, ..., р,+р,) ьь( — Мз (см, рис. 18). Эти полиномы, очевидно, удовлетворяют первым двум требованиям, наложенным на полиномы 8(ал!(Е), и обращаются в нуль пРи Е=ЬА Для обслуживания зоны от 0.147М до 0.067М служат полиномы 3-й степени ~, !(е) = !А> (Еа — МЕ) (2Š— М) (е~~ — Мс„) (2с .
— М) где с. точки между Еа и Ез. Мы не будем входить в подробности относительно выбора полиномов более высокой степени, так как ниже мы рзссмотрим другие, более просто выполняемые способы подавления компонент, отвечающих собственным значениям, близким к нулю. Отметим только, что во всем изложенном взжную роль играет знание числа М. Ошибка в оценке релелем этого числа в сторону уменьшения чееелаееа имеет некоторую опасность. Ошибка же в сторону увеличения может Рис. 18.
лишь несколько увеличить объем работы. Выбор точек деления обусловливается требовзнием точности с одной стороны и желанием иметь их кзк можно меньше (обслуживать зону подлиннее) с другой стороны. Приведем результат использовзния полиномов низших степеней к нахождению решения системы (9) $ 23. Здесь М = 2.62. Взяв а, = 2.62, аз= 2.30, аз= 2.00. ае= 1.70, аз= 1 40 Ьг=1 20 ба=О 9 Ьз=О 6 бе=0 3 получим Х' = ( — 1.2284428, 0.0473912.
1.0233490, 1.4591532)' Приближение Х' получено в результате применения 13 итераций. Длина вектора ошибки построенного приближения составляет 1.85% длины вектора ошибки начального приближения Ке=(0, О, О, 0)'. $ 861 газличныи вогмы.пговедвния янивввслльных алгогивмов 663 Описанный прием выбора подавляющих полиномов является довольно грубым, и как мы увидим ниже, при более тщательном выборе полиномов может быть получен лучший результат при использовании того же числа итераций.
5 86. Различные формы проведения универсальных алгорнфмов Прежде чем перейти к описанию конкретных универсзльных алгорифмов, коснемся вопроса об их численном осуществлении, ограничиваясь рассмотрением одного шага процесса при различных способах задания полинома, определяющего этот шаг. 1. Известны коэффициенты полинома Й(г), или, что то же самое, коэффициенты й (Г). Пусть Й (г) = сег + с,Г + ... + с В этом случае вычисление Х' можно производить двумя следую- шими способами. а) Прежде всего вычисляется невязка г = à — АХ. Затем последовательно вычисляются векторы Аг, Ааг, ..., А' г и, наконец, Х' находится как известная линейная комбинация уже известных векторов Х' = Х+ с,,г + с, аАг+ ...
+ г. А" 1г. (2) При таком построении вектора Х' возможен рост ошибок округления с одной стороны, а также уничтожение значащих цифр с другой стороны, ибо, как правило, коэффициенты с„, с,...., с,, имеют разные анаки. Ь) Вычислив г = Р— АХ, находим последовательно векторы 2о= сог Е, = АЛа+ с,г 2,, = АЛа а+ св аг. Ясно, что л(А) г= 2,, и, следовзтельно, Х' = Х+ Л, Этот способ есть по существу не что иное, как применение известной схемы Хорнера. При таком построении вектора Х' ошибки округления сказываются несколько менее, чем в предыдущем способе. 2.
Известны корни а„ ..., в, полинома л (Г). Тогда 564 [гл. |х уннаегсалъныв Алгогиемы В этом случае вектор Х' может быть нзйден как последний член Е следующей последовательности векторов: 7, = Х+ — (Р— АХ) 2; = К|,+ — (гт — АЕ|,) (1 = 2, ..., з). 1 Действительно, при всех 1 Х' = — Х'+ — (г". — АХ'), ы где Х* — точное решение системы, и поточу Л вЂ” Л| = (Х* — 2;,) — — А (Х" — 2;,) = (Š— — А) (Х* — 2, |). Следовательно, Х* — 2,=(Š— — А)...
'[Š— — А)(Х' — Х)= = д (А) 1' = У вЂ” й (А) АУ = )' — Ь (А) (Р— АХ) Е, = Х' — У+й (А) (Р— АХ) = Х[ — Д (А) [Р— АХ) = Х'. Эта схема впервые описана в работе Ричардсона [1[. При применении этой схемы наиболее опасными в смысле влияния ошибок округления являются шаги, соответствующие малым корням е;. Целесообрззно располагать корни в порядке их убывания.
3. Известны рекуррентные соотношения для определения полинома хг(1). Мы рассмотрим случай наиболее часто встречающихся трехчленных соотношений. Пусть д(()= — д,(Г), где а'о Ю = 1 а| (Г) = я Г+ 1 (6) а(~) = [от+(Р;-[-1)[а (Г) — М (Г) (| = 2. " з). Вид рекуррентных соотношений выбран так, чтобы все полиномы д|(1[ были нормированы условием а|(0) = 1. Строим последовательность векторов (7) Х;= Х;,— а;(г'' — АХ;,)+р|(Х;,— Х; з) при Хз = Х и Х, = Хе — а, (с — АХ). Тогда Л"' = Х,. Действительно, из (7) следует, что )гг= 'г'|,-[-а;Аг';,+р|(1', | — У; а). Отсюда заключаем по индукции, что 1| з|(А) ) 0 $861 вазличныв еовмы пговвдвння яниввгсальных ллгогиемов 565 В частности, и потому 1 е з е (А) ) о Х, = Х'.
Следую1пне приемы относятся к системе, подготовленной к виду Х= ВХ+ О. 4. Известны коэффициенты полинома .г(~), именно У() 0~ +~! + ' ' ' +13 — 1' (8) (9) Ь) Вычислив невязку г, строим последовательность векторов ~0 1ОГ 21 = В21 1+ 61г (1' = 1, 2, ..., е — 1). (10) Тогда Х =Х+Г, ). 6. Известны коэффициенты полинома е(1), именно е(1) = а ге+ а1Р '+ ... +а„. (11) а) Вычисляем последовательные приближения Х,=Х, Х, = ВХО+ +О,..., Х,=ВХ,,+О н составляем нх линейную комбинацию а,Х, + а,хе, -+ ...
'+ а, Х . (12'1 Она и будет искомым приближением Х'. Действительно, пусть УО Х ХО' 11 Л Х1' '''' )О Х Х' Тогда =(ао+а,+ ... +а,)Х вЂ” аОВ'1'о — а,В' )ге — .. — ае10=. = е (1) Х" — е (В) )го — — Х' — 10+ ((В) (Š— В) УО = = Хо+ ((В)(ВХО+ Π— Ло) = Х'. Ь) Вычисляем последовательность векторов по формулам ео — — аОЛ' Уг,01= Вкг+аг 1Х+(аО+ ... +а1)О (1=0,..., з — 1). (13) Тогда последний вектор е, будет равен Х'. а) Вычислив невязку начального приближения г = ВХ+ Π— Х, вычисляем векторы Вг, ..., В' г и находим Л в виде известной линейной комбннацзи уже известных векторов Х'=Х+б,,г+ ...
+6,В' 'г. 566 (гл. ох УНИВЕРСАЛЬНЫЕ АЛГОРИФМЫ 6. Известны корин е,...,, е, полинома е(г), Тогда е(1) = (Г ог)... (à — оо) (! — .,) ... (1 — .,) ' (14) ибо е (1) = 1. Переход от вектора Х к вектору Х' можно осуществить в а шагов, полагая на 1-и шагу ео(1)= ! ', ибо при применении нескольких 1 — о, шагов полиномы ео(1) перемножаются. При этом Л(1) = —, так как ! 1 — ог Следовательно, вектор Х' находится как г-я член хо последовательности г",; = г.;, + — (ВЛ;, + й — г".;,), (16) начнная с Ао=Х. 7. Известны рекуррентные соотношения для определения поли- нома г'(г).
Пусть 7(!)=у,,(г), где уо (1) = Р ° 7 (1) = аФ+ Ь а(1)=(ггг +)А!- (г) — 7г- (1) (16) Вычисляем последовательность векторов г = ВХ+ 0 — Х, Ао — — рог, Е, = а1Вг+ ~,г, Лг=а!ВЕг,+~,Л;,— То2; я (1=1, 2, ..., в — 1). (17) Ясно, что ~,, =7'(В) (ВХ+ ~ — Х) Х' = Х+ х., 8. Известны рекуррентные соотношения для определения полинома е(1). Пусть е(1)= ео(Г), где ео (1) = 1, е, (П = а,1+ р, е; (1) = (а/ + ~о) е;, (1) — 7;е;, (1).
Предполагается, кроме того, что все полиномы е;(Г) удовлетворяют условию е,(!) = 1, так что а,+р,=1, ко+~о — 7;= 1, 1= 2,..., г. В этом случае Х' будет равен вектору Х, в последовательности Хо = Х, Хг = аг (ВХо+ ~) + 1ЬХо Х,=а;(ВХ;,+от)+~!Ха,— 7,Хг м Действительно, в силУ Условий а, + ~, = 1, а;.+ ~о — Тг = 1 имеем Х" = а, (ВХ'+ О) + ~),Х" Х'=;(ВХ'+а)+~гХ' — Т;Л . й 87] ' ллговием, наилвчший в смысла пвввого квитввия 567 Вычитая, получим 1', = а,ВУе+ ~, 1', = е, (В) 1'е У; =(;В+ р Е) У;,— Т;У!,, откуда по индукции У; = гч(В) У„, в частности, Уа = е (В) Уе и, следовательно, Х' = Х,. Как правило, наиболее удобными оказываются схемы, использующие рекуррентные соотношения.
5 87. Универсальный алгорнфм, наилучший в смысле первого критерия ') Пусть известно, что все собственные значения матрицы А расположены в промежутке(ш, М), 0( гл с. М, и различны. Подготовим систему АХ= Р к виду Х= ВХ+0 так, чтобы собственные значения матрицы В расположились в симметричном интервале с центром. 2 в нзчале координат. Очевидно, что для этого нужно взять л = —, М+ гл' В = Š— ИА, О = — ЬГ. Тогда все собственные значения матрицы В 1 11 М+т попадут в интервал ~ — †, — !, гле 7 = т М вЂ” т ) 1. Построим универсальный алгорифм Х,= Х,+7,,(В)(ВХа+() — Х,), подобрав почином У, ,(1) так, чтобы при данной его степени г — 1 было обеспечено максимально возможное подавление компонент для всего класса матриц В с собственными значениями, заключенными 1 1т в промежуток ( — —, Т Для этого в качестве полинома е,(г)=1 — (! — 1)7,,(1) нужно, очевидно, взять полипом, наименее уклоняющийся от нуля на про-- 1 1~ межутке ~ — —, — ), нормировзнный условием е,(1)=1.
т т Таким полиномом является т,(тг) т,®= (2), а) л1. Ш. Б приап (1!. [гл. гх :568 яниввгслльныв ллгогиэмы где Т, (г) = соэ з агссоз |. 6 На рис. 19 дан график Тэ(г) при ( = 4. Полиномы Тг(1) связаны простыми рекуррентными соотношениями. Действительно, для полиномов Чебышева такими являются соотношения Т,а=2(ТГ,(1) — Т, з(Г) при Те Я = 1, Т, Я = С. Поэтому Т,(г)=~! + Т ~ ЕТа г(Г) — Т (г — Т, з(г), Те(г)=-1, Тг(1)=(. Тз (1) 41 (3) В соответствии с рекуррентными соотношениями (3) универсальный алгорнфм (8 86 и. 8) строится по формулам т л,=вл",+а тг(1) ) — Х; з (1=-1, 2, ..., з), (4) Т, (1) Для вычисления по формулам (4) нужно предварительно заготовить по рекуррентным соотношениям значения — ' . При возра- Т з(;) т,(т) стающем г зти значения довольно быстро стре- мятся к пределу Рис.
19. в -(- — )г'- — 1)'. Быстротз сходимости описанного процесса при э -ь со будет иметь порядок 1 2 ( + Ута — 1)'+(т — Утз — 1)' так что процесс сходится значительно быстрее метода последовательных приближений, для которого быстрота сходимости будет (-'. 25 Так, например, при у= —,' (( '=0.96) будет 24 1 3'8 т (1) (4 з ~з~ 4 /24 т" в то время как (-'=~ —,. ) . 12э) ' $87) ллговнэм, наилэчший в смысля ппгвого кгитевия 569 При пользовзнии формулами (4) вместо того, чтобы брать все увеличивающиеся значения лля 5, можно брать не очень большие 5, но повторять процесс несколько раз, принимая приближение, полученное в конце цикла, за начальное приближение нового процесса.
Для данной матрицы А осуществить подготовку к зилу, позволяющему использовать описанный процесс. не просто. Действительно, если для оценки числа М можйо воспользоваться хотя бы оценкой Гершгорина, то опрелеление числа и оказывается гораздо более М+и трудоемким. Процесс же определяется выбором числа 7 = „ М вЂ” и которое быстро приближается к елиннце при и -ьО, и слишком грубый выбор 7 может сильно замедлить быстроту сходимости процесса (если истинное значение 7 будет значительно больше взятого на основании грубых оценок М и и). Описанный процесс по существу дела идентичен тому, с которым сравнивался метод наискорейшего спуска при выводе оценок лля быстроты сходимости.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
