Алгоритм

Перед выполнением первой итерации и полагаются равными нулю, а для вектора устанавливается значение

. Вычисление градиента

. Вычисление вектора направления

. Вычисление величины смещения по заданному направлению

. Вычисление нового приближения

Сходимость метода

Если все вычисления точные, и исходные данные точны то метод сходится к решению системы не более чем за итераций, где - размерность системы. Более тонкий анализ показывает, что число итераций не превышает , где - число различных собственных значений матрицы . На практике чаще всего используют следующий критерий останова: .

Критерий останова

Критерий останова одномерного поиска вдоль каждого из направлений записывается в виде:

.

Реализация

Применим метод сопряжённых градиентов для решения системы

,

где .помощью метода сопряжённых градиентов решение этой системы

получается за три итерации.double EPS = 1e-7;

// скалярное произведениеinner_prod (vector<double> a, vector<double> b) {ans = 0;(int i = 0; i < a.sz; i++) {+= a[i] * b[i];

}ans;

}

// вычисление градиента<double> grad (vector<vector<double> > A, vector<double> B, vector<double> X) {<double> ans (B.sz, 0);(int i = 0; i < X.sz; i++) {(int j = 0; j < X.sz; j++) {[i] += A[j] [i] * X[j];

}

}(int i = 0; i < ans.sz; i++) {[i] = B[i] - ans[i];

}ans;

}conv (vector<double> g) {inner_prod (g, g);

}

// приближение ответа<double> nextApp (vector<double> prev, double len, vector<double> dir) {<double> ans = prev;(int i = 0; i < prev.sz; i++) {[i] += dir[i] * len;

}ans;

}

вычисление направление движения<double> direction (vector<double> dir, vector<double> prev, vector<double> now) {a = inner_prod (prev, prev), b = inner_prod (now, now);(int i = 0; i < dir.sz; i++) {[i] *= (b / a);[i] -= now[i];