Сергеев В.Л. Интегрированные системы идентификации

Подождите немного. Документ загружается.

161

],]['['

2/12/1

RDDRDRRA ==

2/12/1

∇ – якобиан (функциональный определитель).

2.5. Стационарные точки:

скалярная функция с

∂

∧

, минимум, если

∧

∂

положительно определена;

2.6. Скалярный квадрат:

()

,' Uβzeee −=

],['22

UβzUeU

−−=−=

∂

3. Матричные ряды и экспонента:

()

f AA

∑

∞

++++=

][

Теорема Кэли–Гамильтона: если nn

−

A – матрица, то любой полином

или сходящийся степенной ряд от А может быть записан в виде линейной ком-

бинации

IAA ,,,

…

−n

. Например, если А – квадратная матрица порядка 3, то

210

AAI

ααα

++=

e .

Неравенство Шварца (схема доказательства):

,0][]'[ ≥

ByAxByAx

,0''''''''

≥



ByByAxByByAxAxAx

0]'['][]'[

12/12/12/12/1

≥−+++

−−−

yDCDEyDyCxCDyCxC



= 0, если выбрать

DyCx

1−

−= .

Следовательно,

0]'['

≥−

−

yDCDEy при всех

, т. е.

≥−

−

DCDE ,

].'[]']['['

BAAAABBB

−

≥

Список литературы

1. Гантмахер Ф.Р. Теория матриц. – М.: «Наука», 1967.

2. Беллман Р. Введение в теорию матриц. – М.: Наука, 1976. – 351 с.

3. Ланкастер П. Теория матриц. – М.: Наука, 1978. – 280 с.

162

ПРИЛОЖЕНИЕ 2

ПРАКТИЧЕСКИЕ МЕТОДЫ ОПТИМИЗАЦИИ ФУНКЦИЙ

Рассматривают некоторую вещественную непрерывную функцию

)(xf от n переменных

xxx ,...,

в замкнутой области D n-мерного простран-

ства. Задача заключается в определении минимального значения функции

)(xΦ в области D и точки

, в которой это значение достигается. В общем

случае это трудная задача и не все методы ее решения совершенны с вычис-

лительной точки зрения. Потребность решения задач минимизации определя-

ется широким кругом их приложений.

Обычно различают задачи безусловной минимизации, когда множество

ограничений (область D) совпадает со всем пространством, т. е. ограничения

отсутствуют, и задачи условной минимизации – в противном случае. Как пра-

вило, последние сводятся к первым на основе различных приемов типа мето-

дов множителей Лагранжа, штрафов и др. [1]. Здесь рассмотрим только зада-

чи безусловной минимизации. Обычно их решают на основе различных мето-

дов спуска.

Основная идея этих методов такова. Выбирают некоторое начальное

приближение

x , направление ),...,,(

llll = , не касательное к поверхности

)()(

xx Φ=Φ (такое направление называют допустимым), и минимизируют

скалярную функцию

)(),,()(

0000

lxlx

ααϕαϕ

+Φ==

параметра

Пусть

– точка минимума этой функции. Полагают

lxx

+= , вы-

бирают новое допустимое направление спуска

l и минимизируют функцию

)()(

ααϕ

+Φ= и т. д.

В целом любой метод спуска заключается в следующих действиях:

1) выбор в точке

x допустимого направления

l с целью сведения исход-

ной задачи к задаче одномерной минимизации;

2) определение шага спуска

из условия минимума функции

)()(

ααϕ

+Φ= ;

3) определение очередного приближения

1+r

x по формуле

lxx

