А.А. Самарский - Теория разностных схем (1989), страница 8

п. 6), )» +хгб Ук = 1 — алх Таким образом, для определения у» получаем задачу Коп»о ИО), И5) (формулы обратной прогонки). Изложенный адесь метод называется методом прогонки (правой прогонки). Соберем всв формулы правой прогонки и запишем их в порядке использования: (-в) В( а(+)= (, (=1,2,..., Л( — 1, а,=х„ С» — а»А» ' (-') А(б» + Р» ))»+»= с (»»=1,2,, ))» — 1» р»=)(»» )» +хфк ( — а х к г (» ) у» = а(+,у(+» + 6(+м 1 = »»( — 1, )»( — 2, ..., 1, О. Стрелки наверху указывают направление счета: (- ) — от 1 к »+1, ( -) — от 1+1 к». 6.

Устойчивость метода прогонки. В предыдущем пункте формулы про)'онки были выведены формально. Мы делили на выран(ения С»-а»А, и 1 — а„х,, не зная, когда это можно делать. Укажем достаточные условия', при которых формулы ИО) и И5) имеют смысл: (С»)) (А»(+ !В»(, 1=1, 2, ..., Л(-1, (х,! <1, а=1, 2, )х,(+ (х,! <2. 3 х РАзностныв уРАВнения 37 Покажем, что при этих условиях (а,! (1 для» = 1, 2, ..., )У.

Предполох»нм, что !а»! (1, и покажем, что )а,+,! (1; так как )а,! - !х,! < 1, то отсюда и будет следовать, что !а<! < 1 для всех 1=1, 2, ..., Ф. Рассмотрим разность )С» — а»А»! — (В»! ) (С<! — !а»! (А<)-)В<!) ))А,! И вЂ” )а,!) ) О. Поскольку В»чьО, то )С» — а;А<! ) О, т. е. ! в<! )а'+' ! = ! с — А а.! ( 1' с» »~< Отсюда видно, что (а,+»! <1, если )а ! <1; эсе (а,! <1 прн )а,! = (х,! (1.

Оценим снизу знаменатель в формуле И5): !1 — а<х,! > 1 — !аа! . (х,! > 1 — )х,! > О, так как (х,! <1 или (а„! < 1, т. е. )1 — а х,! >О. Таким образом, знаменатели в формулах И1), И2) и И5) отличны от нуля при условиях И6). Заметим, что если )С<а!) > )А»,)+!В»с! хотя бы в одной точке <= <,, то !а,! (1 для всех 1) 1, и в том числе для 1 )У: )а»<! (1.

В этом случае условие (х,!+ )х,! (2 является лишним, так как )1 — а»<х<! > ) 1 — )а ! ! х<! > 0 при х< = 1 и х< = 1. Таким образом, при выполнении условий Иб) задача (9) нмеет единственное решение, определяемое по формулам 110)— И5). Вычисления по этим формулам ведутся на ЭВМ приближенно, с конечным числом значащих цифр.

В результате ошибок округления фактически находится не функция у» — решение задачи (9), а у< — решение той же задачи с возмущенными коэффкциентамп А„В», Со х„х, н .правыми частямя Р„)»„)<». Воввякает естественный вопрос: не происходит ли в ходе вычислений возрастание ошибки округления, что может привести как к потере точности, так и к невозможности продолжать вычисления пз-за роста получаемых величин.

Примером может служить определение у, по формуле у»+,= ду, при»()1. Отсюда видно, что у д"у„и для любого у. можно указать такое и<, при котором у сбудет машинной бесконечностью, т. е. при определении уз произойдет авост (аварийный останов) ЭВМ. В этом случае, в силу опшбок округления, определяется не у», а у»из уравнения у»+» = Чу< + Ч где ») — ошибка округления. Отсюда следует, что для погрешности бу< у» — у» имеем уравнение бум, = лбу<+»), бу. <) д< — 1 Из формулы бу» = у»!) + — )) видно, что ошибка бу< при д) 1'экспоненциально нарастает с ростом 1. Гл. ь пгедвзгительнь»в сввдвния 38 Вернемся к методу прогонки и покажем, что, в силу условия (а<1(1, ошибка бу<+ =у»<» — у»».» в определении у»+» не нарастает прн определении у .

