Размещено на http://www.allbest.ru/

Зміст

• Теоретична частина 2
• Загальні положення 2
• Метод виключення інтервалів 4
• Метод золотого перетину 5
• Метод Больцано (метод поділу інтервалу навпіл) 8
• Метод рівномірної розбивки 10
• Практична частина 11
• Пакетна реалізація 11
• Програмна реалізація 11

ТЕОРЕТИЧНА ЧАСТИНА

Загальні положення

Функція однієї змінної, що має на інтервалі дослідження один горб (западину) називається унімодальною.

Функція y=f(x) називається зростаючою (спадною) в деякому інтервалі, якщо при x1< x2 виконується нерівність f(x1)< f (x2) (f(x1)> f(x2)).

Якщо диференційована функція на відрізку [а, b] зростає (спадає), то її похідна на цьому відрізку f''(x)<0 (f''(x)>0).

Точка x_о називається точкою локального максимуму (мінімуму) функції f(x), якщо існує окіл точки x_о, для всіх точок якої вірна нерівність f(x)<f(x_о) (f(x)>f(x_о)).

Точки максимуму і мінімуму називаються точками екстремуму, а значення функції в цих точках - її екстремумами.

Необхідна умова екстремуму. Якщо точка x_о є точкою екстремуму функції f(x), то або f'(x_о) = 0, або f'(x_о) не існує. Такі точки називають критичними, причому сама функція в критичній точці визначена. Екстремуми функції слід шукати серед її критичних точок.

Перша достатня умова. Хай x_о - критична точка. Якщо f`(x) під час переходу через точку x_о міняє знак плюс на мінус, то в точці x_о функція має максимум, інакше - мінімум. Якщо під час переходу через критичну точку похідна не міняє знак, то в точці x_о екстремуму немає.

Друга достатня умова. Хай функція f(x) має похідну f `(x) у околиці точки x<sub>о</sub> і другу похідну в самій точці x<sub>о</sub>. Якщо f`(x_о) = 0, f``(x) >0 (<0), то точка x<sub>о</sub> є точкою локального мінімуму (максимуму) функції f(x). Якщо ж f``(x₀)=0, то потрібно або користуватися першою достатньою умовою, або залучати вищі похідні.

На відрізку [а,b] функція в = f(x) може досягати найменшого або найбільшого значення або в критичних точках, або на кінцях відрізку [а,b].

Для того, щоб нам знайти екстремум деякої функції, ми знаходимо першу похідну та перевіряємо необхідну умову існування екстремуму - f`(x)=0 чи не існує. Далі ми перевіряємо першу достатню умову. Таким чином ми знайдемо екстремум нашої функції. Але іноді через незручний чи занадто громіздкий вигляд функції ми не можемо використовувати класичний метод. Аналітично вирішується лише незначна частина задач, тому розглядаються і деякі чисельні алгоритми. Чисельні алгоритми запрограмовані, як правило, у математичних комп'ютерних пакетах, які забезпечують високу точність і швидкість знаходження екстремуму, але, на жаль, не завжди знаходять глобальний екстремум. Серед таких пакетів слід відзначити математичні програми Maple, MatLab, Mathematica. Але це не означає, що для знаходження екстремумів слід користуватися ними, не маючи поняття про математичні алгоритми.

Існує низка інших методів, що допомагають у вирішенні даної задачі, які в загальному вигляді поділяють на:

* локальні методи: сходяться до якого-небудь локальному екстремуму функції (у разі унімодальному функції, цей екстремум єдиний, і буде глобальним максимумом / мінімумом).

* глобальні методи: мають справу з багатоекстремальними функціями (при глобальному пошуку основним завданням є виявлення тенденцій глобальної поведінки функції).

Існуючі в даний час методи пошуку екстремуму можна розбити на три великі групи:

1. детерміновані;

2. випадкові (стохастичні);

3. комбіновані.

Серед всіх найбільш відомими є:

· метод рiвномiрної розбивки;

· метод випадкового пошуку;

· методи виключення iнтервалiв:

- метод половинного ділення;

- метод золотого перетину;

- метод Фiбоначчi;

· методи полiномiальної апроксимації:

- метод квадратичної апроксимації;

- метод кубічної апроксимації;

· методи з використанням похідних:

- метод Ньютона-Рафсона;

- метод середньої точки;

- метод сiчних.

Метод виключення інтервалів

Фактично всі одновимірні методи пошуку, які використовуються на практиці, засновано на припущенні, що досліджувана функція в припустимій області принаймні має властивість унімодальності. В нашому випадку ця властивість присутня. Корисність її визначається тим фактором, що для унімодальної функції порівняння значень у двох різних точках інтервалу пошуку дозволяє визначити, у якому із заданих двома зазначеними точками під інтервалів точка екстремуму відсутня.

