Вычислительный алгоритм метода "Наискорейшего спуска" с тестированием на функции Розенброка

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С.П. КОРОЛЕВА (НИУ)

Факультет летательных аппаратов

Кафедра летательных аппаратов

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К индивидуальному заданию по профессионально-ознакомительной практике

Выполнил студент

Резинкина В.А.

Самара 2011

Задание

Разработать вычислительный алгоритм метода «Наискорейшего спуска» с тестированием на функции Розенброка.

Разработать программный продукт, реализующий данный алгоритм в среде DELPHI.

Разработать интерфейс пользователя.

Разработать модуль графического отображения поиска решения.

Апробировать алгоритм на тестовых примерах.

Записать программный продукт на диск.

Оформить описание разработки в соответствии с СТП СГАУ.

вычислительный алгоритм функция розенброк delphi

Реферат

Градиент, метод квадратичной интерполяции, множители лагранжа, метод одномерного поиска.

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

Содержание

Введение

1. Математическая часть задачи

2. Тестовый расчет

2.1 Назначение тестовой функции и ее форма

3. Алгоритм работы программы

4. Руководство пользователя

Заключение

Список использованных источников

Приложение А

Введение

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

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

Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода.

Методом наискорейшего спуска может быть найден минимум функции n переменных F(x1, . . . ,xn) или найдены решения системы уравнений вида:

Fi(x1,x2, . . .,xn)=0, i=1, . . ,n.

Алгоритм наискорейшего спуска реализует итерационную процедуру движения к минимуму из произвольно выбранной точки начального приближения в направлении наиболее сильного уменьшения функции, определенном в окрестности текущего значения аргумента минимизируемой функции. Такое направление противоположно направлению, задаваемому вектором градиента минимизируемой функции F(x1, . . . ,xn)

1. Математическое описание

Основной целью программы является вычисление экстремума функции.

В методе наискорейшего спуска в качестве направления поиска минимума заданной функции выбирается вектор, направление которого противоположно направлению вектора градиента функции F(X), где X=x1, x2, x3, … xn. Координаты этого вектора :

В математическом анализе доказывается, что вектор gradF(X) характеризует направление наиболее быстрого возрастания функции. Поэтому вектор - gradF(X) (антиградиента) является направлением наиболее быстрого ее убывания. Каждое последующее приближение получается из предыдущего смещением в направлении антиградиента функции F(X) (смотри рис.1).

Рис. 1

Задавшись начальным приближением X0, ищется следующее приближение с помощью реккурентного соотношения вида:

, i=0,1,2…

Приведенное соотношение не определяет алгоритм однозначно, поскольку ничего не сказано о выборе параметра i. Например, его можно определять из условия минимума величины:

Рассматриваемая функция является функцией одного параметра и ее минимум находится или методами одномерной минимизации или решением уравнения, которое имеет вид:

,

минимальный неотрицательный корень этого уравнения и является искомым значением i.

Поиск прекращается при выполнении условия

,

так как градиент в точке минимума функции = 0, а при приближенных вычислениях .

2. Тестовый расчет

2.1 Назначение тестовой функции и ее форма

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

С целью сравнения эффективности различных алгоритмов разработаны специальные (т.наз. тестовые) функции, имеющие "неприятные" для методов поиска экстремума особенности. Одна из самых известных - функция Розенброка (автора многих популярных алгоритмов поиска экстремума).

Формула, определяющая функцию Розенброка:

