А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978), страница 3

Особое место в книге занимает предложенный и развитый авторами в 1964 †19 гг. универсальный попеременно-треугольный метод, эффективность которого особенно сильно проявляется при решении задачи Дирихле для уравнения Пуассона в произвольной области и задачи Дирихле для уравнения д!ч (й ягаб и) = = — 7(х), х=-(х„х,) с сильно меняющимся коэффициентом й(х).

В книге показано, как переходить от общей теории к конкретным задачам, и приведено большое число итерационных алгоритмов решения разностных уравнений для эллиптических уравнений и систем уравнений. Даны оценки числа итераций и проведено сравнение различных методов. Так, в частности, показано, что для простейшей задачи прямые методы более экономичны, чем метод переменных направлений. Следует подчеркнуть, что возпика>ощие па практике все более и более сложные задачи линейной алгебры требуют как разработки новых методов, так н рашппрсппя области применимости старых методов. При этом происходит переоценка сравнительных характеристик разных методов.

Прп паппсашп> книги авторы использовали материалы лекций, читавпп>хгя пмп в период 1961 — !977 гг. на механико-математическом факультете и па факультете вычислительной математики и киб<рпсвпкп МГУ, а также материалы опубликованных работ авто!нп>. Лпторы п<>льву>отея возможностью выразить благодарность В. Б. Лпдрссву, И. В. Фрязинову, М. И.

Бакировой, А, Б. Кучерову, И. ! . Капорину за ряд полезных замечаний по материалу кпнгп. Лвторы благодарны Т. Н. Галишниковой, А. А. Голубевой и особенно В.М.Марченко за помощь при подготовке рукописи к печати. Москва, декабрь 1977 г, А. А. Самарский, Е. С. Николаса ВВЕДЕНИЕ Применение различных численных методов (разностных, вариационно-разностных, проекционно-разностных методов, в том числе метода конечных элементов) для решения дифференциальных уравнений приводит к системе линейных алгебраических уравнений специального вида — к разностным уравнениям.

Эта система обладает следующими специфическими чертами: 1) она имеет высокий порядок, равный числу узлов сетки; 2) система . плохо обусловлена (отношение максимального собственного значения матрицы системы к минимальному велико; так, для разностного оператора Лапласа это отношение обратно пропорционально квадрату шага сетки); 3) матрица системы является разреженной — в каждой ее строке отлично от нуля несколько элементов, число которых не зависит от числа узлов; 4) ненулевые элементы матрицы расположены специальным образом — матрица является ленточной.

При аппроксимации па сетке интегральных н интегро-дифференциальных уравнений мы получаем систему уравнений относительно функции, заданной на сетке (сеточной функции), Такие уравнения естественно называть сеточными уравнениями: ,)'., а (х, $) у Д) = ) (х), х Е а, (1) 16Ю где суммирование проводится по всем узлам сетки в, т, е. по дискретному множеству точек. Матрица (а(х, $)) сеточного уравнения является, в общем случае, заполненной.

Если перенумеровать узлы сетки, то сеточное уравнение можно записать в виде ~а;,у,=~;, 1=1,2, ..., У, (2) 1=! где 1, 1 — номера узлов сетки, Л' — общее число узлов. Обратный ход рассуждений очевиден. Таким образом, линейное сеточное уравнение есть система линейных алгебраических уравнений и, обратно, любую линейную систему алгебраических уравнений можно трактовать как линейное сеточное уравнение относительно сеточной функции, заданной на некоторой сетке с числом узлов, равным порядку системы. Заметим, что вариационные методы (Рнтца, Галеркина и др.) численного решения дифференциальных 11 уравнений приводят обычно к системам с заполненной матрицей. Разностное уравнение есть частный случай сеточного уравнения, когда матрица (аы) является разреженной. Так, например, (2) представляет собой разпостное уравнение л»-го порядка, если в строке номера 1 имеется лишь л« + 1 отличный от нуля элемент аы при 1'-=1, 1+1, ..., 1+т.

Из сказанного ясно, что решение сеточных и, в частности, разностпых уравнений является задачей линейной алгебры. Для решения задач линейной алгебры существует много различных численных методов, непрерывно ведется работа по их усовершенствованию, проводится переоценка методов, разрабатываются новые методы.

В результате оказывается, что значительная часть имеющихся методов имеет право на существование, обладает своей областью применимости. Поэтому для решения конкретной задачи на ЭВМ существует проблема выбора одного метода на множестве допустимых методов решения данной задачи., Этот метод должен, очевидно, обладать наилучшими характеристиками (или, как любят говорить, быть оптимальным методом) такими, как минимум времени решения задачи на ЭВМ (или миг нимум числа арифметических и логических операций при отыскании решения), вычислительная устойчивость, т. е.

устойчивость по отношению к ошибкам округления, и др. Естественно требовать, чтобы любой вычислительный алгоритм для ЭВМ позволял в принципе получить решение данной задачи с любой наперед заданной точностью е > О за конечное число действий Я(з). Этому требованию удовлетворяет бесчисленное множество алгоритмов, в котором и следует искать алгоритм с минимумом Я(з) для любого е ) О.