Обычно добиваются, чтобы последовательность

)(

xΦ=Φ , )(

xΦ=Φ и

т. д. монотонно убывала, а точки

,...,

xx сходились к точке минимума

функции

)(xΦ

(быть может локального). При этом основная задача – это

минимизация функции одного переменного. Часто ее необходимо решать

лишь приближенно путем достижения некоторого смещения в сторону мини-

мума вспомогательной функции и перехода затем к минимизации в другом

направлении.

163

Методы типа спуска

1. Метод наискорейшего (градиентного) спуска. Если известно при-

ближение

x , то вычисляют градиент в этой точке

)./)(,...,/)(()(

1 n

rrr

xxxxxgrad ∂Φ∂∂Φ∂=Φ

Тогда направление спуска ).(

xgradl Φ−= Следующее приближение оп-

ределяют согласно формуле

),(

1 r

xgradxx Φ−=

где

выбирают из условия минимума функции ))(()(

xgradx Φ−Φ=

ααϕ

по

. Если начальное приближение

x выбрано достаточно хорошо и в окрест-

ности искомого минимума

нет других (локальных) минимумов функции

)(xΦ

, то последовательность

x обычно сходится к

. При этом на каждом

шаге движемся в направлении наибыстрейшего убывания функции

)(xΦ

. Ес-

ли линии уровня в окрестности искомой точки минимума

представляют

слабо деформированные сферы, то метод наискорейшего спуска быстро дает

хорошее приближение, в противном случае метод будет сходиться достаточ-

но медленно, т. е. требуется большое число арифметических операций для

достижения требуемой точности. Метод асимптотически имеет геометриче-

скую скорость сходимости.

2. Метод сопряженных градиентов. В этом методе последовательные

направления спуска выбирают согласно

формулам:

,)(

−

+Φ−=

lxgradl

)(,...,2,1

xgradlr Φ−== ,

где

,)(/)(

−

ΦΦ=

xgradxgrad

т. е. направление антиградиента минимизируемой функции в точке

опре-

деленным образом комбинируется с предыдущим направлением спуска. Шаг

спуска

выбирают, как обычно, из условия минимума функции )(

по

Как отмечено в § 16, для квадратичных функций

),(2),()( xbxxAx −

метод

сопряженных градиентов дает точное решение за конечное число шагов.

Можно ожидать, что при хорошей аппроксимации функции

)(xΦ в окрестно-

сти искомого минимума квадратичной функцией метод сопряженных гради-

ентов быстро даст хорошие приближения. Поэтому его применяют, как пра-

вило, на стадии завершения поиска минимума, используя вначале более гру-

бые методы спуска (покоординатный и градиентный).

Для реализации метода сопряженных градиентов, как и метода наиско-

рейшего спуска, требуется вычисление градиента функции

)(x

, что не все-

гда оказывается простой задачей. Часто вычисляют приближение к градиенту

на базе замены производных разностными отношениями.

Существует модификация данного метода, когда на каждом шаге надо

проводить не одномерную минимизацию, а двумерную, т. е. приближение

)()(

11 −

−−

−+Φ+=

xxxgradxx

βα

164

где параметры

−

определяют из условия минимума функции

(

)

(

)

[

−

−−

−β+Φα+Φ

rrrr

xxxgradx по .,

−−

βα

Сформулированный метод полностью совпадает с методом сопряженных

градиентов для квадратичных функций и обладает аналогичными свойствами.

Метод сопряженных градиентов имеет несколько меньшую скорость

сходимости, чем касательных Ньютона.

3. Метод Ньютона. Задачу поиска безусловного экстремума функции

)(xΦ можно свести к задаче нахождения корня уравнения 0)( =Φ xgrad , кото-

рое равносильно n уравнениям относительно n неизвестных

0/)(/)(/)(:,...,,

2121

∂

∂Φ∂=

∂

Φ∂

xxxxxxxxx  .

К решению этого уравнения можно применить метод Ньютона, т. е. ис-

кать приближения по формуле

)()](''[

11 rrrr

xgradxxx ΦΦ−=

−+

где )('' xΦ – матрица порядка n с элементами

xxx ∂∂Φ∂ /)(

, называемая гес-

сианом. В обобщенном методе Ньютона направление спуска

)()](''[

1 rrr

xgradxl ΦΦ−=

−

, шаг спуска

определяют как обычно.

Если функция

),(2),()( xbxAxx

−

=Φ с положительно определенной матри-

цей А порядка n, то метод Ньютона на первом шаге дает решение задачи.

В общем случае скорость его сходимости – квадратичная. Метод Ньютона

может быть успешно применен для уточнения точки минимума функций, хо-

рошо аппроксимируемых положительно определенными квадратичными

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

дится медленно и если начальное приближение

выбрано неудачно, то даже

расходится. Поэтому применение метода Ньютона требует достаточно слож-

ных алгоритмов выбора шага и вычисления вторых частных производных

функций

)(xΦ .

3.1. Квазиньютоновский метод (метод переменной метрики) – более

эффективный метод минимизации. Направление спуска в методе

)(

xgradl ΦΗ−= , где

Η – квадратная матрица порядка n, определяемая из

рекуррентных соотношений

111

1111

−−−

−−−−

−−

−

−+Η=Η

rrr

rrrr

;

−

−=

;

)()(

−

Φ−Φ=

xgradxgrady ;

Η – произвольно задаваемая положительно определенная симметричная

матрица (например, единичная).

Если функция

)(xΦ – положительно определенная квадратичная функ-

ция, то квазиньютоновкий метод, как и метод сопряженных градиентов, дает

точное решение не более чем за n шагов. В случае произвольной функции

)(xΦ квазиньютоновский метод асимптотически обладает свойствами обоб-

щенного метода Ньютона, так как матрицы

при больших r аппроксими-

165

руют матрицу )('' xΦ в точке минимума

. Этим фактом объясняется назва-

ние метода. Его преимущество перед методом Ньютона – отсутствие необхо-

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

В настоящее время существует значительное число модификаций метода

[1, 12].

4. Метод Гаусса–Ньютон. Метод Гаусса–Ньютона используется для

минимизации суммы квадратов отклонений

,),((

xfy −=Φ

∑

где ),(

xf – нелинейная по параметрам

функция регрессии.

Суть метода Гаусса–Ньютона состоит в том, что функция регрессии ап-

проксимируется линейной по параметрам функцией в окрестности точки

.)),((),()(

),(

),(),(

ααααα

αα

Δ∇+=−

⎟

⎠

⎞

⎜

⎝

⎛

∂

∑

xfxf

Индекс «0» у частных производных означает, что они вычислены в точке

αα

= С учетом данного приближения функции регрессии функционал каче-

ства

Φ можно представить в виде:

)()(

000000

αα

Δ−Δ−=Φ DeDe

⎥

⎦

⎤

⎢

⎣

⎡

−

),(

xfy

⎥

⎦

⎤

⎢

⎣

⎡

∂

= .

...

nnn

fff

ααα

⎥

⎦

⎤

⎢

⎣

⎡

−

=Δ

αα

e – вектор столбец невязок;

D – матрицы частных производных в точках

nix

,1, = , при

αα

= ,

Δ – вектор столбец приращений параметров.

Для определения вектора приращений

достаточно взять производ-

ные от функционала

Φ и приравнять их к нулю:

0)(2

000

=Δ−Δ−=Φ∇

αα

DeD

В результате получим систему линейных уравнений

000

)()( eDDD

=Δ

решение которой позволяет получить следующее приближение для параметров

ααα

Δ+= h .

Получив '

, можно аналогичным образом построить ''

Δ+= hxx ,

где

– размер шага на второй итерации.

166

Таким образом, для всех итераций 0, 1, 2, ...j

алгоритм Гаусса–

Ньютона можно записать в виде

, 0,1, 2,...,

()(),

TTj

DD De

αα α

−

⎧

=+Δ =

⎪

⎨

Δ=

⎪

⎩

где

)(

−

DD – обратная матрица на j-м шаге.

Если матрица

плохо обусловлена, то метод Гаусса–Ньютона схо-

дится очень медленно. В данной ситуации для определения приращений

на шаге j используется СЛУ вида

jTj

eDADD )()( =Δ+

αβ

где 0≥

, A – неотрицательно определенная матрица. При

= и

0, 0, 1, 2, ...

=> = , метод Гаусса–Ньютона совпадает с методом Левен-

берга

, 0,1, 2,...,

()(),

jj j

jT Tj

DD I De

αα α

αβ

−

⎧

=+Δ =

⎪

⎨

Δ= +

⎪

⎩

где матрица )( IDD

+ невырождена.

5. Метод оврагов. Этот метод применяют в ситуациях, когда линии

уровня минимизируемой функции сильно отличаются от сфер и спуск по гра-

диенту происходит медленно. Основная идея метода состоит в следующем.

Задаются приближениями

и проводят спуск из этих точек каким-либо

методом – покоординатного спуска, градиентным и т. п. Обычно делают не-

сколько шагов и получают новые приближения

, которые, как прави-

ло, лежат в многообразии, содержащем относительно большие оси «эллип-

соидов» – поверхностей уровня функции

)(x

. Из точки

производят спуск

в направлении

L , определяемом вектором

−

, и получают приближение

x .

Из точки

спуск осуществляют выбранным ранее методом и получают но-

вую точку

Χ , из которой проводят одномерный спуск по направлению

121

L −= , и т. д. Точки ,...,,

210

XXX расположены на «дне» оврага. Отсюда

и произошло название метода. Часто приближения

1+r

осуществляют по

формуле

)()(

11 r

XgradXXXx Φ+−+=

−+

βα

в которой

определяют из условия

)]()([min

rrrr

XgradXXX Φ+−+Φ

−

βα

Метод оврагов «работает» в ряде случаев, когда линии уровня функции

)(xΦ имеют сложную структуру и другие методы неэффективны.

6. Метод регуляризации. Задача минимизации часто оказывается плохо

обусловленной в том смысле, что для некоторой точки

x значение )(

xΦ мо-

жет быть достаточно близким к минимальному

)(

, однако точку

x нельзя

принять за хорошее приближение к точке минимума v. При наличии погреш-

167

ностей в задании функции )(xΦ даже вычисленные значения )(

xΦ могут не

быть близкими к

)(

. В таких случаях применяют метод регуляризации за-

дачи минимизации.

Пусть для определенности

0)( ≥

x . Обычно выбирают некоторую квад-

ратичную функцию

)()'(

)( XxCXxXx −−=−Ω

с положительно определенной матрицей С и рассматривают регуляризован-

ную задачу минимизации: найти точку

x , в которой достигается минималь-

ное значение функции

),()()( Xxxx

−

Здесь Х – вектор пробного решения, задаваемый из априорных соображений

относительно искомой точки минимума v;

– параметр регуляризации;

)(yΩ

– стабилизирующая функция. Если выбрать X = v, то все регуляризо-

ванные решения

≡x ,

. Обычно

≈

, поэтому можно ожидать, что

при некотором значении параметра регуляризации

≈

x . Можно показать,

что

→

lim

[считается, что v – единственная точка минимума функции

)(xΦ ].

Регуляризованная задача минимизации (р. з. м.) при больших значениях

обусловлена значительно лучше, чем исходная. Причиной этого является

следующее:

Xx =

∞→

lim

, а вектор Х очевидно минимизирует функцию

)( Xx −Ω

. Таким образом, при больших значениях

р. з. м. можно заменить

задачей минимизации функции

)( Xx

−

. Отсюда вытекает тактика компро-

миссного выбора параметра регуляризации: параметр регуляризации (п. р.)

должен быть достаточно мал, чтобы регуляризованные решения (р. р.) ап-

проксимировали искомое, но не настолько, чтобы потерялась устойчивость

задачи.

При численном решении регуляризованная задача минимизации обычно

задают последовательность значений

>>> ...

, где

– соответст-

венно достаточно большое и достаточно малое числа. Для определения регу-

ляризованных решений

x используют один из методов спуска, который счи-

таем выбранным. Чтобы определить приближение к

, в качестве начально-

го приближения выбирают Х, которое затем уточняют на основе выбранного

метода спуска. Полученное приближение к

x обозначим



. Пусть на осно-

ве этой процедуры уже определены приближения



≈

. Тогда в качестве

начального приближения при отыскании



берут



, которое затем уточ-

няют. Приближение к искомому решению находят среди полученной серии

приближенных р. р.

, , ...,

αα α



, исходя из приведенных ранее соображе-

ний. При получении этих решений нет необходимости делать много уточ-

168

няющих итераций, так как рассматриваемое значение параметра регуляриза-

ции может быть далеко от искомого. Как только подходящее значение п.р.

выбрано, процедуру можно повторить, взяв более густую сетку по

в окре-

стности выбранного значения, и т. д.

Удобно задавать геометрическую сетку по

,1,...,1,0,:

−=

Miq

оп-

ределяемую начальным значением

и знаменателем сетки 1≈q . В этом слу-

чае подходящие приближенные решения определяют из принципа выбора ква-

зиоптимальных значений параметра регуляризации, при которых достигается

минимальное значение уклонений

1ii

−



по i для некоторой нормы

•

Процедура выбора параметра регуляризации трудно формализуема, од-

нако решение значительного числа модельных и практических задач показало

эффективность применения метода регуляризации. В частности, можно при-

влекать и некоторые неформальные соображения, основанные на априорном

представлении о качественных характеристиках поведения модели. В этих

случаях весьма эффективным оказывается использование при решении на

ЭВМ таких

наглядных средств представления дискретной информации, как

АЦПУ, графопостроители, дисплеи и т. п.

Выбор стабилизирующей функции

)( Xx

−

можно осуществить и в дру-

гих формах. Часто

)( Xx −Ω характеризует «стоимость» отклонения парамет-

ров х новой модели от параметров Х, описывающих старую модель. Метод

регуляризации позволяет найти такое решение задачи минимизации, которое

обладает минимальной «стоимостью» в смысле выбранного критерия

)( Xx −Ω

. Иногда вектор Х – результат прямых (непосредственных) измере-

ний искомого параметра х.

Метод регуляризации успешно применяют и для решения еще одной

трудной задачи минимизации – нахождения глобального минимума. Это свя-

зано с тем, что при больших значениях параметра регуляризованная задача

чувствительна только к глобальному минимуму, локальные минимумы ниве-

лируются.

Если для минимизации

)(x

Φ выбран метод Ньютона, то последователь-

ные итерации

)]()('[)](''[

XxCxxCxx

rrrrr

−+ΦΦ+−=

−+

αα

определяют регуляризованный метод Ньютона. При этом требуется, чтобы

матрицы

)(''

xΦ были неотрицательными.

Часто, особенно в задачах аппроксимации, функция

)()(

xfx

∑

=Φ .

Если функции )(xf

дифференцируемы, то справедливо линеаризованное

представление

)( yx

≈

),(

)(

)()(

yfxf −

∂

+≈

∑

169

так что

∑∑

−

∂

+≈Φ

xfx

])(

)(

)([)(

в окрестности точки

x . Отсюда можно приближенно определить как

),(' xΦ

так и

)('' xΦ

. При этом матрица

)('' x

будет заведомо неотрицательной.

Если при определении

1+j

заменить в регуляризованном функционале

вектор Х на предыдущее приближение

, то получим адаптивный метод

регуляризации задачи минимизации. Иногда он может оказаться более пред-

почтительным, так как область подходящих значений параметра регуляриза-

ции в этом случае существенно шире.

Список литературы

1. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике. В 2-х

кн. / пер. с англ. – М.: Мир, 1986.

2. Мину М. Математическое программирование. Теория и алгоритмы. –

М.: Наука, 1990.

3. Рубан А.И. Оптимизация систем: учебное пособие. – Томск: Изд-во

Томск, ун-та, 1984.

4. Дэннис. Дж., Шнабель Р. Численные методы безусловной оптимиза-

ции и решения нелинейных уравнений / пер. с англ. – М.: Мир, 1988.

5. Карманов В.Г. Математическое программирование: учебное пособие. –

М.: Наука, 1989.

6. Химмельблау Д. Прикладное нелинейное программирование. – М.:

Мир, 1991.

7. Аоки М. Введение в методы оптимизации. – М.: Наука, 1988.

8. Полак Э. Численные методы оптимизации. Единый подход. – М.: Мир,

1994.

9. Уайлд Д.Дж. Методы поиска оптимума. – М.: Наука, 1997.

10. Габбасов Р., Кириллова Ф.М. Методы оптимизации. – Минск: Изд-во

БГУ, 1988.

11. Бахвалов Н.С. Численные методы. – М.: Наука, 1989.

12. Гилл Ф. и др. Практическая оптимизация. – М.: Мир, 1992.

13. Коршунов Ю.М. Математические основы кибернетики: учебное посо-

бие для втузов. – М.: Энергоатомиздат, 1987.

14. Боглаев Ю.П. Вычислительная математика и программирование: учеб-

ное пособие для студентов втузов. – М.: Наука, 1989.

15. Рубан А.И. Методы оптимизации: учебное пособие. – Изд. 2-ое, испр.

и допол. – Красноярск: Изд-во НИИ ИПУ, 2001.

16. Мицель А.А., Шелестов А.А. Методы оптимизации: учебное пособие. –

Томск, 2002. – 192 с.

170

ПРИЛОЖЕНИЕ 3

КЛАССИЧЕСКИЕ МЕТОДЫ ИДЕНТИФИКАЦИИ СИСТЕМ

В УСЛОВИЯХ НЕПОЛНОЙ ИНФОРМАЦИИ

Введение

В данном приложении рассматриваются стабильные классические мето-

ды идентификации систем в условиях неполной информации. При обычной

постановке задач идентификации предполагается, что в распоряжении иссле-

дователя имеется весьма полная информация. Так, считаются известными

(с точностью до параметров) законы распределения помех, априорная плот-

ность распределения вероятности решения, уравнения модели. Однако в ре-

альных условиях подобная информация, как правило, неточна – распределе-

ния лишь приближенно можно считать заданными, фактическое поведение

объекта не адекватно его модели и т. п. В этой ситуации весьма остро встает

вопрос о стабильности методов идентификации, принимаемых решений и

важное значения приобретают методы решения статистических задач, кото-

рые бы эффективно работали при

неполной исходной информации.

В приложении приведен обзор наиболее используемых стабильных ме-

тодов идентификации, связанных с методами оценивания параметров функ-

ций регрессии при решении широкого спектра различных научно-

технических задач.

Постановка задачи идентификации параметров функций

Пусть имеется модель статического стохастического объекта вида

,),(

αxfy

где х – входные величины;

- параметры объекта; y – выходные величины;

– помехи. Здесь ,

Ry ∈ ,

R∈

R∈x

R∈α . Требуется по измерениям

niy

,1 ,,

=x :

iii

+= ),(

αx (1)

оценить параметры

α . При этом предполагается, что помехи

независимы и

имеют одинаковую симметричную плотность

),(zp т. е. ).()( zpzp −= В даль-

нейшем будут сделаны те или иные предположения о доступной информации

относительно

)(zp

и решении α .

Методы максимального правдоподобия и наименьших квадратов

Предположим, что плотность )(zp известна, а априорная информация о

решении полностью отсутствует. Одним из наиболее распространенных ме-

тодов оценивания в этой ситуации является метод максимального правдопо-

добия [1], который в данном случае принимает вид