Page 80 - 6449

Методи пошуку екстремуму функцій без використання похідних
базується на двох основних означеннях:
1. Функція f(x) називається унімодальною на відрізку [a;b], якщо на
цьому відрізку існує єдиний екстремум функції, що визначається в єдиній
точці, або на єдиному інтервалі, що міститься на відрізку [a;b].
2. Відображення f(x) називається стискуючим на відрізку [a;b], якщо

для будь яких двох точок , xx  [a , ] b виконується нерівність:
1 2
f (x )  f (x )  xc  x , c ) 1 , 0 ( (3.24)
1 2 1 2
При пошуку екстремуму функції f(x), яка є унімодальною на
відрізку [a;b], будується стискуюче відображення, яке відрізок [a;b]
переводить у відрізок [a k;b k], такий що
a  b   (3.25)
k k
де ε – точність з якою потрібно знайти екстремум. Розглянемо
кілька найбільш відомих алгоритмів знаходження екстремуму.

1 Метод ділення відрізка навпіл
Нехай ставиться задача знаходження екстремуму функції f(x) на
інтервалі (a;b], причому на вказаному інтервалі функція є унімодальною
(рис. 3.3). На вказаному інтервалі знаходимо дві точки:
a  b a  b
x   ;  x   ,  0 (3.26)
1 2
2 2
f(x)

δ δ
0 a x1 x2 b x
Рисунок 3.3 – Унімодальна функція

Не порушуючи узагальненість викладання, вважатимемо, що
знаходиться мінімум f(x). Знаходиться значення f(x 1) та f(x 2).
)
– якщо f (x 1 )  f (x 2 , то a : x ; b : b (3.27)
1
)
– якщо f (x 1 )  f (x 2 то a : a ; b : x 2
Таким чином, точка в якій значення функції менше, залишається
всередині відрізка пошуку. Величина параметру δ залежить від величини
відрізка [a k;b k], де a k,b k – границі відрізка пошуку на k-ому кроці
ітераційної процедури. Кількість обчислень значень функції f(x) необхідна
для знаходження екстремуму з точністю ε, становить:

80