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