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