А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 33
Текст из файла (страница 33)
Пусть 7т"=2" и заданы коэффициенты Фурье. Тогда необходимо вычислить суммы ел-ю се 1 У»= )~ а) соз 2„+ хы а',"з1п 2е, 1=О, 1, ...,2" — 1, (53) )=о 1=1 Построим соответствующий алгоритм. Для этого заменим в (53) индекс й на 2" — й. Учитывая равенства о (2е — ») я) 2»и), 2 (2е») и) 2»п. соз 2» 2» = соз —, щп 2е = — з)ив 2м в получим, что у» можно вычислить по формулам У»=У»+У» уе -»=у» — у», й=1, 2, ...,2" 1 — 1, (54) Уе = Уе Уе"-' = Уе"-' где ее у» = л, а';" соз — „',, й = О, 1, ..., 2'-т (55) 1=о ск 3 1 у = ~~'., а)'з1п-;=т й=1,2, ...,2"-1 — 1.
(56) 1=1 Итак, вычисление сумм (53) сводится к вычислению сумм (55) и (56) и последующему использованию формул (54). Сравнивая формулы (55) и (56) с формулами (44) и (22), находим, что суммы (55) и (56) можно вычислить по алгоритмам пп. 2 и 3, заменив в них п на и — 1. Подсчитаем теперь число арифметических операций, необходимых для вычисления сумм (53) указанным способом. Из оценок числа операций, найденных для алгоритма п. 2, получим, что суммы (56) вычисляются с затратой Я, = (Зп!4 — 7!4) 2" — и+ 3 операций сложения и Я =(и!4 — 3!4)2" +1 операций умножения.
178 Оценки алгоритма п. 3 дают для сумм (55) следующие значения: Ц+ — — (Зп)4 — 7!4) 2" +и+! операцийсложения и 1,1, =(п)4 — 3,!4) х х2" +1 операций умножения. Добавляя сюда Я+ — 2" — 2 операций сложения, затрачиваемых на реализацию(54), получим для построенного алгоритма 9~ = (Зп,!2 — 5!2) 2" + 2 операций сложения и»г,=(п!2 — 3!2)2" +2 операций умножения, а всего Я = =(2 !о81 У вЂ” 4) Аг+ 4 А! 2и Обратимся теперь к вычислению коэффициентов Фурье действительной периодической сеточной функции. Задача состоит в нахождении сумм 2" — ! у»= ~, а)1!соз — „!, А=О, 1, ..., 2" ' (57) !эа 2" — ! у„= ~Ч' а~)11з1п — „!, А=1, 2, ..., 2" ' — 1, (58) 1=! где а!!»! — заданная функция.
Алгоритм вычисления (57) и (58) родствен алгоритмам пп. 2 и 3, но отличается некоторыми деталями. Здесь на первом этапе группируются члены сумм (57) и (58) сначала с индексами ! и 2 1-1-! для ! =О, 1, ..., 2" ' — 1, затем с индексами ! и 2" '+! для ! =О, 1, ..., 2" ' — 1 и т. д. Приведем более подробно первый шаг процесса последовательной группировки слагаемых на примере суммы (57). Преобразование суммы (58) осуществляется аналогично. Итак, представим (57) в следующем виде: »и 1 »и у»= »'» о! соз 2 + »'» о1'соз 2 %~ !»! 2»п! % 1 !Л! 2»!1! !=о /-»п-ю и совершим во второй сумме замену, полагая ! =2" '+!'. Это дает »л-1 !=о Обозначая о! !о! <а! а! еа! +а, а,, 1,,=а! — а,, 1 ! 1=0, 1, ...,2 — 1, получим вместо (57) следующие суммы: 1» — 1 ! ч !О (2» — !) !и !=О ! у,» —— ~~' а~!Осоз — „!,, А=О, 1, ..., 2" '. !=о (59) (60) 179 Аналогично вместо (58) получим суммы 2»-1 Е !1) .
(2» — 1) )<У )'= 1 2» 1 1 1 '" 2»-1> 1=! Уаа-1 = (61) )2=1, 2, ..., 2»-' — 1, где а<" определены в (59). На этом первый шаг закончен. На втором шаге описанным способом преобразуются суммы (60) и (61). В результате р-го шага будем иметь 2»-И ч-и <1) (2а — 1]»/ у,»-)„„ы —— ~~ а,'», )соз )=о )о = 1, 2, ..., 2" ' ', з = 1, 2, ..., р, 2»-Р 2Ащ Уара= ~ а<р'соз2»-р, У=О, 1, ..., 2»-р-а ° )=о (62) где р = 1, 2, ..., и†1 и 2»-8 Т» !1) . (2<< — 1) я) 1~2-~) = ~ й»-» 3!и )'=1 2, ...,2»'1, 2=1,2, ...,р, ! <> . 2Ащ я=1, 2» Р- (63) у>ра а'р)=а<р "+а!И 1),. ! ! » -! (ю <»-и <Р !) аа» р,.— — а)' — аа» р, 1=0,1, ...,2»р — 1, р=1,2, ..., а. Полагая в (62) р = а — 1 и з = р» в — 1, получим у й<»-1) ! йа)-О й<И> Уа= О < 1 = » < у = й<»-'> — а<И "= а'») Уа»-1= а 1 = 1 > <И-1) У и-а=па (65) 180 где р = 1, 2, ..., и — 2.
Коэффициенты а<Р) находятся рекуррентно по формулам пз (63) при р=п — 2 найдем у и-я — Ом-1> — а>л-1>=а»г И, (бб) Остальные у„и у» находятся по формулам 2» о-1 ч~ у>! (2» — !) >>/ у... и — ~Е а„, соз у=о О» о- 1 %~ (5) . (2» — !) >>у У '-'уы-ц = ~ а>.-.+уз!и ,=1 1=1,2, ...,2" '', з=1,2, ...,а — 2. Совершим здесь замены для фиксированного уп г»>о>(1)=у, -,, а»о>(1)=у -"у>» >! >уо 1, 2, ..., 2"-'-', (>у>о>(1)=а,',,„., 1=0, 1, ..., 2«-о 1, 1=п — з, а=1, 2, ..., и — 2. Это приводит нас к вычислению сумм 2 — 1 21»о> (1) — ~~» (>>о> (1) соз (2» у=о 2' 2 -1 зуо>(1) ~~> ~ (>>о> (1) зн>(2» !) пу я=1,2, ...,2' ', 1=2,3, ...,а — 1.
(67) (2» — !) (2у — 2) л . (2» — !) 2у» з1п +з1п 21-»>+1 21-»>+1 соз (2» — !) и ( (2» — !) (21 — !) и зп 21-»>+1 21->о+1 (2» — !) (2у' — 2) и (2» — !) 2у>л 21-»>+1 21-»>+1 = 2 сов (2» — !) я (2У> — !) (2у — !) >о соз 21-я+а 21 >о+» !$! На втором этапе алгоритма вычисляются суммы (67).
Здесь, как и в алгоритме п, 2, эти суммы преобразуются путем разделения слагаемых с четными и нечетными индексами у и использования равенств ... Это дает следующие рекуррентные формулы: (~) = г1 ' (2э)+ 2г 1) а~со (2э — 1), 1 2 сов 21 — ге+1 (2!г — 1) ! 2 соэ 21-ю +1 (э) = г~ь ' (2э) + „4"'(2з — 1), (68) 2 соо 21 — а+1 (з) = — г1'" (2з) + (,) „г(,"'(2э — 1), 2 соэ 21 — о + 1 2' ', з=1, 2, ...,2 ',т=1,2, ...,1 — 1 для т=!, 2, ОП-1) гь (о1 — 1 ) г (-и :ОО-1! гь "(о1-1) 11 с-а+1 Ь=1, 2, для последовательного вычисления сумм с(-И гь '(э) = ~ Ь! '(э)соз( (=о о(- т гь 1(Э) = ~ Ь1,.
1(З) З)П (2)с (=1 й=1, 2, ..., 2' " ', з=1, 2, ..., 2"' (69) 182 при т=О, 1, ..., 1 — 1. Коэффициенты Ь( '(з) также определяются рекуррентно для з=!, 2, ..., 2 ', начиная с заданных Ь';"(1), по формулам Ь)"'о(2Э вЂ” 1)=Ь,'":","(Э)+Ьсо(","(Э), 1=1 2, ..., 2' ' — 1, (70) Ь1((™(2э)=Ьсо(о "(э), 1=0, 1, ..., 2' " — 1 Полагая в (69) т=1 — 1, получим начальные значения для со- отношений (68) г," "(э)=Ь1' "(э), г" о(э)=В1( '1(э) з=! 2 2 '(71) Итак, алгоритм одновременного вычисления сумм (67) и (68) описывается формулами (64) — (66), (68), (70) и (7!). Заметим, что, как и в алгоритмах пп.2 и 3, здесь в соотношениях (68) возможны замены г1 1(Я) = з(п (аь~~ (3), (2А — !) ((-, гь '(з) = з)п ' и(о"1(з) Ь 1 (2)с — 1) а которые позволяют избежать деления на 2 соз 21 ю+1 (73) 183 Элементарный подсчет числа арифметических операций для построенного алгоритма дает: Я~ =За(2 2" — 1 операций сложе- ния и 9 = (п(2 — 3!2) 2" + 2 операций умножения, а всего Я = (2 1ои, Ас — 3!2) Ас+ 1, с')5' = 2".
Таким образом, вычисление коэффициентов Фурье и восста- новление действительной периодической сеточной функции по предложенному алгоритму требуют 0(А51пА)) арифметических действий. б. Преобразование комплексной периодической сеточной функ- ции. Рассмотрим теперь задачу 3 о вычислении коэффициентов Фурье и восстановлении комплексной периодической сеточной функции. В п. 1 было показано, что эта задача сводится к вы- числению сумм (21), которые в случае А(=2" имеют вид 25 ) 5525( С у„= ~~' а(ее, Й=О, 1...,, 2" — 1, (72) с=о где ас)5) — комплексные числа.
Алгоритм для вычисления сумм (72) строится так же, как и алгоритм рычисления коэффициентов Фурье действительной периодической функции. На первом этапе группируются члены сумм (72) сначала с индексами ! и 2" '+! для 1=0, 1, ... ..., 2"-' — 1, затем с индексами ! и 2" 5+! для 1=0, 1, ..., 2 -5 — 1 Н т. д.
УЧИтЫВая раВЕНСтВО Ечы=( — 1)', ПОЛУЧИМ в результате р-го шага следующие суммы; 25-5 (22-1) 55( (5) 25— у,,„, = ° а,',,е )=о й = 1, 2, ..., 2" ', е = 1, 2. ..,, р, 25-Р ( 2255) . у,р = ~, а'Р) е'", й — 0 1,, 2 —. 1 )=о где коэффицианты ар' находятся по рекуррентным формулам (64), Полагая в (73) з=р=п, будем иметь у,=а,'"', у, -(=а,'"', (74) а остальные у, находятся по формулам 25-5 (22- () 55( с (5) 2 у, -5(,,)= ~ а,,е с=о й=1, 2, ..., 2" ', 2=1, 2, ..., п — 1.
Совершим здесь для фиксированного ! замены, полагая ~~е(1)=у, -5... Й=!, 2, ..., 2" ', ь(55 !1) а(5) 5 ! 0 ! 25-5 1=п — и, з=1,2, ..., и — 1, перейдем к вычислению сумм (22-1! >>С Зса> (1) ~Ч> ' Ьсо> (1) 2' Ь ! 2 21 (76) с=о для 1=1, 2, ..., л — 1. Второй этап алгоритма, заключающийся в вычислении сумм (75), строится, как и ранее, путем разделения слагаемых с четными и нечетными индексами ! при использовании равенств (22-1) (21-2) >> (22-1) 21» (22-1) (21-1) >с е ' +е ' =2соз с-о>+! 21-о>+! (2)с — !) >о 21" о>+2 е 21 - о>+ ! Будем иметь рекуррентные формулы г), "(2) = гсо '(22) +, гсо > (22 — 1), 1 2 соэ 21 227:,."+2 (2) = гооо (22) —, „го '(22 — 1), 2 соо 21 й 1 2 2с- з 1 2 2 с лс=! 2 1 — 1 (76) для вычисления сумм 21-о> (22-1) >>С ест>( ) ~Ч>~' 1>оо(э) „, с=о 1=1,2, ...,2' '", з=1,2, ...,2" (77) при л(=0, 1, ..., ! — 1.
Коэффициенты Ьссоо вычисляются по рекуррентным формулам (70). Осталось указать начальные значения для (76). Полагая в (77) ос=! — 1, получим г(с — 1> (2) Ьсс — 1> (2) + ййп — 1> (2) зос' "(2) = Ьо" 1>(2) — (Ь!' "(2) з = 1 2, ° ° > 2' ' ° Подсчитаем теперь число арифметических операций для построенного алгоритма. Получим Я+ — — (Зп)2 — 1/2)2" операций ело! о4 Итак, алгоритм вычисления сумм (72) описывается формулами (64), (70), (74), (76) и (78).
Отметим, что построенный алгоритм не содержит (за исключением простейшей формулы (78)) операций умножения комплексных чисел. Поэтому в приведенных формулах легко выделить действительную и мнимую части вычисляемых величин. Это удобно для реализации алгоритма на ЭВМ, не имеющей комплексной арифметики. Далее, в соотношениях (76) может оказаться полезной замена 2Г) (2)=з!и(, ) и>( ) (2). л ения комплексных чисел и >г, =(п(2 — 3(2) 2" операций умножения комплексного числа на действительное число.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
