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

Рассмотрим итерационные методы вида

(2)

в которых параметры выбираются из условия минимума погрешности при заданной погрешности . Здесь D – заданная симметричная положительно определенная матрица, . В зависимости от выбора матриц D и B получим различные итерационные методы.

Метод минимальных невязок. Рассмотрим систему (1) с симметричной положительно определенной матрицей А. Обозначим через

(3)
невязку, которая получается при подстановке приближенного значения x_k, полученного на k-й итерации, в уравнение (1). Заметим, что погрешность

z_k = x_k - х и невязка r_k связаны равенством Az_k= r_k.

Рассмотрим явный итерационный метод

(4)

и перепишем его в виде

(5)

Методом минимальных невязок называется итерационный метод (4), в котором параметр выбирается из условия минимума при заданной норме . Получим явное выражение для итерационного параметра . Из (5) получаем

и, следовательно,

(6)

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

Возводя обе части уравнения (6) скалярно в квадрат, получим

(7)

Отсюда видно, что достигает минимума, если

(8)

Таким образом, в методе минимальных невязок переход от k-й итерации к (k+1)-й осуществляется следующим образом. По найденному значению х_к вычисляется вектор невязки и по формуле (8) находится параметр . Затем по формуле (5) досчитывается вектор .

Метод минимальных невязок (5), (8) сходится с той же скоростью, что и метод простой итерации с оптимальным параметром .

Теорема 1. Пусть А – симметричная положительно определенная матрица. Для погрешности метода минимальных невязок выполняется оценка

(9)

Где

, = (10)

Доказательство. Рассмотрим тождество (7). При заданном векторе r_k правая часть этого тождества достигает минимума, если выбрать согласно (8). При любом другом значении правая часть тождества (7) может только увеличиться. Поэтому, полагая в (7) где

(11)

получим неравенство

и, следовательно,

. (12)

Т.к. =р₀, поэтому при всех k справедливо неравенство

(13)

или, что то же самое, неравенство

.
Отсюда и следует оценка (9).
3. Метод скорейшего спуска. Рассмотрим явный метод (4) и выберем итерационный параметр из условия минимума при заданном векторе z_k, где z_k+1=x_k+l – х. Поскольку погрешность z_k удовлетворяет уравнению
имеем
.
Следовательно, будет минимальной, если положить
Так как величина z_k=x_k – х неизвестна (поскольку неизвестно точное решение x), надо учесть, что , и вычисление проводить по формуле
(23)
Так же, как и в теореме 1, доказывается, что метод скорейшего спуска сходится с той же скоростью, что и метод простой итерации с оптимальным параметром . Для погрешности метода скорейшего спуска справедлива оценка
(24)
где
Неявным методом скорейшего спуска называется метод (2), в котором параметр выбирается из условия минимума . Так как погрешность z_k = x_k –x удовлетворяет уравнению

Получим

,

или

.

Следовательно, будет минимальной, если положить

(25)

При этом для неявного метода скорейшего спуска справедлива оценка (24), где