Метод золотого перерізу для пошуку екстремумів функцій
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
КАФЕДРА КОМП’ЮТЕРНИХ СИСТЕМ І МЕРЕЖ
КУРСОВА РОБОТА
З курсу “Обчислювальна техніка і програмування”
на тему “Метод золотого перерізу для пошуку екстремумів функцій”
Ужгород 2009
Зміст
Вступ
1. Теоретичні відомості
1.1 Мінімізація функції однієї змінної
1.2 Метод золотого поділу відрізка
2. Постановка задачі
3. Текст програми
4. Результат роботи програми
Висновок
Список використаної літератури
Вступ
Через 2500 років після стародавніх греків в сучасній науці на передній план знов вийшли три «вічні» проблеми (рахунки, вимірювання і гармонії систем), які стояли біля витоків створення математики і точних наук. Авторові вдалося об’єднати нові математичні теорії, дані для вирішення цих проблем, в струнку математичну теорію, названу «Математикою Гармонії». У основі цій математики лежить «Золотий Перетин»! Ця нова математика може стати початком нового етапу в розвитку «Вищої Математики» і основою для створення нової науки — «Науки про Гармонію Систем». Вона може також стати початком реформи математичної освіти і нових комп’ютерних проектів, заснованих на Золотому Перетині.
Ще однією тенденцією сучасних наукових досліджень є повернення до проблемі гармонії систем , яка стояла в центрі античної науки; у зв’язку з цим виникає інтерес до знаменитого «Золотого Перетину», який зіграв в розвитку людської культури не меншу роль, чим число π, яке лежить в основі тригонометрії. Іоганн Кеплер назвав Золотий Перетин одним з «скарбів геометрії» і порівняв його із знаменитою «Теоремою Піфагора». Оцінюючи роль Золотого Перетину у розвитку старогрецької культури, геніальний російський філософ Олексій Лосев якось сказав «З погляду Платона, та і взагалі з погляду всієї античної космології, світ є якесь пропорційне ціле, таке, що підкоряється закону гармонійного ділення — Золотого Перетину».
Із Золотим Перетином тісно пов’язано інше математичне відкриття, зроблене в 13-му столітті видатним італійським математиком Леонардо Пізано (по прізвиську Фібоначчі).
Йдеться про так звані числа Фібоначчі, які пізніше були вибрані предметом математичного дослідження групою американських математиків, що організували в 1963 р. так звану Фібоначчі-асоціацію. Золотий Перетин і пов’язані з ними числа Фібоначчі пронизує всю історію культури. Піраміда Хеопса, скульптурні і архітектурні пам’ятники грецької культури і епохи Ренесансу, неперевершена «Джоконда» Леонардо да Вінчі, картини Рафаеля Шишкіна і Костянтина Васильова, етюди Шопена, музика Бетховена, Чайковського і Белли Барток, «Модулор» Корбюз’є, соснові шишки, кактуси, ананаси, морські зірки і раковини, Єгипетський календар, квазікристали Шехтмана — ось далеко не повний перелік «творів» природи, науки і мистецтва, наповнених чудовою гармонією, в основі якої лежить Золотий Перетин!
Золотий Перетин займає значне місце в сучасних дослідженнях кількісних співвідношеннях живої і неживої природи. Яскраві відкриття сучасної науки — квазікристали Шехтмана, нова геометрична теорія філлотаксиса українського архітектора Боднара, закон структурної гармонії систем білоруського філософа Сороко, резонансна теорія Сонячної системи російського астронома Бутусова і інші сучасні наукові відкриття, засновані на Золотому Перетині, поза сумнівом мають «стратегічне» значення для розвитку сучасної науки. Необхідно відзначити також великий інтерес сучасної теоретичної фізики золотому перетину. Іншими словами, в даний час неможливо уявити собі подальший розвиток наук про природу без Золотого Перетину. І є надія, що і математична освіта також не залишиться в стороні від Золотого Перетину.
1. Теоретичні відомості
З задачами пошуку екстремуму однієї змінної частково вивчають у курсі математичного аналізу. На перший погляд ці задачі видаються простими і добре вивченими. Однак методи диференціального числення мають обмежене застосування і не завжди зручні для реалізації на ЕОМ. Хоча в останні десятиліття з’явилися набагато зручніші методи для використання на ЕОМ, які вимагають меншого об’єму чисельної роботи, але тим не більше цю область екстремальних задач не можна рахувати завершеною. Роботи, присвячені для нових методів екстримізації однієї змінної, продовжують з’являтися на сторінках математичних книг і журналів. Ми тут зупинимося на декотрих найбільш відомих методах, які достатньо добре себе проявили на практиці.
1.1 Мінімізація однієї змінної
Задача мінімізації однієї змінної має такий вигляд де
Залежно від функції і множини множина розв’язків , може містити одну, декілька, або навіть і безмежну кількість точок. Можливі випадки, коли
Приклад 1 нехай , при і На множині мінімальне значення дорівнює 0, одна точка. Якщо то — три точки, у випадку — зчисленна множина точок, а для
Зазначимо таке якщо то нижня межа і min функції збігаються У цьому випадку говорять,що на досягає своєї нижньої межі,завжди існує, а не завжди має сенс.
Означення I Послідовність називають мінімізаційною для функції на множині , якщо
Означення II Послідовність збігається до не порожньої множини , якщо де — відстань від до множини.
Якщо то завжди існує мінімізаційна послідовність, яка збігається до . Однак не кожна мінімізаційна послідовність буде збігатися до .
Приклад 2
У нашому випадку Послідовність для є мінімізаційною
хоча
У разі розв’язування задач мінімізації на множині розрізнятимемо два типи задач
1) Необхідно визначити
2) Потрібно визначити і точку
У першому випадку можливий варіант у другому – обов’язково . Отримати точний розв’язок задачі першого,або другого типів практично неможливо. Тому в першому випадку за беруть, для мінімізаційної послідовності , деяке значення при достатньо великому . Для задач другого типу необхідно побудувати мінімізаційну послідовність ,яка збігається до , і за наближення до і взяти, відповідно і при достатньо великому . Під час розв’язування задач другого типу в окремих випадках треба виконувати додаткові дослідження.
У випадку розв’язування задачі можна використовувати класичний метод. Нехай функція кусковогладка на [a,b], тобто може існувати лише скінчена кількість точок, де має розрив першого роду, або неперервна, однак не має похідної. У цьому разі точкою екстремуму функції на [a,b] може бути лише та точка, для якої виконується одна з умов
1). має розрив першого роду;
2). неперервна, однак похідна не існує;
3).
4). х – точка на кінці відрізка;
Ці точки прийнято називати підозрілими на екстремум. На жаль, класичний метод має досить вузьке застосування. Обчислення похідної в окремих випадках може бути трудомісткими, або взагалі неможливо обчислити.
Крім того, розв’язування рівняння може бути не менш складним, ніж вихідна задача. Тому на практиці використовують методи, які дають змогу безпосередньо знайти мінімум . Для цього треба зробити обмеження на класи функції.
Означення III. Функція є унімодальною на проміжку , якщо існують такі числа , що
1). строго монотонно спадає при ;
2). строго монотонно зростає при ;
3). при , тобто
Випадки, коли один з відрізків , , або два одночасно вироджуються в точку, можливі. Якщо , то є строго унімодальною на [a,b].
Означення IV. Відрізок є локалізований, якщо і значення обчислено не більше, ніж в одній точці .
1.2 Метод золотого поділу відрізку
Означення V. Золотим поділом відрізка на дві неоднакові частини називають поділ, за якого відношення довжини всього відрізка до довжини довшої його частини дорівнює відношенню довжини довшої частини відрізка до довжини його коротшої частини.
У випадку відрізка одиничної довжини , звідси і .
Отже, довший відрізок має довжину , а коротший .
У випадку довільного відрізку [a,b] точками золотого перерізу є
, (1)
Виявляється, що точки х1,х2 – це точки золотого поділу для відрізків відповідно Використовуючи властивість точок золотого поділу, можна запропонувати для розв’язування задачі (1.1) метод золотого поділу відрізка. Алгоритм цього методу такий.
Приймемо виберемо точки
золотий поділ відрізок екстремум
й обчислимо значення . Якщо , то приймемо , в іншому випадку Побудований відрізок є локалізований ,
і відомо значення Нехай уже визначено точки , локалізований відрізок , обчислено відповідні значення функції
.У цьому випадку
,
Відома точка , яка виконує золотий переріз відрізка , і обчислено значення мінімізаційної функції в цій точці За іншу точку вибираємо , яка є другою точкою золотого перерізу відрізка
У цій точці обчислюємо і визначаємо локалізований відрізок , а саме (будемо вважати, що ) у випадку приймемо , а у випадку (випадок розглядається аналогічно). Новий відрізок є локалізований
Точка — це точка золотого поділу відрізка і в цій точці обчислено значення функції Якщо кількість обчислень функції не обмежено,то цей процес можна продовжити доти, доки не виконається нерівність — задана точність обчислень. Якщо кількість обчислень функції задана і дорівнює n, то після отримання локалізованого відрізка обчислення припиняємо і на розв’язок задачі другого типу беремо — наближення до множини з похибкою
Якщо враховувати аналогічну оцінку в методі поділу відрізка наполовину
Отже, навіть для малих n метод золотого поділу ефективніший, ніж метод поділу відрізка наполовину. Недоліком методу золотого поділу в запропоновану вигляді є його нестійкість. Розглянемо числову реалізації методу. Обов’язково число буде задано наближено, а це призведе до наближеного обчислення точок Розглянемо як ця похибка впливатиме на результат наступних кроків. Уведемо позначення тоді маємо різницеве рівняння з початковими умовами (2)
Розв’язок шукатимемо у вигляді для визначення маємо характеристичне рівняння (3)
Лінійно незалежними частинними розв’язками рівняння (2) будуть , де — корені рівняння (3). Довільний розв’язок (2) можна записати у вигляді
(4)
Сталі С1,С2 можна визначити з початкових умов
(5)
У разі точного розв’язування системи (5)
тоді Однак на практиці замість у системі (5) беремо наближене значення і замість (4) з точними значеннями С1,С2 = 0 отримаємо
Оскільки то похибка становитиме
і зі збільшенням n зростатиме досить швидко. Отже, уже для малих n точки відрізнятимуться від теоретичних, які можна отримати лише внаслідок точних обчислень. Практичні підрахунки також підтвердили нестійкість методу. Цей недолік можна легко усунути. Нехай маємо локалізований відрізок і внутрішню точку із обчисленим значенням . Знаходимо точки золотого поділу відрізка
Точку, яка є далі від точки вибираємо за В іншому алгоритм незмінний. За такої модифікації метод втрачає симетричність і красу в обчисленні, однак зберігає стійкість і повністю відповідає теоретичним висновкам.
2. Постановка задачі
Задача 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 і переходять до методу Фібоначі.
3. Текст програми
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.
4. Результат роботи програми
Рис. 1
Розв’язок вручну
Розв’язок рівняння в роботі Розв’язок прикладу 2
Отже максимум = -1 при х = ±1, у = 4 – т. мінімума
а мінімум = 0,57 при х = ±2, у =13 – т. максимума
Висновок
Метод золотого перерізу належить до симетричних методів. Використовуючи цю ідею, можна будувати й інші симетричні методи, але як і в методі золотого поділу, їх потрібно досліджувати на стійкість.
Список використаної літератури
1. Сторнгин Р.Г. Численные методы в многоэкстремальных задачах (Информационно-статистические алгоритмы). – М. Наука, 1978. –240 с.
2. Бейко И.В., Бублик Б.Н., Зинько П.Н. Методы и алгоритмы решения задач оптимизации. – К. Вища школа, 1983. –512 с.
3. Стахов О.П. За принципом золотої пропорції перспективний шлях розвитку обчислювальної техніки. Журнал Вісник Академії наук Української РСР», №1-2, 1990 г.
4. Ю.В. Васильков, Н.Н. Василькова. «Компютерные технологии вычислений в математическом моделирование» Москва, «финансы и статистика» 2002. – 249 с.
«