А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 21
Текст из файла (страница 21)
Алгоритм (8) — (10) в применении к решению систе- мы (5) корректен и устойчив. Рассмотрим теперь вопрос об объеме запоминаемой промежуточной ин-. формации н об оценке числа арифметических действий для алгоритма (8) — (10), считая для простоты, что в системе (б) все матрицы кведретиые )06 и имеют размер МХМ, а все векторы Еу и Г имеют размерность М. В этом случае прогоночные коэффициенты а будут квадратными матрицами размера МХМ, а векторы ру будут иметь размерность М. Для реализации (8) — (10) необходимо хранить все матрицы гху для 1~)чц У„все векторы рг для ! ~! ~ У+1 и матрицу (СУ вЂ” Адилг)-х, используемую для вычисления Рв.ьг.
Векторы Ру могут быть расположены на месте, отведенном для векторов неизвестных )~ г. Для хранения же всех матриц ге и матрицы (Сл — Аыххж)-' нужно запомнить М'(У+ !] элементов этих матриц, так как в общем случае матрицы сг являются полными н не. симметрнчнымн. Объем дополнительно запоминаемой информации при этом в М раз превышает общее число неизвестных в задаче, которое равно М (У+!).
Оценим теперь число арифметических действии для алгоритма (8) — (!О), имея в виду, что для решения серии задач (6) с различными правымн частями Ру прогоночные матрицы се и матрица (слг — Аллху) г могут быть сосчнтайы только один раз, в то время как векторы р н 3'у для каждой новой задачи пересчитываются.
В общем случае матрицы С вЂ” Аугх являются для любого ) полными матрицами. Поэтому для их обращения потребуется 0 (Ма) арифметических действий. Далее, умножение (Су — А)от)-г на матрицу Ву потребует не более 0(М') операций. Поэтому для вычисления ауег при заданном а по формуле (8) потребуется 0(М') арифметических действий. Для вычнсленйя всех и и матрицы (Су — Аугелг) г потребуется 0(М'У) действий. у Если матрица Ау является полной, то на вычисление Р ьг при заданном Ру и вычисленной (Су — Ауа )-' потребуется: 2М' операйнй умножения и 2Ма — М операций сложения.
Если Ау является диагональной матрицей. то это число сокращается — потребуется М'+М умножений и 2М' — М сложений. Следовательно, на,вычисление ру для 2 ~ ! ~ У+1 потребуется в общем случае 2МзУ умножений н (2М' — М) У сложений. Добавляя сюда операции, затрачиваемые на вычисление Рг прн заданной С,' (М' умножений и Мз — М сложений), окончательно получим М' (2У+1) уыножений и М' (2У+1)— — М (У+1) сложений. Для нахождения всех Ку для О~)~У вЂ” ! при заданном Ку потребу.
ется М'У умножений и М'У сложений. Итак, для вычисления Р и Гу потребуется М'(ЗУ+1) операций умножения и М' (ЗУ+ !) — М (У+1) операций сложения. Если не делать различия между этими операциями, то это составит 0 щ 6МзУ действий. Именно такое количество арифметических операций нужно затратить, чтобы найти решение каждой новой задачи из серик. Для решения единичной задачи вида (6), когда необходимо вычислять и прогоночные матрицы иу, потребуется () =.ОризУ+МзУ) действий. Пусть серия состоит из л задач вида (6).
Тогда потребуется затратить 0„=0 (МаУ)+блМаУ действий. При этом общее числа неизвестных в серии равно пМ (У+1). Отсюда следует, что на нахождение одного неизвестного /Мз1 потребуется в щ 0!1 — ) А-6М арифметических операций. Таким образом, '1 л ) с увеличением л относительное число операций на одно неизвестное уменьшается, однако оно всегда больше 6М. В этом заключается существенное отличие метода матричной прогонки от метода скалярной прогонки, где относительное число действий на одно неизвестное есть конечная велвчина, нв зависящая от числа неизвестных. 3. Прогонка для двухточечных векторных уравнений.
Рассмотрим теперь метод решения двухточечных векторных уравнений Рг+,Ц,,— ~171=Р, ы 0<1()() — 1, Р, 1~, = Рю (Ь'и'у = Р'д где 1д,— вектор размерности М, Рг+г и (;)г для 0(1(Л! — 1 квадратные матрицы МхМ, Р, и ((У вЂ” прямоугольные матрицы 109 соответственно размеров МзхМ и М,хМ, М,+М,=М. Вектор Р,; для 0<!(У вЂ” 1 имеет размерность М, а Р, и Рл+,— Мг и М, соответственно. Сначала сведем систему (11) к виду (6).
Для этого представим матрицы, входящие в (11), следующим образом: Р, = М'! — РЛ, О~ = 1! — 1%1(%, (12) "'= Р)! ! — Р),' ~' ' Ез'! — а)~ где Рззз и Щ' для 0 < Е < У вЂ” матрицы размеров М„х М„Уг, 1 = =1, 2. В соответствии с представлением (12) положим Ро=У' Р + =,г где ез; и !".зз — векторы размерности Мм я=1, 2. Используя (12) и (13), запишем систему (11) в следующем виде: Рззтзз Рззтзз зоз — Ото+ РЗОЗ + РКзо)оз — РйзтОМз =й; !зоз з ! дзз з ! Рзз ) рзз з !зз 0~(!(У вЂ” 1, (14) Введем теперь новые векторы неизвестных, полагая з е)оз и матрицы А„+1 — 10зз) Щ~, , 1<1<У вЂ” 1, ~';,'., 0<6'<У вЂ” 1, Рооз где 0"' — нулевая матрица размеров МзхМ„К 1=1, 2.
В этих обозначениях система (14) будет иметь вид Со~о Вооз Ро 1=0, — А,У;,+С,У,— В,У;.„-=Рп 1:з'(У, — А~+;)лз+См+;1'.„.зз=Гд+, (=У+1. (15) Итак, система двухточечных векторных уравнений (11) сведена- к системе трехточечных векторных уравнений вида (15), метод матричной прогонки для которой построен в п. 2. Для (15) 1!О а лгоритм матричной прогонки имеет следующий вид: ай+, — — (С; — Агой)-'Во й = 1, 2, ..., У ай = Сй 'Вй, (16) ()1+,— — (С,— А,ай) '(Р1+Ай(!1), 1=1,2,... Л'+1 ~1=С2'Рй (1'7) 3; = а;, 1 Уььй+ ()йй „! = Л', У вЂ” 1,... „О, К ..„й = (1,+, (18) причем матрицы а, и ан+1 имеют размер М,х М и Мх М, соответственно, а а, для 2(!(У являются квадратными матрицами размера МхМ.
Векторы рй для 2(! (У+! имеют размерность М, а рй и ~н,й — размерность М, и М,. Преобразуем формулы (!6) — (18). Учитывая структуру матриц Во находим, что матрицы а, имеют вид 22 22 Ойй Подставляя (19) в (16) и учитывая определение матриц А,, В и С,, получим формулы для вычисления а)' и ам 22 ! 12 1 12 1 р11 ! 1 ~ р12~! 12 ~ ойб 1221 12 ) р21 ~ ~р~~~ где а,"=(Р,")-'Р,". Далее, представляя вектор (1, в виде р;=рй, ~и+2=(!йн„, (3;= ', 2(1(У+! (21) и подставляя это выражение в (17), получим 2 М-1' ~ ° 2 й ° ()йнйй=()()йй — 1Жа)1)„.,~ 1(г й+1+11л)рЬ21), (23) где !!11 ="!Рй'(( 'Я. Подставим теперь (19) и (21) в (18) и используем введенные обозначения для Го В результате получим следующие формулы для вычисления компонент вектора неизвестных: тйййй=айй,ойй+Я„, (=У, Л' — 1, ..., 1, тйй=()н„, тй) = а)+ о'й+ ())1+ 1 = У, У вЂ” 1, ..., О.
(24) Итак, алгоритм метода матричной прогонки для системы двухточечных векторных уравнений (11) описывается формулами (20), (22) — (24). Так как эти формулы являются следствием из алгоритма прогонки решения системы (16), к которой мы свели исходную систему двухточечных векторных уравнений (! 1), то достаточные условия корректности и устойчивости полученного алгоритма сформулированы в лемме 5, где нужно заменить У на У+1, а матрицы Со А, и В; определены выше. 111 Используя алгоритм встречных прогонок для системы (15), можно построить соответствующий алгоритм для исходной системы двухточечных векторных уравнений (11). 4. Ортогональная прогонка для двухточечных векторных уравнений.
Рассмотрим еще один метод решения системы двухточечных уравнений (11), известный под названием метода ортогональной прогонки. Этот метод содержит обращение матриц Р, для !<!<У и ортогонализацию вспомогательных прямоугольных матриц. Будем искать решение системы (11) в следующем виде: У!=ВА+)'о 0<1<У, (25) где В; для л1обого 1 — прямоугольная матрица размера МХМ„ а ()~ и 3~,— векторы размерности М, и М соответственно. Определяя В, и К, из условия Р„В,=(р', Р,Г,=г„где О'* — нулевая матрица размера М,хМ„получим, что 17, удовлетворяет условию Р,У, =Р,. Найдем теперь рекуррентные формулы для последовательного построения, исходя из В, и г'„ матриц В; и векторов )'о Подставим (25) в (1!). Если Р~,— невырожденные матрицы, то будем иметь В; 1();+г+ У~н1 — Р('Д;Вф;=Р~+' (Р!.;-1-Д;1;.), 0<1<У вЂ” 1 или В;,1()с+!+ У~+1 — А!+1() =Х~+~ 0(!<У вЂ” 1ю (26) где А+г=Рс+Д;Во Х,~; = РД (Р~~,+ !1,З~~).
Матрица А,+, имеет размер М х М„а вектор Х„,— размерность М. Определим В;+, и г";~, следующим образом: А,,=В;~,й;.,о Г!+,— — Х;~,— В! р;+и (27) где й;+, и <р,„,— неопределенные пока квадратная матрица М,хМ, и вектор "размерности М,. Подставляя (27) в (26), получим соотношение В;+,(р;+,— й;+1р;) =В;+,~р,ам которое превращается в тождество, если положить й!+ (!г —— (1~+ — ~р;+, 0<1<У вЂ” 1. (28) Итак, если заданы невырожденные матрицы й; для 1 <1 < У и векторы ~р; для тех же 1, то по формулам (27) можно найти, исходя из В, и г'„все необходимые матрицы В; и векторы г; для ! <1<У. Осталось определить векторы р;.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
