ЗМІСТ
Введення
1 Постановка завдання
2 Математичні і алгоритмічні основи рішення задачі
3 Функціональні моделі та блок-схеми рішення задачі
4 Програмна реалізація рішення завдання
5 Приклад виконання програми
Висновок
Список використаних джерел та літератури
ВСТУП
Завдання пошуку максимуму еквівалентні завданням пошуку мінімуму, так як потрібно лише поміняти знак перед функцією. Для пошуку мінімуму необхідно визначити інтервал, на якому функція могла б мати мінімум. Для цього можна використовувати графічне представлення функції, аналітичний аналіз апроксимуючої функції і відомості про математичної моделі досліджуваного процесу (тобто закони поведінки даної функції).
Методи, що використовують виключення відрізків, засновані на порівнянні функцій в двох точках пробного відрізка, враховуються лише значення функції в цих точках.
Врахувати інформацію про значеннях функції між точками дозволяють методи поліноміальної апроксимації. Їх основна ідея полягає в тому, що функція апроксимується поліномом, а точка його мінімуму служить наближенням до мінімуму. Зрозуміло, в цьому випадку крім властивості унімодального (тобто наявності єдиного мінімуму на розглянутому відрізку), необхідно на функцію накласти і вимоги достатньою гладкості для її поліноміальної апроксимації.
Для підвищення точності пошуку мінімуму можна як збільшувати ступінь полінома, так і зменшувати пробний відрізок. Оскільки перший прийом призводить до помітного збільшення обчислювальної роботи і появи додаткових екстремумів, зазвичай користуються поліномами другий (метод парабол) або третьої (метод кубічної інтерполяції) ступеня.
Метою даної курсової роботи є розгляд методу парабол для пошуку мінімуму функції.
-->p>
1 Постановка завдання
Функція має локальний мінімум при деякому, якщо існує деяка кінцева Оѕ-околиця цього елемента, в якій
,.
Потрібно, щоб на безлічі X функція f (x) була принаймні кусково-неперервною.
Точка, в якій функція досягає найменшого на безлічі X значення, називається абсолютним мінімумом функції. Для знаходження абсолютного мінімуму потрібно знайти всі локальні мінімуми і вибрати найменше значення.
Завдання називають детермінованою, якщо похибкою обчислення (або експериментального визначення) функції f (x) можна знехтувати. В іншому випадку задачу називають стохастичною.
Потрібно обчислити мінімум заданої функції методом парабол.
У цьому методі обчислюється значення функції відразу в трьох довколишніх точках, ,, Де h - мале число. Через ці три точки проводиться інтерполяційна парабола:
.
Мінімум параболи досягається при, тобто при. Для трьох точок отримуємо систему трьох лінійних рівнянь для коефіцієнтів a, b, c. Знаходимо a і b і тоді:
.
Приклад 1. Знайти мінімум функції методом парабол на проміжку [-5; 3] з необхідною точністю 0,0001.
Рішення:
k номер ітерації
1
-3,872291
0,010093
2
-3,871639
0,000004
Таблиця 1. Приклад 1
Так як <, отже мінімум x = -3,871639.
Малюнок 1. Функція
Приклад 2. Знайти мінімум функції методом парабол на проміжку [-2; -1] З необхідною точністю 0,0001.
Рішення:
k номер ітерації
1
-1,882843
0,831300
2
-1,919519
-0,009568
3
-1,919112
-0,000004
Таблиця 2. Приклад 2
Так як <, отже мінімум x = -1,919112.
Малюнок 2. Функція
Приклад 3. Знайти мінімум функції методом парабол на проміжку [-1; -0,5] З необхідною точністю 0,00001.
Рішення:
k номер ітерації
1
-0,497419
0,116021
2
-0,451529
-0,003278
3
-0,450185
-0,000003
Таблиця 3. Приклад 3
Так як <, отже мінімум x = -0,450185.
Малюнок 3. Функція
2 Математичні і алгоритмічні основи рішення задачі
Нехай має першу та другу похідну. Розкладемо в ряд Тейлора в деякій точці, обмежуючись при цьому трьома членами розкладання:
. (3)
Іншими словами, апроксимуємо нашу функцію в точці, параболою (малюнок 1). Для цієї параболи можна аналітично обчислити положення екстремуму як корінь рівняння першої похідної від (3):
.
Нехай мінімум апроксимуючої параболи знаходиться в точці. Тоді обчисливши значення функції, ми отримуємо нову точку наближення до мінімуму.
Малюнок 4. Пошук мінімуму функції методом парабол
Зазвичай в практичних реалізаціях даного методу не використовують аналітичний вигляд першої та другої похідних. Їх замінюють звичайно-різницевим апроксимаціями. Найбільш часто беруть симетричні різниці з постійним кроком h:
Це еквівалентно апроксимації функції параболою, що проходить через три близькі точки
,, .
Остаточне вираз, по якому можна будувати ітераційний процес, таке:
(4)
Даний метод відрізняється від інших методом пошуку мінімуму високою швидкістю збіжності. Поблизу екстремуму, аж до відстаней ~, збіжність практично не відрізняється від квадратичної. Однак алгоритм вимагає постійного контролю збіжності. Наприклад, ітераційний процес буде сходитися до мінімуму, якщо:
1) знаменник формули
повинен бути> 0. Якщо це не так, потрібно зробити крок у зворотному напрямку, причому досить великий. Зазвичай в ітераційному процесі думають
.
Іноді заради спрощення розрахунків вважають
,
однак це суттєво зменшує швидкість збіжності.
2) якщо це не так, то від слід зробити крок
,
с.
Якщо і при цьому умову убування не виконано, зменшують П„ і знову роблять крок.
3 Функціональні моделі і блок-схеми рішення задачі
Функціональні моделі та блок-схеми рішення задачі представлені на малюнку 5, 6.
Використовувані позначення:
В· X0, MIN_VAL - початкова точка;
В· H, MAX_VAL - кінцева точка;
В· EPS - необхідна точність;
В· FN - функція для обчислення мінімуму;
В· X1 - допоміжна точка;
В· X2 - допоміжна точка;
В· XN - допоміжна точка;
В· F_X0 - функція від початкової точки X0;
В· F_X1 - функція від допоміжної точки X1;
В· F_X2 - функція від допоміжної точки X2;
В· F_XN - функція від допоміжної точки XN;
В· Q - робоча змінна;
В· A - робоча змінна;
В· B - робоча змінна;
В· C - робоча змінна;
В· D - робоча змінна;
В· Z - робоча змінна;
В· K - робоча змінна.
Малюнок 5 - Блок-схема рішення задачі для функції PARABL_METHOD
...
