Метод золотого сечения

1. Находят две дополнительные точки x1:=a+sech*(b-a) и x2:=a+(1-sech)*(b-a), где sech=0.3819660113;
2. Находят значение функции в этих точках: y1 и y2;
3. Рассматривают дополнительную переменную int – расстояние между рабочими точками (длина текущего итерационного отрезка), начальное значение которой êa-bú.
4. Если int>e*x1, где е – относительная погрешность, то переходят к пункту 5, в противном случае происходит окончание итерационного процесса и x1 – искомая точка минимума.
5. Если y2>y1, тогда уменьшаем рабочий интервал int=x2-a. Переприсваиваем: b=x2;  x2=x1; y2=y1; x1=a+sech*int; y1=f3(x1).
6. Если y2>y1, тогда уменьшаем рабочий интервал int=b-x1. Переприсваиваем:

          int=b-x1; a=x1; x1=x2; y1=y2; x2=a+(1-sech)*int; y2=f3(x2).

7. Возвращаемся к пункту 4.

 

 Результаты

 

1. x⁴-14x³+60x²-70x

 

 

 

 

 

 

 

 

   2) –e^-xln(x)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3) 2x²-e^x

 

 

 

 

 

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

 

 

 

3.3 Обоснование выбора языка программирования

 

Для создания программы курсового проекта я выбрал язык программирования – Delphi.

Delphi — это язык программирования, который используется для создания  разнообразных продуктов ПО. До  недавнего времени он имел  другое название — Object Pascal. Delphi представляет собой объектно-ориентированное  программирование, которое предполагает  существование определенной объектной  библиотеки или так называемой  библиотеки прототипов, использование  которой больше не характеризует  процесс программирования как  громоздкое и сложное мероприятие. 

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

Специфической особенностью и вместе с тем недостатком Delphi являлось то, что использование подобного  языка программирования на первых порах  возможно было только в рамках операционной системы Microsoft Windows. Сейчас же работа с Delphi осуществляется и на таких платформах, как GNU/Linux, Mac OS X и Windows CE.

Во многом Delphi стал основой  для создания такого языка программирования как С#.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

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

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

  В процессе работы над  методом золотого сечения нами  была разработана программа на  Delphi 7.0. работающая на основе этого метода.

          При разработке программы были учтены все требования к программе и выполнены в полной мере.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

1. Ковалев Ф.В. Золотое сечение в живописи. К.: Выща школа, 1989.
2. Кеплер И. О шестиугольных снежинках. – М., 1982.
3. Дюрер А. Дневники, письма, трактаты – Л., М., 1957.
4. Цеков-Карандаш Ц. О втором золотом сечении. – София, 1983.
5. Стахов А. Коды золотой пропорции.
6. Виктор Лаврус  Золотое сечение. - Киев, 2000 года

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение №1.

 

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

 

unit Unit1;

interface

uses

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

  Dialogs, StdCtrls;

type

  TForm1 = class(TForm)

 

    GroupBox1: TGroupBox;

    RadioButton1: TRadioButton;

    RadioButton2: TRadioButton;

    RadioButton3: TRadioButton;

    Button1: TButton;

    Memo1: TMemo;

    procedure FormCreate(Sender: TObject);

    procedure Button1Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

 

var

  Form1: TForm1;

implementation

{$R *.dfm}

function f1(x: real): real;

begin

  Result:=x*x*x*x-14*x*x*x+60*x*x-70*x;

end;

 

function f2(x: real): real;

begin

  Result:=-exp(-x)*ln(x);

end;

 

function f3(x: real): real;

begin

  Result:=2*x*x-exp(x);

end;

 

procedure TForm1.FormCreate(Sender: TObject);

begin

RadioButton1.Checked:=true;

Memo1.Clear;

end;

 

procedure TForm1.Button1Click(Sender: TObject);

const

sech=0.3819660113;

e=0.00001;

var

a,b,int,x1,x2,y1,y2:real;

kol:integer;

