Лекция 10.

Итерационные методы решения СЛАУ. Методы решения уравнения Пуассона. Метод простых итераций.

Рассмотрим итерационный метод (т.е. метод последовательных приближений) решения системы линейных уравнений:

Будем считать, что решение задачи (1) существует и единственно.

Различные варианты метода простых итераций связаны с переходом от системы (1) к эквивалентной системе

Итерационный процесс строим следующим образом:

где xr(0) задано, k - номер приближения.

Условия сходимости метода последовательных приближений (3) форму-

лируются в следующих теоремах.

Теорема 1.

Для сходимости итераций (3) к решению системы (2) достаточно, чтобы в

Доказательство

При подстановке точного решения в (2) оно обращается в тождество:

xr* = P xr* + gr .

Вычитая его из уравнения (3) , (т.е. xr(k) = P xr(k−1) + gr), получим:

xr(k ) − xr* = P (xr(k−1) − xr* ) .

Здесь xr(k ) − xr* - погрешность - го приближения.

88

Оценивая погрешность по какой k - либо норме (с которой согласована норма матрицы), получим:

Ясно, что при q <1 lim xr(k ) = xr* .

k→∞

Теорема 2.(без доказательства)

Для сходимости итераций (3) (т.е. xr(k ) = P xr(k −1) + gr ) к решению системы

(2) (т.е. xr = P xr + g ) необходимо и достаточно, чтобы все собственные значе-

ния матрицы P по абсолютной величине были меньше единицы.

Опираясь на формулу (4) , т.е. xr(k ) − xr* ≤ qk xr(0) − xr* , можно получить ап-

риорную оценку числа приближений

xr(k ) − xr* ≤ qk xr(0) − xr* ≤ ε .

Разрешая последнее неравенство относительно k , получим:

(Квадратные скобки означают ближайшее сверху целое число от того, которое заключено в скобки).

Этой оценкой можно воспользоваться, если мажорировать как-то

xr(0) − xr* .

Упражнение:

Показать, что в условиях Теоремы 1 справедлива оценка:

Подумаем теперь, зачем нужны итерационные методы, если мы умеем вычислять решение пользуясь, например, какой - либо модификацией метода Гаусса.

89

Вопрос становиться ясным, если оценить эффективность различных подходов с точки зрения вычислительных затрат.

Метод Гаусса (в простейшей интерпретации), при n >1 требует выполне-

грешность достигается при k < n3 , то метод итераций становиться предпочти-

тельней.

В задачах, с которыми практически приходится иметь дело, часто k < n . Кроме того, методы итераций могут оказаться предпочтительней с точки зрения устойчивости вычислений, т.е. в смысле влияния вычислительных по-

грешностей на результаты расчетов.

Примеры итерационных процессов.

1) Метод Якоби.

Запишем каждое уравнение системы Axr = f в виде, разрешенном относи-

тельно неизвестного с коэффициентом на главной диагонали матрицы A :

m =1,2,..., n .

Таким образом, мы переписали (1) ( Axr = f ) в виде (2) ( x = P x + g ), с мат-

рицей

Если ввести в рассмотрение диагональную матрицу:

90

Пусть теперь дано двумерное уравнение Пуассона в прямоугольнике

U xx +U yy = − f , U Г =U0

Выбирая для простоты сетку, равномерную и одинаковую по x и y , полу-

чим пятиточечный шаблон Рис.10.1):

Рис. 10.1. Пятиточечный шаблон “Крест”

Итерационный процесс Якоби здесь реализуется следующим образом:

1)Значения функции на границе заданы, известны.

2)Зададим некоторое начальное приближение функции во внутренних узлах (близость этого значения к решению часто бывает очень важна).

3)Вычисляем U22(1) по окружающим точкам нулевого приближения: U21 и

U12 на границе, а также U23(0) и U32(0) .

92

Ясно, что при вычислении U23(1) удобно воспользоваться уже известным значением U22(1) с первого шага итерации. В этом случае погрешность преды-

дущей итерации последовательно оттесняется слева направо и снизу вверх.

Такая модификация итерационного процесса называется методом Зейделя. Формулы метода Зейделя имеют вид:

Если представить матрицу A в виде суммы A = A− + D + A+ ( A−, D, A+ - ниж-

няя треугольная, верхняя треугольная и диагональная матрицы с элементами матрицы A ), то методу Зейделя соответствует матрица:

P = −(A − A+ )−1 A+ = −(A− + D)−1 A+ (для метода Якоби P = −D−1(A − D) ). Можно доказать, что метод Зейделя гарантированно сходится, если

-выполнено условие диагонального преобладания матрицы A или

-матрица A является симметричной ( A = A* ) и положительно определен-

ной.

93

Условия сходимости: A = A* > 0 и (как в методе Зейделя). Скорость сходимости зависит от параметра ω . Существуют теоретические

оценки для ω и скорости сходимости, но их применение требует знания спек-

тра оператора D−1( A− + A+ ) , который не всегда легко найти.

Поэтому на практике параметр ω подбирают так, чтобы минимизировать число итераций. Это особенно удобно, если решается класс однотипных задач.

Для примера рассмотрим применение метода верхней релаксации в одной сложной численной схеме (нелинейные уравнения Навье - Стокса), где на каждом шаге по времени необходимо решать эллиптическое уравнение Пуассона

U xx +U yy = − f , U Г =U 0

с граничными условиями условиями первого рода. Запишем разностную схему в виде:

U m−1,n +U m+1,n − 4U m,n +U m,n−1 +U m,n+1 = − fmn h2 , U Г =U 0

В данном случае используются цилиндрические координаты и неравномерная сетка, но это приводит лишь к появлению зависящих от индекса m и n прогоночных коэффициентов.

Скорость сходимости процесса сильно зависит от нулевого начального приближения, за которое принято значение U на прошлом шаге по времени.

Сначала, как и в методе Зейделя, выполняются прогонки по строкам от

n = 2 до n = N −1 .

Вторая часть итерации состоит в выполнении прогонок по столбцам.

96

U =U mn (k ) −U mn (k −1) .

На первых шагах итераций берется ω = 0.5 ÷ 0.7,(ω <1) , затем, когда насту-

пает условие δ <1 , значение ω меняется на ω =1 , а когда δ < 0.1 или δ < 0.01 , то можно взять ω =1.5 ÷1.7 , и итерации быстро сходятся до δ < ε =10−5 .

97