Крок 4. Алгоритм яружного методу 1

Крок 3.

Крок 2.

Крок 1.

Алгоритм яружного методу 1.

Уводяться

х ₀ — початкове наближення,

e ₁ і e ₂ — точність розв’язання,

a — крок для градієнтного спуску,

l — початкове значення для яружного кроку.

Із точки х ₀ здійснюється градієнтний спуск з постійним кроком a на дно яру. В результаті виходить точка u ₀. Покладається k =0.

В околиці х_к береться точка і з неї здійснюється градієнтний спуск. В результаті отримується точка .

Нова точка х_{к +1} визначається в такий спосіб. По формулі

або

обчислюється точка x ' _{k +1}. З неї здійснюється градієнтний спуск і ми одержуємо точку . Якщо , то приймаємо і .

В іншому разі зменшуємо яружний крок (наприклад в 2 рази λ=λ/2) і повторюємо крок 3.

Якщо і , то приймаємо:

і пошук мінімуму на цьому закінчується, інакше к = к +1 і переходимо до кроку 2.

Рис. 7.

Схема алгоритму яружного методу 1

Ідея модифікованого методу Гельфанда

Нехай х ₀ і х ₁ — дві довільні близькі точки. Як і в попередньому алгоритмі, з кожної точки здійснимо градієнтні спуски з постійним кроком a. Одержимо точки u ₀ і u ₁, що лежать в околиці «дна яру». З'єднуючи їх прямою, робимо «великий крок» l в отриманому напрямку. В результаті одержимо точку х ₂. Із цієї точки здійснимо градієнтний спуск і одержимо точку u ₂. Далі, для того щоб здійснити «яружний крок», беремо передостанню точку u ₁. З'єднуючи прямою точки u ₂ і u ₁, робимо крок l в отриманому напрямку й визначаємо х ₃. Далі аналогічним образом обчислюються х ₄, х ₅,

x⁽¹⁾

Рис. 6.

Схема алгоритму яружного методу 1

Дата добавления: 2015-05-23