В самом деле, из уравнений у = а+»у+»+ р<+< у а»»»у<+<+ р<+» следует бу» = а»+,бу»+„1бу,( ( (а,+,1 1бу»+»1, т. е. 1бу,!<!бр»+,1, так как !а<+,1<1. Если учесть, что в ходе вычислепий возмущаются и козффициенты а<+„(),+„то можно показать, что ошибка в определении решения у< нашей задачи (9)' пропорциональна квадрату числа узлов шах !бр<!а е №, »ч»чя у»+» = Ь+»у»+ Ч»+», » = 0; 1, ..., )т' — 1; А» $» =, » = )'»' — 1, »'»' — 2,..., 2, 1 $я = х;, У»Ч»+»+ )'» Ч» =, » = ))< — 1, Ж вЂ” 2,..., 2, 1, с» — б,+,в» Чл 12 (17) (18) (19) 1 1 1 (20) » — ех 11 В самом деле, предполаган, что имеет место соотношение у<+» з»+ у<+ Ч<+», исключим из (9) последовательно у<+„у, = ь»у<-»+ Ч»: — А у — + (В»Ь+» — С<)у + В<Ч,+, = [А, — (С< — ВД<+»Ц<)у, » + В»Ч»+» — (С< — ВД,+,)Ч».

Уравнение (9) удовлетворяется при А» — (С» — ВД»».,)$< = О, — Р» В,»)ы, — (С,— ВД<т,)Чо Отсюда получаем формулы (18) и (19). Значение у, находим-из где е, — ошибка округления. Отсюда видно, что существует связь между точностью е определения решения задачи, числом )<» уравнений и числом значащих цифр ЭВМ, так как е<№ ~е. (Здесь и выше = означает приближенное равенство по порядку величин с точностью до множителя й(»=сопе$, не аависящего от е.) 7.

Метод левой прогонки и метод встречных прогонок. Аналогично формулам (10) — (15) получаются'-формулы левой прогонки: з з. газностнь»в твавнвния 39 условия у.=х,у,+р, и формулы у,=3<у<+»)о. Из неравенств )С вЂ” В~Ь,м! > )С! — )В!.а<, ), !1 — ф,х,! >1 — )$,! )х,! евдно, что условия Иб) гарантируют применимость формул ле- вой прогонки и их вычислительную устойчивость, так как ! $<! < 1 для всех» = 1, 2, ..., Л». Комбинируя левую и правую прогонки, получаем метод встреч- ных прогонок. Пусть $ = »„0 < 1, < )о',— некоторый внутренний узел.

Тогда в области 0<1<»о+1 вычисляются по формулам ИО) — Иб) прогоночные коэффициенты а<, б<: в а»+,=, 1=1,2, ...,$о< а»=х„ с» '<»» А»(»»+ Р !)»+»= С А, »=1,2<. <(о< р»= !»1< а в области», <» <)<( по формулам И7) — (20) находятся з< и г)<. ~»= с — $ в»=)У 1)У вЂ” 2 (о $к=х„ А» с1 — 5»+,в» в»<»н, + р» й»= с * ° в»=)У вЂ” 1,)У вЂ” 2," <о, Чк=р' » б»+»» При» = »< сшиваем решения в форме ИО) и И7). Из формул у»о = а» +»у< +»+ р» +и у» +».= с» +»у» + Ъ+» находим в» „, +а< «.,ч»,+ у» =. о .

» — а» +»<»» + Эта формула имеет смысл, 'так как 1 — а»оо.»о)» «.» ) О, поскольку хотя бы одна из величин )а» «»! или !»)» «»! меньше единицы в силу условий Иб). Зная у»о, можно по формуле ИО) найти все у< при»<»;, а по формуле И7) — значения у, при»>»,. Метод встречных прогонок может оказаться полезным, если, например, требуется найти у» лишь в одном узле 1 8. Принцип максимума. Для оценки решения краевой задачи (9) через заданные правые части Р<, )»< и )»о (через «входные данныеэ), можно воспользоваться так называемым крик<)илом максимума. Он имеет место для уравнений более частного вида, когда А< > О, В< > О, С, > О. Для упрощения изложения сначала рассмотрим первую крае- вую задачу (при х, = О, х, = 0): 2ЧУ<) А у<- — С<у<+ В уо = — Р<, 1=1, 2, ..., )'<' — 1, у,=р, ук~ р«.

