Теорема Самарского

Теорема Самарского устанавливает условия сходимости рассмотренных выше стационарных явных и неявных методов простой итерации (Ричардсона, Якоби, Зейделя, релаксации) в случае самосопряженной (симметричной) положительно определенной матрицы : . Метод простой итерации рассматривается в виде

, (40)

где - некоторая новая матрица. Если легко обращаемая матрица, то это явный метод простой итерации (Ричардсона с параметром, Якоби, Якоби с параметром), в противном случае - это неявный метод (Зейделя, релаксации (Зейделя с параметром)).

Теорема Самарского. Для самосопряженной, положительно определенной матрицы СЛАУ условие

, (41)

есть достаточное условие для сходимости процесса итераций (40) при любом начальном приближении. Если и – самосопряженная матрица, то это и необходимое условие.

Докажем сначала Лемму.

Лемма. Если - положительно определeнная матрица, то существует такое положительное число (), такое что для любого выполняется:

Действительно

Т.о., для симметричной, положительно определенной матрицы . Лемма доказана.

Доказательство достаточности Теоремы.

Пусть - погрешность на -ой итерации. Из (39) и следует

, ,

Обозначим . Тогда ,

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

Обозначим функционал , в силу .

Таким образом, установлена связь между функционалами на соседних итерациях. Последовательность функционалов положительная и убывающая

в силу - по условию теоремы. Таким образом, это ограниченная бесконечная последовательность и она сходится.

В силу Леммы и условия Теоремы существует число , такое что

Отсюда и при .

По тексту и

Поэтому из и следует, что и при .

Достаточность доказана.

Пояснения. Что означает - положительно определенная матрица? Или ? Это значит, что для любого вектора выполняется

, ,

,

В частности, если

Ранее определили подчиненную норму и евклидовую норму матрицы как , .

Найдем .

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

,

Величина . Равенство нулю достигается на векторе и тогда . То есть,

Итак, достаточное условие сходимости для метода Ричардсона с параметром

, ,

есть

Или в обозначениях параметра , который связан с как

где

Достаточные условия сходимости

(41)

Ранее нами найден оптимальный параметр сходимости для случая

,

который лежит в области (41).

В методе Якоби и . Здесь и условие теоремы выглядит как

,

Можно показать [3], что последнее неравенство следует из условий диагонального преобладания матрицы

(42)

Таким образом, условие (42) при – достаточное условие сходимости метода Якоби.

В методе Релаксации . Условие Теоремы ввиду симметричности матрицы и превращается в

; (43)

Из леммы в п. 1.6 следует положительность диагональных элементов , из (43) следует и условие сходимости метода Релаксации

(44)

Значение соответствует методу Зейделя. Таким образом, для самосопряженных, положительно определенных матриц метод Зейделя всегда сходится. Дополнительно для блочно-трехдиагональных матриц известно значение оптимального параметра для сходимости

, ,

где - максимальное собственное число матрицы перехода Якоби. Таким образом, оптимальный параметр лежит в верхней части области сходимости (44)

и оптимальный метод для таких матриц известен под названием метода последовательной верхней релаксации [6-8]. Параметр также лежит в верхней части области сходимости .