Samarskij A.A. Vvedenie v chislennye metody (ru)(400dpi)(T) (969542), страница 38
Текст из файла (страница 38)
(19) Отсюда находим Ч1ч1 — Ч1+т (2р1+ 2211 =Ч1 = ° =- Ч2 == О, т. е. 2), = 0 лля всех ) = О, 1, ..., и х' = е1. +1м — ' т ~)2 =- О (т) 112' == О (т) ° (20) Из (16) получаем )~;21 ) .($,)+ т!2р1 ), ~ $1ь1) »<! $1;12(+ т! 1р2! » <!В1! + т 0 2р1 !+! 1)1!), так что справедлива оценка ~ г'" ~( ~~ т(( ф,~+ ~Ц2~), (21) иа которой в силу (17), и следует сходимость со скоростью 0(т) аддитивной схемы (14). а 3. окот>омпчные схемы 257 13мегто (1!) можно взять другую систему уравнений: деп > — + а! дг> =- )1(() т>~ г ~ (>+ ° 'и>(гг) =- ь'((г) л '~,> (22) + агиы> >з(~)г 1> ~ ~ ~~г->г г(т> ((>) гйг> (1>>г)г 7' =- О, 1, ..., оп (О) = и,.
Решеппем этой задачн является функция и(1) = и,м(Е). (23) В отличке от (11) здесь оба уравнеппл интерпретируются на всем отрезке 1, ~ 1 ~ 1г.гг, н поэтому аппроксимация этих уравнений проводптся с шагом т (а не т/2, как в случае (1'1)) и дает те >ке схемы (14). Оба способа сведения задачи (9) к системе задач (11) плн (22) используют одно и то же свойство (2й) н условие ) =,>г + /г, которому всегда можно удовлетво)ш та.
Рассмотрим в качестве примера уравнение теплопро- водкостн — 1 и + ) (х, >), х =-.. (х„х„), Л гг Ви — Ли =. Х„и+ 1>гг, !„гг.=- — „', а == 1, 2, дх (25) г.г и г.г — «одномерные» операторы. 1'ешенпе уравнения (26) ниы> =- г г гдг> + 1тг г Ъг Г; (1( 1,„, „> — Х„, гег у+г = ьег> . очевидно, является более простой задачей, чем решение уравнення (25). Условпн В = йг + Е г. >' = >', + /г гарантирук>т суммарную аппрокспмацшо дзя схемы, получающейся прн обычной аппрокспмацпн, папример, с помощью двухслойной схемы с весамп каждого из уравнений снстемьт г>г'г и у > -- ~Р(г> + 1> 1> ~ ~г ~ ~(ю.г ь<П -- и, 258 тл.
тгг. телвпкпии твппопроводпости В результате мы получим аддитивпую схему, локально-одномеркую схему пли схему расьцепления .=.= Л, (агу' ' ' + (1 — а!) у!) + «р'„х ~ юг, г -!-с Ь!-! со Уг У Л ( 1«с+ (1 ) тассо) + хаааа, 1==0,1,..., (27) уо —. ио (х), х е= «ого гысс ! / гс/о 3+! ! Нг У (то =)с У !та =- Рс Здес! Л,у= у-,, Лоу = — у- „.
Параметры о, и оо определяются пз условий устойчивости и аипроггсимации. Например, ирп о, = ос = 1 получаем схему с оиереженпет! гс ' а 1.«сlо ! ! г-г«о = Льр , с«ге —:- 1.,у''+«р'., 1=-0 1 Подставляя сюда у'= г'+ и', у'+"' =г' ""+ (ьу+игы с/2, ус+! =го+'+ иы', получим для погрешности г уравпеппя о' 'гы — ог == Л,г! + «р!', сг! сог!г где и — регпеипе походкой задачи (25), грг и гро — певязкгг, равпые ! и-';и 1и — и 1 1и — и гр! — Л,:,; — — — ( гр„сро == Л,гс — — „, — + грм п=п"', п=и', Ото!ода видно, что гр! = 0(1), «р! =-0(1), т. е.
каждое пз уравнений (27) в отдельности ие аппроксивгирует уравнение (25). Возьмем сумму иевязок и+и и — и 2 + о ' рг+ро т = (Е! + с,о) и — —" + гр! + «ро + О (т + ()с (о)г Я 3 ЭКОНОМИЧГСКИГ СХЕМЫ 9чо где й = и'+". Учитывая уравнение (25) прп (=(;+он по- лучим ~р = ~р, + <р, — Р'и+ 0(т+ )й!') = 0(т+ (я!'), )Ч = Ь,'+ Ьг, осли ср, + (р, = у"+п2+ 0(тв), Этого можно достигнуть, полагая, например, ~р, =О, гр, =~""" нли ср, =<р~ =)Ч2. Можно показать, что схема (27) сходится равномерно со скоростью 0(т+ (й!'), т.
е. ))у'" — и"'!)с = 0(т+ )й!'). Из приведенных примеров видно, что метод суммарной аппроксимации позволяет проводить расщепление ело;нных аадач на последовательность более простых и существенно упрощать решение многомерных задач математической физики, ДОПОЛ11ЕЕ!ИЕ Марш-алгоритм и метод редукции для решения системы линейных уравнений с трехднлгоналъной матрицей Во многих приложениях вгтрсчаготсн задачи, приводящие к ре!иеншо систем линейных алгебрап*иски! уравнений специального вида (с разреженной мзтрнцей, имглощай много ггулевых элементов) высокого порядка.
Такие системы возникают прн разностной аппраксимацви эллиптических уравнений илт~ ирв нспальаовании неявны:г схем длн уравнении теилоирооодности и лр. После аппроксимации обыкновенного дифференциального уравнения второго порядка па тргхточс ~ноас шаб:нии. в нь !Ч было получено разиостноа урззи~ ииа второго порядка. которое представляет собой систему линейных алгебраичсски. уравнений порядка Л' — 1 (У вЂ” 1 — число внутренних узлов) с тргткиаганальной матрицгй. В 1 3 гл. ! для решения такой системы был построен метод, для реализации которого требуется О(т) арафметичегних операций.
Прп аппроксимации двумерного уравнении Пуассона нв иятиточечиои шаблоне в гл. Ч! бьша получена разностизя сы ма. которой сжывстствуст система линейных а.игбраичсских уравнений с !штпдизгоижн пой матрпцей парлдка Д = (У~.-. 1)(Л -- !), гто Л', — 1, Лг — '! — чис.ю внутрсшшх уздав на кшш!аму направлению.
Нри разбиении вектора неизвестных на блоки, содержшциа ио Л'~ — ! элементов. мы получим зашив системы с блочио-трюдпзгоиальиой матрицей, число блакан которой равно Лз — !. Дли такой системы и ! 2 гл. У! бь(л рассмотрен метод разделения ир~ мгппьж с оценкой о(л'!онл) для числа операций. при многакратпам решении систем подобного тина важное значение приобретает экономичность вы ишлитсльиых а:иоритмов. Ниже ау,ит иост1юси прлмой мета;! решения специальных сигтем с трсхдиаганальиой матрпцей, для которого требуется всего 0(Л) операций как н случае, когда элементы матрицы суть скаллры, так и в случае блочпан матрицы. 1.
й!арнаазгоритхь Сначала рассмотрим случай. когда элшшиттл матрицы — скаллры. Запишем систему с трехдиагональнаи матрицай в зидс трсшачечнаи разпостпой задачи: — +Су; — у„=у„1 = ~~Л' — 1, у =Ц у, =О, где С вЂ” число, и предположим, чта Л = 2й+ !. Вслп разпасююе уравнение второго порядка (!] записать а виде рекуррептных соотношепнй уы,=Су,— у~,— Га !~~1, уе=-о, (2) то нетрудно заметить, что все неизвестные у; можно найти последовательно ио формуле (2). если наги!м-либо способом вычислить аначенне уг.
При зтам любое у; будет линейно выражаться через рз и ув Сказанное дает нам основание записать для я!абати 261 Г[ОПОЛПКПИН < ) 1 соотношение у«, = а,у< — р«-уг О< (8) с неопределенными пока коэффициентами а<, 6» р<, Если положить ,„, =- 1, 6, .= О. р, = О, (4) то (3) будет справедливо и прл < = О. Г!таь, решение задачи (1) будем искать в ниде (8) для любого < =- .О. Запксынан (1) в виде ракурреитлых соотношений у;,=Су,— у „— Р» < Л' — 1, у, =О (6) И проводя аналогичные рассуждения, получим, что решение задачи (1) для любога < рр <<ажио искать а виде (6) если положить 6<=-1, ц- =О, а<=О. (7) Зазштим, что если у,, будет найдено, то все у< можно вычислить последовательно по формуле (5). Найдем у, и ут, Для этого определим коэффлппепты и» (Г<, $» ц» р» д» Сравнивал (2) и (8) прн < = 1, а (6) и (6) прп < = К вЂ” 1, получим а,=8<=С, бе=<1,=1, р,=р» у<=У«-<, (8) Найц<м теперь рекурргптяыа формулы для определения пег<оных коэффициентов.
Подставим (3), а также вытекающие иэ него выражения длл у; и у< у' == и -<у< (Г -гуз Р<-» у -< †' и<-гу< 6<-гуо — Р<-з в уравнения (1). Получим — (<х,-з — Сп; <+ п,)ю+ ((Г< г — Сб, г.< 6, <)уз+ +Р -".— С!« — тр<=Р» 1~~2.
Для тога чтобы этп равенства были тождегтнеипымп для всех <, достаточно положить для < ув 2 р, = ср, , — р, , + р<, (6) а<=Си« вЂ” а< ., 6, <=-Сб< ° — 6< ь (16) Лналопшио, испольэуи (6) и (1), получим для < ~ У вЂ” 2 рекурронтные соотношения У,,=Се„,,— у...+Р„ ал-< = Саг-«- ся-«- т)г'-«- =С<1 я-<-з — Чх-<-з Заменяи адесь д« вЂ” на <, получим для < ~ 2 формулы у<=Се« вЂ” у<,+Рл, (11) $< = Сй;-~ — й<-з, т)<-г = Сц<-.— ц<-з. (12) Итак, формулы (4), (7) — (12) полностью определяют искомые коэффициенты. Сравнивая (10) л (12) при условиях (4), (7), (8), ДОПОЛНЕНИЕ получим, что р, — г), = $» = а, для г ) О.
Таким образом, формулы (3), (6) нршп»мают вид уьы = а,у» — а,,у,— Ро 1) О, (13) У»-г = а»-»Ул-г — ал-,-~у. — д» -ь !»= 8', (!4) где Р' = СР»-» Р'-г+Р, г) 2, Рг = О, р» =)'ь (!3) д»=СУ,,— у, г+Гл-о г)2, д»=0, Ч,=Гл-ь [16) а»=Са㻠— аг-г, !)2, а»=1, а»=С.
(17) Найдем теперь у~ п ул ь Для этого положим в (13) ! = А., а в (14) ! = )» + 2. Учитывая, что д! = 28 + 1, получим У»+» = а»У» а»-»Уг — Р» У»г» = а» ~уе г — и» гул — Ч» Вычитая нз второго равенства первое, получим уравнение оюшсительно у» и уь — »: а у, г — а»уг + а» ~уг — а»-гул = Ч»-» — Рь (18) По. учим еще одно уравненне для у» п ул-ь полагая ! = ь. — 1 в (13) и ! У+1 в (14) и вычитая из первого равенства второе, — а»У»'-» + а»-гу» — а»-~у»+ а»-»Ул = Р»-1 — Ч». (18) Учитывая, что у» = у» = О, сложпм и вычтем (!8) п (19). Получим энвнвалентную систему (а»-» гг») (ух-~ + У») = Ч»-» — Р» + Р» -1 Чм (20) (а»- + а») (у.
— — Р~) = у -! — Р» — Р»- + у», решая которую, найдем искомые значения у, и у; Уг = (аа г а») (а» (Уа г Р») + аа. г (Ра г — Я»)) (21) Ум — г = (а»-! а») (а»-г(Ч»-г Р») + а» (Р»-! Ча)) Таким образом. алгоритм решении задачи (!) состоит е вычислении по формулам (15) — (17) ьоэффнцпектов р» ь Р», у» у!ы а» ь аы по фар»гулам (21) — значений уь у».-~ и иенззестпыс уь ! == 2. 3, ..., У, г)о формуле (2). а чля» = Д вЂ” 2, )У--3..., ..., 8 + ! по формуле (3) нрп заданных уг.
у; п зычпслешгых !гь ул-ь Описанный алгоритм получил название .»арлоалгорлтла, Легко подсчитать, что для его реализация требуется прлмерно 8»т' операцкй. Можяо показать, что если С чь 2 сов глл/У, эь — целоо число, то задача (!) разрешима прп любои правой части и а;, чь ~аз. Следовательно, в этом случае формулы (21) пе содержат деления па пуль. Оппсапнып выше марш-а;порптм можно испольэовать и в случае, когда С вЂ” квадратная матрица, Р', — заданные, а уг — искомые векторы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
