Метод золотого перерізу для пошуку екстремумів функцій
![]()
і відомо
значення
Нехай уже визначено
точки
,
локалізований
відрізок
,
обчислено
відповідні
значення функції
.У
цьому випадку
,
Відома
точка
,
яка виконує
золотий переріз
відрізка
,
і обчислено
значення
мінімізаційної
функції в цій
точці:
![]()
За іншу точку
вибираємо
![]()
,
яка є другою
точкою золотого
перерізу відрізка
![]()
У цій
точці обчислюємо
і визначаємо
локалізований
відрізок
,
а саме (будемо
вважати, що
)
у випадку
приймемо
,
а у випадку
(випадок
розглядається
аналогічно).
Новий відрізок
є локалізований

Точка
- це точка золотого
поділу відрізка
і в цій
точці обчислено
значення функції
Якщо
кількість
обчислень
функції
не обмежено,то
цей процес
можна продовжити
доти, доки не
виконається
нерівність
- задана
точність обчислень.
Якщо кількість
обчислень
функції задана
і дорівнює n,
то після отримання
локалізованого
відрізка
обчислення
припиняємо
і на розв’язок
задачі другого
типу беремо
-
наближення
до множини
з похибкою

Якщо враховувати аналогічну оцінку в методі поділу відрізка наполовину
![]()
![]()
Отже,
навіть для
малих n
метод золотого
поділу ефективніший,
ніж метод поділу
відрізка наполовину.
Недоліком
методу золотого
поділу в запропоновану
вигляді є його
нестійкість.
Розглянемо
числову реалізації
методу. Обов’язково
число
буде задано
наближено, а
це призведе
до наближеного
обчислення
точок
Розглянемо
як ця похибка
впливатиме
на результат
наступних
кроків. Уведемо
позначення
тоді маємо
різницеве
рівняння
![]()
з
початковими
умовами
(2)
Розв’язок
шукатимемо
у вигляді
для визначення
маємо характеристичне
рівняння
(3)
Лінійно
незалежними
частинними
розв’язками
рівняння (2)
будуть
, де
- корені рівняння
(3).
Довільний
розв’язок (2)
можна
записати у
вигляді
(4)
Сталі С1,С2 можна визначити з початкових умов
![]()
(5)
У разі
точного розв’язування
системи (5)
![]()
тоді
Однак
на практиці
замість
у системі (5)
беремо наближене
значення
і замість (4) з
точними значеннями
С1,С2 = 0 отримаємо
![]()
![]()
Оскільки
то похибка
становитиме
![]()
і
зі збільшенням
n
зростатиме
досить швидко.
Отже, уже для
малих n
точки
відрізнятимуться
від теоретичних,
які можна отримати
лише внаслідок
точних обчислень.
Практичні
підрахунки
також підтвердили
нестійкість
методу. Цей
недолік можна
легко усунути.
Нехай маємо
локалізований
відрізок
і внутрішню
точку
із
обчисленим
значенням
.
Знаходимо точки
золотого поділу
відрізка
![]()

Точку,
яка є далі від
точки
вибираємо за
В
іншому алгоритм
незмінний. За
такої модифікації
метод втрачає
симетричність
і красу в обчисленні,
однак зберігає
стійкість і
повністю відповідає
теоретичним
висновкам.
Постановка задачі
Задача
1. Знайти
для заданої
функції
і заданого
відрізка
.
Припущення
1. Функція
така, що на відрізку
точка
її локального
мінімуму
є точкою абсолютного
мінімуму на
відрізку
.
Алгоритм 1
Початок.
I. Обчислити
константу
(
).
II. Обчислити точки

