А.А. Самарский, Е.С. Николаев - Методы решения сеточных уравнений (1978) (1160094), страница 48
Текст из файла (страница 48)
Если В» хотя бы для одного й отлично от единичного оператора, то схема называется неявной. Числа т» называются итерационными параметрами. Если т»„зависит от итерационного приближения у, то итерационный процесс будет нелинейным, Очевидно, что в стационарном итерационном процессе операторы В» и параметры т» (точнее, В»1т»,) не должны зависеть' от номера итераций я. Отметим, что схему (6) можно трактовать как неявную двухслойную схему для нестационарного уравнения В(1) — „+Ао= — 1, 8) О, о(0)=у„ более общего, чем рассмотренное выше уравнение (2).
При этом параметр т„, можно рассматривать как шаг по фиктивному времени. Различие между итерационными схемами и схемами для не- стационарных задач вида (2) заключается в следующем: 1) при любых В„+, и т, решение и исходного уравнения (1) удовлетворяет (6); 2) выбор параметров т»~1 и операторов В»„ следует подчинить лишь требованиям сходимости итераций и минимума арифметических действий, необходимых для нахсякдения решения уравнения (1) с заданной точностью (для нестационарных задач выбор шага подчинен прежде всего требованию аппроксимации). Выше предполагалось, что оператор А линеен. Очевидно, схема (6) может быть использована для нахождения приближенного решения уравнения (1) и в случае нелинейного оператора А.
При этом обычно оператор В„„, выбирается линейным. Двухслойные итерационные схемы (6) являются наиболее употребительными. Однако при решении уравнения (1) используют и трехслойные схемы, которые описывают итерационные 260 процессы второго порядка. Наиболее исследованными являются трехслойные схемы «стандартного» типа. Они записываются в виде В„,у»э,= а»,,(В»„— т„»,А) у +(1 — а»«,) В„,,у„,+а„+,т„»,1 (7) для я=1, 2, ... Здесь используются две последовательности итерационных параметров (т„) и (а»).
Для реализации схемы (?) необходимо, помимо начального приближения у„задать еще приближение у,. Обычно оио находится по у, с использованием двухслойной схемы (6), т. е. В,у, = (В, — т,А) у, + т,?, у, Е Н. (8) Можно показать, что для (7), (8) решение и уравнения (1) является неподвижной точкой.
Если В =— Е для всех й = 1, 2 ..., то схема (7) называется явной: у»+« — -- а»+, (Š— т„»,А) у»+ (1 — а»+,) уь-, + а»+»т»~,7. В противном случае схема (7) неявная. 3. Сходимость и число итераций. Основное отличие итерационных методов от прямых заключается в том, что итерационные методы дают точное решение уравнения (1) лишь как предел последовательности итерационных приближений (у ) при й- оо, Исключение составляют методы «конечных» итераций, к которым относятся методы сопряженных направлений, теоретически позволяющие найти точное решение при любом начальном приближении за конечное число действий, если А — линейный оператор в конечномерном пространстве. Для характеристики отклонения итерационного приближения у» от точного решения и задачи (1) вводится погрешность г„=у» — и.
Итерационный процесс называется сходни(имся в энергетическом пространстве Но, если (г»!р — О при й- оо. Здесь Нр — пространство, порожденное самосопряженным положительно определенным в Н оператором О. Смысл введения энергетического пространства Но заклю. чается в следующем. Как мы знаем, последовательность элементов Н, сходящаяся в одной норме, сходится и в эквивалентной норме. Поэтому при исследовании конкретной итерационной схемы удобно выбрать такое энергетическое пространство Нр, в котором операторы итерационной схемы А и В„ обладали бы заданными свойствами, например были самосопряжены и положительно определены. Одной из важных количественных характеристик итерационного метода является число итераций.
Обычно задается некоторая точность е ) О, с которой надо найти приближенное решение уравнения (1). Если (и(о = 0 (1), то требуется, чтобы выполнялось условие 1у„— и(р(е пр ' пЪ п„(е). (й) 261 Здесь п,(е) — минимальное число итераций, гарантирующее заданную точность е. Это число зависит от того, какое взято начальное приближение. Условием (9) можно пользоваться для определения момента окончания итераций, если указанная норма может быть эффективно вычислена в процессе итераций. Например, если оператор А невырожден и положительно определен, то, выбирая в качестве .0 оператор А*А, получим из (9) ')у„— и)р — — - )! Ау„— ) )( (е, так как (у„— и, у„— и)р — — (А'А(у„— и), у„— и) = =(Ау„— Аи, Ау„— Аи)='1Ау„— Д', Для сравнения качества различных методов в общем случае используется число итераций, определяемое из условия '1ӄ— и!!(р(е~~У,— и)р пРи п~~п,(е).
(! О) Это число указывает, сколько итераций достаточно выполнить, чтобы при любом начальном приближении у, норма начальной погрешности в Ор была уменьшена в 1(е раз. Условие (10) также можно использовать в качестве критерия для окончания процесса итераций. Уравнению (1) можно поставить в соответствие большое число итерационных схем (6) или (7), (8) с любыми В„и тю ам Между тем при решении конкретной задачи возникает проблема выбора одной схемы. С точки зрения вычислительной математики наиболее важным является построение таких итерационных методов, которые позволяют получить решение (1) с заданной точностью за минимальное машинное время. Это требование экономичности метода является естественным. При теоретических оценках качества метода оно часто заменяется требованием минимума числа арифметических действий !е(е), достаточных для получения решения с заданной точностью. л Общий объем вычислений ~(е) равен Я(е) =,).", ды где д„— е=! число действий для вычисления итерации номера Й, а и — число итераций, п)п,(е).
Задача построения итерационного метода ставится так (для двухслойной схемы (6)): оператор А фиксирован, а параметры (тм й=1, 2, ..., и) и операторы Ве нужно выбрать из условия минимума 9(е). В такой общей постановке эта задача вряд ли имеет решение. Обычно набор операторов В„задается априори, и если число действий, необходимое для обращения оператора В„, не зависит от й, то де= д и Я (е)=дп,(е). В этом случае задача о минимуме 9(е) сводится к задаче выбора итерационных параметров т» из условия минимума числа итераций п,(е). 2б2 Чтобы установить иерархию методов, надо сравнить их по каким-либо характеристикам. Иногда используются асимптотические оценки для числа действий или для числа итераций при стремлении числа неизвестных в разностной схеме к бесконечности. Однако существует фактическое ограничение на число неизвестных при решении эллиптических многомерных уравнений методом сеток. Так, например, для трехмерного уравнения Пуассона среднее число узлов по каждому переменному Лгж100 приводит нас к системе линейных алгебраических уравнений с М = 10' неизвестными.
Вряд ли целесообразно увеличение . числа узлов. Поэтому надо сравнивать методы прежде всего на реальных сетках. 4. Классификация итерационных методов. Итерационные методы характеризуются структурой итерационной схемы, энергетическим пространством Но, в котором исследуется сходимость метода, типом итерационного метода, условием окончания процесса итераций, а также алгоритмом реализации одного итерационного шага. Мы будем рассматривать только двухслойные и трехслойные итерационные схемы, явные и неявные, для которых условием окончания процесса итераций будет условие ()у„— и()р(а))у,— и(р, з > О. В общей теории итерационных методов рассматриваются методы двух типов: использующие априорную информацию об операторах итерационной схемы и ие использующие (методы вариационного тапа).
В первом случае итерационные параметры т„для схемы (6) и ты а~ для схемы (7), (8) выбираются из условия минимума либо нормы разрешающего оператора (оператора, связывающего начальное и конечное приближения), либо нормы оператора перехода от итерации к итерации. При этом итерационные параметры выбираются так, чтобы обеспечить наивысшую скорость сходимости при самом плохом начальном приближении. В методах этого типа качество начального приближения не используется. В методах вариационного типа итерационные параметры выбираются из условия минимума некоторых функционалов, связанных с исходным уравнением. Например, в качестве функционала берется энергетическая норма погрешности й-й итерации. В этом случае итерационные параметры зависят от предыдущих итерационных приближений и обладают свойством учитывать качество начального приближения.
В общей теории итерационных методов мы отказываемся- от изучения конкретной структуры операторов итерационной схемы †теор использует минимум информации общего функционального характера относительно операторов. Зго позволяет достичь главной цели †указа общие принципы конструирования оптимальных итерационных методов в зависимости от 263 характера и вида априорной информации о задаче, а также от тех требований, которые предъявляются к способу решения этой задачи. Эти дополнительные требования могут, например, состоять в том, что нужно построить метод оптимальный ие на одной задаче, а на серии задач с одним и тем же оператором А, но с различными правыми частями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
