Экономичных разностных схем
1. Одним из основных критериев оптимальности в теории численных методов является требование минимума арифметических операций. Для одномерных задач математической физики особых затруднений в этом плане нет. Разностные схемы в этом случае реализуются экономичным алгоритмом прогонки, который на слое сетки допускает количество арифметических операций пропорциональное количеству узлов. Особую остроту приобретает вопрос об экономичности вычислительных алгоритмов в численном решении многомерных задач математической физики. Многомерные краевые задачи моделировать многомерными разностными схемами и решать непосредственно эти схемы нецелесообразно, так как алгоритм становится сложным, неэкономичным и нереализуемым на ЭВМ. Пусть в цилиндре ищется решение уравнения (2.1) удовлетворяющее условиям (2.2) (2.3) где -мерный единичный куб, - боковая поверхность . Задачу (2.1)-(2.3) моделируем разностной схемой с весом: (2.4)
где - вещественный параметр. Разностное уравнение запишем в операторном
где Е - единичный_ оператор. Нахождение при требует обращения многомерного оператора , что связано с весьма трудоемкой вычислительной работой, поскольку соответствующая этому оператору матрица порядка не имеет специального вида. Обращение такой матрицы производится по методу Гаусса, что требует арифметических операций или методом итераций, который также требует много машинного времени. По этой причине непосредственное решение схемы (2.4)-(2.6) даже при нецелесообразно, так, как возникают серьезные проблемы памяти ЭВМ и резко возрастает количество арифметических операций на слое сеткой. Схема может оказаться нереализуемой на современных ЭВМ. Если в уравнении (2.4) , то получаем явную схему которую перепишем в виде
В этом случае обращается диагональная матрица, требующая лишь 0(N) арифметических операций. Условием устойчивости схемы (2.4)-(2.6) будет Отсюда видно, что условием устойчивости явной схемы будет Из условия (2.7) видно, что схемы о , в том числе чисто неявная схема при и симметричная схема при , абсолютно устойчивы. Если имеем уравнение с переменными коэффициентами, т.е. (2.8) то Условие устойчивости схемы (2.4)-(2.6) с эллиптическим оператором (2.8) имеет вид Отсюда получаем условие устойчивости явной схемы в виде (2.9) Условие устойчивости (2.9) налагает весьма жесткие ограничения на шаг по времени и выход на заданный момент времени по явной схеме требует неоправданно большого числа временных шагов. Из условия (2.9) видно, что выбор шага существенно зависит от количества пространственных переменных р и от величины М. С ростом числа р и для быстро меняющегося коэффициента теплопроводности K=K(x,t) шаг становится еще мельче. В этом случае схема (2.4)-(2.6) при становится неэффективной, так как выход на заданный момент времени t=T требует слишком большого числа временных шагов. Чисто неявная схема ( ) (2.4)-(2.6) абсолютно устойчива, т.е. на параметры сетки h и не налагаются ограничения. Поэтому счет можно вести более крупными шагами h и и тем самым удается значительно понизить порядок системы, уменьшить количество временных шагов, необходимых для достижения момента времени t = Т . В неявных схемах придется решать системы алгебраических уравнений, как правило, высокого порядка и с разреженными матрицами. Итак, реализация систем алгебраических уравнений для многомерных задач в общем случае представляется невозможной из-за громоздкости порядка системы (проблема памяти ЭВМ), большого объема арифметических операций. Таким образом, лучшими качествами явной и неявной схем являются количество арифметических операций, равное 0(N) в явной схеме, и абсолютная устойчивость неявной схемы, недостатками - условная устойчивость явной схемы и большое количество арифметических операций в неявной схеме. Отсюда ясно, что если построим разностные схемы, сочетающие в себе лучшие качества обычных явных и неявных разностных схем, то можно эффективно решать многомерные задачи математической физики. Итак, безусловная (абсолютная) устойчивость и независимость количества арифметических операций, требуемые для вычисления приближенного решения задачи в отдельной точке сетки от общего количества узлов сеточной области, определяют класс экономичных схем. Уравнение (2.1) можно аппроксимировать по-другому, стремясь упростить вычислительный процесс. Уравнение (2.1) аппроксимируем разностным уравнением В этой схеме аппроксимация по первому направлению неявная, а по всем остальным - явная. Реализация этой схемы идет по направлению , как в одномерном случае методом линейной прогонки, затратой арифметических операций порядка . Однако схемы (2.10), (2.5), (2.5) условно устойчивы. Таким образом, из требований экономичности разностной схемы первое условие не выполнено, а второе - выполнено. Поэтому схемы типа (2.10), (2.5), (2.6) не относятся к классу экономичных схем, они конструируются специальным образом. 2. Достижением вычислительной математики является разработка экономичных методов решения многомерных краевых задач математической физики. Первые экономичные схемы были схемами в дробных шагах по времени t. Они предложены и обоснованы в 1955 г. одновременно американскими учеными D.W. Peacemdn , H.H.Rachford и J.Douglas. Характерной особенностью экономичных схем этого периода является то, что все они основывались на идее ведения дробных моментов времени и поэтапном решении р задач в промежутках . Решением исходной задачи будет решение последней р -й задачи в момент времени . Решения остальных (р-1) задач являются вспомогательными в моменты времени . Таким образом, наряду с основной сеткой по рассматривается вспомогательная сетка . Все экономичные схемы этого периода относятся к схемам последовательного перехода по времени t. Следуя Н. Н. Яненко, назовем их методом дробных шагов. В 1965г. А. А. Самарский предложил и обосновал экономичный метод без привлечения вспомогательной сетки , т.е. экономичная схема конструируется на исходной сетке . Таким образом, характерной областью экономичных схем этого периода является то, что сетка не вводится, вспомогательные функции рассматриваются на верхнем слое. Составная схема конструируется на исходной сетке . Как будет показано ниже, отказ от вспомогательной сетки дает широкие возможности для построения различных экономичных схем и тем самым удается значительно расширить их класс. Экономичные методы, построенные на такой основе, назовем методом целых шагов. На основе метода целых шагов строятся экономичные схемы последовательного и параллельного (одновременного) перехода с нижнего слоя на верхний слой по t. Любая разностная схема, моделирующая исходную дифференциальную краевую задачу, должна удовлетворять данным условиям устойчивости, аппроксимации на решение исходной задачи и простоты. Если эти требования для одномерной разностной схемы выполняются сравнительно легко, то при переходе к двумерной (многомерной) задаче возникают значительные трудности. Перед вычислительной математикой встала сложная задача построения экономичных методов решения многомерных задач математической физики. Стало невозможным разрешить эту проблему на базе однородных разностных схем, где при переходе от одного временного слоя к другому одновременно удовлетворяются условия устойчивости и аппроксимации. При этом, конечно, формула получается более простой, но схема становится менее гибкой и имеет в своем распоряжении небольшое количество произвольных параметров, что создает основные трудности выполнения вышеописанных требований. Экономичные схемы, расчленяя переход от нижнего слоя к верхнему на ряд промежуточных этапов и не требуя на каждом этапе обязательного выполнения свойств аппроксимации исходного уравнения и устойчивости, имеют в своем распоряжении набор параметров, что дает возможность выбора наиболее эффективного вычислительного алгоритма. Пусть имеем уравнение теплопроводности Разрабатывая в 1955г. первые экономичные схемы переменных направления, Писмен, Рэкфорд и Дуглас имели в виду упростить решение алгебраической системы уравнений высокого порядка, сохранить абсолютную устойчивость и приемлемую точность, тем самым удовлетворили до некоторой степени вышеописанные требования. Идея метода заключается в следующем. Уравнение (2.2) аппроксимируется разностным уравнением
(2.12) Нетрудно заметить, что схема (2.12) является условно устойчивой и симметризуется так, чтобы и менялись ролями от шага к шагу (2.13) Если в схему (2.23) счет повторяется при переходе с j –го слоя на (j+2)-й, то (j+1)-й слоя выступает в роли вспомогательного слоя. Поэтому, введя дробные моменты времени , схему (2.13) можно переписать в виде (2.14) Путем исключения вспомогательных функций в дробные моменты времени получаем эквивалентную ей однородную схему (2.15) Схема (2.15) и эквивалентная ей схема (2.14) аппроксимируют уравнение (2.11), как и схема . Безусловная устойчивость схемы (2.15) или (2.14) устанавливается методом Неймана. Схема (2.14) решается двумя одномерными прогонками, что не только упрощает алгоритм счета, но и уменьшает объем вычислений. Из (2.13) или (2.14) видно, что методы Писмена, Рэкфорда и Дугласа предполагают обязательную аппроксимацию дифференциального уравнения по каждому направлению. Они представляют неявный метод переменных направлений. Заметим, что этот метод не годится для пространства нечетного числа измерений. Например, при р=3 интегрирование в каждом направлении происходит один раз неявно, а явно. Тогда возрастание ошибки в явной схеме не компенсируется убыванием ее в неявной схеме. Это подтверждается точным анализом устойчивости при р=3. Заметим также, что метод переменных направлений не годится для уравнений со смешанными производными даже при р=2. Для решения трехмерного уравнения (2.2) в работе J.Douglas, H.Rachfozd была предложена следующая схема: (2.16) Методом исключения функций в дробные моменты времени показывается аппроксимация, а методом Неймана устанавливается устойчивость. Из (2.16) видно, что первое уравнение дает полную аппроксимацию уравнения (2.11)(p= 3), а следующие два уравнения дают поправку на устойчивость. Такие схемы называются схемами стабилизируюшей поправки или схемами с поправкой на устойчивость. В основу работ советских авторов положен метод расщепления сложных разностных операторов на более простые. При таком подходе, схемы дробных шагов обязаны удовлетворять условиям аппроксимации и устойчивости только на целом шаге. Ниже будет показано, что это дает возможность построения гибких разностных схем для многомерных задач математической физики.- Первой в этом направлении является работа А.А.Багриновского, С.К.Годунова, где был предложен метод расщепления многомерных разностных уравнений, аппроксимирующих системы гиперболических уравнений, путем сведения их к простейшим разностным схемам. Такой метод Н.Н.Яненко называет методом расщепления. Идею метода покажем на примере уравнения (2.2), которое аппроксимируется явной схемой вида (2.17) Схема (2.17) заменяется "расщепленной" схемой . (2.18) Действительно, просуммировав (2.18) по , получим схему (2.17). Однако, практически явная растепленная схема (2.16) не имеет преимуществ по сравнению многомерной схемой (2.17) ни в точности, ни в объеме вычислительной работы. Отсюда видно, что метод расщепления может быть эффективным только в сочетании с неявными схемами указанные выше затруднения метода переменных направлений и явного метода расщепления впервые были устранены в работе Н.Н.Ясненко, где автор использует на каждом дробном шаге только неявные операторы. На каждом дробном шаге в правой части аппроксимируется оператор полная аппроксимация достигается только на полном шаге. Неявный метод расщепления для уравнения (2.11) (например, при р=3) имеет вид: (2.19) При методе исключения величин на промежуточных дробных шагах видно, что схема (2.19) аппроксимирует уравнение (2.11). Безусловная устойчивость показывается методом Неймана. Схема (2.19) при удовлетворяет принципу экстремума, поэтому решение схемы (2.29) сходится в пространстве С к решению дифференциального уравнения (2.11). В работах для повышения точности решения используются схемы с весами. Метод расщепления был применен Н.Н.Яненко для уравнений теплопроводности со смешанными производными, доказана общая теорема сходимости для системы линейных уравнений параболического типа с постоянными и переменными коэффициентами. Метод расщепления был обоснован Г.И.Марчуком для приближенного интегрирования нерегулярных систем в динамической метрологии, при решении многомерных кинетических уравнений Больцмана. Для некоторых динамических и статических задач теории упругости метод расщепления был сформулирован и обоснован впервые А.Н.Коноваловым. G.A. Baker, J.А. Oliphant предложили метод факторизации разностного оператора для интегрирования уравнения типа (2.11). Уравнение (2.11) (р = 2) аппроксимируется схемой вида: (2.20) где - разностный оператор на старшем слое, - результат применения разностных операторов на младших слоях. Если ограничиться рассмотрением девятиточечных операторов, то можно выбрать оператор так, чтобы его можно было представить в виде произведения двух трехточечных операторов А и В. Схема (2.20) возникла из трехслойной аппроксимации уравнение (2.11), где - некоторый девятиточечный оператор. В этом случае
. (2.21) При этом оператор подбирается так, чтобы аппроксимация имела второй порядок точности и оператор из (2.21) представлялся в виде произведения двух трехточечных операторов. Тогда уравнение (2.20) можно представить в виде двух уравнений: каждое из которых решается алгоритмом линейной прогонки. Н.Н.Яненко в работе обосновал метод приближенной факторизации разностного оператора на примере уравнения (2.11). Рассматривается разностное уравнение которое представляется в виде (2.22) Оператор факторизуется приближенно с точностью членов порядка (2.23) Схема (2.22) заменяется факторизованной схемой Водятся вспомогательные величины с помощью неравенств
Отсюда видно, что схема (2.24) является схемой расщепления, эквивалентной схеме приближенной факторизации оператора (2.23). Следует заметить, что схема точной факторизации оператора не применима в случае уравнения диффузии с переменными коэффициентами, так как при этом потребуются дополнительные итерации, в то время как метод приближенной факторизации остается в силе и для уравнений о переменными, коэффициентами. Для решения уравнения (2.11) (р=з) в работе была предложена абсолютно устойчивая схема, получаемая из схемы стабилизирующей поправки применением приема предиктора-корректора (пересчет), которая имеет вид: (2.25а) (2.25б) (2.25в) (2.25г) Уравнения (2.25а, б, в) представляют собой предиктор (схему стабилизирующей поправки), уравнение (2.25г) - корректор. Для нелинейных уравнений метод предиктор-корректор может служить при восстановлении дивергентности схемы, с помощью которой строятся безытерационные разностные схемы. К классу экономичных разностных схем относятся разностные схемы с расщепляющимся оператором на верхнем слое. Метод использует алгоритм счета основанный на расщеплении оператора. Он был предложен Е.Г.Дьяконовым для случая параллелепипеда и для более сложных областей. Заметим, что для уравнений с постоянными коэффициентами разностные расщепляющиеся операторы по существу встречались в экономичных разностных схемах метода расщепления. Обычно неявные разностные схемы для нестационарных задач имеют вид (2.26) где - вектор значений функций на слое сетки - заданный вектор, - некоторые разностные операторы. Е.Г.Дьяконов называет разностный оператор А расщепляющимся, если его можно представить в виде , где - операторы размерности меньшей, чем р. Если все одномерные операторы, то нахождение из (2.26) сводится к последовательному решению p систем уравнений . Наиболее близким к идее расщепляющегося разностного оператора на верхнем слое является метод факторизации разностного оператора на верхнем слое. Однако, как уже было отмечено выше, факторизация расщепляющегося оператора по методу возможна лишь для уравнений с неразделяющимися переменными. В этом случав расщепляющийся оператор А можно факторизовать лишь неполностью, при этом из-за неполной факторизации оператора А возникает необходимость на каждом временном слое применять итерационный процесс, являющийся некоторым видоизменением метода. В работах Е.Г.Дьяконова дан анализ краевого условия первого рода для метода расщепления, из которого видно, что в методе расщепления встречаются некоторые затруднения на границе областей, составленных даже из прямоугольников. Более подробный анализ краевых условий для метода расщепления дается в работе. Н.Н.Яненко. В ней анализируются три реализации краевого условия первого рода для метода расщепления: 1) реализация Е.Г.Дьяконова; 2) реализация краевого условия с погрешностью аппроксимации 3) реализация способа аппроксимации краевого условия первого рода В работе показывается, что реализация 2) годится для областей произвольной формы. В то время как реализация 3) становится неэффективной даже в случае области, состоящей из конечного числа прямоугольников. Более общий прием реализации краевого условия первого рода был предложен почти одновременно С.А.Кряквиной и Н.Н.Анучиной (по Н.Н.Яненко). Сущность метода состоит в замене граничных значений неопределенными функциями. После чего задача состоит в том, чтобы минимизировать ошибку Rn Н.Н.Яненко в работе придает методу неопределенных функций более общую формулировку, где неопределенные функции вводятся сразу в правых частях расщепленных разностных схем. Вопросы анализа краевого условия второго рода для области о криволинейной границей заметно усложняются. В работе предлагается итерационный процесс решения второй краевой задачи для метода расщепления. Дальнейшим развитием метода дробных шагов является локально-одновременный метод переменных направлений А.А.Самарского, пригодный для решения широкого класса задач математической физики для областей произвольной формы. Дадим краткое описание метода на примере уравнения (2.11). В каждом слое рассматривается одномерное дифференциальное уравнение (2.27) Для решения (2.27) используются однородные разностные схемы (2.28) изученные. Таким образом, разностной схемой ПУ, соответствующей уравнению (2.11) является совокупность (блок) одномерных схем . Каждая из схем имеет погрешность аппроксимации
где u – решение уравнения (2.11). Погрешность аппроксимации схемы определяется суммой . Все вычисляются на решении исходной задачи. Если то , где . Сходимость решения разностной схемы (2.28) к решению задачи (2.11) доказывается специально разработанным для однородных разностных схем методом априорных оценок. Дифференциальные задачи аппроксимируются семейством однородных разностных схем, коэффициенты которых задаются шаблонными функционалами. Метод построения семейства однородных разностных схем, предложенный А.Н.Тихоновым и А.А.Самарским успешно используется в локально-одномерном методе переменных направлений. В нем граничные условия для вспомогательных функций задаются естественным образом, поэтому граничная проблема здесь не возникает. Для случая области сложной формы впервые вопрос расщепления краевого условия третьего рода был рассмотрен И.В.Фрязиновым. Некоторые обобщения метода переменных направлений даются в работах В.П.Ильина. A.R.Mitchell в работе методом неопределенных коэффициентов строит схемы переменных направлений повышенной точности, из которых в частном случав получает схемы Писмена, Рэкфорда и Дугласа и схему стабилизирующей поправки Дугласа, Рэкфорда. В работах Н.Н.Яненко и Г.В.Демидова метод расщепления трактуется как метод слабой аппроксимации для многомерной задачи Коши. В работе был рассмотрен вопрос сходимости метода дробных шагов в дифференциальной форме при решении корректной задачи Коши в банаховом пространстве. В работе для однородного уравнения параболического типа второго порядка с однородными условиями первого рода методом Фурье можно показать, что решение р-го расщепленного дифференциального уравнения совпадает с решением исходного уравнения, т.е. . Неоднородная абстрактная задача Коши в банаховом пространстве Н рассмотрена в работе А.А.Самарского. Методу слабой аппроксимации посвящены работы Н.Н.Яненко, А.А.Самарского, Г.И.Марчука, Д.Г.Гордезиани, Г.В.Мелидзе, Е.Г.Дьяконова, В.И.Лебедева, Г.А.Бюлера, Н.М.Охлопкова и др. Метод слабой аппроксимации используется как конструктивный метод построения экономичных разностных. Г.И.Марчук разработал методы покомпонентного расщепления для широкого класса задач математической физики. Различным аспектам метода дробных шагов расщепления посвящены работы В.Б.Андреева, В.И.Лебедева, А.Н.Коновалова, Г.А.Бюлера, И.В.Фрязинова, Н.М.Охлопкова и многих др. До сих пор мы рассматривали экономичные разностные схемы, построенные на основе классических явных и неявных разностных схем. Следует отметить, что наиболее экономичные разностные схемы могут быть построены на основе явно-неявных разностных схем с помощью расщепления разностного оператора и сеточной области. Такие схемы, как правило, реализуются явным образом, поэтому они наиболее эффективны в смысле количества арифметических операций и программирования на ЭВМ. Их изучали В.К. Саульев, Н.Н.Яненко, А.А.Самарский, В.П.Ильин, Н.М.Охлопков и многие другие [2,9].
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (338)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |