2.2. Метод минимальных поправок

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

, (8)

Запишем этот метод в виде

. (9)

Вектор _k =B^1r_k называется поправкой на (k+1)-й итерации. Она удовлетворяет тому же уравнению, что и погрешность z_k=x_kx неявного метода, т. е.

уравнению

. (10)

Будем предполагать, что B=B^T>0. Методом минимальных поправок называется неявный итерационный метод (8), в котором параметр _k+l выбирается из условия минимума нормы ||_k+1||_B=(B_k+1,_k+1)^1/2 при заданном векторе _k. В случае B=Е метод минимальных поправок совпадает с методом минимальных невязок.

Найдем выражение для итерационного параметра _k+l. Перепишем (10) в виде

и вычислим

.

Отсюда следует, что минимум этого выражения достигается при

. (11)

Для реализации метода минимальных поправок требуется на каждой итерации решить две системы уравнений B_k= r_k и Bv_k=A_k, откуда найдем вектор v_k = B^1 А_k (воспользуемся формулой (9)) .

Скорость сходимости метода минимальных поправок определя­ется границами спектра обобщенной задачи на собственные значения

. (12)

2.3. Метод скорейшего спуска

Рассмотрим явный метод (2) и выберем итерационный параметр _k+l из условия минимума ||z_k+1||_A при заданном векторе z_k, где z_k+1=x_k+1x. Поскольку погрешность z_k удовлетворяет уравнению

, то

.

Следовательно, это выражение достигает минимума, если

.

Величина z_k=x_kx здесь неизвестна (так как неизвестно точное решение х), поэтому надо учесть, что Az_k=r_k=Ax_kf, и вычислять _k+l по формуле

. (13)

2.4. Метод сопряженных градиентов

Пусть A - матрица системы . Рассмотрим следующий класс неявных двухшаговых итерационных методов:

. (14)

Здесь , _k+l, _k+l - итерационные параметры, которые будут определены далее. Начальное приближение x₀ будем задавать произвольно, а вектор x₁ вычислять по одношаговой формуле, которая получается из (14) при k=0 и _l=1,

. (15)

Если параметры _k+l, _k+l найдены, то новое приближение x_k+l выражается через два предыдущих значения х_k и x_k1 по формуле

. (16)

Для погрешности z_k=x_kx из (16) получаем уравнения

.

Введем, как и ранее, вспомогательную функцию v_k=A^1/2z_k, для которой ||v_k||=||z_k||_A. Функция v_k удовлетворяет уравнениям

. (17)

где C=A^1/2B^1A^1/2. Будем считать, что A и B - симметричные положительно определенные матрицы, удовлетворяющие неравенствам

. (18)

Исключая последовательно векторы v_l, v₂, , v_kl из уравнений (17) находим, что

, (19)

где P_k(C) - многочлен степени k от оператора С, удовлетворяющий условию P_k(0)=E.

Поставим задачу выбрать итерационные параметры _k, _k так, чтобы при любом n=1, 2, ... была бы минимальной ||v_n||=||z_n||_A.

Параметр ₁ находится из условия минимума ||v₁|| при заданном векторе v₀. Так же, как и в методе скорейшего спуска, получаем

. (20)

Отметим, что при таком выборе ₁ выполняется равенство (Cv₁,v₀)=0, т. е. векторы v₁ и v₀ ортогональны в смысле скалярного произведения

.

Далее, рассмотрим погрешность (19) и запишем многочлен P_k(C) в виде

, (21)

где a_i^(k) - числовые коэффициенты, определяемые параметрами _i, _i, i=l, 2, ..., k. Тогда

. (22)

Найдем условия, которым должны удовлетворять коэффициенты a_i^(k), минимизирующие ||v_n||². Из (22) получаем

, (23)

т. е. ||v_n||² является многочленом второй степени по переменным a₁⁽ⁿ⁾, ..., a_n⁽ⁿ⁾. Приравнивая к нулю частные производные ||v_n||²/a_j⁽ⁿ⁾, j=1, 2, ..., n, приходим к системе уравнений

, (24)

решение которой a_i⁽ⁿ⁾, i=1, 2, ..., n и обращает в минимум ||v_n||².