Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 59
Текст из файла (страница 59)
(2) Оператор (2) подробно изучался в % 1, где было показано, что он имеет полную ортонормированную систему собственных функций с 2 . л»хс Р» (хс) = асс — Яп —, й = 1, 2, ..., У вЂ” 1, с = 1, 2, ..., У вЂ” 1. Соответствующие собственные числа оператора А имеют вид 4 . »л»ь Х»= — яп —. »» 2С Поэтому можно искать решение задачи (1) в виде лс-с ус=у(хс) = 'Я е»)с»(хс), 1=1, 2, ..., У вЂ” 1, (3) где с,— неизвестные пока коэффициенты.
332 Разложим правую часть уравнения (1) в сумму Фурье, т. е. представим ее в виде и-< (с= '~ Яц(хс), а=< где Ь=(1 ра)= ~ ссра(хс)й, 1=1,2, ..., У вЂ” 1. (4) / Подставляя разложения (3), (4) в уравнение (1) при <=1, получим И-с и-а '~~ са(ра(х))-„, = — 'Я ~ара(хс), откуда, учитывая соотношение (ра(х))-,„= — Хара(х;) н линейную независимость функций р,(х), приходим к уравнениям саХ»= ~», й= 1, 2, ..., У вЂ” 1. Отсюда находим значения коэффициентов Фурье функции у(х,): са=1а/Ха, й=1,2, ° У вЂ” 1 (5) Таким образом, приходим к следующему алгоритму решения азностной краевой задачи (1).
Сначала по заданной правой части , н известным собственным функциям р„(хс) вычисляем по форму- лам (4) коэффициенты Фурье правой части. Затем по формулам (5), пользуясь тем, что собственные числа известны в явном виде, находим коэффициенты Фурье с„искомого решения у(х,). И, нако- нец, вычисляя суммы (3), находим решение у(х,). Подсчитаем число умножений и делений, необходимое для на- хождения указанным способом решения задачи (1).
Для вычисле- ния Са при каждом А требуется У вЂ” 1 умножений, а вычисление всех )а, й=1, 2, ..., У вЂ” 1, требует (У вЂ” 1)* умножений. Следует под- черкнуть, что здесь и далее мы предполагаем все функции р„(х,) и числа Х, уже вычисленными и хранящимися в памяти машины. Вычисление коэффициентов с, по формулам (5) требует У вЂ” 1 де- лений. Вычисление ус при фиксированном 1 по формулам (3) тре- бует У вЂ” 1 умножений, а вычисление всех уь 1=1, 2, ..., У вЂ” 1 тре- бует (У вЂ” 1)' умножений.
Таким образом, весь алгоритм осуществ- ляется за 2(У вЂ” 1)' умножений и У вЂ” 1 делений. Вспомним, что уравнение (1) можно решить методом прогонки (см. п. с $4 ч. 1) по формулам 1 а<+с=, <=1,2, ..., У вЂ” 1, сс,=О, 2 — ас ()<+<=а<+<((1<+5<~<), <=1, 2, ..., У вЂ” 1, р,=О, у<=а<+ у<+<+р<+<, <=У вЂ” 1, У вЂ” 2,..., 1, у„=О всего за 2(У вЂ” !) умножений и У вЂ” 1 деление. 5 б. Быстрое дискретное преобразование Фурье Наибольшее число действий в методе Фурье требуется для вычисления сумм (3), (4).
Эти суммы имеют внд л-ь зг — — 'Я гьз(п — ~, !=1,2, ..., У вЂ” 1, (1) У ь где г„— заданные числа. Для непосредственного вычисления всех зь 1=1, 2, ..., )Ч вЂ” 1, требуется, как уже отмечалось, (У вЂ” 1)' умножений. Сейчас мы, следуя (21), изложим метод вычисления сумм вида (1), требующий 0(У1пУ) действий умножения. Такое ускоренное вычисление сумм основано на том, что среди чисел э(п —, А=1, 2, ..., У вЂ” 1, лз/ У 1=1, 2, ..., У вЂ” 1, есть много одинаковых. Поэтому можно перегруппировать слагаемые и уменьшить тем самым число умножений. Для дальнейшего удобно преобразовать сумму (1) к виду зг = ~~~ заз!п — ~ ~~~ за51пв ь=$ 2Ф 2М ь=а где полагаем г,=г =з +,—— ...— — г„,,=О.
Обозначим М=2У и рассмотрим более общую задачу о вычислении суммы аи~ ог = ~ гье и = ~ гэю'l, а о ь о где (2) и 1 — мнимая единица. Итак, будем вычислять суммы м-~ ог = ~ гааз"', 1= О, 1, ..., М вЂ” 1. 1=6 (3) Ясно, что 1ш о,=з; для действительных зь Для дальнейшего существенным является условие М=2", лг)0, означающее, что число точек сетки У=2 ' является степенью двойки. Представим число А в формуле (3) в двоичной системе й= =А,+21, +2%,+...+2" Чг„ о где А, либо нуль, либо единица.
334 Следовательно, предложенный здесь метод Фурье неэкономичен, он требует О(№) действий вместо 0(У) действий в методе прогонки. Пользоваться таким методом для решения одномерных разностных краевых задач нецелесообразно. Однако данный метод в сочетании с методом быстрого вычисления сумм вида (3) нашел применение при решении двумерных разностных уравнений с постоянными коэффициентами. Эти вопросы рассматриваются в следующих параграфах. Обозначим Ь"= (Ь" -з Ь -зз ° ° ° Ьз) з гз=г(йзз йзз ° ° ° Кв-з) ° Тогда сумму (3) можно записать в виде о/= Х г(йо,йа, ..., А а)и'" """ «з Л» «о з 1 = ',~~ и«Л ~ и'«) ...
',""„и' ""-з~г(й„й„..., й„,) . (4) «,=о «;з «,=о Преобразуем внутреннюю сумму 1 и' з«з~г(Фо, )а„..., А,). (5) «м з=о В этом произведении все сомножители начиная со второго рава'-з«ад зм«П м«з -з| ны единице. Действительно,из -'П и зл=и ' и, вспоминая выражение (2) для и, получим и =1, в' -""=1, поскольку Й„,1, равно либо нулю, либо единице. Точно так же равны единице и последующие сомножители в зя-з«ззз-з« произведении (6). Таким образом, и -а'=в' "-зп и сумму (5) можно записать в виде 1 " ' 'г (доз йзз " ., й„ з).
«оз-з-о Обозначая эту сумму через г,()„й» ..., й,), запишем предпоследнюю сумму в выражении (4) в виде 1 га(7«ай«,йа . з йл з). (л «м з —— з Представим число 2" Ч з/ в виде 2"-'й„,()«+21,)+2"й з(1«+... за» з«) а"» з«„», ))зозп) ...+2" '/„,), откуда получим и -з =и "" Л). Следовательно, сумма (7) равна зо»м и нп) га(7« 1» йм, й -з) =,'!»; и' "''М"г)0«> й» "., йи ). «„=о Далее, аналогичный процесс последовательного вычисления сумм ЗЗЗ Представим число 1 в двоичной системе 1=/,+21,+...+2 '1„» Тогда получим и' " -(,'=(и' "' -")( а '" М) ...
( а "-' ). (5) продолжается до тех пор, пока в (4) не исчерпаются все суммы. 1 Последняя сумма имеет вид ой= '5', ий'йгг 1(/„!» ..., ! „й,). 3; — о Итак, можно предложить следующий алгоритм вычисления сумм вида (3), называемый алгоритмом бьлстрого дискретного преобразования Фурье. Числа й и ! представляются в двоичной системе й = йо+ 2йй + 2ййй+ . + 2 йй -1. /=!о+2/,+2!,+ ... +2 где й„ /г-либо нуль, либо единица. Далее обозначается г,= =г(й„й»..., й„,) и последовательно вычисляются суммы, состоящие каждая из двух слагаемых: 1 131-13 гй(/оэ йо1 й» ..
з й~л-3) = ~ ю' "г(йо~ й» . 1 йя-й), гй (/Оэ !» й31 й1 ° ' ° ° ~ йо1-3) = 1 331-33 гй(/о~ йо~ й» ' ' 1 йо1-3) ° 331 — 3 1 г. 1(/о,/» ..., ! -.ьйо)= '~йв "' ' — х ЮН!3+3!1+. 3.33~ 31,11 3) й,=о х г -3(/о /1 ° ° ° ! - > й1, йй), 1 "l=,~ ~ге го-1(/о /» ° ° ° в ! -1, "3). 33=3 Подсчитаем число умножений, необходимое для нахождения всех сумм оь /=О, 1, ..., М вЂ” 1, при указанном способе вычислений. Функция г,(/„й„й„..., й„,) используется только при вычислении функции г,(/„ /» й„й» ..., й„,). При этом необходимо вычислить значения г,(!„й„..., й„,) дважды: при й,=О н й„,=1. Вычисление г,(!„й„..., й„,) при каждом значении й„, требует двух умножений.
Следовательно, общее число умножений, требуемое для вычисления г,(!„й„..., й,), равно четырем. Такое же число умножений требуется для вычисления каждой из сумм 4 (!3, /1,, !1-» й, й„..., й,,). Всего имеется т таких сумм. Поэтому число умножений, необходимое для вычисления о, при каждом фиксированном /, равно 4т, а для вычисления всех оь /= =О, 1, ..., М, это число равно 4тМ=4М!оийМ. При больших Л!=2" ' это приводит к значительному сокращению числа умножений по сравнению с числом умножений (У вЂ” 1)', требуемому при непосредственном вычислении сумм вида (1).
Так, при У=!28 число умножений будет почти в два раза меньше. азв 5 6. Решение разностного уравнения Пуассона с использованием быстрого преобразования Фурье В $1 гл. 2 рассматривалась разностная аппроксимация задачи Дирихле для уравнения Пуассона у„„) +у„„° = )дб хя Е= ыь, (1) у,) = О, хаец7,. Зафиксируем какое-либо значение индекса д, 0<1<й)„и будем рассматРивать Уч, ~ц как фУнкции, зависЯщие только от 1, 1=1, 2, ... ..., й(д — 1. Тогда можно разложить уч, гд) по собственным функциям задачи (2), д.
е. представить их в виде Уа-д Л~з-д рц —,'3 с (д) рь И. 6 — Х Ь (д) Р Ю. (4) Здесь и,— множество внутренних и Т,— множество граничных узлов сетки Пь = (хц = (хд э хд ) ~ хд — — Йд, х д = )ддм и) и) )=О, 1, ..., М„ /=О, 1, ..., М„Ь М =1, к=1, 2). Разностная схема (1) представляет собой систему большого числа линейных алгебраических уравнений, матрица которой является сильно разреженной, т. е. содержит значительно больше нулевых элементов, чем ненулевых (в данном случае в каждой строке матрицы не более пяти ненулевых элементов). Решать такие системы уравнений с помощью численных методов, предназначенных для систем общего вида, нецелесообразно, а часто даже и невозможно из-за большого размера матрицы.
Поэтому развиты специальные методы, прямые и итерационные, пригодные для решения двумерных разностных уравнений. Онн подробно рассматриваются в гл. 5, а сейчас мы познакомимся с одним способом решения задачи (1), сочетающим одномерную прогонку с методом Фурье. Заметим, что предположение об однородности граничных условий не ограничивает общности, так как неоднородные условия Дирихле можно включить в правую часть подобно тому, как это было сделано в начале $1 для одномерного случая. Рассмотрим одномерную задачу на собственные значения )д(У+ ) — ИП)+)д(1 — )+Ар(1) О 1 1 2 У 1 ЬЧХУ=(д, )де=)дФ, =О, рв=)д(х ). и) В $1 было показано, что задача (2) имеет следующее решение: ч / 2 ° пз"ди» 4 . д пь))д р0) =)дд 9 = ~ — яп —, )дд= — гйпд —, (3) )д )г Ь~ 2)д 1=1, 2, ..., Ух — 1.
337 Подставляя разложения (4) в уравнение (1), получим №-1 №-1 №-1 Я )<лО)(слЯ),,<+ ~ч„сл(О О<10))„—,) = — Я Рай)! (!) откуда, учитывая уравнение (2) и линейную независимость рм при- ходим к уравнениям (с1Я)„—,„, 1 — Л„с,(<)+11(1) =О. Таким образом, для нахождения коэффициента с„, Л=1, 2, ..., М,— 1, в разложе- нии (4) получаем систему разностных уравнений второго порядка С~ (Е+ !) — 2С1 (1) + С1 И вЂ” !) Л1С1 (<) + <'1 (1) = О, 1 (5) 1=1, 2, ..., У,— 1, с„(О) =с„(М,) =О. Здесь числа Л„заданы согласно (3), а значения 11(1) вычисляются по правилу №-1 ~ьЯ ~ч~ ЛД«)<1(!). 1=1, 2, ..., М1 — 1. (6) )=1 Уравнение (5) решается методом прогонки а,11 =..., ~1+1 = а<„(Р< + 61)Л(~)), <М ! <М <М <М 1" 2+ Л~Хл — в<и саЯ=а~й,с1((+1)+р<1ь <=М,— !,М,— 2, ..., 1, сь(М1)=О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
