А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 26
Текст из файла (страница 26)
Необходимые разложения найдены. Получим теперь выражения для матриц (С!» !!1 ! и »-2 [С!»-!!1-1П Ссо через матрицу С. Из (13) и (14) с учетом раз- !=О ложений алгебраических полиномов (16), (17) получим 2! г -» [С!» "1 '= ~~' и1»,(С вЂ” 2соз ) Е), 1=1 ГТ (21 — 1) л '! -в (С!»-!1~-! П Сн' = — ~ (С вЂ” 2 сов Е) .1.». —,» ! 2» 1=О 1=! 135 »-1 Итак, явное выражение для С'»' и Д С"' получено. 1=О Для дальнейшего нам потребуется лемма 6 (см. п. 5 2 4 гл. 11). Согласно лемме 6 любое отношение д (х)11„(х) многочленов без общих корней в случае л>т и простых корней („(х) разлагается следующим образом на элементарные дроби: л а (х) ~ ! а ( ) У„( ),х — х1' 1 7,',(,) ' Найденные соотношения позволяют записать в следующем виде как формулы (1О); »Я — 1 ,» и .»-т,, ! !»-»! ~! = 4х и!.
»-.С!, »-~ (Р!-»»- +)з;.~»- ). 1=! р'"=0,5(р!? "+Я)» "), (18) ! Р'н = — Г, 1 г' 1 —.2»,2 2»,3 2", ..., А! — 2», Й=1,2, ...,и — 1, так и формулы (11): »- ?;. = ~, С! !» »[р!» !!+а! „, (?;,»- + ?!ь»»» —.)~, !=! ?'„= — Р„?',ч — — Е»!, 1=-2» ', 3 2» ', 5 2» ', ..., Л! — 2» ", й=н,п — 1, ...,1, (19) где обозначено ( — !)'+! Итак, получены преобразованные формулы (18), (19), описывающие метод полной редукции решения задачи (1). Эти формулы содержат только операции сложения векторов, умножения вектора на число и обращения матриц. Заметим, что если С вЂ” трехдиагональная матрица, то трех- диагональной будет и любая матрица С, »,.
Задача обращения таких матриц была решена в главе П. Лалее, если для матрицы С выполняется условие (С?; ?')) 2(?; ?'), то из (20) следует, что матрицы С, » будут положительно определенными, и, следовательно, будут иметь ограниченные обратные. Тогда из разложения[С'» »!1 'получим, чтодлялюбогой) 1 матрицыС'» " не вырождены. Напомним, что зто предположение использовалось при получении формул (10). 9 3.
Алгоритм метода, Полученные выше формулы (18), (19) служат основой для первого алгоритма метода. Рассмотрим прежде всего, какие промежуточные величины и на каком этапе должны вычисляться и запоминаться для последующего использования.
Анализ формул (19) показывает, что при фиксированном й для вычисления ?' используются векторы р!» " с номерами 1=2»-', 3 2»-', ..., А' — 2»-'. Любой вектор р(!ь с тем же номером 1, но меньшим, чем й — 1, номером 1, является вспомогательным и запоминается временно. Поэтому определяемые на й-м шаге по (!8) векторы р';»' могут размещаться на месте р,'» ", равно как и неизвестные ?'у, вычисляемые по (19). Метод не требует дополнительной памяти ЭВМ вЂ” все векторы р!»' размещаются на том месте, где затем будут размещаться ?". 136 Пронлл<острируем организацию вычислений в рассматриваеои<м алгоритме на примере.
Пусть <о'=-!6(н=-4). На рис. 1 и<и<и.<,н<а последовательность вычисления и запоминания вектои р',". Заштрихованный квадрат означает, что для указанного Рис. 1. Рис. 2. значения индекса й запоминается для последующего использования вектор р<»' с соответствующим номером З Соответственно, незаштрихованный квадрат означает, что р)»< является вспомогательным и запоминается на указанном месте временно. Стрелки указывают, какие векторы р<» " используются при вычислении р<»'. В результате прямого хода метода будут запомнены следующие векторы р';»'. о< <и <о< н< ~<о< <и <о< ~<о«о<»»о< р<о> и«о< ш ~<о< юии нспотьзуются для вычисления Г на обратном ходе метода. 11а рис. 2 показана последовательность вычисления неизвести«, и 1~ (символическое обозначение о).
Стрелками указано, 137 какие у~, найденные на предыдущих шагах, и какие р)«м (символическое обозначение ~) используются для вычисления при заданном й. Переходим теперь к описанию алгоритма метода полной редукции. Прямой ход метода, согласно (18), реализуется следующим образом: 1) Задаются значения для р' >= Р, 1=1, 2, ..., л! — 1. 2) Для каждого фиксированного й=!, 2, ..., и — ! при фиксированном 1=2", 2 2», ..., У вЂ” 2»сначала вычисляются и запоминаются векторы <«- > !«-м Ч~ Рг-»»-~+Р!+«»-~ (21) Затем для 1= 1, 2, ..., 2« ' решаются уравнения Сь «-Рю ="ь «-Л 122) В результате постепенным накоплением результата на месте р';" "' находится р';«' Р)«'=0,5(р)» м+е,+и»+...
+п.,»-.), (23) Обратный ход метода, согласно (19), реализуется следующим образом: 1) Задаются значения для К, и Кч: 1; = Р„ К„= Рм. 2) Для каждого фиксированного й =и„ и†1, ..., 1 при фиксированном 1 =2" ', 3 2» ', 5 2» ', ...,У вЂ” 2«-' вычисляются и запоминаются векторы Ч'= 1)- я»-'+ У!+ »«-м»Р =Р) (24) Затем для 1=1, 2, ..., 2« ' решаются уравнения Сь»-~пс = «р+аь «-М (25) В результате постепенным накоплением значений на месте р)«" находится вектор неизвестных Х' 1 / = Ф«+ ю» + ° ° ° + па»-1. (26) Подсчитаем теперь число арифметических действий, затрачиваемых на реализацию описанного алгоритма. Пусть размерность вектора неизвестных У' есть М, а через о обозначено число действий, требуемых для решения уравнения вида (22) или (25) при заданной правой части. Будем считать, что величины я, » заранее найдены.
Подсчитаем сначала число действий Я„ затрачиваемых на прямом ходе. При фиксированных й и 1 на вычисление вектора ~р по формулам (21) потребуется М операций. Далее, для каждого 1 на вычисление правой части в (22) и на решение уравнения (22) потребуется М +д операцвй. Поэтому на нахождение всех п, потребуется 2» '(М+ д) действий. Вычисление р'"' по формуле (23) осуществляется с затратой 2» 'М + М действий.
138 (7') !39 11»ак, для вычисления р)»> для одного й и 1 нужно затратить М+ 2»-' (2М+ д) операций. Далее, при каждом фиксированном й нужно вычислять й>)2» — 1 различных р!". Следовательно, общее количество действий затрачиваемых на реализацию прямого хода, равно »-1 ,»! Е,=~ [М+(2М+~)2- ~(р — ) = »=! = (М+ 0,5д) Уп — (М + д) 7>! — М (п — 1) + д. (27) Подсчитаем теперь число действий 9„затрачиваемых на об- ратном ходе. При фиксированных й и ! на вычисление по фор- мулам (24) потребуется М действий, на нахождение всех о, в (25) — (2М+д) 2»-' действий и на вычисление 1' по фор- муле (26) — (2»-' — 1) М действий.
Так как число различных значений 1, для которых при фиксированном й проводятся ука- занные вычисления, равно >>!!2», то >',>, равно !>> Я, = ~», [М+ (2М+ д) 2"-»+ (2» ! — 1) М1— »=! = (1,5М+ 0,5д) й>п. (28) Складывая (27) и (28) н учитывая, что п=!од,7>', получим следующую оценку для числа действий метода полной редукции, реализуемого по приведенному выше алгоритму Я = Я>+ >',>» = (2,5М+ д) Л! 1оа» й! — (М+ >!) й! — М (п — 1) + д. (29) Из (29) следует, что если д=О(М), то Я =0(МЛ>!оя, >>!).
4. Второй алгоритм метода. Главным достоинством построен- ного алгоритма является минимальное требование к памяти ЭВМ вЂ” он не требует дополнительной памяти для хранения вспомогательной информации. Это качество достигается ценой некоторого увеличения объема вычислительной работы, которая затрачивается на повторное, вычисление промежуточных вели- чин. Рассмотрим еще один алгоритм метода, который характери- зуется меньшим объемом вычислительной работы, но который требует дополнительную память, сравнимую по величине с общим числом неизвестных в задаче.
Для построения второго алгоритма вернемся к формулам (6), (7), описывающим метод полной редукции: С'»' =[С'» "1' — 2Е, Р>»>=Р!» '> +С» "Г!» >>+Р>~ ',.> (6') ! >»>»-» >' !+»>' ! Э /=2» 2.2» 3.2» й! 2», й=1,2, ...,п-1, Си!>!Г>!»и+у!»»+у!+3» 1'» —— ~'„1'л — — ~ьл, / 2» ', 3 2» ', 5.2» ', ..., й! — 2» ', й=л, п — 1, ...,1.
Здесь, как и в первом алгоритме, векторы Г,'»> непосредственно не вычисляются, а вместо них определяются векторы р)»> и >7)»>, связанные с р>>»' следующим соотношением: р" = С"'р' '+ >7' ', 1=2», 2 2», 3 2», ..., У вЂ” 2", 1=0, 1, ..., а — 1. Найдем рекуррентные формулы для вычисления векторов р';»' и >7>»>. Так как вместо одного вектора р>м мы ввели два вектора, то имеется определенный произвол в определении р)м и >7)»>.
Выберем р';" и >7)»> так, чтобы удовлетворить начальному усло- виЮ Р)">— = Ру. Для этого положим р<»> 0 >><ю> р 1 1 2 У (31) Далее, подставляя (30) в (б'), получим с р»+а'=с — (17'- +р'."-" +С вЂ”,р»»- + (»-'>,,+ > Р>'+>» +г7>,»-, +гу'„»>-,, 1=2",2 2", ...,У вЂ” 2»,й=1,2, „и — 1, Выбирая (32) и УчитываЯ, что С'»>+2Е=[с>»»1', найдем отсюда С>» "Р)»>=>7(» "+Р' "-,+С>» "Р>»-"+Р!»-'> . (ЗЗ) > >-В»- > >»>»-> Здесь мы снова предполагаем, что С>и для любого 1 есть невы- рожденная матрица.
Обозначая 5>» " — — р>>"' — р';» ", получим из (31) †(ЗЗ) следующие рекуррентные формулы для вычисления векторов р)»> и >7>»>: > с — з~ — =: — +р'"-" +р<.'-", '~> +»-в»-> ' Р>»а'>->' р<»> — р>»- >+ е>»-»> (34) <"> = 2 <»> >7> = Р> +>7; >»- > >7>„.,»- >7<о> = р р(о> = 0 1=2», 2 2», 3 2», ..., У вЂ” 2», 1=1, 2, ..., и — 1. Осталось исключить Р)» " из формулы (7'), Подставляя (30) в (7') и обозначая Ф';» "= Р~ — р';» ", получим следующие формулы для вычисления Г,: СЯ М)» >=д>>» >+ 15~ «,+ У~ '» р>»-»+ ~>»-» > > 1»» а> у»> р»> 1=2' ', 3 2» ', 5 2» ', ..., У вЂ” 2"-', й=п, и — 1, ..., 1.
140 (35) Итак, мы получили формулы (34), (35), на которых основывается второй алгоритм метода полной редукции. Эти формулы содержат операции сложения векторов и обращения матриц С'»-о. Остановимся теперь на вопросе обращения матриц С'»- >. Как было показано выше, матрица С'»' есть полипом 2» степени относительно исходной матрицы С и определяется по формуле (13) через полипом Чебышева первого рода Т„(х): С'»'=2Т,» ( — С), причем коэффициент при старшей степени равен единице. Так как корни полинома Т„(х) известны (см. (!5)), то С'»' можно представить в следующем факторнзованном виде: С'»'= Д (С вЂ” 2соз — / (2/ — 1) и Е), й=0,1, ... /= з 2»+» Используя обозначения (20), матрицу С'» " можно записать в следующем виде: 2» 1=! 2» Факторизация (36) позволяет легко решать уравнения вида С'»-пп =~р с заданной правой частью «р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