Теорема: нехай функція унімодальна на замкненому інтервалі , а її мінімум досягається в точці х*. Розглянемо точки х₁ і х₂, які розміщені в інтервалі в такий спосіб, що a < x₁ <x₂ <b. Порівнюючи значення функції в точках х₁ і х₂, можна зробити наступні висновки:

1. Якщо >, то точка мінімуму не лежить в інтервалі , тобто (див. мал. (а)).

2. Якщо <, то точка мінімуму не лежить в інтервалі (), тобто (див. мал. (б)).



Метод золотого перетину

Метод золотого перетину - метод пошуку дійсних значень функції на заданому відрізку. В основі методу лежить принцип поділу в пропорціях золотого перетину.

Нехай дано функція . Тоді для того, щоб знайти певне значення цієї функції на заданому відрізку, що відповідає критерію пошуку (нехай це буде мінімум), що розглядається відрізок ділиться в пропорції золотого перерізу в обох напрямках, тобто вибираються дві точки x₁ і x₂ такі, що:



На першій ітерації заданий відрізок ділиться двома симетричними щодо його центру точками і розраховуються значення в цих точках.

Після чого той з кінців відрізка, до якого серед двох заново поставлених точок ближче виявилася та, значення в якій максимальне (для випадку пошуку мінімуму) чи мінімальне (для випадку пошуку максимуму), відкидають. На наступній ітерації, беручи до уваги вказані раніше властивості золотого перерізу, вже треба шукати лише одну нову точку. Процедура триває доти, доки не буде досягнута задана точність.

Введемо позначення:

¹ = b-a - початковий інтервал;

² - інтервал, отриманий після зменшення інтервалу ¹ шляхом відкидання його лівого чи правого підінтервалу.

^К+1 - інтервал, отриманий після зменшення інтервалу ^К.

Розглянемо тепер метод золотого перетину формально. Як згадувалося вище, золотий перетин відрізка проводиться двома симетрично розташованими точками х₁ і х₂, тобто (b-a)/(b-x₁)=(b-x₁)/(x₁-a)= і (b-a)/(x₂-a)=(x₂-a)/(b-x₂)== (1+5)/21.618. До того ж, точка х₁ в свою чергу проводить золотий перетин відрізку [a, x₂], тобто (x₂-a)/(x₁-a) = (x₁-a)/(x₂-x₁) = . Аналогічно, точка х₂ проводить золотий перетин відрізка [x₁, b].

Отже, метод золотого перетину полягає в тому, що довжини послідовних інтервалів у фіксованому відношенні:

¹/² = ²/³ = … =.

Із співвідношень ^К/^K+1 = ^K+1/^K+2 = і ^K = ^K+1 + ^K+2 отримуємо:

^K/^K+1 = (^K+1+^K+2)/^K+1=1+^K+2/^K+1, = 1 + 1/ чи ² - -1 = 0.

Коренем цього рівняння є золотий перетин

=(5+1)/2 1.618 = 1/ = (5-1)/2 0.618.

Можна записати формули для точок х₁ і х₂, що роблять золотий перетин на інтервалі [a, b]:

x₁ = a+(1-)(b-a) x₂ = a+(b-a)

Алгоритм:

Крок 1. Задаються початкові межі відрізка і точність , =(5-1)/2

Крок 2. Обчислити x₁ =b - (b-a); x₂ =a + (b-a)

Крок 3. Обчислити y₁ = f(x₁); y₂ = f(x₂)

· Якщо , то для подальшого поділу залишають інтервал [a, x₂] та виконують наступне:

b: = x₂; x₂: = x₁; y₂: = y₁; x₁ := b-(b-a) y₁ := f(x₁)

· Інакше - для подальшого ділення залишають інтервал [x₁, b] та виконують наступне:

a := x₁; x₁ := x₂; y₁ := y₂; x₂ := a+(b-a); y₂ :=f(x₂);



Крок 4. Порівняння довжини інтервалу невизначеності із заданою точністю : якщо (b-a), то покласти x*:= (b+a)/2 (точка мінімуму), інакше (якщо (b-a)>) - перейти до кроку 3.

Метод Больцано (метод поділу інтервалу навпіл)

Розглянутий метод дозволяє виключати точно половину інтервалу на кожній ітерації. Іноді цей метод називають точковим пошуком на рівних інтервалах, оскільки його реалізація заснована на виборі трьох пробних точок, які рівномірно розподілені в інтервалі пошуку. Нижче приводиться опис основних кроків пошукової процедури, орієнтованих на знаходження точки мінімуму функції в інтервалі .

Графічні ілюстрації до методу розподілу інтервалу навпіл

Алгоритм:

Крок 1. Покласти і . Обчислити значення .

Крок 2. Покласти і . Зауважимо, що точки поділяють інтервал на 4 рівні частини. Обчислити значення і .

Крок 3. Порівняти і .

· Якщо < (мал. (а)), виключити інтервал (), поклавши . Середньою точкою нового інтервалу пошуку стає точка х₁. Отже, необхідно покласти . Перейти до кроку 5.