Такой алгоритм называется экономичным. Конечно, поиск «оптимального» нлн «наилучшего» метода, как правило, проводится на множестве известных (а не всех допустимых) методов, и сам термин «оптимальный алгоритм» имеет ограниченный н условный смысл. Задача теории численных методов состоит как в отыскании наилучших алгоритмов для данного класса задач, так и в установлении иерархии методов. Само понятие наилучшего алгоритма зависит от цели вычислений.

Возможны две постановки вопроса о выборе наилучшего метода: а) требуется решить одну конкретную систему уравнений Аи=)', А =(а,~) — матрица; б) требуется решить несколько вариантов одной и той же задачи, например, уравнения Аи=( с различными правыми частями ~. 12 При многовариантном расчете можно уменьшить среднее число операций (7(е) для одного варианта, если хранить некоторые величины, а не вычислять их заново для каждого варианта (на-, пример, хранить обратную матрицу). Отсюда ясно, что выбор алгоритма должен зависеть от типа расчета (одновариантного илн многовариантного), от возможности хранения дополнительной информации в памяти ЭВМ, что в свою очередь связано как с типом ЭВМ, так и с порядком системы уравнений. При теоретических оценках качества вычислительного алгоритма обычно ограничиваются подсчетом числа арифметических операций, которые требуются для отыскания решения с заданной точностью; при этом вопрос о параметрах ЭВМ, как правило, не обсуждается.

Бурное развитие в последние годы численных методов решения разностных уравнений, аппроксимирующих дифференциальные уравнения эллиптического типа, и появление новых экономичных алгоритмов привели к необходимости пересмотра представлений об областях применимости существовавших ранее методов. Содержание данной книги в значительной степени обусловлено необходимостью дать эффективные методы решения разностных уравнений, соответствующих краевым задачам для уравнений эллиптического типа второго порядка.

Классификация разностных краевых задач может быть проведена по следующим признакам: !) вид дифференциального оператора Л в уравнении Еи = )'(х), х = (х„х„, хр) Е 6; 2) форма области 6, в которой ищется решение; 3) тип краевых условий на границе Г области 6; 4) сетка в в области 6 =6+Г и разностная схема Лу= — !р(х), хЕв, (4) д!и !.и = Ли = ~~!" —,, — оператор Лапласа, а=! р Еи С' д (Лаз(х) дх ) — д(х)и а.в ! (6) 13 т. е. вид разностного оператора Л, Примерами эллиптического оператора второго порядка могут быть причем коэффициенты й„а (х) в каждой точке х=(х„х,,..., хр) удовлетворяют условию сильной эллиптичности Р Р Р с»,Я~ $'„( ~! й„а (х)3Да (с»~~Л ~Ц, с„с»=-сопз1; О, (7) а=! а,а«н а=! где ь=5„..., $р) — произвольный вектор.

Если и(х) (и'(х), и'(х), ..., и"'(х)) — век!ор-функция, то (3) есть система уравнений и Р (Т,и)'=~ ~ — (йпа —.„), !=1, 2, ..., ~п, а условие сильвой эллиптнчности имеет вид П$ »$ Р р т ; Х Х Д'.)*( Х Х й'!з(х) ~.!Ц (с. Х Х Ю'. с„с, = сон»1 ) О. Форма области сильно влияет на свойства матрицы разностных уравнений. Мы будем выделять области, для которых уравнение ьи = 0 с однородными краевыми условиями допускает разделение переменных. Так, например, для уравнения Лапласа а»и д»и в декартовых координатах (х„х,) Т.и= Аи= —,+ —, метод ах! дх» разделения переменных применим в случае, когда б есть прямоугольник.

Аналогичным свойством обладает и разностная схема на прямоугольной сетке, например, схема «крест»; при этом сетка может быть неравномерной по каждому направлению. При сравнении различных численных методов решения систем алгебраических уравнений будем использовать в качестве эталонной или модельной задачи следующую разностную краевую задачу: уравнение Пуассона, область — квадрат, краевые условия первого рода, сетка — квадратная с шагами й,=й и й,=й по х, и х„ разностный оператор А — пятиточечный. Вторая группа разностных краевых задач соответствует следующим данным: 7.— оператор с переменными коэффициентами вида (6): а) без смешанных производных, б) со смешанными производными, область 6=(О(х„(1„, и=1, 2) — прямоугольник (параллелепипед при р)3).

Третья группа задач — область сложной формы, а 7. либо оператор Лапласа, либо оператор общего вида; здесь степень сложности задачи определяется в первую очередь формой области, выбором сетки и разностного оператора в окрестности границы. Для второй и третьей групп задач разностный оператор обычно выбирается так, чтобы сохранить основные свойства (самосо- 14 нряженность, знакоопредсленность и др.) исходной задачи и удовлетворить требованию аппроксимации с определенным порядком относительно шага сетки. Для решения разностных эллиптических задач применяются прямые и итерационные методы. Прямые методы применимы в многомерном случае в основном для задач первой. группы (Š— оператор Лапласа, 6 — прямоугольник при р= 2 и параллелепипед при р)3, Л вЂ” пяти- или девятиточечная разностная схема при р=2).

Для одномерных задач, когда разностное уравнение имеет второй порядок (матрица является трехдиагональной), а коэффициенты уравнения могут быть переменными, применим метод прогонки, который является вариантом метода Гаусса (см. гл. П). Существует ряд вариантов метода прогонки: монотонная прогонка, немонотонная прогонка, потоковая прогонка, циклическая прогонка и др. (см.