Сходимость итерационных методов

Сравнивая формулы (2.10) метода Якоби и (2.12) метода Зейделя, можно заметить, что если методы сходятся, то есть в некотором смысле , то они сходятся к решению исходных задач .

Пример 2.5. Рассмотрим еще одну систему алгебраических уравнений, несколько отличающуюся от приведенных в предыдущих примерах:

Точное решение этой системы x = 0,5, y = 1,5.

Для решения воспользуемся методом Зейделя. Как и ранее, представим уравнения в виде итерационной схемы

Результаты расчетов сведены в табл. 2.3. На рис. 2.3 отражен ход выполнения процедуры Зейделя.

Таблица 2.3

Результаты выполнения итерационной процедуры метода Зейделя

n	x(n)	y(n)
		0,0
	1,25
		4,5
	-1,0
		-4,5
	3,5
		13,5
	-5,5
		-22,5
	12,5
		49,5
	...

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

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

, (2.13)

где - итерационные параметры.

Y -20x + 5y = -2.5

X

-5 -4 -3 -2 -1 1 2 3 4 5

-1 4x + 2y = 5

-2

-3

-4

-5

Рис. 2.3. Отсутствия сходимости при использовании метода Зейделя

В случае, если не зависят от номера итерации, метод называется стационарным. В частности, для метода Якоби ; для метода Зейделя .

Если , метод называется явным; в случае - неявным. Примеры итерационных методов:

- явный стационарный метод простых итераций

;

- неявный стационарныйметод верхней релаксации

.

Введем пространство m - мерных векторов со скалярным произведением

и нормой

.

Определим матричное неравенство: квадратная матрица C > 0 тогда и только тогда, когда

.

Иначе это определение может быть записано следующим образом:

.

Чтобы определить величину d, рассмотрим два случая:

1. Пусть симметричная матрица С > 0, тогда согласно первоначальному определению квадратичная форма[11] (Сx,x) > 0. Но квадратичную форму можно привести к каноническому виду в главных осях:

,

где - собственные числа матрицы С; - главные координаты.

В силу С > 0 имеем , вследствие чего , и отсюда получаем

,

то есть в качестве d может быть взято наименьшее собственное значение матрицы С.

2. Если С - несимметричная матрица, поступают следующим образом для определения d:

,

.

В последнем соотношении индексы суммирования можно поменять местами:

Теперь очевидно, что . Поскольку , то и .

Построим матрицу :

,

но это означает, что построенная матрица является симметричной. Кроме того,

в силу предыдущих соотношений.

Это, в свою очередь, означает, что - наименьшее собственное значение матрицы . Следовательно,

,

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

Оценка

позволяет утверждать, что существует обратная матрица , так как в случае положительной определенности матрицы все ее главные (угловые) миноры положительны (критерий Cильвестра[12], [7]).

Для установления условий сходимости определим величину погрешности метода формулой , тогда из формулы (2.13) для стационарного итерационного метода можно получить

,

(2.14)

Теорема 2.4. Пусть А - симметричная положительно определенная матрица, A > 0; итерационные параметры удовлетворяют соотношению

.

Тогда стационарный итерационный метод сходится.

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

Построим числовую последовательность вида .

Из формулы (2.14) следует

Теперь можно подсчитать

Вследствие симметрии матрицы А имеем

Иначе говоря, . Отсюда получаем

.

В силу условия теоремы , откуда следует, что , то есть построенная последовательность является монотонно убывающей и, кроме того, в силу , ограничена снизу. Отсюда следует, что существует предел этой последовательности .

Из положительной определенности (B - 0,5 t A) > 0 следует существование константы d >0 такой, что имеет место

.

Теперь предыдущее соотношение может быть переписано в форме неравенства:

.

При n ® ¥ из последнего выражения получаем . Очевидно, что неравенство может выполняться лишь при условии, что .

С другой стороны, , причем существует в силу положительной определенности матрицы А по условию теоремы. Оценим норму погрешности:

.

Теперь становится очевидным, что вследствие имеет место , что и требовалось доказать.

Следствие 1. Пусть А - симметричная положительно определенная матрица. Тогда метод верхней релаксации

сходится при 0 < w < 2. В частности, метод Зейделя (w = 1) сходится.

В рассматриваемом случае, очевидно, .

.

Последнее соотношение справедливо в силу симметрии матрицы А:

.

Условие сходимости итерационного метода теоремы 2.4 принимает вид:

Очевидно, что последнее неравенство выполняется при условии .

Следствие 2. Пусть А - симметричная положительно определенная матрица с диагональным преобладанием, то есть имеет место

.

Тогда метод Якоби сходится.

Поскольку в рассматриваемом случае B = D, условие сходимости принимает вид неравенства

.

Из неравенств

,

следует

.

В силу симметричности и положительной определенности матрицы А имеем

.

Используя предположение следствия, запишем

.

Из двух последних неравенств получаем

,

что и требовалось доказать.