Градиентные методы для решения СЛАУ

}

//приближение ответа

vector<double> nextApp(vector<double> prev, double len, vector<double> dir) {

vector<double> ans = prev;

for(int i = 0; i < prev.sz; i++) {

ans[i] += dir[i] * len;

}

return ans;

}

 

 

 

//вычисление направление движения

vector<double> direction(vector<double> dir, vector<double> prev, vector<double> now) {

double a = inner_prod(prev, prev), b = inner_prod(now, now);

for(int i = 0; i < dir.sz; i++) {

dir[i] *= (b / a);

dir[i] -= now[i];

}

return dir;

}

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

double length(vector<double> dir,vector<double> grad,vector<vector<double> > A) {

double a = 0;

vector<double> B(dir.sz, 0);

for(int i = 0; i < grad.sz; i++) {

a += grad[i] * dir[i];

}

 

for(int i = 0; i < dir.sz; i++) {

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

B[i] += dir[j] * A[j][i];

}

}

return a / inner_prod(B, dir);

}

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

void ConGrad(vector<vector<double> > A, vector<double> B, vector<double> &X) {

vector<double> gP = B, d(B.sz, 0), gN = B, c;

double s;

while(conv(gN) > EPS) {

gN = grad(A, B, X);

if(conv(gN) < EPS) break;

d = direction(d, gP, gN);

s = length(d, gN, A);

X = nextApp(X, s, d);

gP = gN;

}

}

 

 

Сравнение методов

Рассмотрим недостатки и преимущества каждого из рассмотренных  методов.

Метод покоординатного спуска

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

• Простота реализации.
• Хорошо работает на гладких сепарабельных функциях и особенно на квадратичных, линии уровня которых похожи на концентрические круги
• Возможность использования простых функций для одномерной оптимизации

Недостатки:

• При движении вдоль «оврага» скорость сходи мости значительно снижается.
• При попадании в локальный минимум невозможен дальнейший поиск глобального минимума.

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

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

• Простота реализации.
• Высокая скорость работы
• Не требует явного вычисления производных

Недостатки:

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

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

	Метод покоординатного  спуска	Метод сопряженных градиентов
2	1111	2
5	8218	5
20	3432	21
50	6630	64
75	5235	102

 

 

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

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

#include <vector>

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <ctime>

#include <cmath>

using 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) {

double ans = 0;

for(int i = 0; i < a.sz; i++) {

ans += a[i] * b[i];

}

return ans;

}

//вычисление градиента

vector<double> grad(vector<vector<double> > A, vector<double> B, vector<double> X) {

vector<double> ans(B.sz, 0);

for(int i = 0; i < X.sz; i++) {

for(int j = 0; j < X.sz; j++) {

ans[i] += A[j][i] * X[j];

}

}

 

for(int i = 0; i < ans.sz; i++) {

ans[i] = B[i] - ans[i];

}

return ans;

}

 

double conv(vector<double> g) {

return inner_prod(g, g);

}

//приближение ответа

vector<double> nextApp(vector<double> prev, double len, vector<double> dir) {

vector<double> ans = prev;

for(int i = 0; i < prev.sz; i++) {

ans[i] += dir[i] * len;

}

return ans;

}

 

 

 

//вычисление направление движения

vector<double> direction(vector<double> dir, vector<double> prev, vector<double> now) {

double a = inner_prod(prev, prev), b = inner_prod(now, now);

for(int i = 0; i < dir.sz; i++) {

dir[i] *= (b / a);

dir[i] -= now[i];

}

return dir;

}

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

double length(vector<double> dir,vector<double> grad,vector<vector<double> > A) {

double a = 0;

vector<double> B(dir.sz, 0);

for(int i = 0; i < grad.sz; i++) {

a += grad[i] * dir[i];

}

 

for(int i = 0; i < dir.sz; i++) {

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

B[i] += dir[j] * A[j][i];

}

}

return a / inner_prod(B, dir);

}

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

void ConGrad(vector<vector<double> > A, vector<double> B, vector<double> &X) {

vector<double> gP = B, d(B.sz, 0), gN = B, c;

double s;

while(conv(gN) > EPS) {

gN = grad(A, B, X);

if(conv(gN) < EPS) break;

d = direction(d, gP, gN);

s = length(d, gN, A);

X = nextApp(X, s, d);

gP = gN;

}

}

int main() {

int n;

cin >> n;

vector<vector<double> > A(n);

vector<double> B(n), X(n);

for(int i = 0; i < n; i++ ){

for(int j = 0; j < n; j++) {

cin >> A[i][j];

}

}

for(int i = 0; i < n; i++) {

cin >> B[i];

}

ConGrad(A, B, X);

for(int i = 0; i < n; i++) {

printf("%.4lf\n", X[i]);

}

return 0;

}

 

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

 

Заключение

В настоящее время  теория экстремальных задач обогатилась  фундаментальными результатами, появились ее новые разделы. В любой практической оптимизационной задаче существует много совпадающих этапов. Наиболее важным этапом является моделирование рассматриваемой физической ситуации с целью получения математической функции, которую необходимо минимизировать, а также определения ограничений, если таковые существуют. Затем следует выбрать подходящую процедуру для осуществления минимизации. Эта процедура должна быть реализована на практике, что во многих реальных случаях вынуждает использовать ЭВМ для выполнения большого объема вычислений. Не случайно, что многие важные методы оптимизации были разработаны в течение трех последних десятилетий, в период появления цифровых ЭВМ, и эти методы являются машинными. Трудно считать их сколько-нибудь практически значимыми без большой скорости и эффективности вычислительных машин, имеющихся в нашем распоряжении. На многих универсальных ЭВМ имеются пакеты программ оптимизации, реализующие эти методы. Они могут оказаться весьма эффективными и позволят решить широкий круг задач.

В данной курсовой работе был описан алгоритм минимизации  функции нескольких переменных методами сопряженных градиентов и покоординатного спуска, было проведено сравнение их скорости работы и выделены основные достоинства и недостатки. Так же в работе был составлен алгоритм моделирования, на основе которого была написана программа для проведения исследований градиентным методом.

 

Список литературы

1. Пантелеев А.А. Методы оптимизации в примерах и задачах. – М.: Высшая школа
2. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат
3. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ
4. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высшая школа
5. А.А.Самарский, А.В.Гулин.  Численные методы. М.: «Наука»
6. Н.Н.Калиткин.  Численные методы. М.: «Наука»
7. Nocedal J., Wright S.J.   Numerical Optimization ,Springer
8. Н.Н.Моисеев, Ю.П.Иванилов, Е.М.Столярова "Методы оптимизации", М. Наука