і значення
.
III. Якщо
,
то покласти
і перейти на
крок IV, інакше
покласти
і перейти на
крок IV.
IV. Покласти
![]()
Основний
цикл. V. Якщо
,
то обчислити
,
і перейти на
крок VI; інакше
покласти
,
і перейти на
крок VII.
VI. Покласти
,
і перейти на крок VIII.
VII. Обчислити
,
і перейти на
крок VIII.
VIII. Якщо
,
то покласти
і перейти на
крок IX; інакше
покласти
і перейти на
крок IX.
IX. Обчислити
.
X. Покласти
і перейти на
крок V.![]()
Теорема
1. Якщо виконується
припущення
1, то послідовність
яка породжена
алгоритмом
1, така, що
![]()
.
Зауваження
1. Довжина відрізку
,
побудованого
по методу золотого
перерізу, на
17% більша довжини
відрізку
,
побудованого
по методу Фібоначі.
Проте метод
золотого перерізу
має наступну
перевагу, що
на кожній його
ітерації доводиться
робити менше
обчислень.
Зауваження 1'. Іноді на практиці комбінують обидва методи: перші кроки роблять по методу золотого перерізу, а коли оптимум достатньо близький, обраховують число m і переходять до методу Фібоначі.
Текст програми
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Menus, TeEngine, Series, ExtCtrls, TeeProcs, Chart;
type
TForm1 = class(TForm)
Button1: TButton;
Edit1: TEdit;
Edit2: TEdit;
Edit3: TEdit;
Label1: TLabel;
Edit4: TEdit;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Memo1: TMemo;
Label5: TLabel;
Chart1: TChart;
Series1: TLineSeries;
procedure Button1Click(Sender: TObject);
procedure FormActivate(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
eps:real;
a,b,ao,bo:real;
alpha:real;
x1,x2:real;
f1,f2:real;
x_opt:real;
implementation
{$R *.dfm}
function f(x:real):extended;
begin
f:=sin(x+1); //zadannja potribnoji fynkchiji !!!
end;
procedure TForm1.FormActivate(Sender: TObject);
begin
Memo1.Lines.Clear;
Memo1.Lines.Add('F(x)= sin(x+1)');
end;
procedure TForm1.Button1Click(Sender: TObject);
var h:real;xx:real; i:integer;
begin
eps:=StrToFloat(Edit1.Text);
ao:=StrToFloat(Edit2.Text);
bo:=StrToFloat(Edit3.Text);
a:=ao; b:=bo;
alpha:=(sqrt(5)-1)/2;
x1:=bo-alpha*(bo-ao);
x2:=ao+alpha*(bo-ao);
f1:=f(x1);
f2:=f(x2);
while abs(a-b)>eps do
BEGIN
if f1>{<}f2 then
begin
b:=x2;
x2:=x1;
f2:=f1;
x1:=b-alpha*(b-a);
f1:=f(x1);
end ELSE
begin
a:=x1;
x1:=x2;
f1:=f2;
x2:=a+alpha*(b-a);
f2:=f(x2);
end;
END;
x_opt:=(a+b)/2;
Edit4.Text:=FloatToStr(x_opt);
{--------------------------------}
xx:=ao;
h:=(bo-ao)/20;
for i:=1 to 20 do
begin
Series1.AddXY(xx,f(xx),'',clblue);
xx:=xx+h;
end;
end;
end.
Результат роботи програми

Рис. 1
Розв’язок вручну:
Розв’язок рівняння в роботі Розв’язок прикладу 2


Отже максимум = -1 при х = ±1, у = 4 – т. мінімума
а мінімум = 0,57 при х = ±2, у =13 – т. максимума
Висновок
Метод золотого перерізу належить до симетричних методів. Використовуючи цю ідею, можна будувати й інші симетричні методи, але як і в методі золотого поділу, їх потрібно досліджувати на стійкість.
Список використаної літератури
Сторнгин Р.Г. Численные методы в многоэкстремальных задачах (Информационно-статистические алгоритмы). – М.: Наука, 1978. –240 с.
Бейко И.В., Бублик Б.Н., Зинько П.Н. Методы и алгоритмы решения задач оптимизации. – К.: Вища школа, 1983. –512 с.
Стахов О.П. За принципом золотої пропорції: перспективний шлях розвитку обчислювальної техніки. Журнал "Вісник Академії наук Української РСР", №1-2, 1990 г.
Ю.В. Васильков, Н.Н. Василькова. «Компютерные технологии вычислений в математическом моделирование» Москва, «финансы и статистика» 2002. – 249 с.
Размещено на