Курсова робота
Порівняльний аналіз методів квадратичної інтерполяції та золотого перетину
Введення
екстемум інтерполяція ітерація
Завданням оптимізації в математиці, інформатиці та дослідженні операцій називається задача знаходження екстремуму (мінімуму або максимуму) цільової функції в деякій області конечномерного векторного простору, обмеженою набором лінійних та/або нелінійних рівностей і/або нерівностей.
Методи квадратичної інтерполяції та золотого перетину належать до методів одновимірної мінімізації.
Метою цих методів є знаходження безумовного мінімуму функцііодной змінної, тобто таку точку, що при
Метод квадратичної інтерполяції заснований на послідовному застосуванні процедури оцінювання з використанням квадратичної апроксимації.
Метод золотого перетину - метод пошуку значень дійсно-значної функції на заданому відрізку. В основі методу лежить принцип поділу в пропорціях золотого перетину. Найбільш широко відомий як метод пошуку екстремуму у вирішенні завдань оптимізації. Інтервал невизначеності ділиться на дві рівні частини так, що відношення довжини великого відрізку до довжини всього інтервалу дорівнює відношенню довжини меншого відрізка до довжини більшого відрізка.
Метою курсової роботи є порівняльний аналіз методів квадратичної інтерполяції та дихотомії.
1. Метод квадратичної інтерполяції
Постановка завдання
Потрібно знайти безумовний мінімум функцііодной змінної, тобто таку точку, що при
Стратегія пошуку
Метод квадратичної інтерполяції (метод Пауелла) ставитися до послідовним стратегіям. Здається початкова точка і за допомогою пробного кроку знаходяться три точки так, щоб вони були якомога ближче до шуканої точці мінімуму. В отриманих точках обчислюються значення функції. Потім будується інтерполяційний поліном другого ступеня, що проходить через наявні три крапки. В якості наближення точки мінімуму береться точка мінімуму полінома. Процес пошуку закінчується, коли отримана точка відрізняється від найкращої з трьох опорних точок не більше ніж на задану величину.
Алгоритм
Признач початкову точку величину кроку? x gt; 0, і - малі позитивні числа, що характеризують точність.
Обчислити =.
Обчислити=і =.
Порівняти з:
а) якщо, покласти =. (рис 1, а).
б) якщо, покласти =. (рис 1, б).
Обчислити =.
Знайти=min {,, =: =.
Обчислити точку мінімуму інтерполяційного полінома, побудованого по трьох точках:
і величину функції (рис 1).
Якщо знаменник у формулі для на деякій ітерації звертається в нуль, то результатом інтерполяції є пряма. У цьому випадку рекомендується позначити і перейти до кроку 2.
Перевірити виконання умови закінчення:
,
Тоді:
а) якщо обидва умови виконані, процедура закінчена і
б) якщо хоча б одна з умов не виконана і,
вибрати найкращу точку і дві точки по обидві сторони
від неї. Позначити ці точки в природному порядку і перейти до
кроці 6;
в) якщо хоча б одна з умов не виконана і, то
покласти і перейти до кроку 2.
2. Метод золотого перетину
Постановка завдання
Потрібно знайти безумовний мінімум функцііодной змінної, тобто таку точку, що при
Стратегія пошуку
Метод відноситься до послідовним стратегіям. Здається початковий інтервал невизначеності і необхідна точність. Алгоритм зменшення інтервалу спирається на аналіз значень функцій у двох точках (див. Рис. 2). Як точок обчислення функції вибираються точки золотого перетину. Тоді з урахуванням властивостей золотого перетину на кожній ітерації, крім першої, потрібно тільки одне нове обчислення функції. Умова закінчення процесу пошуку стандартні: пошук закінчується, коли довжина поточного інтервалу невизначеності виявляється менше встановленої величини.
Алгоритм
0.Задать початковий інтервал невизначеності, точність.
Покладіть
.Вичісліть,
.Вичісліть.
.Сравніть.
а) якщо, то покласти і, (рис. 3а). Перейти до кроку 6.
б) якщо, покласти, і, (рис. 3б).
.Вичісліть і перевірити умова закінчення:
а) якщо, процес пошуку завершується і. В якості наближеного рішення можна взяти середину останнього інтервалу:;
б) якщо, покласти і перейти до кроку 4.
3. Рішення задач
.1 Перелік ...
