Итерационные методы решения СЛАУ вариационного типа
Метод минимальных невязок
Рассмотрим систему
, (7.1)
с невырожденной симметричной положительно определенной матрицей 
и одношаговый итерационный метод, записанный в канонической форме
, (7.2)
в котором параметры 
выбираются из условия минимума погрешности 
при заданной погрешности 
. Здесь 
заданная симметричная положительно-определенная матрица, 
. В зависимости от выбора матриц 
и 
получим различные итерационные методы.
Обозначим через
(7.3)
невязку, которая получается при подстановке приближенного значения 
, полученного в 
-й итерации, в уравнение (7.1). Заметим, что погрешность 
и невязка 
связаны между собой равенством (доказать) 
.
Рассмотри явный итерационный метод
(7.4)
и перепишем его в виде
. (7.5)
Методом минимальных невязок называется итерационный метод (7.4), в котором параметр 
выбирается из условия минимума 
при заданной норме 
.
Получим явное выражение для итерационного параметра . Из (7.5) получаем
,
а, следовательно, вычитая вектор 
из обеих частей последнего равенства, имеем
. (7.6)
Возводя обе части уравнения (7.6) скалярно в квадрат, получим
. (7.7)
Отсюда видно, что достигает минимума, если
. (7.8)
Таким образом, в методе минимальных невязок переход от -й итерации к 
-й осуществляется следующим образом. По найденному значению вычисляется вектор невязки и по формуле (7.8) находится параметр . Затем по формуле (7.5) досчитывается вектор 
.
Метод минимальных невязок (7.5), (7.8) сходится с той же скоростью, что и метод простой итерации с оптимальным параметром 
.
Теорема 1. Пусть 
симметричная положительно определенная матрица. Для погрешности метода минимальных невязок выполняется оценка
, 
(7.9)
где
, 
. (7.10)
Без доказательства.
Метод минимальных поправок.
Запишем неявный итерационный метод (7.2) в виде
, (7.11)
где невязка. Вектор
называется поправкой на -й итерации. Поправка 
удовлетворяет тому же уравнению, что и погрешность неявного метода (доказать):
. (7.12)
Будем полагать, что 
симметричная положительно определенная матрица. Методом минимальных поправок называется неявный итерационный метод (7.2), в котором параметр выбирается из условия минимума нормы 
при заданном векторе . В случае 
метод минимальных поправок совпадает с методом минимальных невязок.
Найдем выражение для итерационного параметра . Перепишем (7.12) в виде
и вычислим с учетом того, что 
(доказать):
,
Отсюда следует, что 
будет минимальной, если положить
. (7.13)
Для минимизации метода минимальных поправок требуется на каждой итерации решить систему уравнений 
, откуда найдем поправку , и решить систему уравнений 
, откуда найдем вектор 
, необходимый для вычисления параметра .
Скорость сходимости метода минимальных поправок определяется границами спектра обобщенной задачи на собственные значения
. (7.14)
Теорема 2. Пусть , симметричные положительно определенные матрицы и 
, 
наименьшее и наибольшее собственные значения задачи (7.14). Для погрешности метода минимальных поправок выполняется оценка
, 
, (7.15)
где
, 
.
Без доказательства.
Метод скорейшего спуска.
Явным методом скорейшего спуска называется метод (7.4), где итерационный параметр выбирается из условия минимума 
при заданном векторе 
. Поскольку погрешность удовлетворяет уравнению
,
имеем, с учетом того что 
(доказать самостоятельно):
.
Следовательно, 
будет минимальной, если положить
.
Так как величина неизвестна (поскольку неизвестно решение 
), надо учесть, что 
, и вычисление 
проводить по формуле
. (7.16)
Явный метод скорейшего спуска сходится с той же скоростью, что и метод простой итерации. Для погрешности данного метода справедлива оценка
, 
, (7.17)
где
, .
Неявным методом скорейшего спуска называется метод (7.2), в котором параметр 
выбирается из условия минимума 
. Так как погрешность удовлетворяет уравнению (доказать)
,
получим
,
или, учитывая, что 
, получим
.
Следовательно, будет минимальной, если положить
. (7.18)
Для неявного метода скорейшего спуска справедлива оценка (7.17), где
, .
