Автоматизированное проектирование. Норенков И.П. - 104 стр.

  5@!"! 4                                   %!#*%!#&F*:,$*     $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M

во-вторых, имеем
             Xi = Xi-1 + hwi-1 Si-1 - h grad F(Xi-1),
откуда получаем
             ∂F/∂h = (∂F(X)/∂X)(∂X/∂h) = grad F(Xi) grad F(Xi-1) = 0.                                   (4.13)
         Алгоритм поиска сводится к применению формулы (4.9), пока не будет выполнено условие окончания вычислений
             |grad F(Xk)| < ε.
       Чтобы определить коэффициент wi решают систему уравнений (4.8)-(4.13) путем подстановки в (4.10) величин Si+1
из (4.9) и Si из (4.8)
             Si+1TKSi = (wi Si - grad F(Xi))T K(Xi — Xi-1) / h =
             = (wi Si - grad F(Xi))T KK -1 (grad F(Xi) - grad F(Xi-1)) / h = 0;
или
             (wi Si - grad F(Xi))T (grad F(Xi) - grad F(Xi-1)) = 0,
откуда
             wi SiT (grad F(Xi) - grad F(Xi-1)) - grad F(Xi)T grad F(Xi) + grad F(Xi)T grad F(Xi-1) = 0
и с учетом (4.12) и (4.13)
             wi SiT grad F(Xi-1) + grad F(Xi)T grad F(Xi) = 0.
Следовательно,
             wi = grad F(Xi)T grad F(Xi) / SiT grad F(Xi-1)                                             (4.14)
     На первом шаге поиска выбирают S1 = — grad F(X0) и находят точку N1. На втором шаге по формуле (4.14) рассчи-
тывают w1, по формулам (4.9) и (4.8) определяют S2 и N2 и т.д.
      L$&#- 0$"$/$**#; /$&"'%' (иначе метод Девидона-Флетчера-Пауэлла) можно рассматривать
как результат усовершенствования метода второго порядка — метода Ньютона.
L$&#- G5<&#*) основан на использовании необходимых условий безусловного экстремума целе-
вой функции F(X)
          grad F(X) = 0.                                                              (4.15)
      Выражение (4.15) представляет собой систему алгебраических уравнений, для решения которой
можно применить известный численный метод, называемый методом Ньютона. Корень системы
(4.15) есть стационарная точка, т.е. возможное решение экстремальной задачи. Метод Ньютона явля-
ется итерационным, он основан на линеаризации (4.15) в окрестности текущей точки поиска Nk
             grad F(X) = grad F(Xk) + K(X-X k) = 0.                                                     (4.16)
     Выражение (4.16) — это система линейных алгебраических уравнений. Ее корень есть очеред-
ное приближение Nk+1 к решению Xk+1 = Xk - K-1(Xk) grad F(Xk).
     Если процесс сходится, то решение достигается за малое число итераций, окончанием которых
служит выполнение условия
        |Xk+1 - Xk| < ε.
     Главный недостаток метода — высокая трудоемкость вычисления и обращения матрицы K, к то-
му же ее вычисление численным дифференцированием сопровождается заметными погрешностями,
что снижает скорость сходимости.
     В методе переменной метрики вместо трудно вычисляемой обратной матрицы Гессе использу-
ют некоторую более легко вычисляемую матрицу N, т.е.
         Xk+1 = Xk + N grad F(Xk).
         Введем обозначения:
             dgk= grad F(Xk) - grad F(Xk-1);
             dXk= Xk - Xk-1;
E — единичная матрица. Начальное значение матрицы N0 = E. Матрицу N корректируют на каждом шаге, т.е.


 &.+.)$(*),$" . !"#$%!#&'&($"!))$*                  +($*,#&($"!)&*                                         104