А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 25
Текст из файла (страница 25)
ь1+ а2 21+ а2 ! 1 !за2 2 1 в~1 Напомним, что для (32) достаточные условия устойчивости метода прогонки имеют вид ~ С, !) ( А; (+! В; (, ! = 1, 2,..., М вЂ” 1. Из этих условий найдем, что матрица В имеет обратную, если шаги сетки ОО удовлетворяют ограничению 6, ()/2й1. При выполнении этого условия задача (29) может быть сведена к задаче (1), (2) с С=В-'А. $2. Метод полной редукции для первой краевой задачи 1. Процесс нечетко-четного исключения. Переходим теперь к описанию метода полной редукции.
Начнем с первой краевой задачи для трехточечных векторных уравнений — У~,+С~~ — Г ~, =.й~, ! (1'( 12! — 1, (1) УО РО ГЯ РФ' Идея метода полной редукции решения задачи (1) состоит в последовательном исключении из уравнений (1) неизвестных 1'~ сначала с нечетными номерами 1, затем из оставшихся уравнений с номерами 1, кратными 2, затем 4 и т. д. Каждый шаг процесса исключения уменьшает число неизвестных, и если !у есть степень 2, т, е.
0=2", то в результате процесса исключения останется одно уравнение, из которого можно найти Кд12. Обратный ход метода заключается в последовательном нахожде- 130 Рассмотрим первый шаг процесса исключения. На этом шаге нз уравнений системы (1') для 1, кратных 2, исключим неизвестные У~ с нечетными номерами 1. Для этого выпишем три идущие подряд уравнения (1'): — у'~,+ Совр' — К~~, --= Е';", — У~ +Сов)'~о> — )~~о> — — Еф, 1=2, 4, 6,...> У вЂ” 2. Умножим второе уравнение слева на Ско и сложим все три полу.
чившнеся уравнения, В результате будем иметь — )>~ о+С"'à — )>;оо=-)с)», 1'=2, 4, 6, ..., У вЂ” 2, ро = о о> )л'= 1 л» (2) где С'о [С>о>~о 2Е Е»> Е>о> 1 С>о>Е>о> ! Е>о> >-> ! ы> 1 = 2, 4, 6, ..., У вЂ” 2. Система (2) содержит неизвестные )' только с четными номерами 1, число неизвестных в (2) равно У(2 — 1, и если эта система будет решена, то неизвестные )'~ с нечетными номерами в силу (1') могут быть найдены из уравнений С<о'Х~ —— Е)о>+ у~,-~- У~„, 1=1> 3, 5, ..., У вЂ” 1 (3) с уже известными правыми частями.
Итак, исходная задача (1') эквивалентна системе (2) и уравнениям (3), причем по структуре система (2) аналогична исходной системе. На втором шаге процесса исключения из уравнений «укороченной» системы (2) для 1, кратных 4, исключаются неизвестные с номерами 1, кратными 2, но не кратными 4. По аналогии 131 пни неизвестных )'~ сначала с номерами 1, кратными У/4, затем У/8, У/!6 н т. д. Очевидно, что метод полной редукции есть модификация метода исключения Гаусса, примененного к задаче (1), в котоом исключение неизвестных происходит в специальном порядке, )апомним, что, в отличие от этого метода, в методе матричной прогонки исключение неизвестных происходит в естественном порядке. Итак, пусть У=2", п)6.
Для удобства введем следующие обозначения: С"'=-С, Е)">=,Г~, 1=1, 2, ..., У вЂ” 1, используя которые запишем (1) в виде — У~, + С"'); — У, ~, = Р';о>, 1 (1 < У вЂ” 1 У = 2" 1 о = "о о л' — Ел>. (1') с первым шагом берутся три уравнения системы (2): второе уравнение умножается на Ссо слева, и все три уравнения складываются. В результате получаем систему из М(4 — 1 уравнений, содержащую неизвестные Г, с номерами, кратными 4: — У' »+С'"У' — У;,,»=Р)", 1=4,8, 12, ..., Ж вЂ” 4, )о Ео~ Этот процесс исключения может быть продолжен. В результате 1-го шага получим редуцированную систему для неизвестных с номерами, кратными 2'.
— ~; »»+С">1~~ — Уь»»~=Р)", 1=2', 2 2', 3 2', ..., У вЂ” 2', и группы уравнений С'» "Г =Р»» "+Г; »»- -(-Г; ~» ', l ! 1=2» ', 3 2» ',5 2» ', ..., У вЂ” 2» ', (5) решая которые последовательно для 1=1, ! — 1, ..., 1, найдем оставшиеся неизвестные. Матрицы С'»' и правые части Г';»' нахо- дятся по рекуррентным формулам С'»'= (С'» 'ф — 2Е, Г и Р ~~-и + С(»-оР~ о + Р(~-о 1 ~ »-а ! !.~.»» ю ° (6) 1=2», 2 2», 3 2', ..., У вЂ” 2», для й=1,2, ... Из (4) следует, что после (и — 1)-го шага исключения (1= и — 1) останется одно уравнение для К» -,=- Кд~,.
С~»-и У Р)"-о+ 1'1»л-ю+ Уь»»л-~ = Р) '+ У»+ )у»ь 1=2" 1» Ем 1 у Е»г с известной правой частью. Объединяя это уравнение с (5), получим, что все неизвестные находятся последовательно из 132 уравнения Сц'Г = Г~" + У;,+ );+„1= 2, 5, 10, ..., У вЂ” 2 для нахождения нейзвестных с номерами, кратными 2, но не кратными 4, и уравнения (3) для неизвестных с нечетными номерами.
При этом матрица Сев и правые части Г,'" определяются по формулам Сев = [Сц'~» — 2Е, Р)" = Р)"»+ С'"Р)о+ Е)оо»», 1 = 4, 8, 12, ..., У вЂ” 4. Р)»с = Д С'"р';м2», с:-о (8) — с причем формально положим Д С"'= Е, так что рссо' = Р)о'=ос Р~. с=о Найдем рекуррентные соотношения, которым удовлетворяют р)»'. Для этого подставим (8) в (6). Считая, что Ссо — невырожденная матрица для любого 1, из (6) получим »-1 »-2 2 Д С'"рао = Д Сса (рс,'»', +С" "р' "+р", '»с,) с о с=о или 2С вЂ” р," =р,".—,",, +С вЂ” р,'- +р,"..—,,"',. (9) Обозначая Ясс» " = 2р';"' — р';" ", из (9) получим, что рс»' могут быть последовательно найдены по следующим формулам: С'» сс8)» "=р" ", +рс»', р'-" = 0,5 (р" "+ Яс»-о), )=2»> 2 2", 3 2*, ..., сУ вЂ” 2», й=-1, 2, ..., п — 1, р,'"= — Г..
У' 133 уравнений С -» ~;=Р)»-о+ У.С,»-,+)1„.-, У;=Р„)„=Р, 1=2»-', 3 2» ', 5 2» ', ..., с)с' — 2» ', й=п,п — 1,...,1, (7) Итак, формулы (6) и (7) полностью описывают метод полной редукции. По формулам (6) преобразуются правые части, а из уравнений (7) находится решение исходной задачи (1).
Описанный метод мы назовем методом полной редукции, так как здесь последовательное уменьшение числа уравнений в системе осуществляется до конца, пока не останется одно уравнение для )гасо. В методе неполной редукции, который будет рассмотрен в главе 1Ъ', осуществляется лишь частичное понижение порядка системы и «укороченная» система решается специальным методом. 2. Преобразование правой части и обращение матриц.
Вычисление правой части Р,'»с по рекуррентным формулам (6) может привести к накоплению погрешностей вычислений, если норма матрицы С'» " будет больше единицы. Кроме того, матрицы С'»с являются, вообще говоря, полными матрицами, даже если исходная матрица С"' =С была трехдиагональной. А это существенным образом влияет на увеличение объема вычислительной работы прн вычислении Р)»' по формулам (6).
Для рассмотренных в 3 1 примеров норма матрицы действительно будет значительно превышать единицу, и такой алгоритм метода будет вычислительно неустойчив. Чтобы обойти эту трудность, будем вместо векторов Рсс»' вычислять векторы р)»с, которые связаны с Рс»с следующим соотношением: Рекуррентные соотношения (10) содержат сложение векторов, умножение вектора на число и обращение матриц С'х ". Осталось теперь исключить Ггга " из уравнений (7). Подстав- ляя (8) в (7), получим См- гг У. = 2а ' Ц С"'Ргга о + У; ах- + У)+ аа-., (11) 1=2» а,3 2а ', ..., У вЂ” 2" ', й=п, и — 1, ..., 1. Здесь тоже необходимо обращать матрицы С'а ", но, кроме того, в правой части (11) появилось умножение матрицы на вектор.
В рассмотренном ниже алгоритме используемый способ обраще- ния матрицы Сга '> позволяет избежать нежелательной операции умножения матрицы на вектор и реализацию (11) свести к обра- щению матриц и сложениго векторов. Рассмотрим теперь вопрос об обращении матриц С'а ", опре- деляемых по рекуррентным формулам (6) С'аг=[С'а ")а — 2Е, й=1,2, ...,С"г=С. (12) Из (12) следует, что Сга' есть матричный полипом степени 2а относительно С с единичным коэффициентом при старшей сте- пени.
Этот полином через известные полнномы Чебышева выра- жается следующим образом: С'"'=2Таа( — С), Й=О, 1, ..., (13) где Т„(х) — полином Чебышева и-й степени первого рода (см. п. 2 24гл. 1): (' соз (а агссоз х), (х ( ~ 1, ( — [(х+$'ха — 1) +(х+$' х' — 1) ], )х(~ ~1. Действительно, в силу свойств полинома Т„(х) Т (х)=21Т„(хЦа — 1, 7',(х)=х, из (12) очевидным образом следует (13). Далее, используя соотношение а-а П 2Т,г(х)=Уха- г(х), г=о связывающее полиномы Чебышева первого рода с полиномом второго рода У„(х), где Мп ((п 4-!) агссоа х) (х ( и„(х) = ((х+)' х' — 1)"+' — (х+)' х' — 1) '"+г~, ~х~)1, 2 ха — 1 л гко вычислить произведение полиномов Ссо »-г Ц С« =и;-, ! ( — С) . /1 (14) где х,— корни полннома 1„(х).
Используем лемму 6 для разложения отношений 1(Т„(х) и Ул ! (х)(Т„(х) на элементарные дроби. Корни полинома Т„(х) известны: х,=сов го, 1=-1, 2, ...,и, (21 — 1) (15) н в этих точках полипом (7„!(х) принимает отличные от нуля значения яп (л а!асов х,) ( — 1)'+' яп (агссов хй . (21 — 1) в!п — я 2л Поэтому, используя соотношение Т„'(х) =п(7„,(х), из леммы 6 получим следующие разложения: л ( — 1)1+! в!и— (21 — 1) л 1 2л т„(х) с.ы л (х — хс) 1=! л и., рб СТ„(х) Х лл(х — х,)' (16) (17) где х, определено в (15).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
