Общая задача нелинейного программирования

Не всегда можно определить заранее, сколько раз придется вычислять функцию. Метод золотого сечения почти столь же эффективен при n-2, что и метод Фибоначчи, однако при этом не требуется знать n – количество вычислений функции.  
Сущность этого метода заключается в следующем. Интервал неопределенности делится на две неравные части так, что отношение длины большего отрезка к длине всего интервала равно отношению длины меньшего отрезка к длине большего.  
  
где τ - «золотое сечение»  
  

На каждом шаге этой итеративной процедуры, кроме первого, вычисляется только одно значение функции. Однако Химмельблау рекомендовал вычислять на каждом шаге две точки, для того чтобы не накапливалась погрешность, так как τ имеет приближенное значение .  
Если длина конечного интервала неопределенности равна δ, то для достижения требуемой точности число вычислений значений функции по методу золотого сечения можно найти по условию 

 

  

Исходные данные:

а (1;6);  в (7;12) = 0,7

ИТЕРАЦИЯ 1:

∆0 = в – а = (6;6)

∆1 = *∆0 = (0,7*6; 0,7*6) = (4,2;4,2)

∆2 = ∆0 - ∆1 = (1,8;1,8)

У = а + ∆2 = (2,8;7,8)

Z = в – ∆0 = (1;6)

Посчитаем значение ЦФ относительно новых значений:

L(y) = (2,8- 10)2+(7,8-5)2 +(2,8 - 10)(7,8-5) = 37,28

ИТЕРАЦИЯ 2:

a = (2,8;7,8)          b = (7;12)

 

        

 

 

 

 

Посчитаем значение функции в точке ().

 

ИТЕРАЦИЯ 3:

а = ()          b = (7;12)

 

        

 

 

 

 

Посчитаем значение функции в точке ().

 

 

ИТЕРАЦИЯ 4:

a = ()          b = (7;12)

 

                

 

 

)

 

Посчитаем значение функции в точке ().

 

 

 

 ИТЕРАЦИЯ 5:

.      a = ()          b = ()

 

        

 

 

 

 

Посчитаем значение функции в точке ().

 

 

На первой итерации значение функции уменьшилось до значения(37,28) в точках (1;6) (7;12) ,на второй увеличилось, а на остальных уменьшается.

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

Рассмотрим систему нелинейных уравнений

                                   F(x) = 0, F(x), x ∈ Rn ,    (1.1)

и предположим, что существует вектор x ∈ D ⊂ Rn , являющийся решением системы (1.1). Будем считать, что F(x) =(f1(x), f2(x), . . . , fn(x))T.

Разложим F(x) в окрестности точки x¯: F(x) = F(x0) +F’(x0)(x – x0) + o(− ). Здесь

                          ,   ,  . . . 

F’(x) = =   , ,  . . .

                            . . .        . . .      . . .   . . .

                               , . . .

 

называется матрицей Якоби, а её определитель – якобианом системы (1.1). Исходное уравнение заменим следующим: F(x0) +F’(x0)(x – x0) = 0. Считая матрицу Якоби F’(x0) не особой, разрешим это уравнение относительно x: xˆ = x0 − [F’(x)]−1F(x0). И вообще положим

                                                                xk+1= xk− [F’(xk)]−1F(xk).            (1.2)

При сделанных относительно F(·) предположениях имеет место сходимость последовательности {xk} к решению системы со скоростью геометрической прогрессии при условии, что начальное приближение x0 выбрано из достаточно малой окрестности решения x¯. При дополнительном предположении F(·) ∈ C2[a, b] имеет место квадратичная сходимость метода, т.е.

                                      ≤ .

 

Алгоритм: 1) В целевой функции раскрываются скобки, приводятся подобные;2)Находятся производные: , ,, ;

3) Из значений производных  создаётся матрица ;

4)Находятся миноры каждого  элемента матрицы 

 
  и из них создается новая матрица ;

5) Находится определитель  матрицы ;

6) Создаётся матрица, где  значение минора разделено на  определитель (обратная матрица) ;

7) Находится точка ;

8) Находится функция , значение которой должно совпасть с точкой .

, ,,

 

, ,,

 

 

Итоговая формула расчета:  

        

 

 

Значения