Метод первого порядка
В этом методе Xk+1=Xk-hkf(Xk). Очередная точка выбирается в направлении скорейшего убывания функции. Шаг hk должен выбираться достаточно малым, чтоб выполнялось f(Xk+1)< f(Xk)(рис 3).
Рис.3 Рис.4
Величина шага должна уменьшаться по мере приближения к X0. тогда у нас происходит дробление шага. Шаг hk выбирают так, чтоб выполнялось неравенство
f(Xk+1) - f(Xk) ≤ - ε hk// f(Xk)//2
где 0 < ε < 1 - произвольно выбранная константа.
На очередном шаге процесса проверяется неравенство. Если оно выполнено – шаг сохраняется, если нет – шаг уменьшается так, чтобы выполнилось неравенство. Геометрическая интерпретация представлена на рис.4. траектория движения аппроксимирует ломаной линией градиентную кривую, проходящую через точки X0 и X0. Если выбрана постоянная величина шага, то количество итераций, которое необходимо выполнить, может оказаться очень большим.
Разновидностью является метод покоординатного спуска (рис.5). Движение к X0 осуществляется по отрезкам прямых, параллельным координатным осям.
Градиентные методы очень просты в реализации и поэтому часто используются на практике. Но при сложной структуре f(Xk) они могут плохо сходится. Поэтому используют вторые производные f(Xk).
Рис.5
Метод второго порядка
М
етоды
второго порядка являются обобщенным
методом Ньютона. На рис.6 приведена
геометрическая интерпретация отыскания
корня уравнения (X)=0
методом касательных. Разложение (X)
в окрестности Xk
дает (X)
= (Xk)
+ (Xk)(X
- Xk)
+ 0(| X
- Xk
|)
Отбрасывая малые высшего порядка и пологая, что (X)=0,получим
X = Xk+1 = Xk - (Xk) / (Xk).
Рис.6
Пусть теперь (X)- функция n-мерного аргумента. Разложим ее в ряд Тейлора, отбросив малые высшего порядка (Xk) + (Xk)(X – Xk)., откуда Xk+1 = Xk - (Xk) / (Xk).
Теперь считаем (X)градиентом f(X), т.е. = f. Приравнивая f=0, находим стационарные точки f(X). Формула для вычисления координат этих точек преобразуется к виду:
Xk+1 = Xk - f(Xk) / f(Xk).
Недостатки метода Ньютона заключаются в том, что на каждом шаге необходимо вычислять f, и она должна быть положительно определена, иначе процесс может расходится.
Метод весьма эффективен, но его лучше применять, когда к X0 подошли достаточно близко, причем в районе X0 функция сильно выпукла.
Листинг программы по методам 1го и 2го порядков
function f(x:real):real;
begin
// result:=sin(x);
result:=(x-3)*(x-3)*(x-3)*(x-3);
end;
function df(x:real):real;
begin
// result:=cos(x);
result:=4*(x-3)*(x-3)*(x-3);
end;
function ddf(x:real):real;
begin
//result:=-sin(x);
result:=12*(x-3)*(x-3);
end;
procedure TForm1.Button1Click(Sender: TObject);
var e,h,xk,xk1,d:real;
i:integer;
begin
e:=StrToFloat(Edit3.Text);
xk1:=StrToFloat(Edit1.Text);
h:=StrToFloat(Edit4.Text);
Memo1.Clear;
Memo1.Text:='Поиск с использованием f''(x)'#13#10#13#10;
i:=0;
repeat
xk:=xk1;
repeat
xk1:=xk-h*df(xk);
if df(xk)*df(xk1)>0 then h:=h*2;
if f(xk)<f(xk1) then h:=h/3;
until (df(xk)*df(xk1)<=0) and (abs(f(xk))>=abs(f(xk1)));
Memo1.Lines.Add(Format('X( %d )= %4.4f f( %1:4.4f ) = %2:4.4f f''(%1:4.4f )=%3:4.4f h=%4:4.4f',[i,xk,f(xk),df(xk),h] ));
Inc(i);
until (abs(xk1-xk)<e) or (df(xk)=0);
Memo1.Lines.Add(Format(#13#10'Найдено значение f(%4.4f)=%4.4f с погрешностью e=%4.4f',[xk,f(xk),e]));
end;
procedure TForm1.Button2Click(Sender: TObject);
var e,h,xk,xk1,d:real;
i:integer;
begin
e:=StrToFloat(Edit3.Text);
xk1:=StrToFloat(Edit1.Text);
h:=StrToFloat(Edit4.Text);
Memo1.Clear;
Memo1.Text:='Поиск с использованием f''(x)'#13#10#13#10;
i:=0;
repeat
xk:=xk1;
repeat
xk1:=xk-h*df(xk)/ddf(xk);
if df(xk)*df(xk1)>0 then h:=h*2;
if f(xk)<f(xk1) then h:=h/2;
until (df(xk)*df(xk1)<=0) and (f(xk)>=f(xk1));
Memo1.Lines.Add(Format('X( %d )= %4.4f f( %1:4.4f ) = %2:4.4f f''(%1:4.4f )=%3:4.4f h=%4:4.4f',[i,xk,f(xk),df(xk),h] ));
Inc(i);
until (abs(xk1-xk)<e) or (ddf(xk)=0);
Memo1.Lines.Add(Format(#13#10'Найдено значение f(%4.4f)=%4.4f с погрешностью e=%4.4f',[xk,f(xk),e]));
end;
end.