Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 72
Текст из файла (страница 72)
положить Р =-6„+Р = 6„ в — »6 ' >)+»6 (33) Ь вЂ” р а+р =܄— =Ь,. >) — та в+ та Теорема 2. Пусть А=А,+А„где А, и А,— перестановочные самосопряженные операторьц удовлетворяющие условиям (20). Тогда для погрешности итерационного метода (21) — (26) справедлива оценка (11), где 1 — )>! ~ 1 — 1 До к а з а тел ь с та о. Запишем уравнение для погрешности метода (21), (22) в виде г»+> — — 5г„, (28) Таким образом, приходим к системе четырех уравнений отно- сительно пяти неизвестных р, д, г, 6, Л. Положим для определен- ности 6=1. Тогда после несложных, но громоздких выкладок, ко- торые мы опускаем, получим, что решение системы (33) определя- ется формулами (23), (24) и 1 — 1 6=— 1+1' Обращаясь к выражению (32) для собственного числа опера- тора 5, видим, что мы пришли к той же задаче, которая возникла прп доказательстве теоремы 1, а именно: найти зкачение а, кото- рое минимизирует 11Я =шах ~ Х4 (3) ( при условии, что 0(6~ ( Ха„(1.
Согласно теореме 1 для этого достаточно взять а==',= ь — и тогда получим ~Щ!~р„где р,= 1. ч 1+1 1 1 — У$~' У.6 '=~ + йй(' 1 — Г 5=6= †. Этим и завершается доказательство теоремы 2. 1+1 П р и м е р. Рассмотрим разностную аппроксимацию уравнения Пуассона в прямоугольнике 6 с границей Г на прямоугольной сет- ке с шагами Ь, и й;. Ум.г — УУ + У~- л, Уп!~' — Уи + Упг ', (34) = — 10, "1 а 1=1, 2,..., М,— 1, 1=1, 2, ..., 6(,— 1, п)У,=(м у(хч) =О, хпаиГ. В данном случае А=А,+А„где (А„у)у = — у„- „,,, а = 1, 2.
Операторы А, и А, перестановочны. Они являются самосопряженными и положительно определенными операторами в смысле скалярного произведения №-1 №-1 (у, о) = ~~ Ь~ ~~~~~ Йтуипу. 1=а Как показано в $ 1,2 гл. 3, операторы А удовлетворяют неравенствам (20), где 4 ° е пав 6„= —, зш' —" а==1, 2. 2!д Таким образом, для решения разностной задачи (34) можно применить итерационный метод (21), (22), в котором итерационные параметры т, и т, выбираются согласно формулам (26). Разумеется, для решения задачи (34) можно использовать итерационный метод (2), (3) с более простым способом выбора итерационного параметра (10), где 6=пни(6„6,), А=шах(Л„Ь,). Однако 41О при этом для достижения той же точности е потребуется выполнить большее число итераций.
Действительно, согласно теоремам 1 и 2 число итераций при малых $ пропорционально 5 '", где $=$»=бейб для метода (2), (3), й=йз=(1 — 1)1(1+1) для метода (21) — (23). Из формулы (23) находим 1=1 — — — + — + — +— 1 / бг бз бг бт т з 'т бч ат ат ат) Пусть, для определенности, 6,<бм Л,<Лм Тогда получим $,=6,/Ьз, $,= — $х ~~1+ — ') ~1+ — )>$,. 4 ~ бт)т Лд) Отношение числа итераций пг'1(е) в методе (2), (3) к числу итераций пм1 (е) в методе (21) — (23) окажется равным зш (е) =~~:=-'~("Ь~"Й) ' Если, например, 1,=0,51„й»=0,5й„то получим б»=46ь Ьз= =4бо и, следовательно, пеп(е)/а~'~(е)=2,5, Замечание Существенного ускорения сходямостя можно добиться пу- тем использования итерационного метода Уму — У» + Агу»ьн + Агу» = 1, 1 р»ь, — р»+и (»+и + Амт»+М + Агу»» т, с переменными параметрами т»1 ч'1, »1 м1, з О, 1...,л — 1.
Способ выбора ита- рационных параметров я оценка вогрешвостя подробно изложены в [30, с. 463]. Отметим лишь, что в случае модельной задачи число итераций, необходимых для 11 достижения заданной точности е, является величиной О (!П вЂ” ) . «) й 5. Метод матричной прогонки 1. Введение. Матричная прогонка относится к прямым методам решения разностных уравнений. Она применяется к уравнениям, которые можно записать в виде системы векторных уравнений — С,д,+В,д,= — р„ Агуг-г — Сгуг+ В~уг» = — Рь 1=1,2,..., У вЂ” 1, (1) Амуы-» — Смуы = — Ры, 41) удовлетворяющее условию Дирихле и(х„х,) =р(хь х,), если (х„х,) енГ.
(3) Введем прямоугольную сетку Сл = (хуу = (х,, х, )), уи ш где х,"'=йм хУУ'=уй„1=0, 1, ..., Мь 1=0, 1, ..., №, Ь,№=1ь Уу,№=1, и заменим задачу (2), (3) разностной схемой Уу г.у 2УУ+Уу+ьу + Усу ~ 2Усу+Уу,у+1 (4) уР и~ уг 1 3 1=1,2, ..., № — 1, уиу = Ииу. ууу у = рм у 1=1,2, ..., № — 1, 1=1, 2, . ° й(э — 1 (5) 1 = 1, 2, ..., йУ, — 1. ууо = Иуо, уусч = рууу,э Разностная схема (4), (5) представляет собой систему линейных алгебраических уравнений, в которой неизвестными являются значения уи, 1=1, 2, ..., № — 1, 1=1, 2, ..., № — 1.
Число неизвестных равно числу уравнений, т. е. (№ — 1) (№ — 1). Запишем систему (4), (5) в векторном виде (1). 412 где у,— искомые векторы размерности М, г"; — заданные векторы, Аь В;, С; — заданные квадратные матрицы порядка М. Матричная прогонка представляет собой обобщение обычной прогонки на случай системы векторных уравнений (1). По сравне- нию с другими прямыми методами решения разностных задач ма- тричная прогонка более универсальна, так как позволяет решать уравнения с переменными коэффициентами и не накладывает силь- ных ограничений на вид граничных условий. Однако применение матричной прогонки к решению двумерных разностных задач стал- кивается с двумя трудностями: неэкономичностью по числу дей- ствий (т.
е. большое время счета) и, главным образом, необходи- мостью в больших ресурсах машинной памяти. Если же матрицы Аь Вь С, имеют относительно невысокий порядок (как это бывает при аппроксимации систем одномерных дифференциальных урав- нений), то матричная прогонка ничем не хуже обычной прогонки. Прежде чем излагать алгоритм, покажем на простом примере, каким образом двумерную разностную задачу можно привести к виду (1). 2. Запись разностного уравнения Пуассона в виде системы век- торных уравнений. Пусть в прямоугольнике 6= (О<х,<1, сс=1, 2) с границей Г требуется найти решение уравнения Пуассона Уи д'и — + — = — 1(х„х,), дхэ дик (2) При решении системы (4), (5) матричную прогонку можно проводить как по индексу 1, так и по индексу 1.
Покажем, например, как подготовить систему (4), (5) к виду (1), удобному для применения прогонки по индексу 1. Перепишем систему (4) в виде У1- г (2У11 Усу 2УУ + Уст+1 1 + У1+1ц ь,' 1, ь,* ь,' ) ь,' )+ и» 1=1, 2,..., 13'» — 1, 1=1, 2,..., 13'3 — 1 и учтем граничные условия у!3=У!3, Ув3=!3и3. !'=1, 2, .
° » 1у1 — 1. Тогда получим систему уравнений У1-1,1 1 2У»1 2У11 + У!3 1 Ум1,1 3 1333 Ь3 (, Ь' 1 1 3 -1 3 У31Л (2УУ УС!,-2УП + Уи+1 '! + У!+14 Ь' (, Ь' Ь' ) Ь3 1 1 3 Умм 1 (2Усм 1 УП31 3 — 2У1,31 1 1 У1+»,м, 1 1~~к, Ь' 1, Ь' С !3»-1 ° 1 1 3 1 3 где 1=1, 2,..., 13'1 — 1. Далее, обозначим через Е, единичную матрицу порядка 1У3 — 1 и через Л,— следующую трехдиагональную матрицу того же порядка — 2 1 О О ° 1 — 2 1 О ° 1 О 1 — 2 О ° л Ь3 1 — 2 1 О 1 — 2 Ясно, что Л, представляет собой матрицу оператора второй разностной производной по направлению х3.
Введем для 1= 1, 2,...,!У» — 1 векторы Ус=(угм Уи,. ° 'Уиу 1), 1 1= Ь +,3» (!3~ Ь. ° ° ° » 6,М»-3» 71.»Ч;1+ «3 ) Тогда предыдущую систему уравнений можно записать в векторном виде 1 »' 2 1 — Едь-1 — — Е3 — Л3 ус+ —, Етум» = — Рп (9) 1=1, 2, ..., !У» — 1. Эту систему уравнений следует дополнить граничными условиями Уо = 13», Ун»= 1Зн„ 4!З где <т зт 1<0 (1<0< )<<2< ' ' ' 1<0,м <) 1зп< (1зм<«<<и<2 ' ' ' <зм<.и« ) Таким образом, разностная схема (4), (5) записывается в век- торном виде (1), где В, и А — нулевые матрицы, А,=В<= И<Ез, С< =2й< Ез — Л„<'=1, 2, ..., Лс< — 1.
Может оказаться, что <<<з~й7„т. е. что число точек сетки по направлению х, гораздо больше числа точек по направлению х, (например в случае, когда прямоугольник 6 сильно растянут в направлении х,). Тогда выгоднее пользоваться прогонкой по ин- дексу 1, так как при этом соответствующие матричные коэффициен- ты будут иметь порядок ЛС< — 1 гораздо меньший, чем <«'з — 1.
Соот- ветствующая система векторных уравнений имеет вид 1 / 2 т 1 — Е<У1 < — — Е, — Л Уг+ — Е<У1„= — РЛ а, '~зз в', 1=1< 2< ° ° < й7з 1< Уо=)со< Ум<=)зм« где Е, — единичная матрица порядка <з'< — 1, Л, — матрица, анало- гичная (6) и имеющая порядок У< — 1, У1 = (УЫ Узг< ° ° °, Ум;<,<) Ио = ()<<о< Изо< ° ° )<м -ьо) т т 1зм, = (ром,Узм,... )зм,-з,м,) т. 3. Алгоритм матричной прогонки.
Пусть задана система урав- нений (1). Формулы матричной прогонки можно получить так же, как и формулы обычной прогонки (см. п. 7 $4 ч. 1), однако при их выводе надо учитывать, что коэффициенты уравнения (1) непе- рестановочны. Будем искать решение системы (1) в виде У< — — а<+,У<+<+Р<о„(=0, 1, ..., У вЂ” 1, (10) где а<+,— квадратные матрицы того же порядка М, что и порядок матриц А„В„С<, а р«.,— вектор размерности М.
Подставляя у,= =с<<+<у+,+р«., и у« =а<у<+р<=а<а<+<у<+<+(а<()<+<+р<) в уравнение А,у,,— Су,+В<ум,— — — Р<, получаем, что это уравнение будет выполнено, если потребовать (А,а,— С,) а<+, + В<о, = О, (А<а< — С,) р<о< = — (А<р<+ Р<) . Отсюда приходим к следующим рекуррентным соотношениям для определения матриц а<+, и векторов р<+,.
а;+, — (С< — А<а;) з В<, (1 1) ~<+< — (С; — А<а;) ' (А<р<+ Р<). (12) Здесь <=1, 2, ..., Лс — 1. Начальные значения сс, и р< задаются в соответствии с уравнением — С<у. + В<у< = — Ро. 414 которое можно переписать в виде Ц,=С В,у,+С,"Р,.
(18) Сопоставляя (13) с уравнением (10) при <'=О, получаем с<< Со Вм< им< =Со Рм (14) После того как все коэффициенты аь р< найдены, векторы у„ <=<<< — 1, <«' — 2, ..., 1, О, определяются последовательно из уравнения (10), начиная с у,. Для начала счета надо знать вектор у, который определяется из системы двух уравнений Аицп — < — Сиуи= — Ри< Ум-<=а»Ц»+ Ри. Отсюда получаем у»= (С» — А»ам) '(Аири+ Рп). (15) Объединяя формулы (10) — (12), (14), (15), приходим к следующему алгоритму матричной прогонки для системы (1): а<+,— — (С,— А<ай 'В«, =1<2,..., У вЂ” 1, а,=С,'В, (16) рь =(С< — А<а<) '(А41<+ Р<), <'=1, 2, ..., <Ч, Р<=С,"Рм (17) у<=а<+<у<+<+р«<, 1=У вЂ” 1, й<' — 2, ° ° °, 1, О, уи=ри+< (18) При реализации метода матричной прогонки приходится запоминать все матрицы а„р<, <=1, 2, ..., й<' — 1, что ведет в случае матриц больших размеров к необходимости использования внешней памяти ЭВМ и тем самым к увеличению времени счета.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
