А.А. Самарский - Теория разностных схем (1989) (1160092), страница 86
Текст из файла (страница 86)
Этп особенности эллнптнчесшгх сеточных уравнений требуют разработки специальных экономичных алгоритмов для пх численного решения. Прямыо экономичные методы применяются, как правило, для решеш1я узкого, хотя н очень вая1пого, класса сеточных уравнений. Кроме того, прямые методы пспользу1отся в итерационных методах для обращения оператора па верхнем слое, который выбирается соответствующим образом. В настоящее время существуют дза экономичных прямых метода для решения разностных краевых задач в случао уравнения Пуассона в декартовой, полярной, цилиндрической и сферической системах координат. Один пз нпх — метод декомпозиции илп метод нечетно-четного исключения с факторизацией является модификацией метода исключения Гаусса.
Другой метод— метод разделения переменных основан на использовании алгорит ма быстрого преобразования Фурье. Для обоих методов справед. лиза следующая оценка числа арифметических операций О, требуемых для нахождения решения в случае двумерной задачи, -О = 0(№)оя,)У), где У вЂ” число узлов по одному направлению. В этом параграфе, кроме двух вышеуказанных методов, рассмотрен еще один прямой метод — метод матричной прогонки. Оп пригоден для решения разностпых эллиптических уравнений в областях ело>Иной формы. Однако матричная прогонка требует О=О(№) арифметических действий и большу1о память для хранения промежуточных величин.
В то же время при решении серии задач с различными правыми частями п граипчпыми значениями методом прогонки можно за счет хранения прогоночных матриц уменьшить число действий до 0(№) для второго и последующих вариантов. Итерационные методы последовательных приближений применимы для более общих задач в случае произвольной области, уравнения общего вида с переменными коэффициентами. Этиметоды рассмотрены в следующих параграфах. Перейдем теперь к непосредственному пзложенп1о прямых методов.
Всюду в этом параграфе будем рассматривать задачу Дирихле для уравнения Пуассона в прямоугольнике О (0(х,< -)„а=1, 2) с границей Г: ди дв Ьи= — + —, = — )(х)1 х=(лм х) ыб, и)г= И(х). (1) 517 Введем в гз прямоугольную сетку с шагами Ь,и Ь;. озз = (хз зз = (удЬгг 1зЬг) а= бз уа=Ог 1, ° ° ° г )Чаг Ьа)Ча=уа1 гз=1з2] Пусть Тз =- [хзззгон Г! — граница сетки. Ревностная задача Дирихле, соответствующая задаче (1), имеет вид Лу = — у(х), хьюго, у~ „= р(х)з Л = Лг+ Лг, Лау = У-, а = 1, 2, у» зз = У (1зЬз, узЬг). (2) Задача (2) подробно исследована в гл. 1Ч. 2.
Метод декомпозиции. Сведем задачу (2) к системе векторньгц уравнений — Ту о+СТ; — Ту+о =РЬ !=1, 2, .'.,УЧ вЂ” 1, То Ро где Тз и Г» — векторы компонентами которых являются значения решения уо у(гЬо уЬг) и правой части ус=у(гЬо !Ьг) на у-м столбце сетки гоз, а С вЂ” разностный оператор, который мы определим ниже. Действительно, если изменить правую часть в уравнениях (2) в приграничных узлах, то можно считать, что у» О в граничных уалах при 1 О, з = УЧ,.
Перепишем уравнения '(2) в следующем виде: — Усу-з + (2У вЂ” ЬзУ*га,)о — Усу+о = Мзу 1(г(Кз — 1, 1(У'(УЧз — 1, (4) Уоз Уяз О О<У<)Уз Уо Рм Уот Роя О<г<УЧг где грзу = Уп при 1 < У ( УЧг — 1, 1 (у < УЧз — 1, 1 1 'Рзу = угу+ г роу %яг-з,г = улг — гя+ —, розгу. Введем векторы Т, и Р,: Тг = (угу узу ° ° ул -ьу) У =1, 2,..., УЧг — 1, у,г г г з з Рз' = Ьгугу+ з роь Ьгугу ° ° ° Ьгуяг — з,у уггз Гу = (ргу, ргу, ..., рк,;) при у = О, ууг. 34 л л, соазоооза з ьг. Ьзуяз-г,у + г )гигу ь, (5) '518 ГЛ. Х. МЕТОДЫ РЕШЕНИЯ СЕТОЧНЫХ УРАВНЕНИЙ Разностеый оператор С определим'следующим образом: (С)())( = ((2У вЂ” Ь«У., ), 0 ( 1 < А»е У»1 = Ун») = 6.
Отсюда и из (4) следует, что задача (2) эквивалентна системе векторных уравнений (3). Перейдем к описанию метода декомпозиции, предполагая, что № 2". Его идея состоит в последовательном исключении из уравнений векторов 1'1 сначала с нечетными номерами; затем с номерами, кратными,2, 4, 8 и т.
д. Запишем для 1=2,4,6,...,У» — 2, где № 2", следующие три уравнения: — т,»+ст) г — т)=Р, „ — Т,, + СУ, — Т,+, = Гь -'У, + СХ)+, - У,+, — — Р,+,. Применяя ко второму уравнению оператор С и складывая все три уравнения, получим «укороченную» систему: — У) о+си~У) — У;»» = Р»('), 1= 2, 4, 6, ...,Фо — 2, (6) 1о= Ро ~но = ея» которая содержит неизвестные только с четными номерами. Здесь введены обозначения С(1) [С(о)]» 2Е Р(1) Р(о) + С(о)Р(о) + фо) гдЕ С(о) = С, Г(»о) = Р;. Если найдены из (6) Т) с четными номерами, то .неизвестные с нечетными номерами можно определить иа уравнений Сот;=Г»'+т)+1+~) „ (о) (о) У=1,3,5,...,1')( — 1. Действуя так же, как и при исключении из (3) векторов с нечетными номерами, исключим из системы (6) неизвестные с номерами ), кратными 2, но не кратными 4 и т.
д. В результате получаем систему уравнений для последовательного нахождения всех неизвестных путем решения уравнений С Ъ) = г™1 + х) «1-1+ х)+»»-1, (З-1) тз(Д вЂ” 1) 1= 2» 1, 3 2~ 1, 5 2» ',...,Л(» — 2" 1, (7) )« = и, п — 1, ..., 2, 1, 1о = ро~ о)«о е)оа> 519 где С и Р~~ определяются по реккурентным формулам (з> (з> С(~> = ),С(~ ~> ] — 2Е, й = 1, 2, ..., и — 1, С(з> С Р(з> Р(ь 1> У С(ь — 1>Р(з — и ~ Рм — 1> ; зз-> + ю +;.>.зз-м 1 = 2", 2 2~, 3 2",..., Хз — 2», й = 1, 2,..., и — 1. (8) которое решается методом прогонки. Для вычисления Р, используется следующий алгоритм. Вво(з> дятся векторы р, и Ч,, через которые Р, выражается по'фор(ы Ро (з> мула Р(з> С(юр(ю+ Ч(ю Р>, Ч~ (10) Чтобы получить алгоритм для вычисления р> (и Ч> >, подставим (10) в (8): С(з> (ю+ (з> С(з-г> г (ь-г> + (з-1> + (а-т>1 + Р> +Ч> = .
[Р> зз-г + Р>тзз-> + Чю + (С(з-г>)з (з-» + ("-и +' (ь-г> (11) после чего положим Чю = Р> + Ч>-зз-> + Ч>+з~-г (~> = 2 ("> (",'> (+,'> (12) и перепишем (11) в виде (учитывая, что Сго = (С'" "Р— 2Е) (С(з->>)з г ((з> (а-г>) С(з-1> ( (з — и + (л-ч> + (з-») 34' Алгоритм декомпозиции существенно использует факториза- цию операторов С'"': зь См~ = П (С вЂ” »>Е), )>( — — 2соз (9) >-г хз+г что позволяет свести обращение оператора Соз к последователь- ному обращению методом прогонки трехточечных разностных операторов.
В самом деле, пусть требуется решить уравнение С(з>о (р. Если учесть представление С'и в виде (9), то,определение и сво- дится к последовательному решению уравнений (С вЂ” )>,Е)оо>=~р, (С вЂ” >ьЕ)оо> ио '>,! 2, 3, ..., 2~, >зи причем искомое решение и=от) Каждое из написанных выше уравнений есть трехточечное разностное уравнение йгйг о(п (0) = ('> (1,) = 0, 520 ГЛ. Х. МЕТОДЫ РЕШЕНИЯ СЕТОЧНЫХ УРАВНЕНИЙ После сокращения на С'" " получаем С(ь-1)ф-1) (1-1) ~ (1-1> ~ (1-1> (1) (1-1) ~ о(А-1) = Р) 11-1+ Р>ЬОА-1 т% ж Р) = Р) + о) о а Ч)") определяется согласно (12).
Подстановка (10) в (7) дает С"-'> (т) — р("-'>~ = Ч)"-1>+ т>,1 — + т„, — . Таким образом, введенис Ч( и р( вместоР) позволяет найм) ти решение задачи (2), используя только обращение операторов С'* " и сложение векторов при вычислении правых частей уравнения.
Вычисления проводятся в следующей последовательности. 1) Задаются начальные значения р)~), Ч)')1 2) Для всех й = 1, 2, ..., н — 1 решаются уравнения С'» '>8)~ "= (~ "+ (А " + (1 " — Ч) ( Р; 11-1+Р;+11-1 и вычисляются векторы р( н Ч( по формулам Р> = Р) (А> (А-и ( В~А-1> (1> 2Р11) + Ч(1-1> ( Ч(1-1) Ч) = Р Ч; 11-1 Ч>+оь-1 для всех 1 2", 2' 2", 3. 2",, № — 2". 3) Решаются уравнения В) = Ч) + 1)-11-1+ х)+11-1~ хо = Ро Ъно= Р'ко задачи (2) лишь в пригра- 1 11=1 1, № — 1и на — Р ь где (р отлнчается от правой части 7 $ ничвых узлах на величину — р при ьо 1 ПРИ (о 1 11 ))' 1 1.
и вычисляется искомое решение (1-и + ЗУ-1> для всех 1 2" ', 3 2" ', 5.2"-', ..., № — 2"-', й п, п — 1, ... ..., 1. МетоД ДекомпозиЦии тРебУет () 0(>11(оо)обо№) аРифметических действий и полуторной памяти, т. е. используемая машинная память в 1,5 раза больше числа неизвестных. Впрочем, небольшое изменение алгоритма, приводящее к незначительному увеличению времени решения, позволяет избавиться от увеличения памяти. 3. Метод разделения переменных.
Рассмотрим решение задачи (2) с однородными граничными условиями Лу= — Р, р(,„=0, (13) 521 Пусть р„()Ь,) и лА — собственная функция и собственное вна- чение номера Ь вадачи Л НА+ ХАРА О, Ь, < х, < 1, — Ь„р„(0) )21(12) О. И4) Согласно п. 2 $3 гл. П имеем / 2.. Ал! 4 . АьлЛ рА()Ь2) = — вш —, ХА = —,в1в2 2 Ь 1 2 у ~/ 22 Д1 ' А2 21 ~ = ~ ~.. з 2— Решение задачи ИЗ) ищем в виде суммы МА — 1 УО= 2~ сА(1Ь1) рАУЬА), 1=1 (15) 1 = 1, 2,...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
