WikiSort.ru - Программирование

Поправка единичного ранга

Один шаг алгоритма даёт информацию о кривизне вдоль одного направления, поэтому ранг матрицы ${\displaystyle U_{k}}$ полагают малым, и даже единичным:

${\displaystyle B_{k+1}=B_{k}+{\vec {u}}{\vec {v}}^{T}}$

где ${\displaystyle {\vec {u}}}$ и ${\displaystyle {\vec {v}}}$ некоторые вектора.

Тогда, квазиньютоновское условие примет вид:

${\displaystyle (B_{k}+{\vec {u}}{\vec {v}}^{T}){\vec {s}}_{k}={\vec {y}}_{k}}$

${\displaystyle {\vec {u}}({\vec {v}}^{T}{\vec {s}}_{k})={\vec {y}}_{k}-B_{k}{\vec {s}}_{k}}$

Полагая, что предыдущая матрица ${\displaystyle B_{k}}$ на очередном шаге квазиньютоновскому условию не удовлетворяет (т.е. разность в правой части не равна нулю), и что вектор ${\displaystyle {\vec {v}}}$ не ортогонален ${\displaystyle {\vec {s}}_{k}}$ , получают выражение для ${\displaystyle {\vec {u}}}$ и ${\displaystyle B_{k+1}}$ :

${\displaystyle {\vec {u}}={\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}({\vec {y}}_{k}-B_{k}{\vec {s}}_{k})}$

${\displaystyle B_{k+1}=B_{k}+{\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}({\vec {y}}_{k}-B_{k}{\vec {s}}_{k}){\vec {v}}^{T}}$

Из соображений симметричности матрицы Гессе, вектор ${\displaystyle {\vec {v}}}$ берут коллинеарным ${\displaystyle {\vec {u}}}$ :

${\displaystyle B_{k+1}=B_{k}+{\frac {1}{({\vec {y}}_{k}-B_{k}{\vec {s}}_{k})^{T}{\vec {s}}_{k}}}({\vec {y}}_{k}-B_{k}{\vec {s}}_{k})({\vec {y}}_{k}-B_{k}{\vec {s}}_{k})^{T}}$

Полученное уравнение называется симметричной формулой ранга один.

Поправки ранга два

Один из способов конструирования поправок ранга два заключается в построении сходящейся последовательности матриц ${\displaystyle B^{(j)}}$ . В качестве начального значения ${\displaystyle B^{(0)}}$ берут ${\displaystyle B_{k}}$ , ${\displaystyle B^{(1)}}$ вычисляют по формуле:

${\displaystyle B^{(1)}=B^{(0)}+{\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}({\vec {y}}_{k}-B^{(0)}{\vec {s}}_{k}){\vec {v}}^{T}}$

После чего её симметризуют:

${\displaystyle B^{(2)}={\frac {B^{(1)}+B^{(1)T}}{2}}}$

Однако полученная матрица больше не удовлетворяет квазиньютоновскому условию. Чтобы это исправить, процедуру повторяют. В результате на ${\displaystyle j}$ -м шаге:

${\displaystyle B^{(2j+1)}=B^{(2j)}+{\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}({\vec {y}}_{k}-B^{(2j)}{\vec {s}}_{k}){\vec {v}}^{T}}$

${\displaystyle B^{(2j+2)}={\frac {B^{(2j+1)}+B^{(2j+1)T}}{2}}}$

Предел этой последовательности равен:

${\displaystyle B_{k+1}=B_{k}+{\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}[({\vec {y}}_{k}-B_{k}{\vec {s}}_{k}){\vec {v}}^{T}+{\vec {v}}({\vec {y}}_{k}-B_{k}{\vec {s}}_{k})^{T}]-{\frac {({\vec {y}}_{k}-B_{k}{\vec {s}}_{k})^{T}{\vec {s}}_{k}}{({\vec {v}}^{T}{\vec {s}}_{k})^{2}}}{\vec {v}}{\vec {v}}^{T}}$

При выборе различных ${\displaystyle {\vec {v}}}$ (не ортогональных ${\displaystyle {\vec {s}}_{k}}$ ) получаются различные формулы пересчёта матрицы ${\displaystyle B}$ :

• ${\displaystyle {\vec {v}}={\vec {y}}_{k}-B_{k}{\vec {s}}_{k}}$ приводит к симметричной формуле ранга один;
• ${\displaystyle {\vec {v}}={\vec {s}}_{k}}$ приводит к симметричной формуле Пауэлла — Бройдена (PSB);
• ${\displaystyle {\vec {v}}={\vec {y}}_{k}}$ приводит к симметричной формуле Девидона — Флетчера — Пауэлла (DFP):

${\displaystyle B_{k+1}=B_{k}-{\frac {1}{{\vec {s}}_{k}^{T}B_{k}{\vec {s}}_{k}}}B_{k}{\vec {s}}_{k}{\vec {s}}_{k}^{T}B_{k}+{\frac {1}{{\vec {y}}_{k}^{T}{\vec {s}}_{k}}}{\vec {y}}_{k}{\vec {y}}_{k}^{T}+({\vec {s}}_{k}^{T}B_{k}{\vec {s}}_{k}){\vec {\omega }}_{k}{\vec {\omega }}_{k}^{T}}$ ,

где ${\displaystyle {\vec {\omega }}_{k}={\frac {1}{{\vec {y}}_{k}^{T}{\vec {s}}_{k}}}{\vec {y}}_{k}-{\frac {1}{{\vec {s}}_{k}^{T}B_{k}{\vec {s}}_{k}}}B_{k}{\vec {s}}_{k}}$

Нетрудно проверить, что ${\displaystyle {\vec {\omega }}_{k}}$ ортогонален ${\displaystyle {\vec {s}}_{k}}$ . Таким образом добавление слагаемого ${\displaystyle {\vec {\omega }}_{k}{\vec {\omega }}_{k}^{T}}$ не нарушит ни квазиньютоновского условия, ни условия симметричности. Поэтому проводился ряд теоретических исследований, подвергавших последнее слагаемое масштабированию на предмет получения наилучшего приближения. В результате была принята точка зрения, что наилучшим вариантом является отвечающий полному отсутствию последнего слагаемого. Этот вариант пересчёта известен под именем формулы Бройдена — Флетчера — Гольдфарба — Шанно (BFGS):

${\displaystyle B_{k+1}=B_{k}-{\frac {1}{{\vec {s}}_{k}^{T}B_{k}{\vec {s}}_{k}}}B_{k}{\vec {s}}_{k}{\vec {s}}_{k}^{T}B_{k}+{\frac {1}{{\vec {y}}_{k}^{T}{\vec {s}}_{k}}}{\vec {y}}_{k}{\vec {y}}_{k}^{T}}$