Итерационные методы решения СЛАУ
6.3 Необходимое и достаточное условие сходимости
стационарных итерационных методов
Рассмотрим стационарные итерационные методы
, (6.25)
в которых матрица 
и числовой параметр 
не зависят от номера итерации 
.
Погрешность итерационного метода (6.25) 
, где 
точное решение системы (6.16), удовлетворяет уравнению (доказать)
, 
, (6.26)
которое отличается от уравнения (6.25) лишь тем, что является однородным.
Сходимость итерационного метода (6.25) означает, что 
в некоторой норме при 
. Переписывая уравнение (6.26) в относительно 
форме
, (6.27)
где (доказать)
, (6.28)
видим, что свойство сходимости итерационного метода целиком определяется матрицей 
, которая называется матрицей перехода от -й к 
-й итерации.
При исследовании сходимости будем рассматривать векторы 
и 
как элементы 
-мерного линейного пространства 
, в котором введена норма 
вектора . Нормой матрицы 
, подчиненной данной норме вектора , называется число 
, для которого
Норму вектора в можно ввести различным образом, например
.
Подчиненная ей норма матрицы определяется следующим образом:
.
Докажем это утверждение. Для любого вектора 
можно записать
,
т.е.
. (6.29)
Теорема 2. Итерационный метод (6.25) сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы по модулю меньше единицы. При этом справедлива оценка
, 
, (6.30)
где 
. Без доказательства.
Оценки скорости сходимости стационарных итерационных методов
При практическом использовании итерационных методов важен не только сам факт сходимости, но и скорость, с которой приближенное решение сходится к точному. Так как при численном решении всегда осуществляется конечное число итераций, необходимо знать, во сколько раз уменьшается начальная погрешность после проведения заданного числа итераций. В этой связи проведем анализ погрешности итерационного метода.
Оценку (6.30) можно переписать в виде
, , (6.31)
Если выполняется оценка для погрешности вида (6.31), то говорят, что метод сходится со скоростью геометрической прогрессии со знаменателем 
.
Используя оценку (6.31), можно определить число итераций, достаточное для того, чтобы начальная погрешность уменьшилась в заданное число раз. Действительно, зададим произвольное 
и потребуем, чтобы 
, т.е. чтобы
. (6.32)
Тогда из (6.31) получим, что
,
т.е. после проведения 
итераций начальная погрешность снизилась в 
раз.
Выражение 
называется скоростью сходимости итерационного метода. Скорость сходимости целиком определяется свойствами матрицы перехода и не зависит ни от номера итерации , ни от выбора начального приближения 
, ни от задаваемой точности 
. Качество различных итерационных методов сравнивают обычно по их скорости сходимости: чем выше скорость сходимости, тем лучше метод.
Теорема 3. Пусть 
и 
соответственно минимальное и максимальное собственные значения матрицы . Если 
, то для метода простой итерации
(6.33)
при 
справедлива оценка
, 
(6.34)
где 
, 
.
В приложениях часто встречаются задачи с плохо обусловленной матрицей , когда отношение 
велико или 
мало. В этом случае число 
близко к единице и метод простой итерации сходится медленно. Оценим число итераций 
, которое требуется в случае малых 
для уменьшения начальной погрешности в более чем 
раз, т.е. для получения оценки
, где 
Из условия получаем, что 
, где
,
и при малых имеем
. (6.35)
Таким образом, метод простой итерации (6.33) в случае малых является медленно сходящимся методом. Ускорить сходимость итерационных методов можно двумя способами: во-первых, за счет применения неявных итерационных методов, когда 
, и, во-вторых, оставаясь в классе явных методов, можно выбрать 
зависящим от номера итерации и таким, чтобы уменьшить общее число итераций. Применяется и комбинация этих двух способов, т.е. используются неявные итерационные методы с переменными итерационными параметрами.
Оценим скорость сходимости в случае симметричных матриц и для неявного стационарного итерационного метода (6.25).
Будем рассматривать решение 
и последовательные приближения 
как элементы конечномерного линейного пространства , а матрицы как операторы, действующие в пространстве , где введены скалярное произведение 
и норма 
. Для двух симметричных матриц и неравенство 
означает, что 
для всех 
. В случае симметричной положительно определенной матрицы 
будем обозначать 
.
Теорема 4. Пусть и 
симметричные положительно определенные матрицы, для которых справедливы неравенства
, (6.36)
где 
положительные постоянные, 
. При
(6.37)
итерационный метод (6.25) сходится и для погрешности справедливы оценки
, , (6.38)
, , (6.39)
где 
, 
и 
, 
.
Без доказательства.
Сделаем необходимые замечания и приведем следствия из этой теоремы.
Рассмотрим обобщенную задачу на собственные значения
. (6.40)
Если для матриц и выполнены неравенства (6.36), то из (6.40) для любого собственного вектора получим неравенства
.
Отсюда следует, что 
, следовательно
, 
, (6.41)
где 
и 
минимальное и максимальное собственные числа матрица 
. Таким образом, наиболее точными константами, с которыми выполняются неравенства (6.36), являются константы
, 
.
В этом случае параметр
называется оптимальным итерационным параметром, так как он максимизирует величину и минимизирует величину :
, при 
на множестве всех положительных 
, удовлетворяющих условиям (6.41).
Использование неявных итерационных методов (6.25) объясняется тем, что при соответствующем выборе матрицы отношение 
для обобщенной задачи на собственные значения (6.40) может быть больше, чем отношение 
.
