Наближене розв’язання рівнянь половинного ділення

Розглянемо метод розв’язування одновимірних задач, а саме: метод дихотомії (метод половинного ділення).

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

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

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

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

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

Дамо визначення унімодальної функції при пошуку мінімуму.

Неперервна функція називається унімодальною на відрізку якщо:

· точка локального мінімуму функції належить відрізку ;

· для довільних двох точок відрізка х₁ і х₂, взятих по одну сторону від точки мінімуму, точці х₁ більш близькій до точки мінімуму відповідає менше значення функції, тобто при або при справедлива нерівність .

Достатня умова унімодальності функції на відрізку ґрунтується на наступній теоремі:

Якщо функція двічі диференційована на відрізку і в будь-якій точці цього відрізка, то - унімодальна функція на відрізку .

Відмітимо, що умова визначає множину точок, на якій функція являється опуклою вниз. Умова ж визначає опуклу вгору функцію, яка на відрізку має максимум і також являється унімодальною.

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

;

.

Константа повинна бути меншою допустимої кінцевої довжини відрізка, Δk= b_k- a_k > 0.

Потім обчислюють значення функції в цих точках y₁=f(x₁) і y₂=f(x₂) і в залежності від їх співвідношення нові межі відрізка унімодальності [a₁, b₁] будуть наступні:

• y₁ < y₂, a₁=a₀ і b₁=x₂ ;

• y₁ > y₂, a₁=x₁ і b₁=b₀ ;

• y₁ = y₂, a₁=x₁ і b₁= x₂ .

В цьому звуженому проміжку [a₁, b₁] знову розраховуються дві точки х₁⁽¹⁾ і х₂⁽¹⁾, симетричні відносно його середини і значення функції в цих точках. Процедура буде продовжуватись до тих пір, поки не буде виконуватись умова Δk = b_k-a_k ≤ ε, де ε – точність пошуку, і тоді в якості точки локального мінімуму можна наближено прийняти середину відрізку .

Назва методу половинного ділення мотивована тим, що якщо величина ε достатньо мала, то довжина відрізка унімодальності (b – a) зменшується майже вдвічі.