1626435586-15eceb6ba43f688400eaeb312dc6d98a (844237), страница 16
Текст из файла (страница 16)
Обозначим величину ошибки через е) = и — п); имеем е)" = 9)е', ))е)"!!'=!)е)1' тоь где 11' = 1 — К)А КА. Для того чтобы обеспечить выполнение ~ е1"))'(~ е)))', необходимо потребовать положительной определенности матрицы 21 — К'АтКА. Этим определяется верхнее ограничение на К). К сожалению, для задач существенно более сложных выяснить условия сходимости гораздо труднее. Выполнение (4.2.2) свидетельствует лишь о наличии у функции штрафа локального экстремума. Для того чтобы выяснить, является ли этот экстремум максимумом или минимумом функции штрафа, необходимо проанализировать вторую производную или второй дифференциал этой функции.
Однако в настоящей книге подобное исследование не проводится (Сейдж И16)). Значительно интереснее задача минимизации функции штрафа при наличии ограничений в форме равенств. Итак, требуется минимизировать по и (4.2.9) Х = О (х, к) зл] МЕТОДЫ ИДЕНТИФИКАПИИ СТАТИЧЕСКИХ СИСТЕМ 1сб или — + — 1,=0, де д(Т д«д« д(т — + — 1=0, дх дх 1(х, и) = О.
(4.2ЛЗ) (4.2.14) (4.2.15) Часто решение этой системы оказывается затруднительным и его пытаются заменить итеративной процедурой. Если выбрано и', можно решить уравнение (4.2.10), определив такое х', что 1(х', и') = О. Разлагая Х в ряд в окрестности этого решения, получим Н(х, и, ).) = 8(х', п~) + [ '. 1 (х — х')+ Г де (х', «') т д„1 + [ де(х, «') 1Т з + т[д((х, «') 1;) + + 2~~[ ( '")1 (и — п1) (4.2ЛО) Для того, чтобы упростить зто выражение, воспользуемся (4.2.14): ЬН' = Н (х, и, 3~) — Н (х' «' У) = дз (х~, «и) 1Т ~ д1т(хз «1) 1т ~т ' '+х ~ ''.
"л;= д«' ( д«' ) 1 'Ь~', (4.2Л7) где Лп' = п — п', Лх' = х — х'. (4.2ЛЗ) так, чтобы выполнялось следуюп(ее условие: 1(х,и) = О, (4.2.10) где и — вектор размерности М, а 1 и х — Н-векторы. 3того можно достичь, определив функцию Н (х, и, 1) = О (х, и) + Л~1 (х, и), (4.2.11) где Л вЂ” множитель Лагранжа. Затем решается система нелинейных уравнений дН дН дН д«дк д3~ (4.2Л2) цщ гРАд11еитные методы идентиеикАции [Гл, А Метод наискорейшего спуска получается, когда отрицательное ЬН1 (или Л,)1) выбирается максимальным по модулю. Таким образом, полагаем 1 дН (х', э', Ь1) (4.2.19) дэ1 где К1 — положительное число, которое выбирается иэ соображений, связанных со сходимостью и скоростью сходимости итеративного процесса.
Таким образом, вычислительная процедура градиентного метода первого порядка сводится к следующим этапам: 1) определить к', 2) найти х' иа уравнения 1 (х', и') = О, 3) оценить У из соотношения 4) определить дН(.1, э', Ь1) да(„1 э1) дгт(1 „1) — + 5) вычислить б) повторять процедуру до тех пор, пока уиравяеиие и не перестанет изменяться. Отметим, что существует много способов синтеза градиентных процедур. Так, можно записать (4.2.20) Если разложить 1 (х, и) в ряд Тейлора в окрестности точки (х', и'), то, ограничиваясь членами первого порядка малости, получим Г ( ' )1йх1+ Г ( ' )1 АИ1 0' (4'2'21) цВ гвадивнтныв методы идвнтиеикацнн ~гл.
з где оценки Н, х, и и Л относятся к ~-й итерации вычислительного процесса. Очевидна возможность минимизации АР путем соответствующего выбора Ьпд Используя стандартную технику теории матриц, получим откуда видно, что действительно получена процедура для вычисления изменений управления при переходе от ите- рации к итерации. Так как минимизация АХ проводилась при учете квадратичных членов относительно Аи и Ьх, естественно ожидать, что использование градиентного метода второго порядкаили метода вторых вариаций дает выигрыш в скорости сходимости по сравнению с градиент- ным методом первого порядка.
Однако ускорение сходи- мости приобретается ценой аначительного усложнения вычислительных процедур и возрастания трудностей, связанных с исследованием сходимости. Процедура вычи- слений весьма напоминает соответствующую процедуру для градиентного метода первого порядка: 1) выбрать и', 2) определить х' иа 1(х', и') = О, 3) определить Н (х', и', У) = О (х*, и*) + Л'т1 (х', и'), 4) оценить Х' с помощью соотношения )=О У= — ~ 5) вычислить все проиаводные, которые входят в со- отношения (4.2.25), 6) определить пмг = и' -)- Ап', 7) повторять вычисления до тех пор, пока и'непере- станет заметно меняться от итерации к итерации.
Алгоритм существенно упрощается, если нет ограни- чений в форме равенств и О (х, и) = О (и). В этом случае формула (4.2.25) приобретает вид (4.2.26) ВЛ) МЕТОДЫ ИДЕНТИФИКАЦИИ СТАТИЧЕСКИХ СИСТЕМ 299 Таким образом, приходим к алгоритму вида „'+. Р в29 (э2) 1-2 вэ ~~ (4.2.27) (йв2)2 Еи2 Пример 4.2.2. Рассмотрим снова решение системы Ап = Ь как задачу минимизации функции штрафа У = 0 (п) = — (Ап — Ь) В (Ап — Ь), Из формулы (4.2.27) получим поп п2 (АТВА)-2 АТВ (Ап' Ь) — 4-2Ь Видно, что процедура сходится за один шаг независимо от выбора п'.
Решение системы пмт = А 'Ь. Эта особенность присуща всем линейным задачам. Однако обычная процедура вычислений содержала А ', и в этом простом случае смысл использования итеративного метода состоял в том, чтобы избежать вычисления обратной матрицы. В общем случае градиентные методы особенно полезны для решения систем нелинейных уравнений, причем градиентный метод второго порядка иногда имеет большие преимущества. До сих пор функция Х = 0 (п) минимизировалась путем применения градиентных методов первого или второго порядка. В первом случае имело место соотношение ЛЦ2 = — К' —, (4.2.28) дэ~ тогда как для градиентного метода второго порядка (4.2.29) Градиентный метод первого порядка в вычислительном отношении прост, но дает медленную сходимость в окрестности акстремума, если только не используется оптимальный градиентный метод(Сейдж, (116)), который в общем случае очень трудно реализовать.
Метод вторых вариаций дает быструю сходимость в окрестности экстремума, однако чреавычайно усложняется вычислительная про- Ддо ГРАДИЕНТНЫЕ МЕТОДЫ ИДЕНТИФИКАПД!И ДГЛ. Д удт ~ ""1уд 0 д+у (4 2 30) и д)' Затем проводится поиск в направлениях, определяемых каждым из векторов уд с тем, чтобы выбрать оптимальную величину шага. Таким образом, д+д д Кд д \ (4.2.31) где К' — положительное число, которое обеспечивает шш О (пд — К'уд), кд (4.2.32) так что в результате получается оптимальный градиентный метод. Нетрудно показать, что формула (а*) + Н (а)/ а!Р д-д (4 2 33) диа~ Нлз(ид д)/Ы дНд определяет набор положительных векторов — решений уравнения (4.2.30).
Вектор уд выбирается из формулы уд = = дНО (пд)/д(пд. На практике определение оптимального Кд, как правило, невозможно. Обычно ограничиваются проверкой нескольких возможных значений, выбранных из близкой окрестности того значения, которое использовалось на предыдущей итерации. Затем выбирается то К', которое обеспечивает наименьшее значение функции О. Метод сводится к следующей процедуре: 1) выбрать пд, 2) определить у' = дНО (пд)/дНи', 3) определить К', минимизирующее О (кд — Кдр'), 4) вычислить пд" = и' — К'у', цедура, а в окрестности экстремальной точки для обеспечения сходимости необходимо решить задачу о выборе начального приближения.
В методе сопряженного градиента (Флетчер и Пауэлл, [41)) сделана попытка соединить лучшие качества двух рассмотренных методов. Вместо того, чтобы вычислять (дРО (и)/дНпд] ', рассматривается последовательность векторов уд, уд,..., у, ортогональных к дНдО (и)/д(пэ так, что ае) ыетоды идентиФикАции стАтических систем 1$$ 5) определить ЕО(ппт) 1ЕО(пт'~)/)и '~Р— 1ее(')"1 " 6) вернуться к пункту 3) и повторять вычисления до тех пор, пока п не перестанет заметно изменяться от итерации к итерации. Прильер 4.2.3. Рассмотрим снова решение системы линейных уравнений Ап = Ь. Вновь используется квадратичная функция штрафа Х = 0(п) = — (Ап — Ь)т К (Ап — Ь).
1 2 Выберем и', тогда у' = АТК (Ап' — Ь). Заметим, что и' = пт — й'А К (Апт — Ь), где йэ выбирается так, чтобы минимизировать Х' 0(п') = — (Ап' — АА КАЕ'й'+ АА КЬй' — Ъ) х Х К(АЕ' — АА КАптй'+ ААтКЬйт — Ь) = = ((1 — АА~Кй') (Ап' — Ь))тК ((1 — ААтКй') (Апт — Ь)). Легко получить (Ап 1 — Ь)т КААТК (Аи1 — Ь) (Ап' — Ь) КААТКААТК (Ап' — Ь) Таким образом, и' определено.
После этого вычисляются у', й', пз, ... Можно показать, что если п — М-вектор, то процедура сходится к точному решению за ))Х шагов. Это утверждение можно отнести к любым линейным задачам при использовании метода сопряженного градиента с квадратичной функцией штрафа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
