Федоренко Р.П. Введение в вычислительную физику (1185915), страница 34
Текст из файла (страница 34)
Если граница области не проходит по координатной линии сетки, нормальная производная аппроксимируется по шаблону, захватывающему как минимум две соседние горизонтали (вертикали) сетки. Такие краевые условия препятствуют непосредственному расщеплению уравнений «на верхнем слое» метода переменных направлений и прямое обобщение вычислительной схемы не проходит. Что касается выбора параметров, то они, естественно, рассчитываются для системы с «замороженными» коэффициентами (в качестве таковых берут, например, средние значения) и для минимального прямо- ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ 1зз 1ч.т угольника, содержащего данную область. Опыт показывает, что такой способ часто приводит к успеху (к быстрой сходимости итераций), особенно когда коэффициенты уравнения изменяются не очень сильно. Однако при появлении в уравнении смешанной производной и„отказывает не только теория сходимостн, но н алгоритмическая схема.
Что делать в этом случае? Общая схема итерационных процессов. Пусть Р— разносгная аппроксимация общего эллиптического самосопряженного дифференциального оператора. И пусть разностная аппроксимация выбрана так, что Р= Р' (сохраняется самосопряженность). Нужно решить уравнение Ри = ~, Многие итерационные методы решения этого уравнения укладываются в общую схему: где  — некоторый разностный оператор, называемый (по терминологии А.
А. Самарского) регуляриэатором. Он должен обладать следующими свойствами: 1) В В' (самосопряженность); 2) В ) О, т.е. (Ви, и) ~ у(и, и) для всех и; 3) (очень важное свойство) оператор В должен быть легко обратимым, т.е. задача ВО = к легко решается; мы имеем алгоритм, позволяющий сравнительно щешево» определить О из этого уравнения («дешево» по сравнению с «ценой» исходной задачи Ри = /'); 4) (очень важное свойство) оператор В должен быть «энергетически эквивалентен» оператору — Р в смысле неравенств у!(Ви, и) < ( — Ри, и) ц т (Ви, и), 'т! и. Положительные постоянные О ( т! с тз называются константами эквивалентности В н — Р; будем считать нх известными.
Итерационный процесс фактически реализуется так: 1) вычисляем г' = Ри! — У (и' — известно); 2) решаем уравнение ВО! = г'; 3) вычисляем и!+' = и' + тв!. Формально процесс можно записать в виде и!+' = и! + тВ 'Ри! — тВ Алгоритм напоминает метод простой итерации с оператором В 'Р. Если В н Р неперестановочны, нз самосопряженности В и Р не следует самосопряженность В 'Р.
Однако это легко исправить. Так как 1б9 5 14! гвшвниз эллиптических злаьч методом сеток В В' и В > О, существуютоператоры Визн В Нз. Сделаем замену переменных в = Вози и умножим формулу итерации на Вцз: Внзи'+г «Внзи1+ тВнзВ 1РВ изВнзи' — тВ11зВ 1/, т.е. и'+1 и1+ тВ нзРВ ням' — тВ нз/. Обозначим Б В ихРВ ит.
Легко видеть, что Г = Я и итерация может изучаться в виде н'+' = н'+ тБю'+ 7. Из предположения об энергетической эквивалентности можно вывести важный факт: спектр оператора 5 (в смысле Б р = — Ьр) положительный и у, н Хн уз. В самом деле, т,(Ви, и) н ( — Ри, и) ч 'у,(Внзи, Вити) и ( — Ри, и), т и (так как В = ВпзВпз, (Внз)' = Впз). Полагая Вази = ю, имеем у1(н, я ) н (-РВ изн, В нззг) = ( — В цзРВ нзгг, ю), т.е. у1(и, и) < (-Юи, и), Ч и. Аналогично, из ( — Ри, и) < ух(Ви, и), ч и следует ( — Би, и) н уз(н, и). если Яю= — хзг, то ( — 51«, «) = = Ци, 1«), т.е. х е (У„Уз). Сведя исследование итерационного процесса с регуляризатором В к исследованию простой итерации с оператором 5, можно воспользоваться уже знакомой нам теорией.
В частности, если границы у, и у близки друг к другу (т.е. оператор В 'Р «хорошо обусловлен»), то в качестве оптимального итерационного параметра можно взять т = 2/(у, + уз), что приведет к сходимости с множителем (уз — т,)/( у, + уз) за одну итерацию. Правда, не следует забывать, что «цена» такой итерации зависит от затрат вычислительной работы на решение уравнения Ве = г. Если оператор В 'Р «плохо обусловлен (у /у,з~!), то можно использовать чебышеаское ускорение и получить процесс, в котором средняя за итерацию эффективность соответствует множителю (1 — 2 ~7;/Я).
Применение общей схемы. Конкретные итерационные алгоритмы получаются при конкретном выборе регуляризатора В. Приведем некоторые примеры. Метод простой итерации. Он получается при В = Е. Метод переменных направлений (точнее, некоторые его обобщения).
Он получается при выборе в качестве регуляризатора «факто- ризованной» конструкции В»в Š— а — Š— оз— [ч. 1 основы вычнслнтхльной млтемлтнкн 1то (Напомним, что мы договорились производные понимать в смысле их простейших разностных аппроксимаций.) Оператор В легко «обращается». Решение уравнения Во = з сводится к решению последовательности задач: а) Š— а — н'=г, б) Š— аз — о=о'. ! хг) ' ~ г) Каждая из этих задач расщепляется на серии «одномерных», легко решаемых прогонкой систем уравнений. Здесь мы сталкиваемся с характерной ситуацией: конструкция оператора В содержит некоторые параметры (а„а в данном случае).
Вместе с параметром т они должны быть найдены таким образом, чтобы получить возможно более высокую скорость сходимости. Точный анализ сходнмости в общем случае провести не удается. Поэтому задача «оптимизации параметров» обычно решается раздельно: сначала за счет выбора параметров регулярнзатора стремятся уменьшить обусловленность 5 — величину уз/у,, т.е.
сблизить оценки в неравенствах энергетической эквивалентности операторов В и — Р. Теоретической предпосылкой для существования хороших оценок такого типа является известный факт из теории эллиптических операторов; два любых эллиптических дифференциальных оператора одного порядка энергетически эквивалентны друг другу. Следствием этого является и энергетическая эквивалентность их разностных аппроксимаций с постоянными ун у, не зависящими по существу от шага сетки Л. Рассматриваемый здесь факторизованный оператор В является, как легко заметить, аппроксимацией дифференциального оператора четвертого порядка (правда, вырожденного).
Дифференциальные операторы разных порядков не могут быть энергетически эквивалентными. Это приводит к существенной зависимости констант у, от Л: у /у, = О(Л ') при «оптимальном» выборе ан а. Попеременно-треугольный метод. В качестве регуляризатора используется факторизованный оператор В=Я1йз Е+ а — „+ — д Š— а — „+— д д1З д д 2 Очевидно, В= Š— аз~ — + — ~.
Оператор ~ — + — ) имеет второй дх ду~ ' дх ду порядок, но, к сожалея)по, не является строй эллиптическим. Сла- гаемое Е при подходящем выборе о. придает разностной аппроксимации В «эллиптический» характер. Оператор В легко обратим: решение уравнения Ви= г требует числа операций, пропорционального числу неизвестных, т.е. числу з! 41 гашение эллиптнчвскнх э»д«ч методом свток узлов сетки. Чтобы убедиться в этом, выпишем подробно разностную аппроксимацию Я, и Рз: «! На рис. 16 показана сетка и расположение в ней шаблонов операторов Я,, Яз; такая аппроксимация обеспечивает важное свойство Я =Я; Из этого рисунка очевиден алгоритм «обращеннй» Вп Я при нзвестнык значениях о на границе.
Решение, например, уравнения Я,о = з осуществляется «маршевым» алгоритмом вычисления слева-направо и снизу-вверх, начиная с левою нижнего угла области. На каждом шаге такого алгоритма в выражении (М|о)» из трех значений о два (о«, и о„ ,) и уже известны н можно вычислить 1 Г о 1+2«ул ~ кч л ( «-к ««,т-1) Устойчивость этого «марша» легко устанавливается (прн о > О). Обращение йз осуществляется аналогично, но в обратном направлении (начиная с правого верхнего угла области). Оптимизация оценок эквивалентности за счет о приводит к уз/у, = О(л '). Выбирая далее последовательность итерационных параметров т,. в соответствии с теорией чебышевского ускорения, получаем алгоритм, в котором число итераций, необходимых для уменьшения погрешности начального приближения в е ' раз, есть (для сетки ЖхуУ) У(е) = О(~/У!и е 1).
Ограничимся здесь этими общими сведениями, отправляя интересующихся деталями (как оценивать у„уз, как выбирать и и т.п.) к специальной литературе. «Двухступенчатые» итерационные методы. Почти очевидно, в каком направлении следует искать операторы В, наилучшие с точки зрения оценок энергетической эквивалентности: оператор В должен быть возможно более похожим на — Уэ (идеальный случай: В = — Ю, у, = уз »» 1„ достаточно одной итерации; к сожалению, она просто эквивалентна решению исходной задачи). Однако по мере сближения В с — Р возрастают трудности решения уравнения Во = г. основы вычислительной млтемлтики !ч.1 Удачным компромиссом является, например, выбор В этом случае у~у, ие зависит от л, а для решения разиостиого уравнения — Ьн= з можно использовать построенные в последние годы эффективные алгоритмы для решения в прямоугольной области уравнения с постоянными коэффициентами. Ограничимся здесь только названиями методов, тем более что многие из иих уже оформлеиы как стаидартиые быстро работающие программы математического обеспечения современных ЭВМ: это методы циклической редукции, быстрого преобразоваиия Фурье (см.
5 24), маршевый и иекоторые другие. Кстати, включение некоторых из иих в арсенал средств практических вычислений было связаио с анализом вычислительной неустойчивости и разработкой вычислительно устойчивых модификаций (как это было с чебышевским ускорением).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
