1. Індивідуальне завдання
Обчислити мінімум функції F (x) = L (x 1 ) x 2 -2.5L (x 2 ) x-3 на відрізку [a; b] з точністю Оµ.
L (x 1 ), L (x 2 ) значення інтерполяційного многочлена, побудованого для таблично заданої функції f (x) в точках x 1 , x 2 .
Вихідні дані:
a = 0; b = 2;
x 1 = 0.041770;
x 2 = 0.587282;
Оµ = 10 -4 ;
x
0
0.1
0.2
0.3
0.4
0.5
0.6
f (x)
1.858652
1.851659
1.851401
1.848081
1.841914
1.833125
1.821948
2. Постановка завдання та формалізація
Для вирішення поставленого завдання необхідно розробити програмні модулі, що виконують наступні дії:
- головний модуль, який отримує вихідні дані (таблично задану f (x), a, b, x 1 , x 2 , Оµ), що передає їх на обробку і виводить проміжні і кінцеві результати (L (x 1 ), L (x 2 ), знайдений мінімум функції)
- модуль пошуку значення інтерполяційного многочлена L (x 1 ), L (x 2 )
- модуль пошуку мінімуму функції F (x) чисельним методом, що використовує L (x 1 ), L (x 2 ) як коефіцієнти при x 2 і x
3. Вибір, обгрунтування, короткий опис методів
3.1 Пошук значень інтерполяційного многочлена в точках x 1 і x 2
3.1.1 Постановка завдання
Потрібно знайти L (x 1 ), L (x 2 ) - значення інтерполяційного многочлена, побудованого для таблично заданої функції f (x) в точках x 1 , x 2 Тут вирішується завдання апроксимації, яка полягає в заміні деякої функції
у = f (х) іншою функцією g (х, а 0 , а 1 , ..., a n ) таким чином, щоб відхилення g (х, а 0 , а 1 , ..., a n ) від f (x) задовольняло в деякій області (на безлічі X) певній умові. Цим умовою є g (x i , a 0, a 1 , ... a n ) = f (x < sub> i ) при i = 0, n, яке означає, що функції, що апроксимується f (x) збігається з g (x i , a 0, a 1 , ... a n ) в т.зв. вузлах інтерполяції x 0 , x 1 , ..., x n . Це окремий випадок апроксимації, званий інтерполяцією.
3.1.2 Вибір і опис методу
Задача інтерполяції може бути вирішена безліччю методів, серед яких:
1) інтерполяційний многочлен Лагранжа
інтерполяційні формули Ньютона Виберемо для вирішення задачі інтерполяції інтерполяційний многочлен Лагранжа, так як його побудова просто в алгоритмізації, не вимагає обчислення кінцевих різниць функції,, може бути уміщено в одну невелику процедуру - функцію.
Крім того, метод Лагранжа працює і для нерівновіддаленими інтерполяційних вузлів, до того ж не має відмінностей, якщо точки x 1 і x 2 для пошуку значень L (x 1 ), L (x 2 ) лежать на початку або в кінці відрізка, де таблично задана функція.
Опис методу:
Задача інтерполяції будемо вирішувати побудовою многочлена Лагранжа, який має вигляд:
Ступінь многочлена n забезпечується n +1 інтерполяційним вузлом. Для завдання таблиці значень функції будемо використовувати два масиви x () і y (). Поліном повинен задовольняти умові L n (x i ) = y (i)
3.2 Пошук мінімуму функції F (x) на відрізку [a; b]
3.2.1 Постановка завдання
Необхідно чисельним методом знайти мінімум функції F (x) = L (x 1 ) x 2 -2.5L (x 2 ) x -3
на відрізку [a; b] з точністю Оµ, при тому, що L (x 1 ) і L (x 2 ) - коефіцієнти, отримані обчисленням полінома Лагранжа в точках x 1 , x 2 . Це завдання одномірної оптимізації.
Вибір методу: Для вирішення завдання одномірної оптимізації існує безліч методів, серед яких:
1) метод прямого перебору
2) метод дихотомії
3) метод золотого перетину
4) метод Фібоначчі
5) метод дотичних
6) метод Ньютона
оптимізація методом квадратичної інтерполяції Виберемо метод дихотомії, тому він простий у алгоритмізації, забезпечує швидку збіжність (на кожній ітерації відрізок невизначеності звужується майже вдвічі). Його недолік у вигляді необхідності багаторазового обчислення F (x) не грає особливої вЂ‹вЂ‹ролі, тому F (x) - звичайний поліном і розрахунок його значень не змарнує багато ресурсів ПК.
Опис методу:
Нехай f (x) - унімодального на [a; b] і потрібно знайти мінімум f (x) з абсолютною похибкою Є. Ідея методу дихотомії полягає в проведенні на кожній ітерації двох відліків (Обчислень значень функції), віддалених від середини відрізку невизначеності [а; b] на величину de [0; 2E] і порівняння значення досліджуваної функції в двох точках х ( n -1) і
x ( n -1) . визначуваних рекурентними формулами:
Якщо
, то
Інакше
N = 1,2, ... - номер ітерації, а 0 = а , B 0 = b.
Обчислення проводяться до тих пір, поки b-а> Є.
Тоді з абсолютною похибкою, не перевершує Е, вважають
x * = (a N + b N )/2
Довжина кінцевого відрізка невизначеності:
L 0 = ba - довжина початкового відрізка
На кожній ітерації відрізок невизначеності [a N ; b N ] зменшується приблизно вдвічі. Число відліків функції n і число ітерацій N пов'язані співвідношенням N = n/2
Практично величина d вибирається з умов розрізнюваності двох відліків функції
Процедура пошуку мінімуму методом дихотомії використовує більшу кількість відліків функції для локалізації точки мінімуму на відрізку заданої довжини.
Геометрична ілюстрація методу дихотомії
4. Перевірка умов збіжності методів. Пошук значень інтерполяційного многочлена в точках x 1 і x < sub> 2
Для правильної роботи цього методу необхідно, щоб функція була обмежена на відрізку інтерполювання. Виконання цієї умови очевидно за завданням.
Умови унімодального на відрізку [a; b] (перша похідна зростає, друга більше нуля) виконуються, отже, відрізок [A; b] залишається таким же як за завданням [0; 2]
