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