(21) Гл. ь пгвдВАРиткльныв свидания 40 Теорема 1 (принцип максимума). Пусть выполнены условия А<)0, В,)0, Р<=С,— А,— В,>0 (22) для всех»'= 1, 2, ..., У вЂ” 1. Тогда из условий Я'[у<) > 0 (2'[у<) ~ 0) для всех < = 1, 2, ..., У вЂ” 1 (во внутренних узлах), где у< — функция, отличная от постоянной, следует, что у, не может принимать наибольшего положительного (наименьшего отрицательного) значения во внутренних узлах, т.

е. при» = 1, 2, ..., У вЂ” 1. Доказательство. Пусть дано .У[у<1 ~0, » 1, 2, ..., У вЂ” 1. Предположим, что в некотором внутреннем уале $ = »», 0(»е(У, функция у» достигает наибольшего полон»п'- тельного значения у», = шах у» = ЛХ, ) О. о«»«н Так как у<Феона», то найдется такая точка», (», может совпадать с (е), в которойу;, = у», = Мг) О, а в одной иа соседних точек, например в точке» = »» — 1, выполняется строгое неравенство у»г» (Мг. Запишем теперь выражение .У[у<) в виде Я[у<) = В,(уьы — у,) — А,(у, — у,,) — (С, — А, — В<)у,. В точке 1= », в силу условий (22) выполняется неравенство !2' [у»г1 = В, (у~,+ — у,) — А, [у»г — у, ) — (С, — А,— — В»г) у < — В»~ (у,~ — у~~+~) — А (у — у ) так как у»о~)у»г+» ' у»г) у»о-» А»о) О, В»о) О.

Это противоречит условию теоремы: Я[у<) ) 0 для всех 2, ..., У вЂ” 1 и в том числе для» (», Первое утверждение теоремы доказано. Вторая часть теоремы доказывается аналогично (достаточно заменить у» на — у< и воспользоваться доказанным выше утверждением)'. Следствие 1. Если выполнены условия (22) и йу<) ~<0, »=1, 2,, У вЂ” 1, у»~~0, ув~~О, то функция у< неотрицательна, у<) О, »=О, 1, 2, ..., М. Если же У[у<1 ) О, у»<0, ув(0, то у<(0 при»=1, 2, ..., У-1.

В самом деле, пусть м'[у,) < 0 и у< (0 хотя бы в одной точке » = [в, 0(»е()ч; тогда у< должна достигать наименьшего отрицательного значения во внутренней точке»=(„0(»»(У, что в силу теоремы 1 невозможно. $2. РАЗНОСТНЫЕ УРАВНЕНИЯ 41 С л е д с т в и е 2. Если выполнены условия (22), то единственным решением задачи !2'(у»! =О, <'=1, 2, ..., )т' — 1, у, О, у» 0 (23) является у» О, и, токио образом, задача (21) однозначно разрешима при любых Р<, )<„)<р. В самом деле, предполагая, что решение задачи (23) у<чьО хотя бы в одной точке 1=<»,мы сразу придем к противоречию с принципом максимума: если у<,>0, то у< достигает наибольшего положительного аначения в некоторой точке 1„0((р(Л(, что невозможно в силу теоремы 1; случай у, (О также невозможен. Теорема 2 (теорема сравнения). Пусть выполнены условия (22) и у, есть решение гпоачи (21), а у» — решение задачи 2'(у») = — 7„< = 1, 2, ..., Ж вЂ” 1, у, =-)»„у» = )<„ причем !Е»! ~Р<, 1=1, 2, ..., М вЂ” 1, (р ! - )<„!)<р! <)<р.

Тогда справедлива оценка )у»! ( у». Доказательство. В силу следствия 1 имеем у»>0, 0((<М, так как Ы(у<) = — Р,(0, у,>0,, у '>О. Функции и, у,— у, и и»=у,+у» удовлетворяют уравнению (21) с правыми частями Е< — Е<> 0 и Е»+Е») 0 и граничными значениями и, р,— )<,>О, и»=)ьр — )ьр>0 и и, р,+)<<>О, и =)<р+ + р, > 0 соответственно.

Применяя теперь следствие 1, получаем и<>0, и<>0 или -у,<у,<у», т. е. (у ! (у». Функцию у, будем называть мазеорантой для решения задачи (21). Если удастся построить мажоранту у<, то тем самым удастся получить оценку для решения задачи (21) ()у!)е <!)у))е. Следствие 3. Для решения задачи !з (у») 0 0< (<Л ' у< = )<< у» )<р справедлива оценка(у!)с = шах )у< )(шах()р,(, ! р !).

ге<ля Рассмотрим вспомогательную задачу 2'(у»! = О, 0 < ( «<<, ур у»=р, где р,» шах(!)<»), !)<р!). В силу теоремы сравнения !!у!!е(1у!!е, а из теоремы 1 следует, что 1у!!ее= р, так как у,> 0 может достигать наибольшего положительного значения только на границе при»=0 или (=)«. Теорема 3. Пусть выполненьг условия !А<! > О, !В»! > О, В< = (С<! — !А,! — !В<! > О, (24) <=1, 2, ..., )'р' — 1. Тогда для реи»ения задачи Я'(у»1 * — Е„(. 1, 2, ..., Ф вЂ” 1, у. О, у»=0' (25) гл. 1. Пгвдвагитвльньгв сввдвния скраведлива сценка (26) (зо) Это следует из леммы. Лемма.