МІНІСТЕРСТВООСВІТИ І НАУКИ УКРАЇНИ
УЖГОРОДСЬКИЙНАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
КАФЕДРАКОМП’ЮТЕРНИХ СИСТЕМ І МЕРЕЖ
КУРСОВАРОБОТА
Зкурсу “Обчислювальна техніка і програмування”
натему: “Метод золотого перерізу для пошуку екстремумів функцій”
Ужгород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;
procedureButton1Click(Sender: TObject);
procedureFormActivate(Sender: TObject);
private
{ Privatedeclarations }
public
{ Publicdeclarations }
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}
functionf(x:real):extended;
begin
f:=sin(x+1); //zadannjapotribnoji fynkchiji !!!
end;
procedureTForm1.FormActivate(Sender: TObject);
begin
Memo1.Lines.Clear;
Memo1.Lines.Add('F(x)=sin(x+1)');
end;
procedureTForm1.Button1Click(Sender: TObject);
varh: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);
whileabs(a-b)>eps do
BEGIN
iff1>{
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 20do
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 с.