begin

  Memo1.Clear;

  with Form1 do

  begin

    if RadioButton1.Checked then

    begin

      kol:=0;

      a:=0;

      b:=2;

      int:=2;

      Memo1.Lines.Add('x'+#9+'a'+#9+'b'+#9+'f(x)');

      Memo1.Lines.Add('');

      Memo1.Lines.Add('2'+#9+'0'+#9+'2'+#9+FloatToStrF(f1(b),ffGeneral,4,6));

      x1:=a+sech*(b-a);

      x2:=a+(1-sech)*(b-a);

      y1:=f1(x1);

      y2:=f1(x2);

      while int>e*x1 do

      begin

        kol:=kol+1;

        if y2>y1 then

        begin

          int:=x2-a;

          b:=x2;

          x2:=x1;

          y2:=y1;

          x1:=a+sech*int;

          y1:=f1(x1);

        end

        else

        begin

          int:=b-x1;

          a:=x1;

          x1:=x2;

          y1:=y2;

          x2:=a+(1-sech)*int;

          y2:=f1(x2);

        end;

      Memo1.Lines.Add(FloatToStrF(x1,ffGeneral,4,6)+#9+FloatToStrF(a,ffGeneral,4,6)+#9+FloatToStrF(b,ffGeneral,4,6)+#9+FloatToStrF(f1(x1),ffGeneral,4,6));

      end;

      Memo1.Lines.Add('');

      Memo1.Lines.Add('Количество итераций: '+IntToStr(kol));

    end;

        if RadioButton2.Checked then

    begin

      kol:=0;

      a:=0;

      b:=2;

      int:=2;

      Memo1.Lines.Add('x'+#9+'a'+#9+'b'+#9+'f(x)');

      Memo1.Lines.Add('');

      Memo1.Lines.Add('2'+#9+'0'+#9+'2'+#9+FloatToStrF(f2(b),ffGeneral,4,6));

      x1:=a+sech*(b-a);

      x2:=a+(1-sech)*(b-a);

      y1:=f2(x1);

      y2:=f2(x2);

      while int>e*x1 do

      begin

        kol:=kol+1;

        if y2>y1 then

        begin

          int:=x2-a;

          b:=x2;

          x2:=x1;

          y2:=y1;

          x1:=a+sech*int;

          y1:=f2(x1);

        end

        else

        begin

          int:=b-x1;

          a:=x1;

          x1:=x2;

          y1:=y2;

          x2:=a+(1-sech)*int;

          y2:=f2(x2);

        end;

         Memo1.Lines.Add(FloatToStrF(x1,ffGeneral,4,6)+#9+FloatToStrF(a,ffGeneral,4,6)+#9+FloatToStrF(b,ffGeneral,4,6)+#9+FloatToStrF(f2(x1),ffGeneral,4,6));

      end;

      Memo1.Lines.Add('');

      Memo1.Lines.Add('Количество итераций: '+IntToStr(kol));

    end;

        if RadioButton3.Checked then

    begin

      kol:=0;

      a:=0;

      b:=2;

      int:=2;

      Memo1.Lines.Add('x'+#9+'a'+#9+'b'+#9+'f(x)');

      Memo1.Lines.Add('');

      Memo1.Lines.Add('2'+#9+'0'+#9+'2'+#9+FloatToStrF(f3(b),ffGeneral,4,6));

      x1:=a+sech*(b-a);

      x2:=a+(1-sech)*(b-a);

      y1:=f3(x1);

      y2:=f3(x2);

      while int>e*x1 do

      begin

        kol:=kol+1;

        if y2>y1 then

        begin

          int:=x2-a;

          b:=x2;

          x2:=x1;

          y2:=y1;

          x1:=a+sech*int;

          y1:=f3(x1);

        end

        else

        begin

          int:=b-x1;

          a:=x1;

          x1:=x2;

          y1:=y2;

          x2:=a+(1-sech)*int;

          y2:=f3(x2);

        end;

         Memo1.Lines.Add(FloatToStrF(x1,ffGeneral,4,6)+#9+FloatToStrF(a,ffGeneral,4,6)+#9+FloatToStrF(b,ffGeneral,4,6)+#9+FloatToStrF(f3(x1),ffGeneral,4,6));

      end;

      Memo1.Lines.Add('');

      Memo1.Lines.Add('Количество итераций: '+IntToStr(kol));

    end;

end;

end;

end.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение № 2.

 

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

 

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

 

program ZolotoeSechenie;

const t1=0.382;

const t2=0.618;

var i: integer;

Eps, a,b,x0,x1,x2,x3,x: real;

 

function f(x:real):real;

begin

f:=2*x*x-ln(x);

end;

 

begin

writeln ('Поиск экстремума  функции одной переменной методом  золотого сечения');

writeln ('Введите интервал  неопределенности');

readln (a, b);

writeln ('Введите требуемую  точность');

readln (Eps);

 

x0:=a; x3:=b; i:=0;

while abs (x3-x0) > Eps do begin

inc(i);

x1:=x0+t1*(x3-x0);

x2:=x0+t2*(x3-x0);

if f(x1)>f(x2) then x0:=x1;

if f(x1)<f(x2) then x3:=x2;

end;

 

x:=(x0+x3)/2;

writeln ('Значение функции  в точке экстремума f(', x, ')=',f(x));

writeln ('Количество итераций',i);

readln;

end.

Результат работы  программы.

 

Поиск экстремума функции одной  переменно методом золотого сечения

Введите интервал неопределенности

0

10

Введите требуемую точность

0.0001

Значение функции в точке  экстремума

f ( 5.0002792383E-01) =     1.1931471837E+00

Количество итераций 24

 

Поиск экстремума функции одной  переменно методом золотого сечения

Введите интервал неопределенности

0

4

Введите требуемую точность

0.000001

Значение функции в точке  экстремума

f ( 5.0000018330E-01)= 1.1931471806E+00

Количество итераций 32

 

Поиск экстремума функции одной  переменно методом золотого сечения

Введите интервал неопределенности

0

4

Введите требуемую точность

0.0001

Значение функции в точке  экстремума

f ( 4.9999405402E-01)= 1.1931471807E+00

Количество итераций 23