Факультет экономики и управления
Кафедра математических методов и моделей в экономике
на тему: «Быстросходящийся итерационный способ обращения матриц..
Градиентный метод наискорейшего спуска.
Метод сопряженных градиентов»
обратной матрицы быстросходящимся итерационным способом обращения матриц.
Метод наискорейшего спуска.
Задание 3. Реализовать метод сопряженных градиентов.
Содержание
Введение………………………………………………………………………….....4
1 Быстросходящимся итерационным способом обращения матриц ………….5
2 Метод наискорейшего cпуска…………..……..…………………..………..…10
3 Метод сопряженных градиентов ……………………….……………………..13
Заключение………………………………………………………………………….15
Приложение А………………………………………………………………………16
Приложение В……………………………………………………………………....26
Приложение Г………………………………………………………………………34
Список используемых источников………………………………………………..41
Введение
Для решения систем линейных алгебраических уравнений используются итерационные способы, служащие серьёзной альтернативой прямым методам решения таких задач, по крайней мере в случаях, когда их размерность велика. Одним из таких методов, является быстросходящимся итерационным способ обращения матриц.
Процесс нахождения решения задач оптимизации с помощью градиентных методов состоит в том, что начиная с некоторой точки осуществляется последовательный переход к некоторым другим точкам до тех пор, пока не будет найдено приемлемое решение исходной задачи. Наиболее часто используемым градиентным методом является метод наискорейшего спуска.
Одним из методов для решения СНАУ является метод сопряженных градиентов.
Цель работы: исследовать быстросходящийся итерационный способ обращения матриц и методы многомерной оптимизации.
Задачи:
разработать и реализовать алгоритмы следующих методов:
- быстросходящийся итерационный способ обращения матриц;
- градиентного метода наискорейшего спуска;
- метода сопряженных градиентов.
1 Быстросходящийся итерационный способ обращения матриц
Нахождение обратной матрицы с помощью быстросходящегося итерационного способа обращения матриц.
Исходные данные: Система стандартного вида
Ax=b,
где - n*n-матрица, а
и - n-мерные векторы столбцы, E-единичная матрица.
Лемма 1.1
Условие, что все собственные числа матрицы В по модулю меньше 1, является необходимым и достаточным для того, чтобы:
1)
2) матрица имела обратную и
Лемма 1.2
Если , то матрица имеет обратную матрицу и при этом справедливо неравенство:
Согласно леммам 1.1 и 1.2, если матрица мала (в смысле нормы или собственных значений), то обратная к А матрица
в принципе, может быть найдена сколь угодно точно приближенным суммированием данного матричного ряда. Построим итерационный процесс, определяющий существенно более быстро сходящуюся последовательность приближений к обратной для А матрице . Будем далее обозначать эти приближения, получаемые на k-м шаге, через , а их невязки .
Лемма 1.3
Если для матрицы А найдется такая обратимая матрица , что модули всех собственных чисел матрицы меньше единицы, то матрица А обратима и для обратной матрицы справедливо представление
Доказательство:
Из неравенства
В силу обратимости матрицу и (последнее по лемме 1.1), имеем:
т.е матрица А обратима и справедливо представление:
Доказательство завершается разложение в матричный ряд (лемма 1.1).
Очевидным следствием лемм 1.1 и 1.2 является следующая лемма.
Лемма 1.4
Пусть матрица обратима и
Тогда:
1) Существует матрица ;
2) Справедливо представление по формуле (1.1);
3) Имеет место оценка
Для построения итерационно го процесса зафиксируем в разложении (1.1) m+1 первых слагаемых и будем считать первым приближением к матрицу:
Найдем выражение невязки этого приближения через невязку предыдущего (в данном случае начального) приближения :
Благодаря полученной связи между невязками, можно утверждать, что если выполняются условия лемм 1.3 или 1.4 по отношению к матрицам , , то для матриц , они тем более будут выполнены. Следовательно, к матрицам ,, можно применить все рассуждения, проведенные выше для ,. Таким образом, приходим к итерационному процессу:
где k=0,1,2…-номер итерации; - задаваемая начальная матрица, близкая к в указанном выше смысле, а - параметр метода.
Изучим сходимость этого процесса.
Теорема
Пусть квадратные нормы матрицы А и таковы, что матрица обратима и Тогда существует обратная к А матрица и к ней сходится последовательность матриц , определяемая итерационным процессом (1.4). При этом имеет место точное равенство:
и справедливы оценки погрешности:
1) ;
2) .
Доказательство:
Существование А следует из леммы 1.4. Упомянутая повторяемость рассуждений и выкладок, проведенных на первом итерационном шаге, позволяет считать очевидными равенства типа (1.11), (1.3) для к-й итерации:
a из (1.6) аналогично (с учетом (1.7)) получаем:
Заменяя здесь в правой части на (см. (1.8)), получаем утверждаемое в теореме равенство (1.5). Переходя в нем к нормам, в соответствии с условием заключаем, что
т.е имеет место сходимость последовательности к матрице а-1 по норме, а значит, и поэлементная сходимость.
Для доказательства первой оценки (апостериорной) вычтем из (1.6):
Отсюда по лемме 1.2 с учетом (1.7) получаем требуемую оценку 1).
Вторая оценка (априорная) может быть найдена в результате загрубления первой. Но можно вывести ее непосредственно из равенства (1.9), подставив в его правую часть вместо А-1 выражение (см. (1.1)):
Переход к нормам в последнем равенстве и привлечение леммы 1.2 завершает доказательство теоремы.
Равенства (1.4) определяют фактически не один, а целое семейство итерационных методов обращения. Фиксированием параметра т = 1,2,... можно получать конкретные процессы (m+1)-го порядка скорости сходимости. Этот порядок может быть сколь угодно большим, однако обычно ограничиваются процессами второго (т = 1) и третьего (т =2) порядков. Приоритет процесса второго порядка связан с его простотой и более ранним появлением: первая публикация об этом методе относится к 1933 г. и принадлежит Г. Шульцу [205], в связи с чем и все семейство (1.4) естественно называть методом Шульца'. Метод третьего порядка целесообразно использовать из тех соображений, что он, как показал М. Альтман [201], обладает свойством минимальности вычислительных затрат, требующихся для обращения матриц с заданной точностью методами семейства (1.4).
Отметим, что как сам быстросходящийся итерационный процесс (1.4), так и представленные теоремой результаты можно без каких-либо особых дополнительных условий отнести к более общей задаче обращения линейных ограниченных операторов в полных нормированных пространствах.
Алгоритм:
- Вводим матрицу А и начальное приближение обратной ей матрицы;
- Элемент последовательности приближений на k-ом шаге . Их невязки
- Итерационный процесс:
- Проверяем критерий останова:
Блок-схему алгоритма метода, текст программы и тестовый пример смотри в приложении А.
2 Метод наискорейшего cпуска
Требуется найти минимум функции на множестве допустимых решений , т.е. найти такую точку , что
Метод вида: , где , называется методом спуска, если вектор на каждом шаге принадлежит множеству направлений убывания функции в точке и
Вектор задает направление убывания функции в точке x, если ,
где - значение, задающее шаг направления вектора .
Метод наискорейшего спуска относится к методам, в которых в процессе поиска кроме информации о самой функции используется информация о производных первого порядка. К группе таких методов относятся различные градиентные методы.
Градиентные методы представляют собой методы спуска, в которых в качестве направлений убывания выбирается направление антиградиента функции:
-grad
Критерием остановки итерационной последовательности являются обычно следующие неравенства:
или ║grad║.
Суть данного метода заключается в том, что с помощью метода минимизации функции вдоль заданного направления осуществляется поиск минимума из заданной точки. В данном методе направление выбирается таким образом, чтобы на каждом этапе поиск точки минимума производился вдоль "наилучшего" направления. Не ясно, какое направление является "наилучшим", но известно, что направление градиента является направлением наискорейшего возрастания функции. Следовательно, противоположное направление является направлением наискорейшего убывания функции. То есть в качестве направления поиска минимума в методе наискорейшего спуска используют вектор антиградиента.
Метод наискорейшего спуска требует решения на каждом шаге задачи одномерной оптимизации
т. е он основывается на выборе шага из следующего соображения - из точки будем двигаться в направлении антиградиента до тех пор, пока не достигнем минимума функции f на этом направлении.
Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода.
При нахождении решения задачи градиентными методами итерационный процесс продолжается до тех пор, пока градиент функции в очередной точке не станет равным нулю или же пока не выполнится неравенство , где - точность полученного решения.
Иллюстрация метода:
|
|
Алгоритм
1) Зададимся , ε, k=0.
2) Определим направление -grad;
3) Находим шаг методом одномерной оптимизации;
4) Рассчитываем ;
5) Проверяем условие:
- если оно выполнилось, то ,
- иначе и переходим к шагу 2.
К достоинствам метода наискорейшего спуска относится высокое быстродействие на регулярных участках рельефа целевой функции. К недостаткам - низкая эффективность в "оврагах".
Практика показывает, что этот метод часто требует меньшего числа итераций, чем градиентный метод с постоянным шагом.
В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.
Вообще говоря, процедура наискорейшего спуска может закончиться в стационарной точке любого типа, в которой .
Эффективность алгоритма зависит от вида минимизируемой функции. Алгоритм наискорейшего спуска сойдется за одну итерацию при любом начальном приближении для функции , но сходимость будет очень медленной, например, в случае функции вида . В тех ситуациях, когда линии уровня минимизируемой функции представляет собой прямолинейный или, хуже того, криволинейный "овраг" эффективность алгоритма оказывается очень низкой. Очевидно, что хорошие результаты может давать предварительное масштабирование функций.
Процесс наискорейшего спуска обычно быстро сходится вдали от точки экстремума и медленно в районе экстремума. Поэтому метод наискорейшего спуска нередко используют в комбинации с другими алгоритмами.
Блок-схему алгоритма метода, текст программы и тестовый пример смотри в приложении В.
3 Метод сопряженных градиентов
Определение сопряженности формулируется следующим образом: два вектора x и y называют А-сопряженными (или сопряженными по отношению к матрице А) или А–ортогональными, если скалярное произведение x и Ay равно нулю, то есть:
xTAy = 0 (3.1)
Сопряженность можно считать обобщением понятия ортогональности. Действительно, когда матрица А – единичная матрица, в соответствии с равенством 3.1, векторы x и y – ортогональны. Остается выяснить, каким образом вычислять сопряженные направления.
Для нахождения сопряженных направлений существует несколько способов. Один из возможных способов – использовать методы линейной алгебры, в частности, процесс ортогонализации Грамма–Шмидта. Но для этого необходимо знать матрицу А, поэтому для большинства задач этот метод не годится. Так же, существуют другие, итеративные способы вычисления сопряженного направления, самый известный – формула Флетчера-Ривса:
(3.2)
где:
(3.3)
r(i+1) – антиградиент в точке х(i+1)
d(i) - новое сопряженное направление
Формула 3.2 означает, что новое сопряженное направление получается сложением антиградиента в точке поворота и предыдущего направления движения, умноженного на коэффициент, вычисленный по формуле 3.3. Направления, вычисленные по формуле 3.2, оказываются сопряженными. То есть для квадратичных функций метод сопряженных градиентов находит минимум за n шагов (n – размерность пространства поиска). Для функций общего вида алгоритм перестает быть конечным и становится итеративным. При этом, Флетчер и Ривс предлагают возобновлять алгоритмическую процедуру через каждые n + 1 шагов.
Можно привести еще одну формулу для определения сопряженного направления, формула Полака–Райбера:
(3.4)
Метод Флетчера-Ривса сходится, если начальная точка достаточно близка к требуемому минимуму, тогда как метод Полака-Райбера может в редких случаях бесконечно зацикливаться . Однако последний часто сходится быстрее первого метода.
Алгоритм:
- Вычисляется антиградиент в произвольной точке x(0).
- Осуществляется спуск в вычисленном направлении пока функция уменьшается, иными словами, поиск a(i), который минимизирует
a(i) находим методом наискорейшего спуска. - Переход в точку, найденную в предыдущем пункте
- Вычисление антиградиента в этой точке
- Вычисления по формуле 3.3 или 3.4. Чтобы забыть последнее направление поиска и стартовать алгоритм заново в направлении скорейшего спуска, для формулы Флетчера–Ривса присваивается 0 через каждые n + 1 шагов. Вычисление нового сопряженного направления
- Переход на пункт 2.
Блок-схему алгоритма метода, текст программы и тестовый пример смотри в приложении Г.
Заключение
В своей работе я исследовала и реализовала быстросходящейся итерационный способ обращения матриц, метод наискорейшего спуска и метод сопряженных градиентов.
Решены поставленные задачи - были разработаны и реализованы алгоритмы следующих методов:
- нахождение обратной матрицы, используя итерационный способ обращения матриц;
- для проведения многомерной оптимизации: метод наискорейшего спуска и метод сопряженных градиентов.
Недостатками быстросходящегося итерационного способа обращения матриц является выбор начального приближения, поэтому это не позволяет относиться к ним как к самостоятельным универсальным методам, конкурирующим с прямыми методами обращения, основанными, например, на LU–разложении матриц. Такие методы обращения матриц не имеют своей сферы применения.
Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода. В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.
Процесс наискорейшего спуска обычно быстро сходится вдали от точки экстремума и медленно в районе экстремума. Поэтому метод наискорейшего спуска нередко используют в комбинации с другими алгоритмами.
Первые итерации приводят к перемещению в направлении градиента, поэтому глобальная сходимость алгоритма вытекает из глобальной сходимости метода наискорейшего спуска. Опыт показывает, что когда алгоритм периодически не обновляется, метод может не сходиться к локальному оптимуму.
В методе сопряжённых градиентов используется информация только о линейной части приращения в точке, как и в методах градиентного спуска. При этом метод сопряжённых градиентов позволяет решать квадратичные задачи за конечное число шагов. На многих других задачах метод сопряжённого градиента также превосходит метод градиентного спуска. Сходимость метода градиентов существенно зависит от того, насколько точно решается задача одномерной оптимизации. Возможные зацикливания метода устраняются с помощью обновлений. Тем не менее, если метод попадёт в локальный минимум функции, скорее всего, ему не удастся из него выбраться.
Приложение А
Блок-схема быстросходящегося итерационного способа обращения матриц
Текст программы
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, XPMan, ComCtrls, Grids;
type
TForm1 = class(TForm)
strngrd1: TStringGrid;
edt1: TEdit;
ud1: TUpDown;
xpmnfst1: TXPManifest;
lbl1: TLabel;
strngrd2: TStringGrid;
lbl2: TLabel;
strngrd3: TStringGrid;
lbl3: TLabel;
btn1: TButton;
procedure edt1Change(Sender: TObject);
procedure btn1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
const eps=0.01;
var i,j,k,n:Integer;
a,u,psi,psi2,sum,am1:array [0..4, 0..4] of Real; //am1=A^(-1), psi2=psi^2
pog:Real;
Form1: TForm1;
implementation
{$R *.dfm}
procedure psimatrix;
var x:Real;
begin
for i:=0 to (n-1) do
for j:=0 to (n-1) do
begin
x:=0;
for k:=0 to (n-1) do
x:=x+a[i,k]*u[k,j];
psi[i, j]:=x;
end;
for i:=0 to (n-1) do
psi[i, i]:=psi[i, i]-1;
for i:=0 to (n-1) do
for j:=0 to (n-1) do
psi[i, j]:=-psi[i, j];
end;
procedure psisquare;
var x:Real;
begin
for i:=0 to (n-1) do
for j:=0 to (n-1) do begin
x:=0;
for k:=0 to (n-1) do
x:=x+psi[i,k]*psi[k,j];
psi2[i, j]:=x;
end;
end;
procedure summing;
var x:Real;
begin
for i:=0 to (n-1) do
for j:=0 to (n-1) do
if i=j then sum[i,j]:=1+psi[i,j]+psi2[i,j]
else sum[i,j]:=psi[i,j]+psi2[i,j];
end;
procedure unext;
var x:Real;
un:array [0..4, 0..4] of Real;
begin
for i:=0 to (n-1) do
for j:=0 to (n-1) do
begin
x:=0;
for k:=0 to (n-1) do
x:=x+u[i,k]*sum[k,j];
un[i, j]:=x;
end;
for i:=0 to (n-1) do
for j:=0 to (n-1) do
u[i,j]:=un[i,j];
end;
procedure pogr;
var mas1: array [0..4, 0..4] of Real;
x,y,upsin, psin:Real; //upsin - норма u*psi
begin
for i:=0 to (n-1) do
for j:=0 to (n-1) do
begin
x:=0;
for k:=0 to (n-1) do
x:=x+u[i,k]*psi[k,j];
mas1[i, j]:=x;
end;
upsin:=0;
psin:=0;
//Ищем строковые нормы
for i:=0 to (n-1) do
begin
x:=0;
y:=0;
for j:=0 to (n-1) do
begin
x:=x+abs(mas1[i,j]);
y:=y+abs(psi[i,j]);
end;
if x>upsin then upsin:=x;
if y>psin then psin:=y;
end;
pog:=upsin/(1-psin);
end;
//ввод матрицы
procedure TForm1.edt1Change(Sender: TObject);
begin
n:=StrToInt(Edt1.Text);
Strngrd1.ColCount:=n;
Strngrd1.RowCount:=n;
Strngrd2.RowCount:=n;
Strngrd2.ColCount:=n;
Strngrd3.RowCount:=n;
Strngrd3.ColCount:=n;
end;
procedure TForm1.btn1Click(Sender: TObject);
begin
for i:=0 to (n-1) do
for j:=0 to (n-1) do begin
a[i,j]:=StrToFloat(Strngrd1.Cells[j,i]);
u[i,j]:=StrToFloat(Strngrd2.Cells[j,i]);
end;
psimatrix;
psisquare;
summing;
unext;
pogr;
while pog>eps do
begin
psimatrix;
psisquare;
summing;
unext;
pogr;
end;
for i:=0 to (n-1) do
for j:=0 to (n-1) do
Strngrd3.Cells[j,i]:=FloatToStr(u[i,j]);
end;
end.
Тестовый пример
Рис.1 - Реализация быстросходящегося итерационного способа обращения матриц
Рис. 2 - Проверка в MathCad
Приложение В
Блок- схема алгоритма наискорейшего спуска
Текст программы
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids,ExtCtrls;
type
T=array [1..10]of real;
TForm1 = class(TForm)
Label1: TLabel;
Edit1: TEdit;
Memo1: TMemo;
Label2: TLabel;
Button3: TButton;
StringGrid1: TStringGrid;
Label3: TLabel;
Edit2: TEdit;
Label4: TLabel;
Function F_x(Var x:T):real;
Function Suma( v,g:T):T;
Function Ymn(v:T; a:real):T;
Function Gradient(Var x:T):T;
Function Norma (x:T):real;
procedure Button3Click(Sender: TObject);
procedure lok_alfa(Var x,gr:T;Var a,b:real);
procedure Met_nais_spyska(Var x:t);
Procedure Min_alfa(Var alfa,a,b:real;Var x,gr:T);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
n:word;
e:real;
implementation
{$R *.dfm}
procedure TForm1.lok_alfa(Var x,gr:T;Var a,b:real);
Var i:integer;
f1,f2,z,sum,l:real;
x0,x1,d,h:T;
f:boolean;
Begin
l:=0.5;
f:=false;
x0:=x;
sum:=0;
h:=gr;
While not f do begin
f1:=F_x(x0);
x1:=Suma(x0,Ymn(h,l));
f2:=F_x(x1);
i:=0;
sum:=l;
While f2<f1 do Begin
x0:=x1;
f1:=f2;
l:=2*l;
sum:=sum+l;
x1:=Suma(x0,Ymn(h,l));
f2:=F_x(x1);
inc(i);
end;
if i=0 then l:=l/2
else f:=true;
end;
b:=sum;
a:=Sum-1.5*l;
End;
Procedure Tform1.Min_alfa(Var alfa,a,b:real;Var x,gr:T);
Var i,k,n_m:word;
d,y:T;
mas:array[1..20]of real;
min,f,f1,h:real;
Begin
While abs(b-a)>0.1 do begin
mas[1]:=a;
min:=mas[1];
n_m:=1;
y:=Suma(x,Ymn(gr,min));
f:=F_x(y);
k:=20;
h:=abs(b-a)/k;
for i:=2 to k do begin
mas[i]:=mas[i-1]+h;
d:=Ymn(gr,mas[i]);
y:=Suma(x,d);
f1:=F_x(y);
if f1<f then begin
n_m:=i;
min:=mas[i];
y:=Suma(x,Ymn(gr,min));
f:=F_x(y);
end;
end;
If (n_m<>1) and (n_m<>20) then begin
a:=mas[n_m-1];
b:=mas[n_m+1];
end
else if n_m<>1 then
begin
b:=mas[2];
a:=mas[1];
end
else begin
b:=mas[20];
a:=mas[19];
end
end;
alfa:=(b+a)/2;
End;
procedure TForm1.Met_nais_spyska(Var x:t);
var x0,x1,gr:T;
i,j:integer;
alfa,s,a,b:real;
begin
x0:=x;
gr:=Gradient(x0);
While Norma(gr)>=e do begin
x0:=x1;
gr:=Gradient(x0);
lok_alfa(x0,gr,a,b);
Min_alfa(alfa,a,b,x0,gr);
x1:=Suma(x0,Ymn(gr,alfa));
end;
x:=x1;
end;
procedure TForm1.Button3Click(Sender: TObject);
Var i:word;
x:t;
begin
n:=StrToInt(Edit1.Text);
e:=StrTofloat(Edit2.Text);
for i:=1 to n do x[i]:=StrToFloat(StringGrid1.Cells[i-1,0]);
Met_nais_spyska(x);
For i:=1 to n do Memo1.Lines[i-1]:='x'+inttostr(i)+'='+FloatTostr(x[i]);
end;
Function Tform1.F_x(Var x:T):real;
begin
result:=sqr(x[1]-4)+sqr(x[2]-4);
end;
Function Tform1.Ymn( v:T; a:real):t;
Var i:word;
Begin
For i:=1 to n do Ymn[i]:=v[i]*a;
End;
Function TForm1.Suma(v,g:T):T;
Var i:word;
Begin
For i:=1 to n do Suma[i]:=v[i]+g[i];
End;
Function TForm1.Gradient(var x:t):T;
Begin
Gradient[1]:=-2*(x[1]-4);
Gradient[2]:=-2*(x[2]-4);
End;
Function TForm1.Norma(X:T):real;
Var i:word;
s:real;
begin
s:=0;
For i:=1 to n do s:=s+sqr(x[i]);
result:=sqrt(s);
end;
end.
Тестовый пример
F(x)=(x1-4)2+(x2-4)2
Рис.3 Реализация метода наискорейшего спуска
Приложение Г
Блок – схема метода сопряженных градиентов
Текст программы
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Edit1: TEdit;
Edit2: TEdit;
Edit3: TEdit;
Label1: TLabel;
Button2: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
Type
Mas=Array[1..3]of real;
Function NormaGr (x:mas):real;
begin
NormaGr:=sqrt(sqr(4*(x[1]-5))+sqr(2*(x[2]-2))+sqr(2*(x[3]-3)));
end;
Function F (x:mas):real;
begin
F:=2*sqr(x[1]-5)+sqr(x[2]-2)+sqr(x[3]-3);
end;
procedure proiz (x:mas; var gr:mas);
begin
gr[1]:=4*(x[1]-5);
gr[2]:=2*(x[2]-2);
gr[3]:=2*(x[3]-3);
end;
const n=3;
var
x,k,p,gr,w:Mas;
EPS,h,b:real;
i:integer;
begin
x[1]:=1;
x[2]:=3;
x[3]:=12;
h:=0.5;
eps:=0.001;
proiz(x,gr);
for i:=1 to n do
p[i]:=-gr[i];
repeat
for i:=1 to n do
k[i]:=x[i]-p[i]*h;
{proiz(x,gr);
h:=h+normagrk(grad)/normagrx(gr)*h;}
w:=x;
if F(k)<F(x) then
begin
while F(k)<F(x) do
begin
for i:=1 to n do
x[i]:=k[i];
// proiz(x,gr);
for i:=1 to n do
{proiz(x,gr);}
k[i]:=x[i]+p[i]*h;
end;
{h1:=proiz(x,gr)+normagr(x,gr,grad)*h0;}
end
else
begin
while (F(k)>F(x)) and (h>eps) do
h:=h/2;
begin
for i:=1 to n do
begin
k[i]:=x[i]+p[i]*h;
end;
{ h1:=proiz(x,gr)+normagr(x,gr,grad)*h0;}
end;
b:=sqr(normagr(k)/normagr(w));
x:=k;
proiz(k,gr);
for i:=1 to n do
p[i]:=-gr[i]+b*p[i];
end;
until {(sqrt(sqr(gr[1])+sqr(gr[2])+sqr(gr[3])))}normagr(k)<eps;
Edit1.Text:=floattostr(x[1]);
Edit2.Text:=floattostr(x[2]);
Edit3.Text:=floattostr(x[3]);
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
Form1.Close;
end;
end.
Тестовый пример
Рис. 4 Реализация метода сопряженных градиентов
Список используемых источников
- Вержбицкий В.М. //Численные методы. Численные методы: Учеб. пособие для вузов. — М.: Высш. шк., 2001. — 382 с.:ил. ISBN 5-06-003982-Х
- Бахвалов Н. С., Жидков Н. П., Кобелько Г.М. //Численные методы.-М.: Наука, 1987г.
- Васильев Ф.П.//Численные методы решения экстремальных задач.-М.: Наука, 1990г.
- Волков Б. А.// Численные методы.-М.: Наука, 1990г.
- Пантелеев А.В., Летова Т.А.// Методы оптимизации в примерах и задачах: Учеб. пособие. -2-е изд.,исправл.-М.:Высш.шк., 2005. -544с.:ил. ISBN 5-06-004137-9
- Интернет ссылка www.exponenta.ru.
- Деннис Дж., Шнабель Р.// Численные методы безусловной оптимизации и решения НУ: пер. с англ.-М.: Мир, 1988-440с. ISBN 5-03-001102-1
- Срочко В.А.// Численные методы: Курс лекций. – Иркутск. Иркут. ун-т, 2003.-168с.
- Пшеничный Б.Н., Ланилин Ю.М.//Численные методы в экстремальных задачах. –М.: Наука, 1975.
Скачать: