А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 22
Текст из файла (страница 22)
Из (25) при (=У и системы (11) получим два соотношения ~, = Вп(!д,+ Кк, ()п3/д,— — Гч+, с известными Вч и 3'~,. Отсюда для Р,д найдем уравнение Д,дВ йм= Р,+,— 1~„,~ч с квадратной матрицей 9пВ„, размера М,~сМ,. Эго соотношение можно записать в виде (28) йк. ()л =Ь+,— Ь+, (29) где ~м„=Р „„<р „,= Я,Гг,, й „,= Д„чВа,. !!2 (ЗО) в„„=(Ь„, а»), и=1, 2, ..., й — 1, ⻄—— (32) В силу сделанного предположения о ранге матрицы А,(., столбцы а» для 1 ( й ( М, линейно независимы, и процесс ортонормиро- вания протекает без особенностей. Если матрица йч+, ие вырождена, по формулам (28), (29) последовательно, начиная с (3 „„найдем все р, для О(!()Ч. Решение системы (1! ) может быть тогда найдено по формулам (25).
Так как имеется произвол в выборе матриц Й( и векторов (рп то приведенные выше формулы описывают скорее принцип по-' строения методов решения системы (! 1), нежели конкретный алгоритм. Выбор определенных й, и (р( порождает некоторый метод для системы (11). Такие методы мы будем называть па- прежнему прогонкой, на прямом ходе которой вычисляются Вг и Го а на обратном — р, и решение Уо Остановимся теперь на одном способе выбора О, и (ри Так как формулы (27) и (28) предполагают обращение матрицы ()(+„ то ана должна быть достаточно легка обратима.
В рассматриваемом методе ортогональной прогонки матрица О(„; и вектор Ч((, порождаются требованиями: 1) матрица В;~, строится путем ортонормирования столбцов матрицы А( „2) век- тор У(+( должен быть ортогонален столбцам матрицы В;+,. Следствием этих требований являются равенства В;.,В(+( = Е™, В((., Г(ь»( = О, [29') где В;„— транспонированная к Вг„матрица, а Е" — единичная матрица размерз М,хМ,. Найдем сначала выражение для (р;+,.
Из (27) и (29') получим О = В;„У,+, — — В„",Х„,— В(„В„.,(р(+(= В„",Х„.,— ьр»,, Итак, век- тор ср»+, определен: (р;~,=В;„Х»„. Построим теперь матрицы й(~, и В;„,. Существует несколько способов ортонормирования столбцов матрицы А(+,. Мы рас- смотрим метод Грама †Шмид. Пусть матрица А;~, имеет ранг М,. Обозначим через а» и Ь» — я-е столбцы матриц А(„ и В(~, соответственно, а через (,) †скалярн произведение векторов. В качестве Ь, возьмем нормированный столбец а, Ь( = а(/в„, в„= 1~ (а„а,). Далее будем искать столбец Ь„в виде »-1 Ь,= — ~,— ~ „(.), 2(((»„(3(( в»» (, где коэффициенты в„находятся из условия ортоганальиостн вектора Ь векторам Ь„Ь„..., Ь„„а в»» — из условия норми- ровки Ь». Матрицы В, и,(1! для 0(!(У вычисляются по формулам (30) — (32) и запоминаются.
Полагается Йч+! — — 9«гВ««,. 2) У«=Х! — В!«р«, «р;=В,*.Хо «=О, 1,, У, Х! — — Р!'(Р«+91 «У! !), 1(Е<У, Х,=~ ' ' ). (34) / (р!!)-! р Вычисляются и запоминаются векторы г', для 0(«(У и «р; для 1<«(У. Полагается «р +,— — «',1,чХп,. 3) 1««+«(); = (1!+! †«р;+1, ! = У, У в 1, ..., О, (),+!. — — Р ~-„ 1~, = В«(!!+ Г«, 0(1- ' У. (35) (36) Сведем систему (36) к системе двухточечных векторных урав- нений вида (11), полагая !г«=("! ), О«У вЂ” 1. Несложно видеть, что (36) эквивалентна следующей системе: У«+; — «',1У! =О, 0(! < У вЂ” 2, (37) Р,)~,=1, «Ь „Ул. 1=0, где Р,=(!! (О!/, «1, «='!0(1!/, «! =!~+-~.
Система (37) естьчаст- !~ 1!1 ный случай (!1) с М,=М,=!, М = 2. Для решения (37) используем алгоритм ортогональной про- гонки (33) — (35). Для рассматриваемого примера матрицы В, имеют размерность 2х1, !1! — размерность 1х1, векторы 1! бу- дут иметь размерность 2, а векторы р! и «р! — размерность 1, В табл. 3 приведены матрицы В, и !з«, а также векторы Г«, «р; и (1, для У=11. Применяемый метод ортогональной про- гонки позволяет получить точное решение у, задачи (36).
11б 3 амеч ание. Так как матрицы й! для 1<«(У являются верхиетреугольными матрицами размера М, х М„то для нахож- дения (11 по заданным р«+! и «р,.„, требуется 0(М',) действий. Для иллюстрации предложенного алгоритма рассмотрим при- мер. Пусть требуется решить следующую трехточечную раз- ностную задачу: у«,+у, уг„-=О, 1«<У вЂ” 1, у,=1, у~=О Эта задача рассматривалась нами ранее в п. 4.
3 2, где методом немонотонной трехточечной прогонки было найдено ее решение для У, не кратных 3, а именно, (Л« — !) П з!п у,=, 0<!'<У. з!и— 3 ).с с'ч 1сч О ~сч (~с )сч сс -~сч -)сч о |сч Ъ -(сс о ! сс — ! ' О ~~сч — )сч ! (~сч ! -Г -1~ о 1 5. Прогонна для трехточечных уравнений с постоянными коэффициентами. Обратимся снова к методу матричной прогонки для трехточечных уравнений и рассмотрим частный случай таких уравнений, а именно: — )'~;+СХ' — К,~,= Г~, 1(1(Л' — 1, где С вЂ” квадратная матрица размера М~~М, а Г~ и Р~ — искомый и заданный векторы размерности М. В и. 1 было показано, что к системе трехточечных уравнений вида (38) сводится разностная задача Днрихле для уравнения Пуассона на прямоугольной сетке, заданной в прямоугольнике, причем матрица С будет симметричной и трехдиагональной.
Далее, в п. 2 5 4 было показано, что метод матричной прогонки, имеющий для (38) вид а~„-— -(С вЂ” а~) ', 1=1, 2, ..., М вЂ” 1, а,=О, (39) Р,.„=~„„(~,.+Р,.), 1=1, 2, ..., У вЂ” 1, Р,=К„(4О) является корректным и устойчивым. Там же было показано, что собственные значения матрицы С больше 2: лэ Ха —— Хд(С)=2+4 — „, 'з1п' — "' >2. (42) "1 1 Напомним, что в случае общих трехточечных векторных уравнений для алгоритма матричной прогонки требуется 0 (М')ч') арифметических действий для вычисления матриц а, н 0(М'У) действий для вычисления прогоночных векторов р и решения У'. Для хранения полных и, вообще говоря, несимметричных матриц а~ необходимо запомнить М'(У+1) элементов этих матриц. Уменьшаются ли эти величины, если методом матричной прогонки решать специальную трехточечную векторную систему (38) с постоянными коэффициентами? Для рассматриваемого примера все матрицы а~ будут симметричными в силу симметрии матрицы С, но хотя С есть трех- диагональная матрица, все матрицы а~, 1 > 2, будут полными.
Следовательно, можно уменьшить, учитывая симметрию матриц и,, только объем промежуточной запоминаемой информации, но не .более чем вдвое. Порядок числа арифметическкх действий по М и У не изменится. Построим теперь модификацию алгоритма (39) †(41), которая не требует дополнительной памяти для хранения промежуточной информации и реализуется с затратой 0(ММ') арифметических действий, если решается задача (38) с трехдиагональной матрнцей С. Сначала найдем явный вид прогоночных матриц а~ для любого 1.
Для этого, используя (39), выразим аг черезматрицу С. 117 Замечая, что гхг=О, сг,=С г, сг,=(Са — Е)-'С, (43) будем искать решение нелинейного разиостного уравнения (39) в виде а = Р) гг (С) Р,, (С), 1 ) 2, (44) где Р,(С) — полином от С степени ). Перепишем (39) в виде сг,+г(С вЂ” сг~)=Е, 1)2, и подставим сюда (44). Получим рекуррентное соотношение Р, (С)=СР, г(С) — Ру,(С), 1) 2, или после сдвига индекса на единицу и учета (43) Р;,(С) =СР (С) — Р,(С), Р,(С)=Е, Р,(С)=С. Итак, формулы (46) полностью определяют полипом Р, (С) для любого 1) О.
Найдем решение (46). Соответствующий алгебраический по- липом удовлетворяет соотношениям Р гг(1)=1Р Я вЂ” Р~ г(1), 1)1, Р, (1) = 1, Р, (1) = 1, которые представляют собой задачу Коши для трехточечного разностиого уравнения с постоянными коэффициентами. В п.
2 9 4 гл. 1 было найдено решение этой задачи Рг(1) =У,. ) — ), /11 1)0, где У,(х) — полипом Чебышева второго рода степени 1 а!и 61+ 1) агссоа х) х)(1, У (х)= Мп агссаа х У аь 61 + 1) Агси х) аь Агсь х Таким образом, явное выражение для прогоночных матриц гх найдено: аг — — У7', (2) Уу, ( ~), 1)2, а,=О. (46) Это избавляет нас от необходимости проводить вычисления по формуле (39) прогоночных матриц а, на что требуется основной объем вычислительной работы в алгоритме (39) — (41). Кроме того, матрицы сг нет необходимости запоминать, Рассмотрим теперь формулы (40) и (41).
Они содержат умножение матрицы сг+, на векторы Р,+() и У'„. Покажем сейчас, как можно, не вычисляя а~ по формуле (46), определить произведение матрицы сг, на вектор. Для этого нам потребуется лемма 6, которую мы приведем без доказательства. 118 где х,— корни )„(х), а !„'(х) — производная полинома 7„(х). Используя лемму 6, найдем разложение иа простые дроби отношения 1р(х)= О (, !)2, Так как корни (7),(х) есть (!,, (х) О!, (.) лп хе=сов —, й= 1, 2, ..., ! — 1, в ° ( Ии-т †„„ (()! ,(х,Ц = МП1 —. ! У!,(хг) =( — 1)" ', то в 'силу леммы 6 имеем следующее разложение для 1г(х)! 51П1 /л~ 1р (х) = — ~= — = ~„, (х — соз —.) У , (х) т ! ! лп 1-1 (!!,( ),~ ! !' (47) Из (46) и (47) следует еще одно представление для матриц и!, которым мы и будем пользоваться !-1 г 51П1— )п а.= ~~' агу (С вЂ” 2соз —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
