А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 32
Текст из файла (страница 32)
2' т=1, 2, ...,1. При этом суммы и-го шага связаны с суммами, полученными на (и — 1)-м шаге, следующими формулами: г' "(з)=г' '(2э)+ г' '(2з — 1), 1 а — ь н (2Ь вЂ” 1) 2 008 24 а+2 2 сов 2~" ~+' й — 12 2с- з — 12 2-2 т — ! 2 Полагая в (35) и=1, получим г'1'(з) =Ье(з) а=1 2 2с (38) Итак, суммы г)" (!) вычисляются следующим образом. Исходя из заданных коэффициентов Ь~)со(!), 1(1(2', по формулам (Зб) вычисляются в итоге коэффициенты Ь',о (з), 1 ( з (2'. Они используются аатем в силу (38) в качестве начальных данных для ре- 172 ! ! ррентных соотношений (37).
Полагая в (37) последовательно ш: 1, ! — 1, ..., 1, получим в результате г'„" (1) и, следовательно, !/зз 4 !з»- з! Таким образом, алгоритм вычисления сумм (22) описывается формулами (30); (36), (38). Вамеч ание. В рекуррентных соотношениях (37) можно избежать де- (2Ь вЂ” 1) и пения на 2соз при помощи замены 2с-и+з оп! . (2Ь вЂ” 1) и ор, гь '(з) = Мп ' шько (з), 2! — и+з При этом формулы для аычислення шоно (з) принимают нид шь "(з) =2соз ш!ь,"о[2!)+шею (2з — 1), 2=1 2, ...,2' "', з=! 2, ...,2м ', и=1, ! — 1...,1, причем ш!з'(з) =Ь|! ! (з), э= 1, 2, ..., 2! н гь (1) = Ми ш! . (2!' — !) и (м а я (1) Й = 1, 2,, 2!.
(40) 2!+! операций сложения и вычитания; 2) для фиксированного ! на реализацию (36) требуется 1-! з) = ~ (2! — 1).2 -! — (! 2)2г-!.+1 т=! операций сложения, а на реализацию (37) требуется ! д! = ~ 2.2з- .2 -! — 2!.2з-а м*! операций сложения и ! !7~ — '~~ 2с-м.2м-! !.2з-а м=! (41) 173 Подсчитаем теперь число арифметических действий, которое нужно выполнить для реализации алгоритма (30), (36) — (38), Будем предполагать, что значения тригонометрических функций вычислены заранее. Элементарный подсчет дает: !) на реализацию (30) требуется «-! (~, =,~~ 2 (2" р — 1) = 2 2" — 2 (и -(- ! ) р=! операций умножения. Всего же формулы (36) и (37) требуют при фиксированном 1 д,=д,+д,=(31 — 2) 2'- +1 (42) операций сложения и у! умножений. Для всех 1= 1, 2, ..., п — ! затраты составят л-! !!- ! !',!,= ~д! = ~ ((31 — 2) 2' '+ Ц = — п2' — 4 2" + а+4 г= ! г=! сложений и Я, = ~., !)~ = ~', 12' ' = — 2" — 2" + 1 !=1 1=1 умножений.
Таким образом, алгоритм (30), (36) — (38) характеризуется следующими оценками числа арифметических операций: Д+ —— = !~!+ Я,=(3п!2 — 2) 2" — и+ 2 сложений и Я,=(п12 — 1) 2" +1 умножений. Если не делать различия между операциями сложения и умножения, то общее число действий есть 1~= Д +9з+Дв=(2!ой,)!7 — 3)Л! — 1ой,йГ+3, й7 2ю Для сравнения приведем оценку числа действий, которое нужно выполнить, чтобы вычислить все суммы (22) непосредственным суммированием. Будем иметь (2" — !)' операций умножения и (2" — 2) (2" — 1) операций сложения, а всего () = (7!1 — 1) (2М вЂ” 3).
Например, для 7!1=128 (п=7) получим 9=-1404 операции (из них 321 операция умножения) для построенного алгоритма и ф =32131 операция (нз них !6873 операции умножения) для алгоритма непосредственного суммирования. Отметим, что использование в алгоритме вместо (37) и (38) соотношений (39) и (40) приводит к следующим оценкам числа гз л действий: Д., = ( — и — 2) 2" — и-1-2 сложений н (~,„= — 2" — 1 2 умножений, а всего 9=(2!оя,7!! — 2) !!1 — !од, Л!чс1, йГ=2", что несколько больше, чем в алгоритме (30), (36) — (38).
Итак, поставленная выше задача 1 решена. Рассмотрим теперь задачу 2 о разложении по сдвинутым синусам. Предполагая, что У=2", запишем сумму, фигурирующую в задаче 2, в следующем виде: (2ь — !) а( Уь= Е пузш з +!, /г=1, 2, ..., 2». (43) Сравнивая (43) с (32), находим, что вычисление сумм (43) по сдвинутым синусам является вторым этапом изложенного выше 174 Используя для 1~2" соотношение шп л+ = . шп +шп — „ (22 — !) и/ 1 Г .
(2 — 1) н! . Ьц1 2 сочв ау 2л+! получим 2л 2п 1 1 чл . (2 — !) щ' чл . Атц1 уу — — . ~ аьз!и 2„+~ осз!и 2„ 2соз— 2п+! 2=! 2л — ! Л/ аь з!ив ов 2'Ч 2» э 2 соз — 2=! 2»+! 1=1,2, ..., 2»-2, где а)п! вычисляются по формуле аьп! = а„+ а„п„й = 1, 2, ..., 2" — 1. Сравнивая полученную сумму с (22), находим, что задача свелась к решенной ранее задаче 1. Для вычисления у,» получим формулу 2» 2»-~ у,»=,~ ~аз( — 1)" '= ~ (а»2,— а»2).
сл! Ьл 1 Здесь суммирование ведется непосредственно. Для числа операций изложенного алгоритма верна оценка Я = 2М 1оя» У вЂ” !оцп Л'. 3. Разложение по косинусам. Рассмотрим теперь алгоритм решения задачи 3, состоящей в вычислении сумм (13), при У=2». 175 .!лгоритма вычисления сумм (22), если в (32) положить != а.
Сле- (овательно, если обозначить 21" (1)=У», й=1,2, ...,2", Ьи>(1) а~ ! 1 2 2„ то формулы (36) — (38) прн 1= а описывают алгоритм вычисления сумм (43). Полагая в формулах (41) и (42) 1=а, получим сле- дующие оценки для построенного алгоритма: 9+ —— дл лл /3 .=~ — п — ! ) 2" +1 операций сложения и Я,=долл — 2" операций л умйожения, а всего Я=(2!оя, Л( — 1) й(+1, У=2'*. Таким обра- зом, суммы (43) вычисляются примерно с такими же затратами арифметических действий, как и суммы (22). Напомним, что суммы (43) используются для вычисления коэффициентов Фурье сеточной функции ао заданной при ! =1, 2, ..., !!Г.
Для восстановления функции по заданным коэффициен- там Фурье необходимо вычислить суммы 2» у, = ~~'„а„з(п „,, 1=1, 2, ..., 2". (43') /г= ! Имеем гп уо=~' а',"сов — '„, Й=О, 1, „2", (44) )=о где введено обозначение а)о) = агл Принцип построения алгоритма совершенно такой же, как и при разложении по синусам, и состоит из двух этапов. На пер- вом этапе группируются слагаемые сумм сначала с индексами 1 и 2" — 1 для 1 = О, 1, ..., 2" ' — 1, затем с индексами 1 и 2" ' — 1, 1 = О, 1, ..., 2" ' — 1 н т.д.
В результате р-го шага будем иметь г--) 'чл о) (2)) — ! ) я( у — <о ))= ~ а -+ усов 2п-лло )'=о и = 1„ 2, ..., 2" ', в = 1, 2, ..., р, гл-р у)го= ~~' а)Р)сов — в)р, й=О, 1, . )=о Полагая в (45) влл р=л, найдем у а)л) + алл у и а)п) а)п) у „, а)п) (47) а остальные уо находятся по формулам гп-л о) (2А 1) щ Угл-~ 1«О и = Р . аоп-л+~ ) СОВ «л) > )=о (г = 1, 2, ..., 2« ', в = 1, 2, ...,и†1. Замены для каждого фиксированного в г)ло) (1) У, ь 1 2 2« -* Ь';о)(1)=а))')- «ь 1=0, 1, ..., 2" ' — 1, 1=и — в, в=!,2, ...„п — 1 приводят нас к вычислению следующих сумм; о) — 1 )оо) (1) ~ ( <о) (1) («и ) ! 2)+) )=о 1=1,2, ...,а — 1.
)о = 1, 2, ..., 2', (48) 176 Эти формулы справедливы для р = 1, 2, ..., л. Коэффициенты а))Р) определяются рекуррентно а)р — — а)р —,-ао -р+* и о ) -и ~ )р-)) а «-р«) )=а)Р-и — а",. 'р+) р 1=0, 1, ...,2 -р — 1, (46) со <р-)) а л-р =-а и-рю р=-!, 2, ..., а. гса " (з) = гасас (2з) -(- „) г$ ' (2З вЂ” 1), 1 2 соз 2с-аеа 2соа 2с й=1,2, ...,2™, з=1,2, ...,2а ', т=1,2, ...,1 (49) для вычисления ас-а гса '(х) = ~~' Ь'; '(и) соз (2а — 1) сс! с'=а А 1 2 2с-а з=1 2 2а (50) при т=0, 1, ..., 1. Коэффициенты Ь'; '(з) также определяются рекуррентно для а=1,2, ..., 2" ', начиная с Ь)а(1), поформулам . Ь'; '(2з — 1) =Ь,',:,м (и)+Ь(с) тсс(з), 1=1,2,...,2с" — 1, т=1,2,...,! — 1, Ь,' с(2з — !)=Ь',"-"(з), т=1, 2, ...,1, Ь';а'(2З) =Ьасас "(з), — ! 2с-а 1 т ! (51) Полагая в (50) т=(, найдем начальные данные для соотношений (49) асс" (з) =Ьес'(3), з=1 2з . ° ~ 2' (52) Таким образом, алгоритм вычисления сумм (44) описывается формулами (46), (47), (49), (51) и (52).
Элементарный подсчет числа арифметических действий для построенного алгоритма дает: Я+ —— (3)2 и — 2) 2" +и+2 операций сложения и Я =(п)2 — 1) 2"+1 операций умножения, а всего Я = Я, + Я е = (2 1од, Ш вЂ” 3) У+!од, У+ 3, сЧ = 2". Заметим, что, как и в предыдущем алгоритме, здесь в соотношениях(49) возможна замена сас .
(2сс — 1) н са> при атом из (о2) следует нс) '(з) =ран(з), з=1, 2, ..., 2с. 177 Второй этап алгоритма состоит в вычислении сумм (48). Как и раньше, последовательно разделяя слагаемые с четными и не-- четными индексами 1, будем иметь следующие рекуррентные соотношения: Рекуррентные формулы дли ы~»"'(е) имеют нид ы»~ '(е) = 2 сон ы1"о(2»)+иф"'(2» — ц 2ю-и+с се,,сСм.„, » „(е) = 2 сое ы» (е) — и» (2» — 1), о -и (2» — 1) и о,о 4. з.о »=1, 2, ..., 2~ м, е=-1, 2, ...,2м-~, от=1, 2, ..., 1. 4. Преобразование действительной периодической сеточной функции. Задача 4 о преобразовании действительной периодической сеточной функции состоит в восстановлении функции по формулам (17) при заданных коэффициентах Фурье ау и а, и в нахождении коэффициентов для заданной функции по формулам (18).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
