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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

(1)

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

(2)

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

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

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

(3)

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

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

.

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

Градієнтні методи[ред. | ред. код]

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

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

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

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

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

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

(5)

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

Алгоритм[ред. | ред. код]

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

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

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

Алгоритм[ред. | ред. код]

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

Метод спряжених градієнтів[ред. | ред. код]

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

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

Алгоритм[ред. | ред. код]

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

Див. також[ред. | ред. код]

Література[ред. | ред. код]

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