Эта функция имеет крайне пологий изогнутый овраг, что сильно затрудняет поиск минимума (значение аргументов в точке минимума очевидны:

x* =1, y* = 0 (при этом f(x*,y*) = 0).



Рисунок 2 - Тестовый расчет

3. Алгоритм работы программы

Общий алгоритм работы программы представлен в виде блок-схемы на рисунке 3.

Рисунок 3 - Блок-схема программы

Подробный алгоритм работы программы представлен в виде блок-схемы на рисунке 4.



Рисунок 4 - Подробная блок-схема программы.

4. Руководство пользователя

До начала работы программы нужно выбрать, каким методом будет находиться экстремум, далее ввести начальные значения: начальный шаг, необходимую точность и начальное приближение X01 и X02 (рисунок 3).

Рисунок 5 - Панель ввода данных.

Далее нажать кнопку «Рассчитать». Для вывода расчетных данных следует нажать кнопку «Показать расчет».

Рисунок 6 - Окно программы

При необходимости тестирования программы на других функциях, следует изменить данные в function f_parab, либо в function f_rozen.

Заключение

При выполнении индивидуального задания была разработана программа нахождения экстремума параболоида и функции Розенброка.

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

Список использованных источников

Б. Банди, «Методы оптимизации» стр. 51 - 56.

В.В. Салмин, «Методы оптимального управления».

СТО СГАУ 02068410-004-2007. Общие требования к учебным текстовым документам. Самара 2007

Приложение А

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls, Menus;

type

TForm1 = class(TForm)

Edit1: TEdit;

Edit2: TEdit;

Button1: TButton;

Edit3: TEdit;

Edit4: TEdit;

Button2: TButton;

Label3: TLabel;

Label4: TLabel;

RadioGroup2: TRadioGroup;

OpenDialog1: TOpenDialog;

SaveDialog1: TSaveDialog;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

N7: TMenuItem;

Label5: TLabel;

Label1: TLabel;

Label2: TLabel;

Image1: TImage;

Label6: TLabel;

RadioGroup1: TRadioGroup;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure RadioGroup1Click(Sender: TObject);

procedure N2Click(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure N5Click(Sender: TObject);

procedure N7Click(Sender: TObject);

private

{Private declarations}

public

{Public declarations}

end;

var

Form1: TForm1;

type fun = function (x1,x2 : double) : double;

implementation

uses Unit2;

function f_parab (x1,x2 : double) : double;

var y,alpha : double;

begin

alpha:=(25*pi)/180;

y:=((x1+3)*cos(alpha)+(x2+9)*sin(alpha))/9;

y:=y*y;

result:=y;

y:=((x2+9)*cos(alpha)-(x1+3)*sin(alpha))/25;

y:=y*y;

result:=result+y;

end;

function f_rozen (x1,x2 : double) : double;

begin

result:=100*(x2-x1*x1)*(x2-x1*x1)+(1-x1)*(1-x1);

end;

function proizv1 (x1,x2 : double; i : integer) : double;

var f : fun;

dx : double;

begin

dx:=0.00001;

if i=1 then f:=f_parab else f:=f_rozen;

result:=(f(x1+dx,x2)-f(x1,x2))/dx;

end;

function proizv2 (x1,x2 : double; i : integer) : double;

var f : fun;

dx : double;

begin

dx:=0.00001;

if i=1 then f:=f_parab else f:=f_rozen;

result:=(f(x1,x2+dx)-f(x1,x2))/dx;

end;

procedure output( i : integer; memo : TMemo; x1m,x2m,f,delta : double);

var s : string;

begin

s:='';

if i<10 then s:='0';

s:=s+inttostr(i)+') X1='+floattostrf(x1m,fffixed,4,3)+' X2='+floattostrf(x2m,fffixed,4,3)+' ';

s:=s+' F(x1,x2)='+floattostrf(f,fffixed,13,10);// Delta= '+floattostrf(delta,fffixed,13,10);

memo.Lines.Add(s);

end;

{$R *.dfm}

procedure local(d,tmp1,tmp2,chp1,chp2,x01,x02 : double; var a1,b1,a2,b2 : double; var i : integer);

var x1,x2,d1,d2 : double;

f : fun;

begin

if i = 1 then f:=f_parab

else f:=f_rozen;

x1:=x01+d*chp1;

x2:=x02+d*chp2;

if f(x01,x02)<f(x1,x2) then begin chp1:=chp1-tmp1; chp2:=chp2-tmp2; d:=-d; x1:=x01+d*chp1; x2:=x02+d*chp2; end

else begin x01:=x1; x02:=x2; x1:=x01+d*chp1; x2:=x02+d*chp2; end;

while f(x01,x02)>=f(x1,x2) do begin x01:=x1; x02:=x2; x1:=x01+d*chp1; x2:=x02+d*chp2; end;

if x1<x01 then begin a1:=x1; b1:=x01; end else

begin a1:=x01; b1:=x1; end;

if x2<x02 then begin a2:=x2; b2:=x02; end else

begin a2:=x02; b2:=x2; end;

end;

procedure TForm1.Button1Click(Sender: TObject);

var tmp1,tmp2,chp1,chp2,d,ee,x01,x02,a,b,x1,x2,x1m,x2m,x31m,x32m,a1,a2,b1,b2,delta,e,f : double;

count,k,c : integer;

flag : boolean;

begin

form2.memo1.Lines.Clear;

count:=0;

ee:=0.05;

x01:=strtofloat(edit1.Text);

x02:=strtofloat(edit2.Text);

e:=strtofloat(edit3.text);

d:=strtofloat(edit4.text);

if radiogroup1.ItemIndex=0 then k:=1 else k:=2;

if k=1 then f:=f_parab(x01,x02) else f:=f_rozen(x01,x02);

if form1.RadioGroup2.ItemIndex=0 then flag:=true else flag:=false;

chp1:=-proizv1(x01,x02,k);

chp2:=-proizv2(x01,x02,k);

delta:=sqrt((chp1)*(chp1)+(chp2)*(chp2));

while (delta>e) do

begin

local(d,tmp1,tmp2,chp1,chp2,x01,x02,a1,b1,a2,b2,k);

x1m:=(a1+b1)/2;

x2m:=(a2+b2)/2;

delta:=sqrt((chp1)*(chp1)+(chp2)*(chp2));

if k=1 then f:=f_parab(x1m,x2m) else f:=f_rozen(x1m,x2m);

output(count+1,form2.memo1,x01,x02,f,delta);

x01:=x1m;

x02:=x2m;

if (flag) then begin

chp1:=-proizv1(x01,x02,k);

chp2:=-proizv2(x01,x02,k);

end else

begin

tmp1:=chp1;

tmp2:=chp2;

chp1:=-proizv1(x01,x02,k);

chp2:=-proizv2(x01,x02,k);

tmp1:=tmp1*(chp1*chp1)/(tmp1*tmp1);

tmp2:=tmp2*(chp2*chp2)/(tmp2*tmp2);

chp1:=chp1+tmp1;

chp2:=chp2+tmp2;

end;

inc(count);

if(count>800) then exit;

if(k=2)and(f<5e-7) then exit;

end;

end;

procedure TForm1.Button2Click(Sender: TObject);

begin

if form2.Visible=false then begin form2.Visible:=true; button2.Caption:='Убрать рассчет'; end

else begin form2.Visible:=false; button2.Caption:='Показать рассчет'; end;

end;

procedure TForm1.RadioGroup1Click(Sender: TObject);

begin

if radiogroup1.ItemIndex=0 then edit4.text:='0,01' else edit4.text:='0,000001';

if radiogroup1.ItemIndex=0 then edit3.text:='0,00001' else edit3.text:='0,001';

end;

procedure TForm1.N2Click(Sender: TObject);

begin

OpenDialog1.Execute;

end;

procedure TForm1.N3Click(Sender: TObject);

begin

SaveDialog1.Execute;

end;

procedure TForm1.N5Click(Sender: TObject);

begin

close;

end;

procedure TForm1.N7Click(Sender: TObject);

begin

WinHelp(Handle, 'Help.hlp', HELP_CONTEXT, 1);

end;

end.

Размещено на Allbest.ru