Мітки: мінімізація функції

Мінімізація функції однієї змінної методом рівномірного пошуку в середовищі програмування delphi

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

Панель інструментів: складається з п’яти полів типу TEdit, два з яких відповідають за значення кінців інтервалу на якому відшукуються точка мінімуму, і три що залишилось, відповідають за точність обчислювального процесу, кількість відрізків, на які розбивається інтервал невизначеності та мінімізуюча функцію; дві кнопки типу TButton одна з яких безпосередньо реалізує алгоритми відшукання точки мінімуму та друга — видаляє всі введені користувачем значення і готує проект до нового прикладу; один компонент типу TMemo, головним призначенням якого є вивід результату роботи програми.
Область графічного представлення: містить компонент типу TChart, який відображає графік мінімізуючої функції і з допомогою якого можна провірити правельність роботи програми.

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

Мінімізація функції однієї змінної методом рівномірного пошуку

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

Використання методу градієнтного спуску для розв’язку СНР в середовищі програмування Delphi

На відміну від систем лінійних рівнянь не існує прямих методів для розв’язку систем нелінійних рівнянь (СНР) загального вигляду. Лише в окремих випадках систему нелінійних рівнянь можна розв’язати безпосередньо. Наприклад, для випадку двох рівнянь іноді вдається виразити одне невідоме через інше і таким чином звести задачу до вирішення одного нелінійного рівняння відносно однієї невідомої. Для вирішення систем нелінійних рівнянь, зазвичай, використовують ітераційні методи, серед яких найпоширенішими є метод простої ітерації та метод Ньютона. Проте використання даних методів вимагає вибір початкового наближення, при якому б ітераційний процес збігався до шуканого розв’язку. Для того, щоб уникнути даної проблеми, задачу на знаходження розв’язку СНР зводять до задачі на знаходження точки мінімуму функції декількох змінних, координати якої і являтимуться розв’язком СНР. Саме такий підхід і реалізує розглядуваний нами delphi-проект. В якості методу, для визначення точки мінімуму програма використовує метод градієнтного спуску. Більш детальну інформацію про застосування даного методу для рішення систем нелінійних рівнянь можна знайти за посиланням Розв’язок систем нелінійних рівнянь за методом градієнтного спуску.

Розв’язок системи нелінійних рівнянь за методом градієнтного спуску

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

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

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

Мінімізація функції багатьох змінних використовуючи метод Ньютона (метод Ньютона на Delphi)

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

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

У поле “Функція” – X*X+Y*Y-16.
У поле “Список змінних” – X;Y.
У поле “Початкове значення” – 0;0.

Після того, як всі поля заповнено, головна форма набуде наступного вигляду: