- •Лекція 1 етапи розв‘язування задач на еом .Елементи теорії похибок
- •1.1 Точні і наближені числа. Джерела похибок. Класифікація похибок
- •1.2 Абсолютна і відносна похибки
- •1.3 Десятковий запис наближених чисел. Значуща цифра числа. Дійсна значуща цифра
- •1.4 Зв’язок між числом дійсних знаків і похибкою числа
- •1.6 Обчислювальний експеримент та його основні етапи. Поняття стійкості та коректності
- •2.3 Особливості методів Гауса
- •Лекція № 3 розв‘язування систем лінійних алгебраїчних рівнянь
- •2.1 Основні поняття та визначення
- •2.2 Класифікація методів розв’язання слар на еом
- •2.3.1 Метод Гауса з послідовним виключенням невідомих
- •2.3.2 Метод Гауса за схемою Халецького
- •2.3.3 Метод Гауса з вибором головного елемента
- •2.3.4 Метод Гауса з одиничними коефіцієнтами
- •2.3.5 Метод Гауса-Жордана
- •Лекція №3 наближені методи розв'язання слар на еом
- •3.1 Постановка задачі та класифікація методів
- •3.2 Загальний підхід до розв’язання слар наближеними методами
- •3.3 Умови збіжності ітераційного процесу
- •3.4 Метод послідовних наближень (метод Якобі)
- •3.5 Метод Гауса-Зейделя
- •3.6 Метод верхньої релаксації
- •Лекція № 4 чисельні методи роз’вязання нелінійних рівнянь та систем нелінійних рівнянь
- •4.1 Загальні поняття та визначення
- •4.2 Принципи розв’язання нелінійних рівнянь на еом
- •4.3 Чисельні методи уточнення коренів
- •4.3.1 Метод половинного ділення
- •4.3.2 Метод хорд
- •4.3.3 Метод Ньютона (метод дотичних)
- •4.3.4 Комбінований метод
- •4.3.5 Метод ітерацій (метод послідовних наближень)
- •4.4 Чисельні методи розв’язання систем нелінійних рівнянь
- •5.1 Способи завдання функцій
- •5.2 Математична постановка задачі інтерполювання
- •5.2.1 Інтерполяційний багаточлен Лагранжа
- •5.2.2 Перша інтерполяційна формула Ньютона для рівновіддалених вузлів інтерполяції
- •Лекція №6 Апроксимація табличних функцій
- •6.1 Апроксимація табличних функцій
- •6.1.1 Апроксимація табличних функцій степеневими поліномами
- •6.1.2 Апроксимація узагальненими поліномами
- •6.1.3 Апроксимація ортогональними поліномами
- •6.1.4 Апроксимація тригонометричними поліномами (гармонійний аналіз)
- •7.1 Основні поняття та визначення
- •7.2 Чисельні методи знаходження визначеного інтегралу
- •7.2.1 Метод прямокутників
- •7.2.2 Метод трапецій
- •7.2.3 Метод Сімпсона
- •8.1 Метод Ньютона-Котеса
- •8.2 Метод Чебишева
- •8.3 Метод Гауса
- •8.4 Загальний підхід до визначення інтегралів на еом
- •9.1. Основні визначення та поняття
- •9.2. Класифікація численних методів розв'язання задачі Коші
- •9.3 Одноточкові методи розв'язання задачі Коші на еом
- •9.1.1 Модифікації методу Ейлера
- •9.1.2 Метод Рунге–Кутта
- •9.4 Методи прогнозу і корекції (багатоточкові методи)
- •9.4.1 Метод Мілна
- •9.4.2 Метод Адамса - Башфорта
- •9.4.3 Метод Хемінга
- •10.1 Чисельні методи розв’язання крайових задач
- •10.1.1 Методи стрільби
- •10.1.2 Кінцево-різницеві методи
- •10.1.3 Метод прогонки
- •11.1 Різницеві методи розв'язування диференційних рівнянь у частинних похідних
- •11.2 Етапи чисельного розв'язування диференційних рівнянь (др) у частинних похідних на еом
- •11.3 Еліптичні рівняння
- •11.4 Гіперболічні рівняння
- •12.1 Параболічні рівняння
- •13.1 Метод загального пошуку
- •13.2 Метод половинного ділення (розділення відрізка навпіл)
- •13.3 Метод дихотомії
- •13.4 Метод “золотого перетину”
- •13.5 Метод Фібоначчі
- •13.6 Порівняння методів одновимірного пошуку
- •14.1 Основні поняття та визначення
- •14.2 Критерії оптимальності
- •14.3 Градієнтні методи
- •14.3.1 Найшвидший підйом з використанням одномірного пошуку
- •14.3.2 Метод найшвидшого спуску
- •14.3.3 Метод Флетчера – Рівса
- •14.3.4 Метод Девідона – Флетчера – Пауела
- •14.3.5 Метод конфігурацій Хука – Дживса
- •14.3.6 Метод конфігурацій Розенброка
14.3 Градієнтні методи
В багатьох алгоритмах багатовимірної оптимізації так чи інакше використовується інформація про градієнти. Проілюструємо це положення наступним простим прикладом. Представимо собі, що альпіністу зав’язали очі і сказали, що він повинен добратися до вершини “унімодальної” гори. Навіть якщо він не буде нічого бачити, він може це зробити, якщо весь час буде рухатися вверх. Хоча будь-яка тропа, яка веде вверх, в кінці-кінців приведе його до вершини, найкоротшою з них буде найкрутіша, якщо, правда, альпініст не наштовхнеться на вертикальний обрив, який необхідно буде обійти. (Математичним еквівалентом обриву на поверхні, яку створює цільова функція, являються ті її місця, де поставлені умовні обмеження). Уявімо, що задача оптимізації не містить обмежень. Пізніше ми включимо їх в схему пошуку. Метод оптимізації, в основі якого лежить ідея руху по самій крутій тропі, називається методом найшвидшого підйому або найшвидшого спуску. Вектор градієнта перпендикулярний лінії рівня і вказує напрямок до нової точки в просторі проектування. Відмітимо, що градієнтний метод на відміну від методу дотичної до лінії рівня можна використовувати до будь-якої унімодальної функції, а не тільки тих, у яких ця властивість явно виражена.
Щоб краще зрозуміти ідею градієнтних методів, більш конкретно зупинимося на властивостях градієнтів. Розглянемо систему незалежних одиничних векторів е1, е2, е3, …, еN, які направлені в здовж вісей координат x1, x2, x3, …, xN, які є в той же час проектними параметрами. Вектор градієнта довільної цільової функції F = (x1, x2, x3, …, xN,) має вигляд
,
де частинні похідні обчислюються в точці, яка розглядається. Цей вектор направлений вверх, в напрямку підйому; обернений йому вектор вказує напрямок спуска. Одиничний вектор градієнта часто представляють у вигляді
,
де
.
(14.16)
Іноді характер цільової функції буває достатньо добре відомий, щоб можна було обчислити компоненти вектора градієнта шляхом безпосереднього диференціювання. Якщо таким способом частинні похідні отримати неможливо, то можна знайти їх наближені значення в безпосередньому околі точки, яка розглядається:
.
Тут - невелике зміщення в напрямку хi. Цю формулу часто називають “наближенням січної”. Отриману інформацію про напрямок градієнта можна використовувати різним чином для побудови алгоритму пошуку.
Постановка
задачі
оптимізації
градієнтними методами: мінімізація
функції F (x1,
x2,
x3,
…, xN)
з N проектними параметрами за допомогою
ЕОМ розв’язується ітераційними методами.
Розв’язок задачі починається з вибору
початкових значень
(i
= 1, 2, …, N), які за звичай визначаються із
умов розв’язуємої задачі, і потім
будують послідовні наближення,
використовуючи ітераційну формулу, яку
отримуємо з формули (14.12):
,
(i = 1, 2, …, N; j = 0, 1, 2, …), (14.17)
де
-
величина кроку ітерації по кожному з
параметрів
;
-
параметр вибору “напрямку”, який
звичайно визначається за формулою
(14.12).
Дана
формула забезпечує збіжність досліджуваної
функції до деякого рішення
при
.
Величина кроку
на
кожній j-ій ітерації визначається одним
з методів оптимізації однопараметричної
оптимізації, наприклад методом ділення
відрізка навпіл або методом “золотого
перетину” або Фібоначчі.
