Градієнтні методи — чисельні методи рішення з допомогою градієнта задач, що зводяться до знаходження екстремумів функції.
Постановка задачі розв'язання системи рівнянь в термінах методів оптимізації Завдання рішення системи рівнянь:
(1)
з еквівалентна задачі мінімізації функції
(2)
або якій-небудь іншій зростаючій функції від абсолютних величин нев'язок (помилок) , . Завдання знаходження мінімуму (або максимуму) функції змінних і сама по собі має велике практичне значення.
Для вирішення цієї задачі ітераційними методами починають з довільних значень і будують послідовні наближення:
або покоординатно:
(3)
які зводяться до деякого рішенням при .
Різні методи відрізняються вибором «напрямку» для чергового кроку, тобто вибором відносин
.
Величина кроку (відстань, на яку треба піднятися в заданому напрямку в пошуках екстремуму) визначається значенням параметра , який мінімізує величину як функцію від . Цю функцію зазвичай апроксимують її розкладанням у ряд Тейлора або інтерполяційним многочленом з трьох-п'яти вибраних значень . Останній метод застосуємо для знаходження max і min таблично заданої функції
Градієнтні методи Основна ідея методів полягає в тому, щоб йти в напрямку найшвидшого спуску, а цей напрямок задається антиградієнтом :
де вибирається: сталою, в цьому випадку метод може розходитися; дробовим кроком, тобто довжина кроку в процесі спуску ділиться на деяке число; якнайскорішим спуском:
Метод найшвидшого спуску (метод градієнта) Вибирають , де всі похідні обчислюються при , і зменшують довжину кроку по мірі наближення до мінімуму функції .
Для аналітичних функцій і малих значень тейлорівський розклад дозволяє вибрати оптимальну величину кроку
(5)
де всі похідні обчислюються при . Параболічна інтерполяція функції може виявитися більш зручною.
Алгоритм Задаються початкове наближення і точність розрахунку Розраховують , де Перевіряють умову зупинки: Якщо , то і перехід до кроку 2. Інакше і зупинка.
Метод покоординатного спуску Гауса — Зейделя Цей метод названий за аналогією з методом Гауса — Зейделя для розв'язання системи лінійних рівнянь. Покращує попередній метод за рахунок того, що на черговій ітерації спуск здійснюється поступово уздовж кожної з координат, однак тепер необхідно обчислювати нові раз за один крок.
Алгоритм Задаються початкове наближення і точність розрахунку Розраховують, де Перевірють умову зупинки: Якщо , то і перехід до кроку 2. Інакше і зупинка.
Метод спряжених градієнтів
Метод спряжених градієнтів ґрунтується на поняттях прямого методу багатовимірної оптимізації — методу спряжених напрямів.
Застосування методу до квадратичних функцій визначає мінімум за кроків.
Алгоритм Задаються початковим наближенням і похибкою: Розраховують початковий напрямок:
Якщо або , то і зупинка. Інакше якщо , то і перехід до 3; і перехід до 2.
Див. також Інтерполяційні формули Математичне програмування Метод градієнта Метод спряжених градієнтів Прямі методи Формула Тейлора Чисельні методи Чисельні методи розв'язання рівнянь Метод Нелдера — Міда
Література