· Якщо (мал. (б)), перейти до кроку 4.

Крок 4. Порівняти і .

· Якщо <, виключити інтервал , поклавши . Через те, що середньою точкою нового інтервалу стає точка х₂ - покласти . Перейти до кроку 5.

· Якщо , виключити інтервали і (). Покласти і . Відзначимо, що продовжує залишатися середньою точкою нового інтервалу. Перейти до кроку 5.

Крок 5. Обчислити . Якщо величина мала, закінчити пошук. Інакше - повернутися до кроку 2.

Зауваження:

1. На кожній ітерації алгоритму виключається точно половина інтервалу пошуку.

2. Середня точка послідовно отриманих інтервалів завжди збігається з однією з пробних точок чи , знайдених на попередній ітерації. Отже, на кожній ітерації потрібно не більше двох обчислень значення функції.

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

4. З усіх методів пошуку на рівних інтервалах (дво-, три-, чотириточковий і т. д.) триточковий пошук або метод розподілу інтервалу навпіл, відрізняється найбільшою ефективністю.



Метод рівномірної розбивки

Рівномірний пошук є прикладом одновимірного пошуку, коли точки, в яких обчислюється значення функції, вибираються заздалегідь. Початковий відрізок [a0, b0] ділиться на рівні відрізки довжиною d сіткою з n точок a0 + dk для k = 1,..., n і тоді b0 = a0 + (n +1)?d. Функція f (x) обчислюється в кожному з n вузлів отриманої сітки, і вибирається точка x, в якій вона має мінімальне значення. Цей метод зазвичай використовується для початкової оцінки відрізка [X - d, x + d], якому належить мінімум. Для досягнення високої точності в цьому методі необхідно здійснити велику кількість обчислень функції. Проте його перевагою є можливість пошуку глобальних екстремумів функції, коли немає впевненості в правильному визначенні початкового відрізка унімодальності.



ПРАКТИЧНА ЧАСТИНА

Знайти екстремуми функції f(x) = 15x²+ 36x - 14 аналітично.

Розв`язок.

f(x) =30x +36

30х+36=0;

5х= -6;

х= -1,2 - критична точка функції. Екстремум може бути лише в цій точці.

Знайдемо другу похідну:

- функція у вточці має глобальний мінімум.

Так як при переході через точку x = -1,2 похідна змінює знак з - на +, то в цій точці у функції мінімум. Обчисливши значення функції в точці x = -1,2, знайдемо екстремум функції:

Пакетна реалізація

Пакетна реалізація здійснена за допомогою пакету Maple.



Програмна реалізація

унімодальна функція максимум екстремум

Програмна реалізація здійснена на мові С.

#include <stdio.h>

#include <conio.h>

#include <math.h>

double f(double x)

{

return 15*x*x+36*x-14;

}

//na otrezke [a;b] funkciya dolgna bit unimodalnoi

double GoldenCut(double f(double),double a, double b, double eps)

{

double x1,x2,y1,y2,tau;

tau = (sqrt(5)-1)/2.0;

x1 = b-(b-a)*tau;

x2 = a+(b-a)*tau;

y1 = f(x1);

y2 = f(x2);

do{

if(y1<=y2)

{

b = x2;

x2 = x1;

y2 = y1;

x1 = b-(b-a)*tau;

y1 = f(x1);

}

else

{

a = x1;

x1 = x2;

y1 = y2;

x2 = a+(b-a)*tau;

y2 = f(x2);

}

}while((b-a)>eps);

return (b+a)/2.0;

}

//na otrezke [a;b] funkciya dolgna bit unimodalnoi

double Bolcano(double f(double),double a, double b, double eps)

{

double x1,x2,xm,L;

xm = (a+b)/2.0;

L = b-a;

do{

x1 = a+L/4.0;

x2 = b-L/4.0;

if(f(x1)<f(xm))

{

b = xm;

xm = x1;

}

else if(f(x2)<f(xm))

{

a = xm;

xm = x2;

}

else

{

a = x1;

b = x2;

}

L = b-a;

}while (fabs(L)>eps);

return (b+a)/2.0;

}

//na otrezke [a;b] funkciya dolgna bit unimodalnoi

double EquDiv(double f(double),double a, double b, double dx)

{

double min, i;

min = a;

for(i=a;i<b;i+=dx)

{

if(f(i)<f(min))

min = i;

}

return min;

}

void main(void)

{

double x,a,b;

clrscr();

puts("Vvedit a, b");

scanf("%lf%lf",&a,&b);

x = GoldenCut(f,a,b,0.0001);

printf("GoldenCut: f(%6.4lf) = %6.4f\n",x,f(x));

x = Bolcano(f,a,b,0.0001);

printf("Bolcano : f(%6.4lf) = %6.4lf\n",x,f(x));

x = EquDiv(f,a,b,0.0001);

printf("EquDiv : f(%6.4lf) = %6.4lf\n",x,f(x));

getch();

}

Размещено на Allbest.ru