Координати середини відрізка
Нехай дано точки 
і 
. Необхідно знайти точку 
, що поділяє відрізок 
навпіл, тобто 
.
Графічне представлення алгоритму знаходження координатів середини відрізка
Для цього, побудуєом два трикутники 
і 
. Вони рівні за стороною і двома кутами, а тому 
. Записавши дану рівність у координатній формі отримаємо лінійне рівняння 
, розв'язком якого буде вираз для обчислення координати 
, середини відрізка :
Поділ відрізка у заданому відношенні
Нехай дано точки 
і 
та додатні числа 
і 
. Необхідно знайти точку 
, що поділяє відрізок 
у відношенні 
, тобто 
.
Графічне представлення алгоритму поділу відрізка у заданому відношенні
Для цього, на першому кроці, побудуємо трикутники 
і 
. Вони подібні за двома кутами, а тому 
. Звідси, виходячи з того, що 
і 
, та скориставшись формулою (1), отримаємо:
Мінімізація функції однієї змінної методом дихотомії в середовищі Delphi(1)
В даній темі розглядається програмна реалізація алгоритму знаходження мінімального значення унімодальної функції на заданому інтервалі і з заданою точністю. В якості рівняння, на якому будемо перевіряти працездатність алгоритму виступає рівняння виду: 
. Інтервал, на якому будемо шукати екстремум візьмемо 
, і точність, якої необхідно досягнути буде 
. Для реалізації поставленого завдання використовується алгоритм методу дихотомії.
Інтерфейс програми, яка реалізує метод дихотомії
Мінімізація функції однієї змінної методом дихотомії
Нехай дано функцію 
, яка є унімодальною на проміжку 
. На даному проміжку необхідно знайти точку мінімуму функції з заданою точністю 
. Для цього, використовуючи наступні формули, обчислюємо точки 
та 
:
де 
. Після чого обчислюємо значення функції в знайдених точках 
, 
і порівнюємо їх між собою. Якщо 
то значення правої межі інтервалу невизначеності змістимо на значення точки , тобто 
. В протилежному випадку, якщо 
то змінюємо значення лівої межі інтервалу невизначеності на значення точки (
).
Графічне представлення методу дихотомії
Мінімізація функції однієї змінної методом Фібоначчі на Delphi(1)
Програма використовує алгоритм методу Фібоначчі, для того, щоб знайти мінімальне значення унімодальної функції 
(
), на інтервалі 
(
). Згідно з методом Фібоначчі, на першому кроці проводяться два обчислення значень в точках 
та 
, розташованих симетрично відносно середини відрізка . Далі, за результатами обчислень одна з частин відрізка 
або 
відкидається. При цьому, одна з точок або отримана в результаті обчислень на попередньому кроці залишається всередині нового інтервалу невизначеності. Тому, на кожному наступному кроці, положення точки чергового обчислення, згідно алгоритму, вибирають симетрично відносно точки, яка залишилася. Таким чином, на першому кроці виконуємо обчислення значень функції в двох точках, а на кожному наступному кроці — лише в одній точці. Процес обчислень закінчується в тому випадку, коли довжина інтервалу невизначеності стане меншою деякого заданого числа 
(
).
Інтерфейс програми, яка використовуючи метод Фібоначчі знаходить мінімум унімодальної функції
Мінімізація функції однієї змінної методом Фібоначчі
Алгоритм пошуку мінімуму функції 
на відрізку 
при реалізації методу Фібоначчі подібний до алгоритму методу золотого перетину. На початку вибирається мінімальне з чисел Фібоначі, що задовольняє умову:
де 
— довжина вихідного інтервалу, на якому здійснюємо пошук мінімум функції; 
— похибка визначення екстремуму; 
— послідовність чисел Фібоначчі, які обчислюються за наступною формулою:
Тобто, в рузультаті використання даної рукурентної формули ми отримуємо наступну послідовність чисел: 
Пошук мінімуму функції однієї змінної методом золотого перетину на Delphi
Метод золотого перетину, використовується для пошуку мінімуму функції однієї зміннї на деякому відрізку 
. Основна ідея даного методу полягає в наступному: якщо точки 
і 
(де 
) розташовані на і 
, то на відрізку 
є хоча б один мінімум функції . Аналогічно, якщо
, то на відрізку 
є хоча б один мінімум. В результаті отримуємо новий відрізок, і якщо для нього повторити зазначену процедуру, то можна знову зменшити його, і таким чином ще більше наблизитись до точки мінімуму.
Метод золотого перетину володіє стабільною лінійною швидкістю збіжності, що не залежить від рельєфу функції . Якщо функція обмежена знизу, то метод завжди знайде мінімум. Якщо функція має кілька мінімумів, метод зійдеться до одного з них (не обов'язково до глобального мінімуму) . Створена програма використовуючи метод золотого перетину знаходить мінімум функції 
на інтервалі 
.
Інтерфейс програми Метод золотого перетину
Загрузка ...