А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 60
Текст из файла (страница 60)
(1) В ряде случаев постоянные у, н у, могут быть найдены точно, т. е. существуют такие элементы хЕН, для которых в (1) до- 324 стпгается равенство. В других случаях для нахождения у, и у, используются вспомогательные процессы и зтн постоянные находятся приближенно. Использование неточной априорной информации приводит к уменьшению скорости сходимости, а в некоторых случаях и к расходимости метода. Целью настоящего параграфа является изучение влияния неточного задания априорной информации на скорость сходимости перечисленных выше итерационных методов.
Ограничимся рассмотрением самосопряженного случая, т. е. предположим, что оператор ВВ 'А самосопряжен в Н. Пусть вместо точных значений т, и у, в неравенствах (1) заданы некоторые приближенные значения у, и у,. Рассмотрим двухслойные и трехслойные методы, итерационные параметры для которых будем выбирать по заданным у, и у,. Напомним формулы для итерационных параметров.
Для двухслойной схемы (2) параметры метода простой итерации определяются по формуле ть=т,=2/(у,+у,), й=1, 2, (3) а параметры чебышевского метода строятся по формуле ть — — т,Г(!+р,рь), р„~%„", й=1, 2, ..., и, ро=(1 — $)/(1+$), $=Ыу,. Для трехслойной итерационной схемы Ву„, =а„, ( — та+,А) уь+ (1 — аз+1) Вуц г+а„+,та+а, й=1, 2, ..., (5) Ву, = ( — т,А) д, + т,! параметры полуитерационного метода Чебышева определяются по формулам та= — то, аь~,—— 4((4 — р',а„), й=1, 2, ..., а,=2, (6) а параметры стационарного трехслойного метода задаются формулами т~ = т„а~ = ! + р'„й = 1, 2, ..., р, = (1 — )~ т ) Я 1 + )~ $. (7) Из общей теории итерационных методов, изложенной выше, следует, что для погрешности гь=у„— и рассматриваемых методов справедливы оценки: 1) для метода простой итерации ( г„~!в ~ ( шах ) 1 — т,1))' ~ г, !)о; т,<с<т, (8) Зйб 2) для чебышевского двухслойного метода и полуитерационного метода Чебышева !! г„(~> ( д„шах 1Т„(='т),'( г, (гм и <г<т ~ Ра (9) где (г„= 2оа!(1+ ртьа); 3) для стационарного трехслойного метода ~г„Ц(р", п х =,Т„~=~+ — , 'и„Ч вЂ” '~ ~~га1,.(10) ", +Р*"~ ° / 1+', ( .) Рассмотрим сначала случай, когда у, и у, являются приближениями для у, и у, соответственно снизу и сверху, т.
е. т <ут<ув<у ° (12) В этом случае, как легко проверить, будут выполняться неравенства — 1(а((г(1. Из (1!) получим, что скорость сходимости метода простой итерации будет определяться величиной р"„чебышевского двухслойного метода н полуитерационного метода Чебышева — величиной д„, а стационарного трехслойного метода — величиной Р", (1+ и (1 — р,')Я1+ р',)). Итерационные методы будут сходиться, но скорость сходимости уменьшится. Рассмотрим пример, лля которого выполняются условия (12).
Пусть тт= рг(1 — а), та=та О~а< 1. 326 Эдесь Т„(х) и У„(х) — полнномы Чебышева первого и второго рода, у, и у,— точные значения постоянных из (1). Приведенйые оценки определяют скорость сходимости рас- сматриваемых методов в случае, когда итерационные параметры вычисляются по неточной априорной информации.
2. Оценки скорости сходимости методов. Оценим теперь мак- симумы модулей полиномов, входящих в оценки (8) †(10). Для этого сделаем в (8) — (10) замену, полагая х=(1 — та!)!р„и обо- значим а =(1 — тау,)ур„6 = (1 — тат,)/ра. Тогда оценки (8) — (!О) будут иметь вид )!гД,(ра( шах !х))а!!га)р, ',а Сх~ь !гЯ =д„шах )Т„(х))))г,!(о, а<х<Ь й ))г„(~~>(рГ шах ! Р', Т„(х)+:1, 'У„(х) !(г,)!и. аах<Ь! 1+Рт 1+Р получим идах 1Т„(х) 1=Т„( —,)= —,~ д!д 1.
1 а<а<о Ро 4» Рд шах 1к(= —,, 1 а<к<б ро идах ! Ь л (х) а<л<Ь Подставляя этн оценки в (11), найдем /- ~д» !!г»!!р~ —, !!го,'!р, Ро (13) !1~.!!р = Ф!1*.Ь, 4» бг„"(р~ (~р/рд)" (1+» (1 — рд)!(1+р7)) !! г 1дь (14) Заметим, что если Н вЂ” канечномерное пространство, то можно указать такое "!начальное приближение уо, для которого в оценках (13), (14) будут достигаться равенства. Найдем теперь условие, при выполнении которого можно гарантировать сходимость рассматриваемых итерационных методов, построенных по неточной априорной информации.
Так как отношение д /д„ стремится к нулю при » - оо лишь при условии рд > рд, а это условие эквивалентно требованию Ро > Ро, то из (!3) †(15) следует, что итерационные методы будут сходиться, если выполняется неравенство Ро < Ро (!6) Используя определения Ро, а и Ь, получим, что (!6) будет иметь место, если !1 — тоуд! < 1 !1 — тото! < 1.
327 В этом случае а= — 1, Ь < 1. Поэтому для погрешности рассматриваемых методов из (11) получим следующие оценки: !! г» !!р ~ Ро !! го !!р (гл!!паул!! го!!р, !! г»!1р ~ Рд (1+»(1 — Р д)/(1+ Рд)) !! го !!р. Из соответствующих формул для числа итераций получим, что для метода простой итерации в случае неточного задания у, число итераций увеличи- вается примерно в 1/(1 — и) раз по сравнению с точным заданием уд, в то время как для чебышевского двухслойного метода и полуитерационного ме- тода Чебышева число итераций увеличивается лишь в 1/ у' 1 — а раз.
Пусть теперь условия (12) не выполнены. Вэтом случае шах(!а!, 1Ь!) > 1. Введем следующие обозначения: 1 — „=шах (! а 1, ! Ь !), Ро Ро Ро Используя эти обозначения, а также соотношение между полиномами Чебы. шева первого и второго рода У„(х) =(Т'„„(х) — !) П' !(Т, '(х) — 1)д1д, ! к ! ~1, решаа зтн неравенства, найдем 71тте > 7 . (17) Итак, если выполнено условие (17), то итерационные методы, построенные по неточной априорной информации, будут сходиться.
Из сказанного выше следует, что в случае конечиомерного просгрансгва Н условие (17) является и необходимым для сходимости методов. Оценим теперь реальное число итераций, достаточных для достижения заданной точности в. Будем, как и раньше, через п обозначать число итераций для случая точного задания априорной информации, через и обозначим теоретическое число итераций, вычисленное по формулам соответствующих теорем по неточной априорной информации, а через по обозначим реальное число итераций, которое достаточно для достижения точности в.
Из формул (13) — (15) следует, что реальное число итераций и' должно определяться из условий: 1) для метода простой итерации из условия р, (ер,"', 2) для чебышевского двухслойного метода'и полуитерационного метода Чебышева из условия е)„(а()„". Легко убедиться в том, что имеют место неравенства по~~я, по) п, причем число итераций и может быть больше или меньше п. Так как единственной количественной характеристикой итерационного метода, которая может быть заранее вычислена, является теоретическое число итераций и, то с точки зрения реализации методов важно оценить, во сколько раз реальное число итераций и* будет больше й.
Для теоретического сравнения качества итерационных методов нужно оценить отношение по)п. Получим требуемые оценки для одного примера. Пусть 7, и те — приблимвинв длЯ те и 7е соответственно свеРхУ и снизУ уе = (1+ а) те, 7е = (1 — а) т„а) О. (18) Из условия (17) и естественного требования те~те получим, что методы будут сходиться, если выполнено условие а < 1п щ) — й), (1 — 1)7(1+й)), Для рассматриваемого примера будут иметь место неравенства пепел~в.
Действительно, нз (18) получим н, следовательно, Ро~КРо=(1 — й)/(1+В), Ребр!=(1 — У а))(1+)7 $), Чл~чл Отсюда следует, что л)й. Оценим теперь величины, входящие в неравенства (13) — (14). Так как т=247е+то)=то!(! — аро) < то то=2!(те+те) 328 то 1/ре =шах (1 а1, 1Ь!) =(а) =(тото — 1)(ро.
Опуская несложные выкладки, получим 1 — е Ро — а Ро===— 1+ $ ! — аро а а 1 — — (1 — $) 1- —,(1 —  — = тото — 1 = !в Ро (1 — Ро) = !в (! — Ро) Ро !+а 1 — аро Ро — а Ро 1+)(7 1 — Ьо+Р'(! — а)(1+Р~)' (, Ра„/ $+ ,/! ао 1У( 1, (1, а) Ц Рг 1 (1 ро) !л (1+а) У В+ У 1 — а' — у'" (1+ )р'2+)(т: ' — —" — 1(( — аП вЂ” (1+ ) вы!+ У0 1 (1 Ро). 1 — а+ (1+ а) $+ 2 )( (1 — ') 2 Рассмотрим сначала метод простой итерации. Из теоремы 2 й 3 гл.
о'1 и из (13) получим для числа итераций л', й и л метода простой итерации следующие оценки: 1п е )п (1/е) - 1п е !и (1/е) и=в и== !иро 1 — Ро ' !про 1 — ро 1п е (и (1/е) 1п(Ро(ро) 1 — Ро/Ро" Подставляя сюда полученные выше выражения, найдем 1+ а и' 1 — аро и ! с' (1 оо) л 1 а ! ое) $ $ Если ахеей, где с < 1, то отсюда получим и" = и/(1 — с), и*ю л((1 — с).
Итак, если игаса, то реальное число итераций ло для метода простой итерации в 1/(1 — с) раз больше теоретического числа итераций и, которое вычисляется по неточной априорной информации. Рассмотрим теперь чебышевский метод и полуитерационный метод Чебышева. Из определения о)„и о(„* получим и 1+ 'оо 2( / ")о Чо Рт 1 +Рс ! + (Рг/Рг) Поэтому для числа итераций и* найдем следующую оценку: 1и (0,5е) 1п (2/е) !и (ро/Рг) 1 — р,/ро 329 Далее, из теоремы 1 $ 2 гл. Ч1 и теоремы 1 2 2 гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
