Градієнтні методи

Градієнтні методичисельні методи рішення з допомогою градієнта задач, що зводяться до знаходження екстремумів функції.

Постановка задачі розв'язання системи рівнянь в термінах методів оптимізаціїРедагувати

Завдання рішення системи рівнянь:

 (1)

з     еквівалентна задачі мінімізації функції

  (2)

або якій-небудь іншій зростаючій функції від абсолютних величин   нев'язок (помилок)  ,  . Завдання знаходження мінімуму (або максимуму) функції   змінних і сама по собі має велике практичне значення.

Для вирішення цієї задачі ітераційними методами починають з довільних значень   і будують послідовні наближення:

 

або покоординатно:

  (3)

які зводяться до деякого рішенням   при  .

Різні методи відрізняються вибором «напрямку» для чергового кроку, тобто вибором відносин

 .

Величина кроку (відстань, на яку треба піднятися в заданому напрямку в пошуках екстремуму) визначається значенням параметра  , який мінімізує величину   як функцію від  . Цю функцію зазвичай апроксимують її розкладанням у ряд Тейлора або інтерполяційним многочленом з трьох-п'яти вибраних значень  . Останній метод застосуємо для знаходження max і min таблично заданої функції  

Градієнтні методиРедагувати

Основна ідея методів полягає в тому, щоб йти в напрямку найшвидшого спуску, а це напрямок задається антиградієнтом  :

 

де   вибирається:

  • сталою, в цьому випадку метод може розходитися;
  • дробовим кроком, тобто довжина кроку в процесі спуску ділиться на деяке число;
  • якнайскорішим спуском:  

Метод найшвидшого спуску (метод градієнта)Редагувати

Вибирають  , де всі похідні обчислюються при  , і зменшують довжину кроку   по мірі наближення до мінімуму функції  .

Для аналітичних функцій   і малих значень   тейлорівський розклад   дозволяє вибрати оптимальну величину кроку

 (5)

де всі похідні обчислюються при  . Параболічна інтерполяція функції   може виявитися більш зручною.

АлгоритмРедагувати

  1. Задаються початкове наближення і точність розрахунку  
  2. Розраховують  , де  
  3. Перевіряють умову зупинки:
    • Якщо  , то   і перехід до кроку 2.
    • Інакше   і зупинка.

Метод покоординатного спуску Гауса — ЗейделяРедагувати

Цей метод названий за аналогією з методом Гауса — Зейделя для розв'язання системи лінійних рівнянь. Покращує попередній метод за рахунок того, що на черговій ітерації спуск здійснюється поступово уздовж кожної з координат, однак тепер необхідно обчислювати нові   раз за один крок.

АлгоритмРедагувати

  1. Задаються початкове наближення і точність розрахунку  
  2. Розраховують , де  
  3. Перевірють умову зупинки:
    • Якщо  , то   і перехід до кроку 2.
    • Інакше   і зупинка.

Метод спряжених градієнтівРедагувати

Метод спряжених градієнтів ґрунтується на поняттях прямого методу багатовимірної оптимізації — методу спряжених напрямів.

Застосування методу до квадратичних функцій   визначає мінімум за   кроків.

АлгоритмРедагувати

  1. Задаються початковим наближенням і похибкою:  
  2. Розраховують початковий напрямок:  
  3.  
    • Якщо   або  , то   і зупинка.
    • Інакше
      • якщо  , то   і перехід до 3;
      •   і перехід до 2.

Див. такожРедагувати

ЛітератураРедагувати

  • Акулич И.Л. {{{Заголовок}}}.
  • Гилл Ф., Мюррей У., Райт М. {{{Заголовок}}}.
  • Коршунов Ю.М., Коршунов Ю.М. {{{Заголовок}}}.
  • Максимов Ю.А.,Филлиповская Е.А. {{{Заголовок}}}.
  • Максимов Ю.А. {{{Заголовок}}}.
  • Корн Г., Корн Т. {{{Заголовок}}}.