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

Министерство образования, науки, молодежи и спорта Украины

Сумской государственный университет

 

 

 

 

 

Курсовая работа

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

 

 

 

 

 

Выполнил:

студент группы ПМ-01

                                                                                                             Морквин Я.В.

                                                                                                                   Проверил:

                                                                                                                 Чибиряк Я.І.

 

 

 

 

 

сумы – 2012 

 

 

 

 

 

 

 

 

Введение

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

Часть этих методов предназначена  для увеличения эффективности научного эксперимента на всех стадиях разработки, исследования, проектирования и эксплуатации производств. Единство теории и практики эксперимента совместно с вычислительной техникой образуют комплекс автоматизированного эксперимента, предназначенный для повышения производительности научного труда.

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

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

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

где D_λ – это оптическая плотность раствора при длине волны света λ, с – молярная концентрация вещества в растворе, l – толщина слоя раствора, через который проходит свет, ε – молярный коэффициент светопоглощения (молярный коэффициент экстинкции), зависящий от длины волны падающего света.

Если в растворе поглощает  несколько веществ, то оптические плотности  веществ складываются (оптическая плотность  – аддитивное свойство). Обозначим  через D_ij оптическую плотность, которую имеет j-й компонент раствора при длине световой волны λ_i (ε_ij – молярный коэффициент светопоглощения j-го компонента раствора при длине световой волны λ_i)

Тогда общая оптическая плотность  раствора при длине световой волны  λ_i (D_i) будет равна сумме по всем M компонентам:

 

Если измерить оптическую плотность раствора на M различных длинах волн, то можно  получить систему из M линейных уравнений  с M неизвестными концентрациями и использовать ее для их расчета.

Матрицу коэффициентов  образуют значения молярной экстинкции каждого из компонента на всех длинах волн, а вектор-столбец свободных членов – отношения общего светопоглощения растовров при различных длинах волн к длине кюветы:

                 

Другой пример – масс-спектрометрическое определение  состава смеси газов по интенсивности пиков  Метод масс-спектроскопии основан на ударной ионизации молекул вещества и наблюдению за отклонением потока ионизированных частиц в электрическом поле. Ионизированные частицы отклоняются в соответствии с величиной  где m - масса иона, e– его заряд. Для каждого вещества состав и соотношение продуктов ионизации индивидуален (так же как и оптический спектр вещества). Абсолютная высота i-го пика с определенным соотношением  (интенсивность) определяется парциальным давлением газа в смеси.

S_i – есть интенсивность i-го пика в масс-спектре вещества с парциальным давлением, равным единице, этот параметр называют коэффициентом чувствительности. Для различных веществ набор пиков масс-спектра и их интенсивность  являются индивидуальными.

В результате экспериментов получены следующие данные:

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

 

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

Алгоритм

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

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

Зафиксируем теперь все  координаты, кроме  , и рассмотрим функцию этой переменной  . Снова решая одномерную задачу оптимизации, находим ее наименьшее значение при  , т.е. в точке  .

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

Данный метод легко проиллюстрировать геометрически для случая функции двух переменных  , описывающей некоторую поверхность в трехмерном пространстве. На рисунке нанесены линии уровня этой поверхности. Процесс оптимизации в этом случае проходит следующим образом.

Точка   описывает начальное приближение. Проводя спуск по координате  , попадем в точку  . Далее, двигаясь параллельно оси ординат, придем в точку   и т.д.

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

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

Метод координатного спуска является простым в реализации методом оптимизации. Главным недостатком метода является его ограниченная применимость.

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

Критерии остановки  процесса приближенного нахождения минимума могут быть основаны на различных соображениях. Некоторые из них:

 

 

Здесь   - значение, полученное после -го шага оптимизации,   - наперед заданное положительное число.

Реализация

Для одномерной оптимизации  будем использовать метод дихотомии. Поиск минимума функции одной переменной будем производить на отрезке . За условие останова примем близость концов отрезка: , где и - правая и левая границы отрезка соответственно.

Применим метод покоординатного спуска для решения системы , где .

C помощью метода покоординатного спуска решение этой системы    

  получается за четыре итерации.

 

const double EPS = 1e-7;

 

double f(double X, vector<double> values, int pos) {

values[pos] = X;

return sqr(fabs(13 * values[0] + 14 * values[1] - 11)) + sqr(fabs(14* values[0] - 13* values[1] - 15)) + sqr(fabs(15 * values[2] - 19));

}

// дихотомия для одномерной оптимизации

void binarySearch(vector<double> &values, int now) {

double l = -(1<<30), r = (1<<30), m1, m2;

for(;fabs(r - l) > EPS;) {

m1 = l + (r - l) / 3;

m2 = r - (r - l) / 3;

if(f(m1, values, now) - f(m2, values, now) > EPS) {

l = m1; 

} else {

r = m2;

}

}

values[now] = m1;

}

//покоординатный спуск

void Coords(vector<double> &answer) {

double prevValue = f(answer[0], answer, 0) + 100, nextValue = f(answer[0], answer, 0);

int i = 0;

while(fabs(nextValue - prevValue) > EPS) {

prevValue = nextValue;

binarySearch(answer, i);

i = (i + 1) % answer.sz;

nextValue = f(answer[0], answer, 0);

}

}

Пакетная реализация

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

Метод сопряжённых градиентов — итерационный метод для безусловной оптимизации в многомерном пространстве. Основным достоинством метода является то, что он решает квадратичную задачу оптимизации за конечное число шагов.

Определение. Два -мерных вектора и называют сопряженными по отношению к матрице (или -сопряженными), если скалярное произведение . Здесь - симметрическая положительно определенная матрица размером .

Предполагается, что квадратичная функция имеет вид:

Если матрица  симметричная и положительно определенная, то функция имеет единственный минимум, который достигается в точке, совпадающей с решением системы линейных уравнений.

Идея метода состоит  в последовательном построении направлений взаимно сопряженных относительно матрицы . На каждом шаге направление получается как линейная комбинация градиентов в точке и предшествующих направлений , причем коэффициенты линейной комбинации выбираются так, чтобы было сопряженным ко всем предшествующим направлениям.

 

 

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

 
где

- очередное приближение

- приближение, построенное на предыдущем шаге

- скалярный шаг

- вектор направления.

Алгоритм

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

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

 

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

 

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

 

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

 

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

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

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

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

Реализация

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

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

  получается за три итерации.

 

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);