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

Преимущества:

· Простота реализации.

· Высокая скорость работы

· Не требует явного вычисления производных

Недостатки:

· При попадании в локальный минимум невозможен дальнейший поиск глобального минимума.

Для сравнения скорости работы этих методов была выбрана задача поиска решения системы .Ниже представлено количество операций для решения системы заданного размера для каждого из методов.

Решение задачи

Для решения нашей задачи выберем метод сопряженных градиентов ввиду простоты его реализации и высокой скорости работы.

#include <vector>

#include <cstdio>

#include <iostream>

#include <algorith>

#include <ctime>

#include <cmath>namespace std;

#define sz size()

#define all(x) (x).begin(), (x).end()

#define pb push_back

#define mp make_pair

#define X first

#define Y second

#define sqr(x) ((x)*(x))

const double EPS = 1e-7;

// скалярное произведение

double 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];

}dir;

}

// длина шага в заданном направлении

double length (vector<double> dir, vector<double> grad, vector<vector<double> > A) {a = 0;<double> B (dir.sz, 0);(int i = 0; i < grad.sz; i++) {+= grad[i] * dir[i];

}(int i = 0; i < dir.sz; i++) {(int j = 0; j < A[i].sz; j++) {[i] += dir[j] * A[j] [i];

}

}a / inner_prod (B, dir);

}

// метод сопряженных градиентовConGrad (vector<vector<double> > A, vector<double> B, vector<double> &X) {<double> gP = B, d (B.sz, 0), gN = B, c;s;(conv(gN) > EPS) {= grad (A, B, X);(conv(gN) < EPS) break;= direction (d, gP, gN);= length (d, gN, A);= nextApp (X, s, d);= gN;

}

}main() {n;>> n;<vector<double> > A(n);<double> B(n), X(n);(int i = 0; i < n; i++) {(int j = 0; j < n; j++) {>> A[i] [j];

}

}(int i = 0; i < n; i++) {>> B[i];

}(A, B, X);(int i = 0; i < n; i++) {(«%.4lf\n», X[i]);

}0;

}

Получили следующий ответ: , он и является ответом на поставленную задачу.