Метод оптимизации

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

Высшего профессионального образования

 

 

Кафедра АСУ

 

 

 

 

 

 

Расчетно-графическая работа

по дисциплине «Метод оптимизации»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Уфа 2013

 

Задание

Найти минимум функции  тремя методами:

• метод средней точки;
• метод хорд;
• метод Ньютона.

 

Содержание

 

 

1 График функции

 

Для построения графика  функции воспользуемся онлайн-сервисом построения графиков функций (режим  доступа: http://yotx.ru/). Полученный график представлен на рис.1.

 

Рисунок 1 – График функции

 

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

 

2 Алгоритмы нахождения экстремума

 

Пусть f(x) - унимодальная функция, имеющая непрерывную производную на отрезке [a,b], и точка является точкой, где функция минимальна. Для непрерывной и дифференцируемой функции в точке минимума имеем: и . Поэтому решение задачи поиска минимума можно заменить на задачу поиска корня уравнения , т.е. использовать методы решения нелинейных уравнений для уравнения .

 

2.1 Метод средней точки

На этапе локализации  было установлено, что на отрезке  [a, b] функция y=f(x) меняет знак, т.е. имеем f(a)·f(b)<0 и имеется всего один корень (рис.2). Предположим, что функция непрерывна, тогда внутри отрезка имеется точка  с,  где y=f(c)=0, a< c <b.

Рисунок 2 – Применение метода средней точки

 

В качестве начального приближения  выбирается точка  , лежащая посередине отрезка [a,b], которая делит этот отрезок на два отрезка равной длины и вычисляется значение функции в этой точке y₀=f(x₀). Далее

рассматривается один из двух отрезков, на концах которого функция  имеет разные знаки, т.к. корень может  находиться только на этом отрезке. Этот отрезок в два раза меньше первоначального. В качестве первой итерации принимают середину этого нового отрезка и т.д. Таким образом, после n итераций отрезок [a,b] уменьшился в 2ⁿ раз, отсюда имеем . Следовательно, метод бисекции сходится со скоростью геометрической прогрессии, знаменатель которой . По сравнению с другими методами он обладает более медленной сходимостью, но зато очень надежен. Для его применения  необходимо чтобы функция была непрерывна и обязательно меняла знак на концах отрезка.

Условие непрерывности  обязательно, т.к. функция может менять знак в окрестности некоторой  точки и одновременно стремится  к  ±¥, т.е. функция имеет особенность внутри отрезка [a,b]. Естественно метод не годится для поиска кратных корней, когда функция  y=f(x)  не меняют знак.

 

2.2 Метод Ньютона

Пусть корень локализован  на отрезке [a,b]. Выбирается точка x₀ на этом отрезке и в этой точке строится касательная к графику функции y=f(x) (рис.3).

Рисунок 3 – Применение метода Ньютона

За новое приближение x₁ принимается точка, в которой касательная пересекает ось 0x. Далее процесс повторяется. Таким образом, на каждом этапе решение исходного нелинейного уравнения заменяется на решение линейного уравнения (уравнения касательной), т.е. проводится линеаризация исходного уравнения.

Запишем уравнение касательной  в точке x_n:

. (1)

Полагая в (1), что при  x=x_n+1  имеем  y=0  получаем:

. (2)

Формула (2) называется формулой Ньютона.

Так как в задаче поиска минимума функции решается уравнение f¢(x)=0, то формула метода Ньютона для задачи минимизации будет иметь следующий вид:

. (3)

Необходимым и достаточным условием сходимости Ньютона сходится для задачи минимизации функции f(x) является знакопостоянство второй и третьей производной.

 

2.3 Метод хорд

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

Производную в точке  x_n  аппроксимируем следующим соотношением:

. (4)

В результате формула  Ньютона преобразуется к виду:

. (5)

Уравнение (5) является уравнением прямой, проходящей через две точки  (x_n, f(x_n))  и  (b, f(b)) на графике уравнения y=f(x), т.е. является уравнением хорды. Поэтому этот метод называется методом хорд.

 

3 Блок-схемы алгоритмов

 

Блок-схема алгоритма  нахождения экстремума методом средней  точки представлена на рис.4.

Рисунок 4 – Блок-схема  алгоритма нахождения минимума методом средней точки

 

Блок-схема алгоритма нахождения минимума методом Ньютона представлена на рис.5.

Рисунок 5 – Блок-схема алгоритма нахождения минимума методом Ньютона

 

Блок-схема алгоритма  нахождения минимума методом хорд представлена на рис.6.

Рисунок 6 – Блок-схема  алгоритма нахождения минимума методом хорд

 

4 Листинг программы

unit Unit1;

 

interface

 

uses

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

  Dialogs, ExtCtrls, TeeProcs, TeEngine, Chart, Series, StdCtrls, Spin;

 

type

  TForm1 = class(TForm)

    Label1: TLabel;

    RadioGroup1: TRadioGroup;

    Button1: TButton;

    GroupBox1: TGroupBox;

    Label3: TLabel;

    Label4: TLabel;

    Label5: TLabel;

    Edit1: TEdit;

    Edit2: TEdit;

    Edit3: TEdit;

    Edit4: TEdit;

    procedure FormCreate(Sender: TObject);

    procedure Button1Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

 

var

  Form1: TForm1;

 

implementation

 

{$R *.dfm}

//подпрограммы, относящиеся  к той функции,

//экстремум которой  следует найти

 

//сама функция, минимум  которой нужно найти

function f(const x: real): real;

  begin

  f:=exp(x)+2*sqr(x)+5;

  end;

//производная функции  f(x)

function df(const x: real): real;

  begin

  df:=exp(x)+4*x

  end;

//вторая производная  функции f(x)

function ddf(const x: real): real;

  begin

  ddf:=exp(x)+4

  end;

 

//построение графика функции

procedure TForm1.FormCreate(Sender: TObject);

begin

 

end;

 

 

//поиск минимума методом  средней точки

//параметры: eps - погрешность  вычисления, cnt - количество шагов,

//a0, b0 - границы интервала

function MiddlePoint(const eps: real; var cnt: integer; const a0,b0: real): real;

  var a,b,c: real;

  begin

  //границы первого  интервала совпадают с заданными  по условию

  a:=a0;

  b:=b0;

  cnt:=0;

  //повторяем вычисления, пока точность не достигнута

  while (abs(b-a)>2*eps) do

    begin

    c:=(a+b)/2; //находим  середину отрезка

    cnt:=cnt+2; //вычисляем  функцию в 2 точках

    if df(a)*df(c)<0 then //локализация корня: в первой  половине или второй

      b:=c

    else

      a:=c;

    end;

  MiddlePoint:=(a+b)/2; //середина интервала признается приближением корня

  end;

 

//поиск минимума методом  Ньютона

//параметры: eps - погрешность  вычисления, cnt - количество шагов,

//a0, b0 - границы интервала

function Newton(const eps: real; var cnt: integer; const a0,b0: real): real;

  var x0, x1: real;

  begin

  x1:=a0;       //за начальное приближение берем  начало интервала

  x0:=b0;

  cnt:=0;

  while abs(x1-x0)>eps do

    begin

    x0:=x1;

    x1:=x0-df(x0)/ddf(x0);

    cnt:=cnt+2; //вычисляем функцию и ее производную, т.е. 2 вычисления

    end;

  Newton:=x1;

  end;

//поиск минимума методом  хорд

//параметры: eps - погрешность  вычисления, cnt - количество шагов,

//a0, b0 - границы интервала

function Chord(const eps: real; var cnt: integer; const a0,b0: real): real;

  var x0, x1: real;

     dfb, dfx0: real;

  begin

  x0:=b0;

  x1:=a0;       //за начальное приближение берем  начало интервала

  dfb:=df(b0);

  cnt:=1; //вычислили функцию  в точке b

  while abs(x0-x1)>eps do

    begin

    x0:=x1;

    dfx0:=df(x0);

    x1:=x0-(x0-b0)/(dfx0-dfb)*dfx0;

    cnt:=cnt+1; //вычисляем функцию в одной точке - х0

    end;

  Chord:=x1;

  end;

procedure TForm1.Button1Click(Sender: TObject);

var min_x: real;

    cnt: integer;

    eps: real;

begin

//ввод точности вычисления

try

  eps:=StrToFloat(Edit4.Text)

except

  ShowMessage('Некорректная  точность!');

  exit;

end;

//выбор метода вычисления

case RadioGroup1.ItemIndex of

  0: min_x:=MiddlePoint(eps,cnt,-2,2);

  1: min_x:=Newton(eps,cnt,-2,2);

  2: min_x:=Chord(eps,cnt,-2,2);

  end;

Edit1.Text:=FloatToStr(min_x);

Edit2.Text:=FloatToStr(f(min_x));

Edit3.Text:=IntToStr(cnt);

end;

end.

 

5 Экранные формы

Экранная форма после  запуска программы приведена  на рис.7.

Рисунок 7 – Экранная форма

 

Самое верхнее поле предназначено  для ввода точности. Ниже расположен блок выбора метода. Еще ниже – блок вывода результата (точки минимума и количества произведенных вычислений). В самом низу формы расположена кнопка запуска вычилений.

 

6 Изучение зависимости скорости работы методов от точности

 

Результаты эксперимента приведены в таблице 1.

Таблица 1 –

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

Точность (допустимая погрешность  найденного значения)	Число вычислений функции  при использовании метода средней  точки	Число вычислений функции  при использовании метода Ньютона	Число вычислений функции  при использовании метода хорд
1	2	4	3
0,5	4	4	3
0,25	6	4	4
0,1	10	6	4
0,05	12	6	5
0,01	16	6	6
0,005	18	6	7
0,001	22	6	8
0,0005	24	8	9
0,0001	30	8	10
0,00001	36	8	12
0,000001	42	8	14

 

Построим графики приведенной зависимости (рис.8).

Рисунок 7 – График зависимости  числа вычислений от точности