А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 36
Текст из файла (страница 36)
Дополнительные затраты на решение задач (38) составят, очевидно, 0(У»Л!,) действий, что не повлияет на главный член в оценке числа арифметических действий алгоритма (37), (39), (40). Приведем точные оценки для числа действий для этого алгоритма. Илюеем (для Ь7» = 2'") Я„.
= [(3!од,й!,— 1) Л',— — 2!он, Л!»+ Ц (М! — 1) операций сложения и вычитания, Я, = ==-[(!од» Л!»+2) Ь7» — 2] (Ж! — 1) операций умножения и 7» 195 0 <х, <1„ 2 — и„, х,=О, Ь« 2 — и„-,х=1 — д,(х), х,=О, г 2 О, Ь,<х,<1,— Ь„ 2 ь, я- (х) х. = 1" ф,(х) = 1(х) = ~р (х) + <р, (х), Л,и = и — „„ для Ь, < х, < 1, — Ь„О < х, < 1,. 196 ° = (М,— 1)(М,— 1) операций деления, а всего при М,=М,=М=2« число операций равно !~=(М' — 1,5М)(4!од, М+2) — М+2!он«М+2. Мы рассмотрели метод разложения в однократный ряд на примере разностной задачи Дирихле для уравнения Пуассона. Существенным моментом является то, что собственные функции разностного оператора Л, допускают использование алгоритма быстрого преобразования Фурье для вычисления соответствующих сумм.
Такая возможность будет иметь место и для случая, когда на сторонах х,=О и х,=1, прямоугольника О заданы вместо краевых условий первого рода условия второго рода или ком- бинация условий первого и второго рода, а также для случая периодических условий. Рассмотрим для примера следующую краевую задачу для уравнения Пуассона: и„- „+ и„-„= — <р (х), х Е а, «,«, и(х)=0, х,=О, 1„0<х,<1„ и,-„+ —,и„,= — ср(х) — —,д,(х), х,=О, (41) 2 2 и-, „— — „и„- = — ~р (х) — — „д„(х), х, = 1„ Ь«~х1<1«Ь« .Схема (41) есть разностная аппроксимация для задачи д«и д«и д«« + д«« — Р (х), х Е 6, и(х)=0, х,=О, 1„ ди — = — а- (х) х =О. дх« ди — — = — д+,(х), х,=1„0<х,<1ь д«« Запишем задачу (41) в другом виде, вводя обозначения: В новых обозначениях задача (41) запишется в виде Ли=(Л,+Л,)и= — Е(х), Ь,<х,<1! — Ь„О<х,<Е„ и(х)=0, х,=О, Е„О<х,<Е,.
(42) Разлагая и(!', Е) и Е(с, Е) в суммы по собственным функциям оператора Л„ будем иметь и (Е, Е) = ~ иь,(Е) ру," ,(Е), 0 Е < ЬЕ„О < Е < ЛЕ„ ь, о хэ Р(Е, 1)= Х )ь,(Е)рьЕ,)(Е), 0<у<ЬЕ„1<Е<ЛЕ,— 1, ь,=о где ! Коэффициент Фурье Еь,(Е) для каждого ! <!<ЛЕ! — 1 вычисляется по формулам И~-1 7ь,(Е) =,Я~ Ь!~(Е, Е) р1',~(Е)+О,БЬ,(Е(Е, 0) рЦ~(0)+7(Е, ЕЧ,) р1',!(ЬЕ,)~. /=! Подставляя (43) в (42), получим для рассматриваемой задачи (42) следующий аналог формул (37) — (39): ма ~рь,(Е)=,х р Е(Е, Е)соя — ' !=а 0<Ь.
<Ум 1<Е<ЬЕг 1 — оь, (! — 1) + (2 + Ь", Л)~ ! ) ц;, (Е) — оь, (! + 1) = Ь~ арь, (Е), 1 < ! (ЬЕ! — 1, оь,(0) =о~,(ЬЕ!) = О, 0(Ь,(Еу„ М~ и ( !, Е) = —,~ Рь,ор, (!) соз— ' ь,=о 0<1 <Л~!1 <! <ЛЕ1 где Ьь!',! определено в (44), а (О 5, 1=0, ЬЕ!, РЕ ) 1, 1<1<де,— 1. 797 есть собственная функция оператора Л„соответствующая собственному значению (44) Приведем оценку числа действий для построенного алгоритма при М,=М,=М=2": 9~=((3!ой, М,— 1) М,+2!од, М,+7)х х (М,— 1) операций сложения и вычитания, Я,=~(1од, М,+ 2)М,+ +!О!(М,— 1) операций умножения и 9,=(М,+1)(М,— 1) операций деления, а всего Ю = (М' — 2 ) (4!ой,М+2)+ 1?М вЂ” 2!ой, М вЂ” 18. Далее, так как в методе разложения в однократный рядсобственные функции разностного оператора Л, не используются и единственное требование к Л состоит в возможности разделять переменные, то в качестве Л, можно взять более общий, чем мы рассмотрели, оператор.
Если ограничиться эллиптическими уравнениями второго порядка, то наиболее общему случаю выбора оператора Л, соответствует разностная аппроксимация для дифференциального оператора 1 д ? ди1 ди коэффициенты которого зависят лишь от х,. Краевые же условия на сторонах х,=О и х,=1, прямоугольника 6 могут быть любой комбинацией краевых условий первого, второго или третьего рода (коэффициенты в краевом условии третьего рода должны быть константами). Это позволяет решать краевые задачи для уравнения Пуассона в цилиндрической, сферической и полярной системах координат.
3 3. Метод неполной редукции 1. Комбинация методов Фурье и редукции. Построенный в п. 3 3 2 метод разложения в однократный ряд позволил ограничиться вычислением только двух сумм Фурье с затратой 0(М,М,!од, М,) действий и решением серии трехточечных краевых задач за 0 (М1М,) действий.
Очевидно, дальнейшее усовершенствование метода разделения переменных возможно на пути уменьшения числа слагаемых в вычисляемых суммах при сохранении возможности использовать алгоритм быстрого преобразования Фурье. Мы достигнем этой цели, комбинируя метод разложения в однократный ряд с изученным в главе 1П методом редукции.
Построим сначала такой комбинированный метод для простейшей задачи Дирихле Ли= — )(х), хбе, и(х) =О, хЕу, Л = Л; + Л„Л„и = и-, „, сс = 1, 2 1) на прямоугольной сетке а. Для упрощения описания метода перейдем от точечной (скалярной) записи задачи (!) к векторной. 198 Введем вектор неизвестных П, следующим образом: Е~~- — -(и(1,1), и(2,1), ..., и(Л',— 1,1)), 0<1<Л'„ и определим вектор правых частей Р~ формулой Р~=--(ЬЦ(1,1), й)(2,1), ...,/ф(М,— 1,1)), 1<1<У,— 1. Тогда разностную задачу (1) можно записать (см. гл.
П1, 9 1) в виде следующей системы векторных уравнений: — И,,+С5~ — С~„,=Е,» 1 1'<Л',— 1, « ~~з где квадратная трехдиагональная матрица С определяется равенствами СЦ=((2Š— Л»Л,) и (1, 1), „, (2Š— и";Л,) и(Л',— 1, 1)), Л,и=и;,, и(0, 1)=и(Ж„))=0. Пусть Л~» есть степень 2: Л'»=2 . Напомним, что первый шаг процесса исключения в методе полной редукции состоит (см. гл. 1П, 9 2) в выделении из (2) «укороченной» системы для неизвестных ~~ с четными номерами / й = сь,=о и уравнений СЦ=,Г,+О,+Гу„-, 1=1,3,5, ..., Л»,— 1 (4) для определения неизвестных с нечетными номерами 1.
Здесь обозначено Г';" = Р; -, + СР' + Гу „1 = 2, 4, 6, ..., М» — 2, (5) С со = (С1' — 2Е. (6) Займемся системой (3). Введем обозначения Ф'~ — — (и (1, 1), о (2, 1), ..., о (Л», — 1, 1)), Ф~ = ИЧ (1, 1), Л1 р (2, !), ° °, Л~ф Фг — 1, 1)) и положим У,=У„, 0<1<Л~»12, Ф =-Еф, 1<1<У»'2 — 1, о(0, 1) =о(У„1) = О, 0<1(У»!2. Эти обозначения позволяют записать систему (3) в виде — Р;,+СоК,— К„,=Ф,, 1=1, 2, ..., М, У,= Рхн= О, где 2М,= 51, и в силу (5) Ф~='Р»у-г+СГ» +Г,.+;, 1=1, 2, ..., М» — 1. (8) 199 где функции !»!',1(!) ==з!и м» 1, й,=1„2, ..., М,— 1 (10) М» образуют ортонормированную систему на сетке»1 в смысле скалярного произведения М,-1 (и, о) =,~ ~и Е о (1) й,. Коэффициенты Фурье г (!) функции ф(1,1) находятся по фор- мулам М,-1 г.,(1) =(ф, р»~1)= Х й»ф(', 1)р»~10) 1=1 1<й,<М,— 1, 1<1<У,— 1.
(11) и Фу следующие разложения: Из (9) получим для векторов У. М» 1 1,=„Х,!М4 О), М»-1 Фт =,Х, й~А,р!" .О). О<1<М„ (12) 1<1(М» — 1, где !',=Ь;(1), у,(2) " у,(У.-1)), У» = (г» (1), г» (2),, г» (У! — 1)). Подставим (12) в (7) и учтем равенства р»*,' (1 — 1) + р!', (1'+ 1) = 2 соз ~ )»1' ,(!), 1 < й, < М, — 1. Получим М»-1 М,-1 (С"' — 2соз+ Е] К р»~',! (1) = ~Ч»', й,'Е» !»!»~(1), »»=1 »,=1 Заметим теперь, что сеточная функция о(1, !) определена для 0 < 1 < У, и 0 < ! < М, и обращается в куль при ! = 0 и 1 = М,.
Функция 1р(1, !) определена для 1 <1'<У,— 1 и 1<! <М» — 1. Поэтому эти функции можно представить в виде однократных рядов Фурье М,-1 о (!', !) = ~'.' ,у», (!') р»!" ,(1)„0 <1 < У„О< ! < М„ »,= 1 М,-1 ф (1, 1) = ~ г», (!) Р», (1), »»= 1 1 <1<У,— 1, 1 < 1<М,— 1, гкуда в силу ортонормироваиности системы (10) будем иметь (Ссо — 2сов м' Е) У~,=Ь»У„, 1<Ь,<М,— 1. (13) Используем соотношение (6) и получим Ссо — 2сов — 'Е=(С1' — 2 (1+сов — ») Е = М~ = (С вЂ” 2 сов — '" Е) (С+ 2 сов — 'Е) .
Так как матрица Ссо — 2сов — Е факторизована, то для реше»»я Мв ния уравнения (13) можно использовать алгоритм ( (С+ 2 сов — „'„Е) )'»,= )4Г»,, где вспомогательный вектор Ю имеет компоненты ш (1): )4/» = (н~» (1), ш„ (2), ..., э (ЛГ, — 1)), ш», (0) = ш», (Л~,) = О. Необходимые формулы получены. Переходя в (4), (8) и (14) от векторной записи к скалярной и используя соотношение и (1, 21) = =о(1,1), вытекающее из определения У,, получим следующие формулы для построенного метода: сР(1, 1) =~(1, 21 — 1)+2)'(а', 21)+)(1, 21+1) — Р4Л ~(1, 21), (15) 1 < 1 < У,!2 — 1, 1 < 1 < Л', — 1, 7 (О, 21) = 7 (Л7», 21) = 0 для вычисления функции ~р(1, 1); уравнения 2 (1 — сов+) и» (1) — Ь4Л1а»,(() =Ь1г» (1), 1 <1< Л',— 1, ш», (О) = ш», ( У,) = О, 2 (1+сов — ') у„,Я вЂ” ~4Л1у (1) =ш» (1), 1 =1<Л',— 1, у„(о) =у„,()у,) =о (16) для определения у»,(1) при Ь, = 1, 2, ..., М, — 1 и уравнения 2и(1, 21 — 1) — Ь,*Л,и(1, 21 — 1) = = Ь2»7 (1, 21 — 1) + и (1, 21 — 2) + и (1, 21), (17) 1 < 1 < М вЂ” 1, и (О, 21 — 1) = и (Ф„21 — 1) = 0 201 для нахождения решения при у =- 1, 2, ..., М,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
