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

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

ред.

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

 (1)

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

  (2)

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

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

 

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

  (3)

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

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

 .

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

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

ред.

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

 

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

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

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

ред.

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

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

 (5)

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

Алгоритм

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

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

ред.

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

Алгоритм

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

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

ред.

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

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

Алгоритм

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

Див. також

ред.

Література

ред.
  • Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М. : Высш. шк., 1986.
  • Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М. : Мир, 1985.
  • Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М. : Энергоатомиздат, 1972.
  • Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М. : МИФИ, 1982.
  • Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М. : МИФИ, 1980.
  • Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М. : Наука, 1970. — С. 575-576.