Метод золотого сечения

Метод половинного деления (бисекции)

Методы одномерного поиска

Метод Ньютона

Метод наискорейшего спуска

Метод градиента

grad F(X) = (∂F/∂x₁; ∂F/∂x₂; …; ∂F/∂x_n)

F(x₁; x₂)

Производные вычисляются численно, путём приращения управляемых параметров.

x₁ = x_1,0 + ∆x₁

∂F/ ∂x₁ = ∆F/∆x₁ ; ∆F = F(x₁₀ + ∆x₁) – F(x₁₀)

В каждой точке для нахождения производных необходимо n+1 вычислений F(X).

В основу метода положен одноимённый метод решения нелинейных алгебраических уравнений.

grad F(X) = 0;

Обозначим Ф(X) = ∂F(x)/∂x = 0

Применим к данной системе уравнений метод Ньютона.

Ф(X_k) + ∂F(X_k)/∂X ∆X ≈0,

где ∆Х – значение X_k+1 - X_k

X_k+1 = X_k – (∂Ф/∂X)^-1 * Ф(X_k)

X_k+1 = X_k – Ю_k^-1 grad F(X_k) - Формула Ньютона.

Если целевая функция является квадратичным многочленом по управляемым параметрам, то минимум находится за один шаг.

Недостатки метода:

1) Высокая трудоёмкость вычисления и обращения матрицы Гессе.

2) Не всегда имеет место сходимость решения.

Найти минимум целевой функции: min F(X_k + hg) = min f(h)

^h>0

g – единичный вектор выбранного направления.

Золотое сечение – это деление отрезка АВ на 2 части таким образом, что большая его часть АСявляется средней пропорциональной между отрезком АВ и его меньшей частью СВ.

АВ/АС = АС/СВ

Для шага а_к и в_к

c_к = а_к + 0,382l_k

d_k = в_к – 0,382 l_k

l_k = b_k - a_k

Если f(c_k) < f(d_k), то b_k+1 = d_k; d_k+1 = c_k; a_k+1 = a_k;

Если f(c_k) ≥ f(d_k), то a_k+1 = c_k; c_k+1 = d_k; b_k+1 = b_k

Если l_k ≤ ε – условие окончания операции.

В методе золотого сечения для сужения интервала неопределённости необходимо сделать только одно вычисление.