А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978), страница 4
Описание файла
DJVU-файл из архива "А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978)", который расположен в категории "". Всё это находится в предмете "численные методы" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 4 - страница
гл. П). Для двумерных задач первой группы (см. выше) эффективен метод полной редукции (гл. 111), метод разделения переменных с быстрым преобразованием Фурье, а также комбинация метода неполной редукции с быстрым преобразованием Фурье (гл. 1Ъ).
Во всех случаях по одному из направлений методом прогонки решается разностное уравнение второго порядка. Указанные прямые методы в случае разностной задачи Дирихле для уравнения Пуассона в прямоугольнике (О ( х„ ( 1„, а=1, 2) на сетке в=-((1,Л„Щ), 1„=0, 1, ..., Лг„, Ь„=1„!ЛГ„, а=1, 2) требуют 9=0(Л',У,!од,Л~,) арифметических действий, где Л',=2г, п > 0 — целое число. Прямые методы применимы для весьма специального класса задач. Разностные эллиптические задачи в случае операторов г".
общего вида или областей сложной формы решаются в основном при помощи итерационных методов. Сеточные уравнения можно трактовать как операторные уравнения первого рода Аи=г (8) с операторами, заданными на пространствах Н сеточных функций. В пространстве Н вводятся скалярное произведение (,) и энергетические нормы ~~~и!р —— ) '(Юи, и), В=0') 0,0:Н вЂ” Н,где П вЂ” некоторый линейный оператор в Н. Итерациойные методы решения операторного уравнения Аи=): можно трактовать как операторно-разиостные (разностные по фиктивному времени или по индексу-номеру итерации) уравнения с операторами в гильбертовом пространстве Н.
Если новая !5 итерация у,+, вычисляется через т предыдущих итераций Уы Уь „, у„„+„то итерационный метод (схема) называется и-!-1-слойным (гй-шаговым). Отсюда видна аналогия итерационных схем с разностными схемами для нестационарных задач. Поэтому и теория итерационных методов фактически является специальным разделом общей теории устойчивости операторноразностных схем.
Мы ограничиваемся изучением двухслойных и в меньшей степени трехслойных схем. Переход к многослойным схемам не дает каких-либо преимуществ (как это и следует из общей теории устойчивости, см. [10)). Важную роль играет запись итерационных методов в единой (канонической) форме, что позволяет выделить оператор (стабилизатор), ответственный за устойчивость и сходимость итераций и сравнить различные итерационные методы с единых позиций. Любой двухслойный (одношаговый) итерационный метод заиисывается в следующей канонической форме: В""" "'+Аул=~, й=О, 1, ю ра~Н» (9) где В: Н- Н вЂ” линейный оператор, имеющий обратный В ', т„т„...
— итерационные параметры, й — номер итерации, уь— итерационное приближение номера й. В общем случае В=Вэ~ зависит от й. В общей теории мы предполагаем, что В не зависит от й. Параметры (т ) и оператор В произвольны, и их следует выбрать из условия минимума числа итераций п, прн котором решение у„ уравнения (9) приближает в Нр точное решение и уравнения Аи = ~ с относительной точностью з > 0: (( У,— и(п < е)У вЂ” и (!о.
(10) Для излагаемой в книге общей теории итерационных методов не требуется никаких предположений о структуре оператора А (матрицы (аы)). Используются лишь свойства общего вида А=А" >О, В=В'>О, у В<А<у В, у,> О. (!1) Операторные неравенства означают, что заданы постоянные у„у, энергетической эквивалентности операторов А н В или границы спектра оператора А в пространстве На (у,— минимальное, у,— максимальное собственные значения обобщенной задачи на собственные значения: Ао =ЛВо). Решение т„т„..., т„указанной выше задачи о ш(п гг,(э) т~, и, при заданных у„у, и фиксированном В в случае В=АВ-'А выражается через нули полинома Чебышева п-го порядка (чебышевский итерационный метод).
При этих оптимальных значениях т„т„..., т„и заданном произвольном з > 0 для числа 16 итераций п, вычисляемых по схеме (9), верна оценка !и (2!е) !и (2!е) ц ~ (( ) ( у )) нли и > пе (е) ф $ уе~ уе н Вы полняется неравенство ((Ау„— 7(|в- ~(а()Ау,— Дв-е. Вычислительная устойчивость чебышевского метода имеет место при определенном способе нумерации (упорядочивания) нулей чебышевского полинома и параметров т*„ т,*, ..., т„', этот способ указан в гл.
Ъ'1. При В = Е (Š†единичн оператор) метод (9) называется явным, а при ВФ Е вЂ неявн. Если параметр т„выбрать постоянным, те=те=2)(у,+уе), )е=1, 2, ..., и, то получим неявную /! !~ схему простой итерации, для нее п>ие(е)=1п ~ — )~(2$), ~ ) Оператор В (стабилизатор) выбирается из условйя экономичности, т.
е. минимума вычислительной работы при решении уравнения Во=Р с заданной правой частью Р, и, как было уже сказано, из условия минимума числа итераций ае(е). Предположим, что мы умеем эиономично решать задачу Ко=7 с затратой Ял(е) действий, где Я: Н вЂ” Н, К=К* > О, сей(А(се)7, С, >О. (!2) Тогда можно положить В=-Я и найти решение задачи Аи=)' по схеме (9) с параметрами (те) при у,=-с„у,=с, за Ял(а) ж ! ж — $'с,)с,!п(2)е) Яя(е) действий. Если, например, Š— оператор общего вида, 6 — прямоугольник, то в качестве Я можно взять пятиточечный разностный оператор Лапласа и решать уравнение Ко=7 прямым методом. Может оказаться, что уравнение Ро=г выгодно решать не прямым, а итерационным методом, тогда В~)7 и не выписывается в явном виде, а реализуется в результате итерационной процедуры.
Известные методы Зейделя и верхней релаксации являются неявными и соответствуют треугольным матрицам (операторам) В. Сходимость этих методов доказывается на основе общей теории разностных схем (см. А. А. Самарский, Теория разностных схем, М., 1977 или А. А. Самарский, А.
В. Гулин, Устойчивость разностных схем, М., 1973). Однако для методов Зейделя и верхней релаисации оператор В несамосопряжен, и потому нельзя воспользоваться чебышевским методом (9) с оптимальным набором итерационных параметров т,", т.,*, ..., т"„, что позволило бы повысить скорость сходимости итераций. Оператор В можно !7 сделать самосопряженным, если положить его равным произведению сопряженных друг другу операторов: В = (Е+ <е)~в) (Е+ «Жв) Азв (13) где «в > 0 — параметр. В качестве Яв и Р, можно взять операторы, имеющие треугольные (нижшою !гв и верхнюю !гв) матрицы, так что !гв+втв=Я: Н вЂ” Н, !т'=Р >О.
В частности, можно положить !гв+ Ив = А, (14) Типичным является предположение !в' ЬЕ, )~Лв~ (4 А, 5>0, гв>0. (15) Выбирая затем ев=-2$'5Х из условия ш!пп,(е), находим параметРы У„У, н вычислЯем паРаметРы (тД. ОпРеделение Ув~, через ув н ! сводится к последовательному решению двух систем уравнений с нижней н верхней треугольными матрицами. Построенный итерационный метод (9) с факторизованным оператором В вида (13) назовем попеременно-треугольным методом (ПТМ). ПТМ, очевидно, является универсальным, так нак представление А в виде суммы К+И,=А, К=!г, возможно всегда. В случае разностной эллиптической задачи построение р У- я, и )~, не представляет труда.
Так, например, йвву— а=! а р Ку — — ~ — „, если Ау — разностный 2р+1-точечный оператор ~в Уаа а=~ а Лапласа, Ау — — ~ у;,, йа — шаг сетки по направлению Оха. а В вава Этот метод является быстросходящимся. Если взять чебышевский набор (тв) и учесть (14), (15), то число итераций для ПТМ (! 6) В частности, для модельной задачи имеем и > и, (е) = 0,3! п — ( ~/ Ь, 2/ е Для случая произвольной области и уравнений с переменными коэффициентами целесообразно пользоваться модифицированным попеременно-треугольным методом (МПТМ), полагая В=(Ю+евРв)!2! в(йб+евР,), К=Я„Ю=!21*>0, (Ч7) где Я вЂ” произвольный оператор. Если вместо (15) выполнены Я>Ы1, вг,й вРв< — Я, 6>0, б>0, (18) то оценка (16) сохраняет силу.
!в. Здесь заданы б и Л, а выбираются оператор Я и параметр в так, чтобы отношение $= у,(у, было максимальным. На практике в качестве матрицы Ж можно брать диагональную матрицу. Укажем два примера эффективного применения МПТМ. 1) Задача Дирихле для уравнения Пуассона в двумерной области сложной формы; основная решетка в плоскости (х„х,) равномерна с шагом 6, схема пятиточечяая. МПТМ при соответству!ощем выборе Ю требует лишь на 4 — 5% больше итераций, чем для той же задачи в квадрате со стороной, равной диаметру области. 2) Для эллиптических уравнений с сильно меняющимися коэффициентами (отношение с,!с, велико) МПТМ с соответствующим образом выбранным 99 позволяет ослабить зависимость от с,1с,.
На практике, помимо одношаговых (двухслойных) методов (9), применяются и двухшаговые (трехслойные) итерационные схемы. При оптимальных итерационных параметрах они по числу итераций сравнимы с чебышевской схемой с параметрами (т!) при О, однако более чувствительны по отношению к ошибкам в определении у, и у,. При условиях (11) целесообразно пользоваться чебышевскон схемой (9) с параметрами (т!). Для решения эллиптических задач весьма важную роль , сыграл итерационный метод переменных направлений (МПН), развивавшийся, начиная с 1955 г., многими авторами.
Однако он оказался экономичным лишь для очень узкого клзсса задач первой группы, когда выполнены условия А = А, + А, А„=А'„)О, а=1, 2, А=А )О, А,А,=А,А,. Если А, и А, перестановочны, то для МПН можно выбрать оптимальные итерационные параметры. Для модельной задачи с такими пара- 1 11 метрами число итераций п,(е) =О (!п — 1п — ), а число дейст- а а)' 11 1 11 вий О(е) =О ( — „, 1п — „!п — ), в то время как для прямых мето- Г! 11 дов 9 = О ( — „, 1п л ! .
Прямые методы в этом случае более экономичны, чем МПН. Если А, и А, неперестановочны, то МПН Г! 11 требует О ( — !п — ) итераций, в то время как для ПТМ доста- (Ь е) (' 1 !Х точно О ! =1п — ! итераций. В случае трехмерных задач, когда 1,уь е) А=А,+А,+А, даже в предположении попарной перестановочности А„А„А, МПН требует больше операций, чем ПТМ. Таким образом, МПЙ в значительной степени утратил свое значение. Если оператор А ) О не является самосопряженным, то яе удается прн помощи схемы (9) с набором параметров и само- сопряженным оператором В = В' ) О построить итерационный 19 процесс с той же скоростью сходимости, что и чебышевский метод при А =А' > О. Все известные методы обладают меньшей скоростью сходимости.
Здесь рассматривается метод простой итерации (гл. 71) с заданием априорной информации двух типов: а) заданы параметры у„у.„входящие в условия (для простоты считаем 0:= В -Е) у,(к, х)((Лх, х), (Лх, Лх)«у,(Ах, х), у, >О, у, >0; (19) б) заданы три параметра у„у.„у„, где у, и у, (при Р=В=Е)— границы симметричной части оператора А: у,Е =А(у,Е, (~А,()(у„у, > О, у,)0, (20) где Л, == 0,5 (А — А') — кососимметричная часть А. Выбирая т из условия минимума нормы оператора перехода или разрешающего оператора, во всех случаях получаем увеличение числа итераций по сравнению со случаем А = А". Любой двухслойный итерационный метод, построенный на основе схемы (9), характеризуется операторами В и А, энергетическим пространством Нп, в котором доказывается сходимость метода, и набором параметров.