Методы вычисления логарифмической функции правдоподобия и ее градиента в алгоритмах калмановской фильтрации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Куликова, Мария Вячеславовна
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Ульяновск
МЕСТО ЗАЩИТЫ
|
||||
|
2005
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
на правах рукописи
КУЛИКОВА Мария Вячеславовна
МЕТОДЫ ВЫЧИСЛЕНИЯ ЛОГАРИФМИЧЕСКОЙ ФУНКЦИИ ПРАВДОПОДОБИЯ И ЕЕ ГРАДИЕНТА В АЛГОРИТМАХ КАЛМАНОВСКОЙ ФИЛЬТРАЦИИ
Специальность: 01.01.09 — дискретная математика и
математическая кибернетика
Автореферат
диссертации на соискание ученой степени кандидата физико-математических наук
Ульяновск - 2005
Работа выполнена на кафедре математической кибернетики и информатики государственного образовательного учреждения высшего профессионального образования Ульяновский государственный университет
Научный руководитель:
Официальные оппоненты:
Ведущая организация:
доктор технических наук, профессор Семушин Иннокентий Васильевич
доктор физико-математических наук, профессор Жданов Александр Иванович
кандидат физико- математических наук, доцент Жарков Александр Валентинович
Ульяновский Государственный Технический Университет, 1'. Ульяновск
Защита состоится " ¿.Л " РДЖ-О^р-М _ 2005 г. в ±4- ч. ОО _мин на заседании диссертационного совета Д 212.278.02 при Ульяновском государственном университете по адресу: I1. Ульяновск, Университетская Набережная, 1, ауд. 703
Отзывы по данной работе просим направлять по адресу: 432700, г Ульяновск, ул. Л.Толстого, 42, УлГУ, УНИ.
С диссертацией можно ознакомиться в библиотеке Ульяновского государственного университета.
Автореферат разослан " 1 £~ "
2005 г.
Ученый секретарь диссертационного совета /рУ/^ Веревкин А Б.
№\Q>
22fZ77J
Общая характеристика работы
Актуальность темы. Одними из важнейших задач математической кибернетики являются: задача адаптации и построения адаптивных систем, идентификация, контроль, т.е. обнаружения неисправностей в функционировании системы и моментов их возникновения. Рассмотрению этих задач посвящено большое количество работ как в отечественной, так и зарубежной литературе. Заметный интерес обусловлен тем, что все они находят глубокое применение в повседневной жизни и охватывают широкий круг приложений Например, особое значение при непрерывном мониторинге за сейсмической обстановкой на территории сейсмоактивного региона имеет надежное обнаружение и точная оценка на записях появлений сейсмических волн от землетрясений1. В промышленности важную роль играет мониторинг за качеством продукции. Отметим, что в современных условиях существует огромный финансовый интерес на промышленных предприятиях в развитии и разработке новых более совершенных диагностических методов для наблюдения за производственной деятельностью и обнаружения аномальных ситуаций2. Особая роль отводится задачам такого тина, например, в навигации3, при эксплуатации радиотехнических систем и т.д.
Одним из наиболее мощных инструментов для решения перечисленных выше задач были и остаются статистические методы. "Для построения современных сложных систем обработки информации и управления решающее значение имеют эффективные статистические методы, дающие основу для решения возникающих здесь задач распознавания, обнаружения, оценивания, фильтрации сигналов, совместной обработки информации и управления4...".
1Bassevii.[ е М., Nikiforov I Detection of Abrupt Changes- Theory and Applications. Prcntice-Hall, Englewood Cliffs: New Jersey, 1993
2Seborg DEA perspective on advanced strategies for process control (revisited)// In Advances in control- highlights of ECC'99, London: Springer-Verlag London Limited, 1999 Г 103-134
3Nikiforov I , Varava V , Kireichikov V Application of statistical fault detection algorithms for navigation systems monitoring// Proc IFAC/IMACS Symp SAFEPROCESS'91 Badpn-Baden 1991 V. 2. P. 351-356.
4Хлзен Э.М Методы оптимальных статистических решений и задачи оптимального управления М. изд-во "Советское радио", 1968
При использовании данной группы методов приходится решать близкие, оказывающие огромное влияние на эффективность и, соответственно, на конечный результат применения самого статистического подхода, задачи аффективного вычисления логарифмической функции правдоподобия и ее градиента.
Объектом исследования данной работы являются линейные дискретные стохастические системы вида:
где х1 — г7-мерный вектор состояния системы, доступный для наблюдения т-мерный вектор измерений. Последовательности {иго, и)\,...} и • ■ •} — независимые нормально распределенные последователь-
ности шумов с нулевыми средними и ковариационными матрицами (¿^О) и /?{(#). соответственно. Кроме того, {гио, »ь • • •} и {г>1, г>2,...} не зависят от начального вектора состояния системы хо ~ Л/"(хо>По). Предполагаем, что элементы матриц Ф*(0) е Япхп, <3,(0) 6 Я"*9, Щв) е Я™*".
& Я4*4 и £ Дг"хт являются функциями от некоторого пара-
метра в е ир.
Для систем (1), (2) вычисление логарифмической функции правдоподобия (ЛФП), как известно, осуществляется с помощью дискретного фильтра Калмана. В то же время задача вычисления градиента ЛФП в каждый момент времени ¿ = 1,2,... N требует применения р параллельных "дифференцированных"фильтров (по отношению к неизвестному параметру системы в € Яр).
Возникающая, в связи с необходимостью применения дискретного фильтра Калмана, проблема хорошо известна — его стандартная реализация является неустойчивой по отношению к ошибкам округления, что очевидным образом влечет за собой некорректное вычисление ЛФП и ее градиента. В итоге, это не только может ухудшить эффективность самого статистического подхода, используемого для решения тех или иных практических задач, но и, вообще, поставить под сомнение полученный результат. В сложившихся обстоятельствах остро встает проблема разработки новых численно эффективных алгоритмов нахождения указанных выше величин.
х,+1 = Ф1(9)х( + С^в)и>ь ^ = Щ(в)Х( + ьи
(1) (2)
Целью работы является разработка, обоснование и тестирование эффективных алгоритмов для вычисления логарифмической функции правдоподобия и ее градиента для линейных дискретных динамических систем, возмущаемых белым гауссовым шумом. В рамках данного исследования будет проведен сравнительный анализ эффективности разработанных алгоритмов, включающий в себя анализ их вычислительной сложности и устойчивости к ошибкам округления.
Методы исследования. В диссертационной работе использованы методы вычислительной математики, математического анализа, линейной алгебры и программирования.
Достоверность результатов обеспечивается строгостью постановок задач и математических методов их решения.
Научная новизна. Построенные на основе покомпонентной обработки вектора измерений, численно эффективные модификации алгоритмов рекуррентного оценивания вектора состояния линейных дискретных динамических систем, возмущаемых белым гауссовым шумом, являются новыми. Разработанные методы вычислетшя логарифмической функции правдоподобия являются новыми. Предложенная методика вычисления производной матрицы специального блочного треугольного вида Я'д, связанной ортогональным преобразованием ф с прямоугольной матрицей А, является новой. Разработанные численно эффективные алгоритмы рекуррентного вычисления градиента логарифмической функции правдоподобия, основанные на квадратно-корневых реализациях дискретного фильтра Калмана, также являются новыми.
Практическая и теоретическая значимость. Работа имеет теоретический характер. Ее научная ценность определяется тем, что в ней предложены новые численно эффективные алгоритмы вычисления логарифмической функции правдоподобия и ее градиента для линейных дискретных стохастических систем, возмущаемых белым гауссовым шумом. Разработан новый способ вычисления производной матрицы по параметру, нетребующий соблюдения условия невырожденности матриц Эти методы, формулируемые в виде теорем, получили строгое математическое обоснование. В прикладном аспекте особо следует подчеркнуть возможность применения полученных результатов при решении совремеп-
пых прикладных задач с использованием многопроцессорных вычислительных комплексов в качестве средства вычислений, поскольку все разработанные в диссертации алгоритмы допускают эффективное распараллеливание.
Исследования проводились при финансовой поддержке Министерства общего и профессионального образования России грант Министерства Образования Российской Федерации (проект N Т02-03.2-3427, 2002-2003)
Основные положения, выносимые на защиту.
1 Численно эффективные модификации квадратно-корневых реализаций дискретного фильтра Калмапа, разработанные на основе покомпонентной обработки вектора измерений системы.
2. Математическое обоснование алгоритма вычисления логарифмической функции правдоподобия, построенного на основе "скаляризо-ванной"стандартной реализации дискретного фильтра Калмана.
3. Численно эффективные алгоритмы рекуррентного вычисления логарифмической функции правдоподобия, разработанные на основе "скаляризованных"квадратно-корневых методах фильтрации и ориентированные на параллельные вычисления.
4. Способ вычисления матрицы Щ специального блочного треугольного вида, связанной ортогональным преобразованием С} с прямоугольной матрицей А.
5. Численно эффективные алгоритмы рекуррентного вычисления градиента логарифмической функции правдоподобия по отношению к неизвестному параметру системы в б ЯР, основанные на квадратно-корневых реализациях дискретного фильтра Калмана и ориентированные на параллельные вычисления.
Апробация работы. Результаты диссертации докладывались и обсуждались на:
• IV международной научно-технической конференции "Математическое моделирование физических, экономических, технических, социальных систем и процессов" (Ульяновск, 2001);
• XXIV конференции молодых ученых механико-ма тематического факультета МГУ им. М.В. Ломоносова (Москва, 2002);
• V международной научно-технической конференции "Математическое моделирование физических, экономических, технических, социальных систем и процессов11 (Ульяновск, 2003);
• international conference on computational science (ICCS- 2003) (St. Petersburg Russia, 2003);
• conference on scientific computing and differential equations (SciCADE 2003) (Trondheim, Norway, 2003);
• conference on scientific computing and differential equations (SciCADE 2005) (Nagoya, Japan, 2005).
Личный вклад автора. Постановка задач осуществлялась научным руководителем, д.т.н., профессором И.В. Семушиным. Доказательство всех лемм и теорем, проведение расчетов и анализ полученных результатов выполнены автором самостоятельно.
Публикации. Основные результаты диссертации опубликованы в работах [1]-[11]. При этом результаты из работ, подготовленных в соавторстве, либо иснользованы частично, в соответствии с личным вкладом каждого автора ([10], [11]), либо приведены в переработанном виде ([6])
Структура диссертации. Диссертация объемом 131 страница состоит из введения, трех глав, заключения и списка литературы (114 наименований). Работа включает 29 таблиц и 13 рисунков.
Содержание работы
Введение содержит обоснование актуальности рассмотренных в диссертации вопросов. Здесь приведен обзор литературы, посвященной последним исследованиям и достижениям при разработке наиболее эффективных (с точки зрения вычислительных затрат и устойчивости к ошибкам округления) реализаций дискретного фильтра Калмана, а также способов
вычисления логарифмической функции правдоподобия (ЛФП) и ее градиента (ГЛФП) для линейных дискретных динамических систем, возмущаемых белым гауссовым шумом. Здесь же определяются цель исследования, научная новизна и практическое значение, перечислены основные результаты диссертации, выносимые на защиту. Кратко изложено содержание диссертационной работы.
Первая глава, состоящая из пяти параграфов, посвящена исследованию и построению численно эффективных алгоритмом рекуррентного оценивания вектора состояния линейных дискретных динамических систем, возмущаемых белым гауссовым шумом
Параграфы 1.1 и 1.2 носят вводный характер. В них приведена постановка задачи и дан краткий обзор инноваций в сфере исследований, посвященных разработке наиболее эффективных реализаций дискретного фильтра Калмана.
В последние 10-15 лет акцент ставится на создание эффективных алгоритмов, ориентированных на возможность дальнейшего применения многопроцессорных вычислительных комплексов в качестве средства вычислений. Реализации данного типа были предложены в 1995 г. и включают в себя: расширенные квадратно-корневые ковариационный и информационный фильтры (РКККФ и РККИФ), модифицированный квадратно-корневой информационный (МККИФ) и комбинированный квадратно-корневой (КККФ) фильтры (см. Park P., Kailath Т.5). Перечисленные выше алгоритмы изложены в параграфе 1.2 диссертационной работы, где также подробно обсуждаются их преимущества и недостатки.
В параграфе 1.3 на их основе разработаны последовательные алгоритмы рекуррентного оценивания с использованием процедуры покомпонентной обработки вектора наблюдений дискретной стохастической системы. Широко известно, что подобная "переформулировка"улучшает как вычислительные характеристики, так и эффективность самого процесса
5Park Р , Каиатн Т Now Square-Boot Algorithms for Kaiman Filtering// IEEE trans on Automatic Control. 1995 V. 40. N 5. P. 895-899
фильтрации (см , например, Kaminski P.G6. Lewis F.L.7, Verhaegen M.8). Здесь же представлено их строгое математическое обоснование.
Методика построения "скаляризованных"типов методов заключается в следующем: если матрица ковариации шумов в измерителе (2) Rt имеет
диагональный вид, Rt = diag ,..., (о"'™') |, то этапы обработки
измерений базовых ("векторных") алгоритмов фильтрации могут быть заменены на алгебраически эквивалентные, полученные с помощью обработки вновь поступившего вектора измерений zt по-компонептио В итоге для указанных выше фильтров получаем следующие (алгебраически эквивалентные "базовым") этапы обработки измерений:
• Для алгоритма РКККФ:
1. Положить: Sf] = Р//2, xf] = xt .
2. Для к = 0,1,... m — 1 вычислять:
п(к) ut,i
otl) О S(k)h(k.и) 5(Чфг
-z[k+1)/a{k+x) <~Т (к)
{sik))~
X
О
J
slk+1)&t
-(fc+1)
(,sik+1)}
-T
)
(к)
где О] 1 — ортогональное преобразование, приводящее к верхнему треугольному виду два первых (блочных) столбца матрицы, стоящей в правой части формулы (3).
(3)
3. Положить: P}!4Tt = S(tm)<S>'[ и Pt~Tßxl
0(m)) *{
(m)
"Kaminski P.G , Bryson A.E , Schmidt S F Discrete Square Ront Filloring A suivey of Current Techniques// IEEE Trans on Aut. Cont 1971 V AC-16 N 6 P 727-735
7Lewis F.L Optimal Estimation with an Introduction to Stochastic Control Theory 1986 Jonh Wiley&Sons New York, 1986
'Verhaegen M , Van Dooren P Numerical Aspects of Different Kaiman Filter Implementations// IEEE Ttans. on Autom Contr 1980 V AC-31 N 10 P 907-917.
Для алгоритма РККИФ:
1. Положить: 5,(0) = Д"т/2, х|0) = х;.
2. Для А; = 0,1,... ш — 1 вычислять:
П(к) и1Л
к+1))т 0
1'де о\д - матрица ортогонального преобразования, которая при умножении слева на первый блочный столбец матрицы, стоящей в левой части формулы (4), приводит- его к нижнему треугольному виду.
3. Положить: Р1 = и ± 1 ^ Для алгоритма МККИФ:
1. Положить: б'^ = Я(_Т/'2, х^ —
2. Для к — 0,1,... т — 1 вычислять:
Г
5«
п(к)
- (лГ4)' /ар+1)
О
О
т
-т
(¿¡Г4) * ФГ
г\к+1)/е\М) З1к)х[к)
(к+1)
-ч 5(*+1)в(*+1)
(5)
где О^д — ортогональное преобразование, которое приводит либо к нижнему треугольному виду первый (блочный) столбец, либо к верхнему треугольному виду второй (блочный) столбец матрицы, стоящей в правой части (5).
3. Положить: Д Т/2 = 5((т) и РГТ'2^ Для алгоритма КККФ:
1. Положить: 5,<0) = Рг1/2, а^0' =
оЫ) (т)
2. Для к = 0,1,... т — 1 вычислять:
О,
«1к+1) О
ге,<
О
К
(*+1)У
(
у
(лГ')
-г
-г
а:«
(к)
-Т
Щ
(*+1)
(6)
где о[д — ортогональное преобразование, приводящее либо к верхнему треугольному виду первые два (блочных) столбца, либо к нижнему треугольному виду третий (блочный) столбец матрицы, стоящей в правой части формулы (6). 1/2 _ Мт) „ _ (т)
3. Положить: Р1/ = 5( и х
Щ
В формулах выше приняты следующие обозначения: пусть матрица А > О, будем рассматривать разложение Холецкого вида: А — АТ^2А1^2, где А1/2 — верхняя треугольная матрица, являющаяся квадратным корнем А. Тогда Ат>2 = (А^У, А'1'2 = (Л1/2)"1 и А~т/2 = (А 1'2)т. Для величин, вычисляемых в фильтре Калмана. примем обозначения:
ь . е^ нормализованные невязки
—Т/2
фильтра Калмана, т.е. е( = < е, где е = 27 — невязка измерений
фильтра в момент времени характеризующаяся ковариационной матрицей Е{е1е^} = ДС14, Н1РН? Ч Кроме того, и Д — предсказанная и отфильтрованная оценки вектора состояния системы (1), (2) и оценки матрицы ковариации ошибки оценивания, соответственно
Таким образом, построены новые модификации алгоритмов калманов-ской фильтрации, отличающиеся от разработанных в последние годы реализаций тем, что вектор измерений в них обрабатывается покомпонентно, что существенным образом сказывается на их работоспособности и улучшает их вычислительные характеристики.
Теорема 1 Пусть матрицы ковариации шумов в измерителе (2) имеют диагональный вид, т.е. Яг — <Иа§ ,... |. Предста-
вим матрицу построчно: Нь =
(к
]х))
) \
Тогда этапы
обработки измерений алгоритмов П-РКККФ, П-РККИФ, П-МККИФ и П-КККФ алгебраически эквивалентны этапу обработки измерений стандартного фильтра Калмана. где вектор измерений в каждый момент времени I обрабатывается поэлементно: = г,2', ..., г^™^.
В параграфе 1.4 проведен сравнительный анализ эффективности разработанных "скаляризованных"алгоритмов фильтрации, включающий в себя анализ вычислительной сложности и устойчивости к ошибкам округления.
Проведенное исследование показало, что последовательные реализации фильтра, построенные с использованием процедуры "скаляризации" измерений, позволяют существенным образом сократить общее количество арифметических действий на организацию вычислений. Здесь же на примерах плохо обусловленных задач изучена устойчивость новых алгоритмов по отношению к ошибкам округления, что подтвердило их превосходство над стандартной реализацией дискретного фильтра Калмана.
В параграфе 1.5 все теоретические результаты главы 1 подтверждены на практике экспериментальными данными.
Вторая глава, состоящая из пяти параграфов, посвящена разработке новых эффективных алгоритмов для вычисления логарифмической функции правдоподобия (ЛФП) для линейных дискретных динамических систем, возмущаемых белым гауссовым шумом. Эта задача находит свое применение при решении многих приложений методами, относимыми к группе статистических.
В параграфе 2.1 изложена постановка задачи данной главы диссертационной работы. В условиях системы (1), (2) отрицательная ЛФП, построенная для результата ¿-го измерения ги задается формулой:
= \ 1п(2тг) + 1п(с1е^Я„,,)) + еГЛ^Ц . (7)
Согласно (7) вычисление ЛФП влечет за собой применение фильтра Калмана, стандартная реализация которого, является неустойчивой по отношению к ошибкам округления. Следовательно, задача эффективного вычисления ЛФП существенным образом зависит от выбора той или иной реализации фильтра.
В параграфе 2^2 представлено математическое обоснование алгоритма для вычисления ЛФП, построенного на основе "скаляризовапной"стандартной реализации дискретного фильтра Калмана
В параграфе 2.3 разработаны новые эффективные алгоритмы для вычисления ЛФП, сформулированные на основе предложенных в первой главе диссертации "скаляризованных"реализаций фильтра. Здесь же представлено их строгое математическое обоснование.
В первой главе диссертационной работы было показано, что алгоритмы П-РКККФ, П-РККИФ, П-МККИФ и П-КККФ превосходят по своей эффективности их "векторные"аналоги. По этой причине, они послужили "базовыми"методами для создания на их основе алгоритмов для вычисления ЛФП.
Предлагаемая методика их построения заключается в следующем: для каждого из указанных выше фильтров на этапе обработке измерений и фильтрации организуем дополнительные вычисления'
1. Для к = 0,1,... т — 1 вычислять:
4*+1) - 1- (е?+1))2; ДГх) = Д« + 21п (г^+1)) .
2. Положить: [ 1п(<ИЯе,«))]== Д»М. [е'/'Я^Ч] := г5((т).
В параграфе 2.4 проведен сравнительный анализ эффективности разработанных алгоритмов ЛФП-ПРКККФ, ЛФП-ПРККИФ, ЛФП-ПМККИФ ЛФП-КККФ, включающий в себя анализ вычислительной сложности и устойчивости к ошибкам округления.
В параграфе 2.5 все теоретические результаты главы 2 подтвержден!.! на практике экспериментальными данными.
Третья глава, состоящая из шести параграфов, посвящена разработке новых эффективных алгоритмов для вычисления градиента логарифмической функции правдоподобия (ГЛФП) для линейных дискретных динамических систем, возмущаемых белым гауссовым шумом В частности, эта задача находит свое применение при использовании метода максимума правдоподобия, с целью нахождения оценки неизвестного параметра системы. Действительно, многие алгоритмы поиска экстремума функции, применяемые для ее решения, требуют вычисления ГЛФП.
В параграфе 3.1 приведена постановка задачи данный главы диссертации и вывод формул для вычисления ГЛФП для рассматриваемых систем (1), (2).
Лемма 1 Пусть элементы треугольной (верхней или нижней) матрицы А £ Д"х" являются достаточно гладкими функциями от некоторого вектора параметров в £ ВР. Тогда, справедливо утверждение:
дв.
[Цае^Л))] = Ьт
А-г дА дв,.
г = 1,2 ,...,р,
(8)
где <;г [•] - след матрицы.
Дифференцируя (7), используя лемму 1, получаем формулы для вычисления ГЛФП, построенной для результата £-го наблюдения в системе (1), (2) при условии обработки предыдущих измерений:
ад дв,
= ^
р—1/2 дИ$
... де,
г = 1,2...р.
(9)
Формула (9) применима только в случае вычисления ГЛФП на основе квадратно-корневых ковариационных алгоритмов фильтрации. Для информационных типов фильтров справедливо:
дв,
1/2 дЯе ( Ее* ' двг
1/2
+ дв,'
"Н7Г' ¿ = 1,2...р.
(10)
Итак, становится очевидным, что нахождение ГЛФП влечет за собой применение р параллельных фильтров Калмана, где р количество параметров системы, значения которых необходимо оценить. Однако, хорошо известно, что стандартная реализация фильтра является неустойчивой по отношению к ошибкам округления.
В первой главе диссертации были изложены новые алгоритмы фильтрации, разработанные за последние 10 лет и существенно превосходящие по своей эффективности стандартную реализацию дискретного фильтра Калмана. Более того, данные алгоритмы ориентированы на параллельные вычисления. По указанным выше причинам, реализации РКККФ,
РККИФ и МККИФ послужили "базовыми" мсходами для создания на их основе новых эффективных алгоритмов для вычисления ГЛФП.
В параграфе 3.2 разработан алгоритм для вычисления ГЛФП на основе РКККФ. Здесь же представлено его строгое математическое обоснование.
Прежде всего рассмотрим вырожденные квадратные матрицы А и В размера к х к такие, что:
О Ак,в 0 = В, 0
0 0
А В
где О ортогональное преобразование, приводящее к блочному верхнему треугольному виду матрицу В. Кроме того, — ненулевой блок расширенной матрицы А размера к х в и В8 невырожденный блок матрицы В размера в х з.
Введем следующие обозначения: пусть - подматрица, разме-
ра в х 5, сформированная из элементов матрицы 0'в0т, стоящих на перс-сечении ее первых в столбцов и строк. Аналогичные обозначения примем для матриц 0(Л)'в, В, т.е. (О(Л)^, Вв.
Лемма 2 Пусть вырожденные квадратные матрицы Ли В размера к х к имеют блочную структуру и удовлетворяют (11). Тогда справедливы утверждения:
• строго нижние треугольные части подматриц (0'в0Т^ и (О(А)д) (Д,)-1 совпадают;
• верно, что
{ВМВ,)-1 = (о'воТ)з + (<0(Л)'в)8 (Вв)-\ (12)
Алгоритм ГЛФП-РКККФ
I. Для каждого 9и г = 1,2...р, осуществляется "базовый"алгоритм фильтрации, т.е. РКККФ;
II. Для каждого в1, г = 1,2 ...р, применяем ортогональное преобразование 0(, что и в РКККФ-
Ot
дК
1/2
00,
0{PjßHj)
de,
о 00,
ä(Ql/2Gf) ddi
00,
o(pt-T/2K) дв,
О
вычисляем:
J* =
где и Т^1 означают первые строки матриц Lt, Кг иТ„ соот-
ветственно О'1! — нулевая строка соответствующего размера. 7'1' первый элемент вектора 7.
IV. Для каждого 9„г — 1,2... р, представляем, вычисленные на этапе III матрицы J, в следующем виде:
J, = Lt + Dt + U„
где Ьг, D, и Ь\ - соответственно, строго нижняя треугольная, диагональная и строго верхняя треугольная части 7,.
V. Для каждого 0,, г = 1,2.. .р, находим: flflff dKrvt det
00,
X, Уг мг
Nt V, W,
4Ч К® Tfl
я1/2 кт О
ОМ 0W
-et
pl/2 0-Г/2--
-ri+1 ":+i xt+i
Xi Vi Mt-
N, к wt
Li к, Тг .
e„ г = 1,2.
-1
1
[i]
дв, О
ot1)
дв, ">1(1
двг О«
дв, дуМ de,
[Lf I D, + £/,] x
p,t
D1/2
nr,L np,i 0
OPl OW
~et
РЦ1 РГТ
rt+1
t+i
y[l]
VI. Вычисляем ГЛФП согласно формуле (9).
В параграфе 3.3 разработан алгоритм для вычисления ГЛФП на основе РККИФ. Здесь же представлено его строгое математическое обоснование.
Лемма 3 Пусть <5А — Я, где А — невырожденная матрица, <3 - матрица ортогонального преобразования, приводящая к нижнему треугольному виду матрицу Н Элементы матриц А, <3 и Я являются достаточно гладкими функциями от некоторого параметра в & ЯР Тогда справедливы утверждения:
• матрица СУдС? является кососимметричной;
• строго верхние треугольные части матриц и совпадают.
Алгоритм ГЛФП-РККИФ
I. Для каждого <?,-, г = 1,2...р, осуществляется "базовый"алгоритм фильтрации, т.е. РККИФ;
II. Для каждого в,, г = 1,2...р, применяем ортогональное преобразование 01, что и в РККИФ:
О,
dRtT'2 dS<2) dSj3)
дв; дв, дв, дв, Y, M, и
0 dSi* 8S\&) dSf] = Ni К w, к,
дв, дв, двг * * * *
0 0 0 0
где приняты следующие обозначения:
5,(1) = -дгт/2я,ФГ\ = Я^Н^С^'2, 5® = -я;Т'\, з^ = РГтпФГ1, ^ = з^ = РГТ'Ч,
III. Далее работаем с блоками матриц. Для каждого вг, г = 1,2...р. вычисляем:
X, У, Мг й:'Т/2 0 0
J,
N, V, W,
д;
-Т/2
e,t
~It+1 Лг>,4 м+1 и
IV. Для каждого ви i = 1,2... р, представляем, вычисленные на этапе III матрицы J, в следующем виде:
m+n+q
Л = Lt + D, + U,
]}
771+П ,
где /V,, Д и £7, — соответственно, строго нижняя треугольная, диагональная и строго верхняя треугольная части подматрицы, сформированной из первых тп+п столбцов и строк матрицы Зг. Звездочками обозначим блок матрицы ,7г размера (т 4 п) х д, который не представляет в данном случае для нас интереса.
V. Для каждого 9{. г = 1,2.. .р, находим следующие величины:
Г/2
двг
д(РГ+т1'2кР,) dp-rß
дв.
м.
[L, + Д + и'!
о Т/2 Ke,t
-Т/2
О
5-Т/2
Р~ ' W Р . ~Г1+1 ЛР,' * Н 1
det дв.
дкГ1
дв{
Rli2et + Yt4>txt - L„
dSj% дв,
д
(РйТг/2КР,)
дв,
+ N,
RTe!t% +
дРиТ
дв.
К
+ К,.
VI. Вычисляем ГЛФП согласно формуле (10)
В параграфе 3.4 разработан алгоритм для вычисления ГЛФП на основе МККМФ Поскольку МККИФ является модификацией РККИФ, то Алгоритм ГЛФП-МККИФ получен из ГЛФП-РККИФ путем организации дополнительных вычислений. В связи с чем, их этапы III, IV и VI полностью совпадают. Таким образом, приведем только этапы I II и V Алгоритма ГЛФП-МККИФ.
I. Для каждого в„ г = 1,2...р, осуществляется "базовый"алгоритм фильтрации, т.е. МККИФ;
II. Для каждого ви г — 1,2...р, применяем ортогональное преобразование Ои что и в МККИФ:
дЩт/2
о.
дв™ 0 дБ™
дв, дв( дв,
д^
дв, дв, дв1 дв.
0 0 0
дв{
'X, у, м, с, и ■
к V, Тг К,
* * * # *
дв, О
О
где приняты те же самые обозначения, что и в ГЛФП-РККИФ.
V. Повторяем действия этапа V Алгоритма ГЛФП-РККИФ и. кроме того, для каждого 0,, г = 1,2,... ,р, вычисляем:
дв,
дв,
д(К+72крЛ)
дв.
Я,ДФ,Г - + Ц.
В параграфе 3.5 проведен сравнительный анализ эффективности разработанных в диссертации алгоритмов ГЛФП-РКККФ, ГЛФП-РККИФ и ГЛФП-МККИФ, включающий в себя анализ вычислительной сложности и устойчивости к оптибкам округления. По его результатам сделан следующий вывод: разработанные методы для вычисления ГЛФП являются
более устойчивыми по отношению к ошибкам округления, чем стандартный "дифференцированный"фильтр Калмана.
В параграфе 3.6 все теоретические результаты главы 3 подтверждены на практике экспериментальными данными.
В заключении приводятся основные результаты:
1. Разработаны численно эффективные модификации квадратно-корневых реализаций дискретного фильтра Калмана, построенные на основе покомпонентной обработки вектора измерений системы.
2 Представлено математическое обоснование алгоритма для нахождения логарифмической функции правдоподобия, сформулированного на основе "скаляризованной"стандартной реализации дискретного фильтра Калмана.
3. Построены численно эффективные алгоритмы рекуррентного вычисления логарифмической функции правдоподобия, разработанные на основе "скаляризованных"квадратно-корневых методах фильтрации.
4 Предложен способ вычисления матрицы Я'в специального блочного треугольного вида, связанной ортогональным преобразованием ф с прямоугольной матрицей А.
5 Разработаны численно эффективные алгоритмы рекуррентного вычисления градиента логарифмической функции правдоподобия по отношению к неизвестному параметру системы 9 € ЯР, основанные на квадратно-корневых реализациях дискретного фильтра Калмана
Список литературы
[1] куликова М В Об эффективном вычислении логарифмической функции правдоподобия для гауссовских марковских последовательностей// Труды Четвертой международной научно-технической конференции "Математическое моделирование физических, экономических, технических, социальных систем и процессов" Ульяновск: Изд-во УлГУ, 2001. С. 77-78.
[2] КУЛИКОВА М.В. Эффективное вычисление логарифмической функции правдоподобия для гауссовских сигналов// Труды XXIV конференции молодых ученых механико-математического факультета МГУ им. М.В.Ломоносова. Москва: Изд-во МГУ, 2002. С. 98-101
|3] КУЛИКОВА М.В. Об эффективности скалярного вычисления логарифма функции правдоподобия// Труды Четвертой между народной научно-технической конференции "Математическое моделирование физических, экономических, технических, социальных систем и процессов". Ульяновск: Изд-во УлГУ, 2003. С. 107-109.
[4] КУЛИКОВА М.В. Об одном способе скалярного вычисления логарифма функции правдоподобия для гауссовских марковских последовательностей// Математическое и информационное моделирование-сборник научных трудов Вып. 5. Тюмень: Издательство "Вектор Бук", 2003. С. 34-42.
[5] КУЛИКОВА М.В. Алгоритм вычисления градиента логарифмической функции правдоподобия с помощью модифицированного квадратно-корневого информационного алгоритма филырации/'/ 15 Международная НТК "Математические методы и информационные технологии в экономике, социологии и образовании", Сборник статей, Пенза: Изд-во Приволжского Дома знаний. 2005. С. 278-288.
[6] Семушин И В., Цыганова Ю.В., Куликова М.В. О вычислении функции правдоподобия для гауссовских марковских последовательностей// Фундаментальные пробл. матем. и механ. Ульяновск: Изд-во УлГУ, 2000 Вын 2(9) С. 93-100
[7] KULIKOVA M.V. On effective computation of the logarithm of the likelihood ratio function for gaussian signals// In: Sloot, P. M A et al (eds) Computational Science — ICCS 2003. Proceedings, Part II: Lecture Notes in Computer Science. 2003. P. 427-435.
[8| kulikova m v On Scalar Evaluation of the Logarithm of the Likelihood Ratio Function for Gaussian Signals// Book of abstracts of the Conference on Scientific Computing and Differential Equations (SciCADE 2003). Trondheim, Norway. 2003. P. 52-52.
|9] KULIKOVA M.V. Some New Algorithms for Evaluating the Gradient of Log Likelihood Function// Book of abstracts of the Conference on Scientific Computing and Differential Equations (SciCADE 2005) Nagoya, Japan. 2005. P. 54-55.
¡10] Kulikova M.V., Semoushin I.V On the Evaluation of Log Likelihood Gradient for Gaussian Signals// International Journal of Applied Mathematics & Statistics, 2005. V. 3. N S05. P. 1-14.
[11] Semoushin I.V, Tsyganova Y.V , Kulikova M.V. Fault Point Detection with the Bank of Competitive Kalman Filters// Sloot, P. M A et al (cds) Computational Science ICCS 2003. Proceedings, Part II: Lecture Notes in Computer Science. 2003. P. 417-426.
Подписано в печать 9 11.05. Формат 60x84/16 Усл. печ. л. 1,0. Тираж 100 -жз Заказ №148/£5й
Отпечатано с оригинал-макета в лаборатории оперативной полиграфии Ульяновского государственного университета 432970, г. Ульяновск, ул. Л. Толстого, 42
«23820
РПБ Русский фонд
2006-4 27916
Введение
1. Модифицированные алгоритмы рекуррентного оценивания
1.1. Постановка задачи
1.2. Инновации в теории калмановской фильтрации
1.2.1. Расширенный квадратно-корневой ковариационный алгоритм
1.2.2. Расширенный квадратно-корневой информационный алгоритм
1.2.3. Модифицированные алгоритмы, построенные на основе РКККФ иРККИФ.
1.3. Последовательные алгоритмы рекуррентного оценивания.
1.3.1. Формулировка последовательных алгоритмов
1.3.2. Теоретическое обоснование
1.4. Сравнительный анализ эффективности
1.4.1. Исследование вычислительной сложности
1.4.2. Устойчивость к ошибкам округления
1.5. Вычислительные эксперименты.
1.5.1. Работоспособность.
1.5.2. Сравнение вычислительной сложности.
1.5.3. Устойчивость к ошибкам округления
2. Последовательные методы вычисления ЛФП
2.1. Постановка задачи
2.2. Вычисление ЛФП на основе стандартного алгоритма Калмана
2.2.1. Формулировка алгоритма.
2.2.2. Теоретическое обоснование алгоритма.
2.3. Вычисление ЛФП на основе последовательных квадратно-корневых фильтров.
2.4. Сравнительный анализ эффективности
2.5. Вычислительные эксперименты.
2.5.1. Работоспособность.
2.5.2. Сравнение вычислительной сложности.
2.5.3. Устойчивость к ошибкам округления
3. Квадратно-корневые алгоритмы вычисления ГЛФП 85,
3.1. Постановка задачи и формулы для вычисления ГЛФП.
3.2. Метод вычисления ГЛФП, построенный на основе РКККФ
3.2.1. Формулировка алгоритма.
3.2.2. Теоретическое обоснование алгоритма.
3.3. Метод вычисления ГЛФП, построенный на основе РККИФ.
3.3.1. Формулировка алгоритма.
3.3.2. Теоретическое обоснование алгоритма
3.4. Метод вычисления ГЛФП, построенный на основе МККИФ.
3.4.1. Формулировка алгоритма
3.4.2. Теоретическое обоснование алгоритма.
3.5. Сравнительный анализ эффективности
3.5.1. Исследование вычислительной сложности
3.5.2. Устойчивость к ошибкам округления .,.
3.6. Вычислительные эксперименты.
3.6.1. Работоспособность.
3.6.2. Устойчивость к ошибкам округления
При изучении явлений окружающего мира мы часто сталкиваемся с процессами, течение которых заранее предсказать невозможно. Эта неопределенность (непредсказуемость) вызвана влиянием случайных факторов, воздействующих на ход процесса. Подобные неопределенности (помехи) присущи большинству процессов, протекающих в технических, экономических, биологических и др. системах. В связи с чем многие математические модели в биологии, медицине, электротехнике и т.д. представляют собой стохастические системы, т.е. системы стохастических дифференциальных уравнений.
Одной из важнейших задач математической кибернетики является задача адаптации, а одним из основных объектов исследования — адаптивные или, другими словами, "самонастраивающиеся" системы. Впервые понятие адаптации было использовано Цянь Сюэ-Сэнем [42] в 1954 г. для обозначения способности живой системы адаптироваться к изменяющимся условиям. В 1955 г. Benner А.Н. и Drenick R. описали техническую систему, обладающую подобным свойством [53]. Особенно интенсивно адаптивные системы начали развиваться во второй половине 50-х годов двадцатого века. С тех пор их исследованию было посвящено огромное количество работ как в отечественной (см., например, [19], [21], [22], [23], [25], [27], [31], [34], [35], [39], [41] и др.), так и в зарубежной (см., например, [47], [67], [79], [82], [90], [104] и др.) литературе.
Процесс адаптации может быть определен как "процесс изменения параметров и структуры системы, а возможно, и управляющих воздействий на основе текущей информации с целью достижения определенного, обычно оптимального, состояния системы при начальной неопределенности и изменяющихся условиях работы" (см., например, [39], [44] и др.). Независимо от способа реализации операции адаптации в ней могут быть выделены три характерные процедуры: идентификация, принятие решения и модифицирование. Таким образом, под адаптивностью можно понимать соединение трех функций системы: идентификации модели реальных условий и процесса функционирования, принятия решения о появлении или отсутствии изменений неизвестных характеристик и выработки управляющего воздействия (сигнала адаптации), модификации системы в соответствии с принятым решением.
Каждая из перечисленных выше функций адаптивной системы является отдельной, не менее важной задачей математической кибернетики и требует особого внимания при ее рассмотрении.
Под идентификацией обычно понимают построение адекватной математической модели объекта, которое включает в себя: определение типа уравнений; определение структуры модели (например, порядка уравнений, наличия/отсутствия нелинейно-стей и т.п.); определение истинных значений, изменяющихся физических величин и связанных с ними параметров уравнений модели. Изучению данной проблемы посвящены, например, такие работы как [1], [7], [9], [12], [86],[20], [24], [26], [29], [40], [45], [61] и многие др.
Под задачей контроля (вторая функция адаптивных систем) или обнаружения параметрических нарушений в системе часто понимается несколько подзадач: обнаружение самого факта неисправности в системе; дальнейшая его диагностика, т.е. определения типа произошедшего нарушения с целью дальнейшей разработки методов по устранению данного типа неисправности; а также определение момента возникновения неисправности в системе. Отметим, что в большинстве практических задач качественные изменения в функционировании системы происходят в неизвестные, вообще говоря, случайные моменты времени. В этих условиях остро встает задача наискорейшего определения не только самого факта неисправности в системе, но и момента его возникновения. Она играет ключевое значение в тех сферах человеческой деятельности, где важно предотвратить или хотя бы максимально уменьшить риск катастрофических последствий нарушений в системе. Исследованию данной проблемы также посвящено большое количество работ (см., например, [2], [6], [43], [80], [81], [87], [93], [94], [109] и др.).
Все рассмотренные выше основные задачи математической кибернетики находят глубокое применение в повседневной жизни и охватывают широкий круг приложений. Например, особое значение при непрерывном мониторинге за сейсмической обстановкой на территории сейсмоактивного региона имеет надежное обнаружение и точная оценка на записях появлений сейсмических волн от землетрясений [51]. В промышленности важную роль играет мониторинг за качеством продукции. Отметим, что в современных условиях существует огромный финансовый интерес на промышленных предприятиях в развитии и разработке новых более совершенных диагностических методов для наблюдения за производственной деятельностью и обнаружения аномальных ситуаций [101]. Для этого необходимо внедрение и использование самых современных мощных стратегий управления и компьютерного контроля за условиями технологического процесса. Очевидно, что улучшенный производственный мониторинг может играть ключевую роль в росте промышленной продуктивности, а также иметь важное значение в участии или, более того, "выживании" предприятия в интенсивной конкурентной экономической среде.
Использование и внедрение современных стратегий управления и контроля играет ключевую роль не только в экономической сфере. Особая роль отводится задачам такого типа, например, в навигаций [95], при эксплуатации радиотехнической системы (приходиться решать вопросы, связанные с оценками ее состояния) и т.д. Так, например, в [56] акцент ставится на разработку и использование методов контроля для развития "систем управления, терпимых к нарушениям". Основным преимуществом подобных систем является возможность продолжения их работы даже в случае обнаружения нарушений или сбоев в технике. Это означает, что система не только способна обнаруживать нарушения, но и продолжать свою работу, путем исправления дефектов, т.е. их корректировки. В качестве практического примера, где необходимо применение "систем, терпимых к нарушениям", можно привести задачу предупреждения столкновений судов при их маневрировании или движении в одном кластере. Во многих сферах человеческой деятельности крайне необходимо и жизненно важно применение подобных систем, поэтому в последние годы на их разработку направлены усилия многих ученых всего мира (см. процитированную выше литературу).
Таким образом, изложенные выше основные задачи кибернетики находят свое применение практически во всех сферах человеческой деятельности, а наиболее мощным инструментом для их решения, в то же время, были и остаются статистические методы. Например, Хазен пишет: "Для построения современных сложных систем обработки информации и управления решающее значение имеют эффективные статистические методы, дающие основу для решения возникающих здесь задач распознавания, обнаружения, оценивания, фильтрации сигналов, совместной обработки информации и управления. Создание автоматизированных комплексов обработки данных наблюдений и управления, развитие сложных "самонастраивающихся" систем возможно лишь на базе современных точных статистических, математических методов" (см. [36, с. 7]).
При использовании методов, относимых к группе статистических, часто приходится решать близкие, оказывающие огромное влияние на эффективность и, соответственно, на конечный результат применения самого статистического подхода, задачи эффективного вычисления логарифмической функции правдоподобия и ее градиента. Таким образом, данная проблема является краеугольным камнем, лежащим в основе аппарата статистических методов. Более того, нельзя не отметить тот факт, что с практической точки зрения разработка и внедрение наиболее продвинутых современных, а значит и более мощных методов, нередко затруднена не только из-за финансовых затрат на приобретение и установку данных стратегий, но и из-за повышенных требований к могцностным характеристикам современной техники. Этот факт все чаще заставляет обращать внимание при разработке новых стратегий на аспект затраты/выпуск [101]. В связи с чем остро встает задача не только разработки нового метода, но и дальнейшего анализа условий его использования или внедрения, работоспособности, области применимости и т.д. Другими словами, необходимо не только разработать новую более мощную стратегию, чем уже существующие, но и дать в дальнейшем оценку "цены вопроса", т.е. провести сравнительный анализ эффективности.
Данная диссертационная работа нацелена на построение новых алгоритмов рекуррентного вычисления логарифмической функции правдоподобия и ее градиента; подробное исследование их эффективности, включающее в себя анализ вычислительной сложности и устойчивости к ошибкам округления, и сравнительный анализ предложенных алгоритмов по сравнению с уже существующими методами решения поставленной задачи.
Объектом исследования данной работы являются линейные дискретные стохастические системы, возмущаемые белым, гауссовым шумом, для которых вычисление логарифмической функции правдоподобия (ЛФП), как известно, осуществляется с помощью дискретного фильтра Калмана (см., например, [33], [49], [54], [55], [100], [105] и др.). В то же время задача вычисления градиента ЛФП для каждого момента времени t = 1,2,. N, влечет за собой применение р параллельных "дифференцированных" фильтров (по отношению к неизвестному параметру системы в 6 Rp). В иностранной литературе: "filter sensitivity equations" (см., например, [49], [55], [59], [83], [84], [102], [103] и др.).
Возникающая, в связи с необходимостью применения дискретного фильтра Калмана, проблема хорошо известна — его стандартная реализация является неустойчивой по отношению к ошибкам округления, что очевидным образом влечет за собой некорректное вычисление ЛФП и ее градиента. В сложившихся обстоятельствах остро встает задача разработки новых численно эффективных алгоритмов нахождения указанных выше величин. Последнее обуславливает практическую ценность и подчеркивает актуальность поставленной в диссертационной работе задачи.
В связи со сказанным выше, коротко остановимся на истории развития теории калмановской фильтрации и ее современном состоянии. В начале 40-х годов двадцатого века, решая поставленную перед ним задачу разработки системы защиты от возникновения пожара на борту самолета, Norbert Wiener впервые применил теорию случайных процессов к проблемам управления и системам передачи данных [113].
Широко известное уравнение Винера-Хопфа (Wiener-Hopf equation [69]) г h(t, s)+ J h(t, t)K(t, s)dr = K(t, 5), t0<s<t<T, (0.1) to позволяет получить импульсную переходную характеристику формирующего фильтра h(t,s) с целью нахождения линейной оптимальной в средне-квадратичном смысле оценки неизвестного вектора состояния x{t) динамической системы, подверженной влиянию шумов v(t), и имеющей следующий вид: т x(t)z= J h(t,s)z(s)ds. (0.2) to
В случае гауссовских величин линейная оценка x(t) совпадает с оптимальной в средне-квадратичном смысле. В уравнении (0.1), K(t,s) = E{x(t)x(s)T x(t)v(s)T + u(f)a;(.s)T} — функция вектора состояния системы x(t) и вектора шумов v(t), Е{-} — операция математического ожидания.
В 1960 г. венгерский ученый Калман Р. впервые показал, что понятие наблюдаемости для динамических систем в теории оценивания имеет алгебраическую двойственность с понятием управляемости систем в теории управления. В том же году Richard S. Busy предположил, что уравнение Винера-Хопфа в случае конечномерных систем эквивалентно матричному уравнению Риккати (Riccati equation [85]):
Pt = FtPtFj - FtPtIlf (IItPtIlf + Rt)~lHtPtFj + GtQtGj. (0.3)
Работая совместно над данной проблемой, им удалось показать, что уравнение (0.3) имеет устойчивое решение даже в случае, если сама динамическая система не является таковой. И только значительно позже (в 1986 г.) этот широко известный феномен был полностью теоретически обоснован Verhaegen М. и Van Dooren Р. (см. [112]).
Таким образом, в 60-х годах двадцатого века был разработан новый эффективный аппарат для нахождения линейной оптимальной в средне-квадратичном смысле оценки неизвестного вектора состояния динамической системы [13], [71]. Авторы книги [64], посвященной наиболее полному и всестороннему изучению данного вопроса, пишут: "это открытие является одним из величайших достижений двадцатого века в теории оценивания". Оно послужило мощным толчком к новым исследованиям и дальнейшему развитию этого направления (см., например, [10], [28], [46], [48], [60], [61], [66], [68], [73], [96], [99], [110], [111], [112] и многие др.).^
С теоретической точки зрения, фильтр Калмана представляет собой, как отмечалось ранее, эффективный механизм для получения линейной оптимальной в средне-квадратичном смысле оценки неизвестного вектора состояния динамической системы, которая в случае гауссовских величин является просто оптимальной в средне-квадратичном смысле. Само же понятие "фильтр" — физическое устройство для удаления нежелаемых осадков в жидкости, было применено к данному методу по аналогии, т.е. как: ". некий математический аппарат, позволяющий отделить полезный сигнал, содержащий ценную информацию, от шума" [64, с. 3].
С практической точки зрения, фильтр Калмана — это универсальный инструмент для решения многих задач. В частности, применение и использование алгоритмов калмановской фильтрации в рамках статистического подхода к задаче контроля было впервые предложено P.M. Newbold и Yu-Chi Но в 1968 г. (см. [92]). Авторами была разработана основная идея группы статистических методов, применяемых к решению задачи обнаружения неисправностей в функционировании системы, которая заключается в анализе невязок оптимального фильтра. Использование мощного аппарата калмановской фильтрации лежит в основе решения таких задач, как: распознавание образов [114], параметрической идентификации [50], [61], [90], [108], обнаружения нарушений в функционировании системы [5], [51], [70], задач теории оценивания [49], [63], [55], развития численных алгоритмов рекурретной обработки наблюдений системы, устойчивых по отношению к плохо обусловленным экспериментальным данным [30], [38], [54], [97], [105] и т.д. Grewal M.S. и Andrews А.Р. в своей книге [64] отмечают: ". нет практически ни одной сферы деятельности человека, где бы не находил свое применение метод калмановской фильтрации, который стал совершенно необходимым механизмом для решения большинства задач", - и далее: ". многие достижения человечества были бы не возможны без его использования" [64, с. 15].
Однако, справедливости ради надо отметить, что успех разработки новой методологии не обошелся и без проблем. При дальнейшем, более глубоком изучении данного механизма были обнаружены ряд недостатков, присущих данному методу. Широко известно, что при решении некоторых задач даже малые ошибки округления, возникающие при использовании ЭВМ в качестве средства вычислений, приводят к потерям точности или, зачастую, вообще не позволяют найти решение. Как оказалось, реализация фильтра Калмана с помощью ЭВМ в том виде, в котором он был изначально сформулирован, не устойчива по отношению к ошибкам округления и терпит поражение при решении плохо обусловленных задач. Таким образом, при решении задач на практике с использованием ЭВМ часто ставится под сомнение конечный результат применения самого механизма калмановской фильтрации. •
В связи со сказанным выше, дальнейшие исследования ученых многих стран были направлены на изучение устойчивости фильтра Калмана, а также на разработку новых типов реализаций фильтра, которые были бы устойчивы к ошибкам округления и позволяли бы найти гарантированное решение (см., например, [10], [11], [21], [28], [46], [48], [58], [60], [61], [66], [72], [88], [91], [96], [99], [110], [111], [112] и многие др.). Прекрасный обзор предложенных к 1971 г. различных типов фильтров, иллюстрация их работы при решении плохо обусловленных задач и сравнительный анализ их эффективности были даны Kaminski P.G. и соавт. в [73].
В связи с обозначенной выше целью диссертационной работы, остановимся более подробно на истории развития существующих в настоящее время различных типов реализаций фильтра Калмана, их сравнительном анализе и современном состоянии данного направления исследований. Дискретный фильтр Калмана описывается следующими уравнениями (см., например, [85]):
• Этап экстраполяции: оценки: xf+1 = Ftxf -f Btut, (0.4) ковариации ошибки: Pt+X = FtPt+ F^ + GtQtGf; (0-5)
• Этап обработки измерений и фильтрации:
Kt+i - + (0.6) оценки: xf+1 = it+1 + Kt+1(zi+1 - Ht+ixJ+1), (0.7) ковариации ошибки: РД^ = Pt+X — Kt+\Ht+iPr+i, (0.8) где Ft, Gt, Bt, IIt, Qt, Rt — известные матрицы-параметры линейной дискретной динамической системы, щ — вектор управления, zt — доступный вектор наблюдений и xt — вектор состояния системы, где х0 ~ Л/"(х0,П0).
Хорошо известно, что при отсутствии наблюдений за состоянием системы наилучшей в средне-квадратичном смысле оценкой вектора состояния является его математическое ожидание. При этом матрица ковариации ошибки оценивания xt = xt — Xt совпадает с матрицей ковариации самого вектора состояния динамической системы. Таким образом, в момент времени t = 0, когда измерения о состоянии системы еще не поступили, наилучшими оценками являются априорные знания, т.е. х0 и П0.
Если в алгоритме фильтрации (0.4) — (0.8) соединить два этапа воедино, то мы получим еще одну известную формулировку данного алгоритма: x-+l = Ftx- + FtPt-Hj{HtPt~Hj + Rt)-\zt - tftx"), Xo = x0, (0.9)
Pt-+1 = FtP~Ff - FtPt-H?(IItPt-II? + Rt)~lHtP;Fj + GtQtGj, P~ = П0. (0.10)
Легко видеть, что уравнение (0.10) есть ни что иное как уравнение Риккати (0.3).
Одной из проблем, возникающей при реализации алгоритма (0.4) — (0.8) или (0.9) — (0.10) с помощью ЭВМ, является потеря положительной определенности матрицы Pf из-за ошибок округления, что в свою очередь, приводит к неустойчивости самого алгоритма оценивания. В связи с чем были разработаны новые типы реализации фильтра, которые алгебраически эквивалентны начальной версии алгоритма, однако, позволяют решать возникающие на практике проблемы, связанные с ошибками округления при использовании ЭВМ в качестве средства вычислений.
Исторически, первыми возникли, так называемые, квадратно-корневые алгоритмы фильтрации. Ключевая идея, лежащая в основе всех таких методов, принадлежит Cholesky и Banachiewicz [73]. Ими были получены два независимых, но эквивалентных доказательства алгоритма представления любой положительно-определенной > матрицы, скажем А, в виде А — LLT. Однако метод факторизации таких матриц был развит ими с целью разработки численного устойчивого алгоритма для нахождения решения системы уравнений, вида Ах = Ь, где А — положительно-определенная матрица.
Первые квадратно-корневые алгоритмы фильтрации появились только в 1963 г. Родоначальниками данного подхода являются Potter J.E. и Stern R.G. [97], кто впервые применил идею факторизации положительно-определенных матриц к алгоритмам калмановской фильтрации. Ими была развита основная идея таких методов, заключающаяся в представлении матрицы ковариации ошибки оценивания Р^ в виде р? = St где sf — так называемый, квадратный корень матрицы Р*. Данная структурная" переформуливка алгоритма позволяет убрать один существенный недостаток, упомянутый ранее, — потерю положительной определенности матрицы ковариации ошибки оценивания Р*. В случае работы с ее факторами Sf, этот недостаток и связанная с ним численная неустойчивость фильтра Калмана устраняются, поскольку теперь Р* = Sf (-S^) — всегда положительно-определенная. Кроме того, исследование чисел обусловленности указанных выше матриц показало, что алгоритмы, созданные для работы не с самой матрицей Р^, а с ее квадратными корнями Sf, обеспечивают вычисления с двойной точностью (см., например, [73]). Таким образом, квадратно-корневые алгоритмы фильтрации существенно превосходят стандартный алгоритм Калмана. В связи с чем именно эти типы реализаций фильтра были успешно применены в космической навигации, в программе исследования Луны (Apollo, см. [52]).
В 1963 г. Potter J.E. в своей работе [97] показал, что этап обработки измерений стандартного фильтра Калмана может быть выражен в терминах множителей
Холецкого (Cholesky), т.е. уравнение (0.8) представимо в следующем виде:
Р+ = 5+(5+)т = Pt~ - KtHtPt- = St(I - affT)Sj, (0.11) где I — единичная матрица соответствующего размера и j = SjHj, и 1/а = ffT + Rt, где Rt G Я1. (0.12)
Он также доказал, что величина (/ — affT) в уравнении (0.11) может быть далее факторизована с помощью специального выбора некой константы 7 и представлена в следующем виде: - affT) = (I - а7//Г)(/ - «7/Я, где
7 = 1/(1 ±y/^Rt) Kt = aStft, St = St-aiStffT. (0.13)
Таким образом, этап обработки измерений стандартного фильтра Калмана, т.е. уравнения (0.6) - (0.8) могут быть заменены на алгебраически эквивалентные (0.12), (0.13), но дающие существенные преимущества, перечисленные ранее, по сравнению со стандартным алгоритмом.
Следует отметить, что при разработке нового подхода к алгоритмам фильтрации Potter J.E. рассматривал определенный класс задач, а именно: он развил свои идеи только для случая одномерного выходного сигнала системы zt и при условии, что матрица ковариации шумов в объекте Qt = 0. Очевидно, что подобные ограничения существенно сокращают потенциал самой методики. Дальнейшие исследования были направлены на преодоление этих ограничений.
Обобщение идеи Potter J.E. и Stern R.G. на случай мульти-выходных систем, т.е. систем, где выходной сигнал Zt есть вектор, скажем zt G Rm, было развито и опубликовано Andrews А. в 1968 г. (см. [48]). Он показал, что в случае, если матрица ковариации шумов в измерителе Rt является диагональной, то для обработки т-мерного вектора измерений zt динамической системы на этапе II алгоритма может быть использована процедура Potter J.E., примененная, соответственно, т раз.
Однако новые открытия также не решили всех проблем, возникающих на практике. Действительно, при реализации предложенных квадратно-корневых алгоритмов фильтрации с помощью ЭВМ, зачастую, возникает ситуация, когда из-за ошибок округления матрицы Sf теряют свой специальный вид (согласно представлению Р* = Sf(Sf)T матрицы имеют верхний или нижний треугольный вид). Устранить данный недостаток можно с помощью, так называемой, процедуры триангуля-ризации, т.е. процедуры приведения матрицы к требуемому треугольному виду. Эта идея впервые была предложена и развита Schmidt S.F. [107] в 1970 г. В частности, он показал, что уравнение (0.5) для предсказания матрицы ковариации ошибки оценивания на этапе экстраполяции может быть заменено на эквивалентное:
St)T ] QJGJ . 0 где Pt+1 = St+1(St+l)T, Pt+ - St(St)T, Qt = QtQj и St+l, Sf, Qt — нижнии треугольные матрицы. Он также разработал алгоритм для нахождения ортогонального преобразования Т, приводящего к требуемому треугольному виду матрицу, стоящую в правой части формулы (0.14). Эта процедура известна как процедура ортогонализации Грама-Шмидта.
Еще одним важным типом реализации фильтра Калмана, гарантирующим положительную определенность Pt+, является, так называемый, стабилизированный алгоритм Джозефа (Joseph stabilized version [85]), впервые предложенный в 1968 г. авторами Bucy R.S. и Joseph P.D. В данной версии алгоритма уравнение (0.8) стандартного фильтра Калмана заменяется на алгебраически эквивалентное [58]:
Р+ = (/-KtHt)Pt-{I - KtHt)T + I<tKf, но уже гарантирующее положительную определенность матрицы Pt+ (которая могла бы быть утеряна из-за ошибок округления).
Все рассмотренные выше алгоритмы калмановской фильтрации относятся к, так называемым, ковариационным типам фильтров, поскольку с основе их работы лежит идея предсказания и фильтрации матрицы ковариации ошибки оценивания Р^ или ее квадратных корней Sf. Однако существует другой важный класс методов, который также заслуживает особого внимания. Это, так называемые, информационные типы алгоритмов. В основе их работы лежит идея предсказания и фильтрации матрицы обратной к матрице ковариации ошибки, т.е. Af — (Р^2)"1 (а также ее факторов). Матрицу Af называют информационной матрицей, что и дало название данному классу методов. Их появление обусловлено тем, что зачастую на практике приходится решать задачи в условиях очень скудной априорной информации или, вообще говоря, в ее отсутствии, что математически может быть записано следующим образом: = х0 = 0 и Р0~ = П0 = оо. В этих условиях применение ковариационных алгоритмов фильтрации не способно решить поставленную задачу, тогда как информационные типы методов справляются с этим легко: в качестве начальных условий достаточно положить Xq = xq = 0 и Aq =0. Именно на решение таких задач и нацелен, прежде всего, данный класс методов. Информационные алгоритмы фильтрации впервые были разработаны и опубликованы в конце 60-х авторами Dyer Р. и McReynolds S. [66].
Таким образом, к началу семидесятых годов двадцатого века были разработаны все основные типы реализаций фильтра Калмана. Дальнейшие исследования в теории фильтрации были обусловлены все повышающимися требованиями к эффективности разрабатываемых алгоритмов, т.е. к их способности быстро и эффективно обрабатывать данные наблюдений, существенно повысив тем самым точность и надежность систем обработки информации и управления. По этой причине усилия ученых в дальнейшем были направлены, прежде всего, на разработку новых, численно устойчивых и более эффективных с точки зрения вычислительных затрат алгоритмов.
Итак, семидесятые годы двадцатого века были ознаменованы целым рядом открытий, последовавших друг за другом. В 1971 г. Kaminski P.G. предложил новые модификации ковариационных и информационных типов квадратно-корневых методов фильтрации, обладающие рядом преимуществ перед ранее известными алгоритмами [72]. Остановимся более подробно лишь на одном из них, который потребуется в дальнейшем. Исходя из хорошо известной дуальности ковариационных и информационных алгоритмов, Kaminski P.G. разработал новую схему для осуществления этапа обработки измерений и фильтрации [72]:
R\'2 О
Htsr sr т = дЗ/2 kt о st
0.15)
1/2 « w где Rti — квадратный корень матрицы ковариации невязки измерении Re,t, где ef = zt — HxJ, Kt = Pf~ HjR~]'2, T — ортогональное преобразование, приводящее к нижнему треугольному виду матрицу, стоящую в правой части формулы (0.15). Он также предложил использовать в качестве этапа экстраполяции формулу (0.14), разработанную Schmidt S.F. Таким образом, возникла еще одна эффективная реализация алгоритма калмановской фильтрации.
В 1972 г. Agee W.S. и Turner R.H. разработали новые квадратно-корневые алгоритмы для этапа экстраполяции фильтра Калмана [46]. Несмотря на то, что эти типы методов были приблизительно одной и той же вычислительной сложности, что и стандартный фильтр Калмана, они обладали, лучшей численной устойчивостью. Улучшенные квадратно-корневые версии фильтра были опубликованы Carlson N.A. [60] в 1973 г. Вслед за этими открытиями в 1975 г. Morf М. и Kailath Т. разработали, так называемые, быстрые квадратно-корневые алгоритмы фильтрации для систем матрицы-параметры которых: F, G, В, Н, Q, R,— не зависят от времени. Их основная идея — создание нового способа вычислений, основанного на работе с матрицами 8Р^ = Pt+i — Р* вместо Р^, что позволило значительно улучшить численные характеристики квадратно-корневых алгоритмов для подобных систем, т.е. сократить общее количество арифметических действий на вычисления и, следовательно, время работы [91]. Кроме того, ими была предложена идея слияния воедино алгоритмов, разработанных Schmidt S.F. для этапа экстраполяции фильтра Калмана (0.14) и Kaminski P.G. для этапа обработки измерений (0.15), с целью получения новой, более эффективной реализации фильтра:
-1/2 о
Pf)1/2^ (Pf)1/2i? о q]/2gj R
1/2 e,t О о кт
Pt-+l)1/2 о
0.16) где Т — любое ортогональное преобразование, приводящее к верхнему треугольному виду матрицу, стоящую в правой части формулы (0.16) и Kp<t = FtKt. Очевидно, что уравнение (0.10) алгебраически эквивалентно формуле выше. Алгоритм (0.16) в настоящее время известен как стандартный квадратно-корневой ковариационный фильтр Калмана.
Еще один важный тип реализаций — это, так называемые, U — D алгоритмы для калмановской фильтрации. Они впервые были предложены в 1974 г. Bier-man G.J. [54] и затем дополнены и улучшены Thornton C.L. [111] в 1976 г. Основная идея данных типов методов заключается в представлении матриц РЯ(, Qt в виде: Р± = (p±)T/2D±(p±)i/2) /f> = Qt = QV2D4Q\I\ где Z)« Я? диагональные матрицы, (Рf1)1^2, Rt^2, QlJ2 — верхнии треугольные с единичной диагональю. Аналогично, можно сформулировать алгоритм, где матрицы (Р^)1^2 « fry
Qt — нижнии треугольные с единичной диагональю. Если в уравнении (0.16) для выше указанных матриц использовать U—D разложение, то оно может быть заменено на алгебраически эквивалентные: обозначим матрицы, стоящие в левой и правой части формулы (0.16) через W и U, соответственно. Тогда с помощью взвешенного алгоритма ортогонализации Грама-Шмидта, разработанного Bierman G.J., можно построить матрицу V такую, что ее строки взаимно ортогональны и выполняются условия:
W = UV, и D — VDVT WDWT = UVDVTUT = UDUT, где матрица D — блочно диагональная с блоками Df, Df и Df, соответственно. В зарубежной литературе данные типы методов называют "square-root-free" алгоритмами, поскольку процедура взвешенной ортогонализации Грама-Шмидта и, следовательно, сами U — D методы не требуют операции извлечения квадратного корня.
Говоря о современном состоянии теории калмановской фильтрации, нельзя не отметить следующее: бурное развитие вычислительной техники, произошедшее за последние 10-20 лет, создание Супер ЭВМ, а также широкое внедрение имитационного моделирования обусловило появление совершенно новых требований, налагаемых на методы решения прикладных задач. Зачастую, только вычислительные алгоритмы, допускающие эффективную реализацию на Супер ЭВМ, были способны решить современные широкомасштабные задачи за приемлемое время. Одним из основных направлений повышения эффективности и скорости вычислений явилось создание многопроцессорных вычислительных комплексов с использованием специальных алгоритмов, ориентированных на параллельные вычисления. Идея распараллеливания не осталась без внимания и в теории калмановской фильтрации.
В 1995 г. авторами Park Р. и Kailath Т. был разработан целый ряд методов для реализации фильтра Калмана, ориентированных на использование многопроцессорных вычислительных комплексов, т.е. алгоритмов, более приспособленных к параллельным вычислениям, чем ранее известные [96]. Проблеме создания новых типов реализаций фильтра Калмана, допускающих их эффективное распараллеливание, и самих схем многопроцессорных вычислительных комплексов, проектируемых с этой целью, в последние годы посвящено огромное количество работ (см., например, [57], [61], [62], [89], [78], [98] и многие др.). Интересное решение поставленной задачи было найдено Jover J.M. и Kailath Т. Им удалось разработать схему для параллельной обработки измерений на этапе фильтрации, позволяющую значительно уменьшить сложность алгоритма и, следовательно, сократить время работы фильтра [68].
Как отмечалось ранее, различные алгоритмы фильтрации служат базисом для построения методов вычисления логарифмической функции правдоподобия (ЛФП) и ее градиента (ГЛФП). Впервые,подобная проблема была поставлена и успешно решена Schweppe F.C. в 1965 г. (см. [100]). С этого момента обсуждению данного вопроса и разработке новых типов алгоритмов вычисления ЛФП на базе различных реализаций фильтра Калмана посвящено большое количество работ (см., например, [33], [49], [55], [59], [65], [83], [84], [102], [103], [105] и др.). Простые и эффективные методы вычисления ЛФП для, так называемых, квадратно-корневых фильтров Potter J.E., Bierman G.J., Carlson N.A. были разработаны и представлены в [105]. Иллюстрация работы предложенных алгоритмов при решении плохо обусловленных задач и сравнительный анализ их эффективности можно найти в [37].
На современном этапе научно-технический прогресс диктует уже новые требования к разрабатываемым методам вычислений. С 90-х годов прошлого века и по наши дни акцент ставится на разработку новых эффективных алгоритмов, приспособленных к параллельным вычислениям, т.е. созданных изначально е учетом возможности дальнейшего применения многопроцессорных вычислительных комплексов в качестве средства вычислений. Новые типы реализаций фильтра Калмана, обладающие подобным свойством, как отмечалось ранее, были разработаны в 1995 г. (см. [96]). Однако вопрос создания таких типов алгоритмов для вычисления ЛФП и ее градиента, оставался открытым. В данной диссертационной работе мы решаем эту задачу, предлагая ряд новых эффективных алгоритмов для вычисления логарифмической функции правдоподобия и ее градиента.
Кроме того, в диссертации разработан новый способ вычисления производной вырожденной матрицы R блочного треугольного вида такой, что R = QA, где Q — ортогональное преобразование, А — прямоугольная матрица. Отметим, что подобная задача, но только для случая невырожденных матриц Rm А, была решена в 1991 г. Bierman G.J. и соавт [55]. Очевидно, что данное ограничение — невырожденность матриц — существенно снижает потенциал самой методики. Здесь удалось усилить этот результат, существенно расширив, тем самым, область его применимости. В конечном итоге, это позволило решить задачу вычисления ГЛФП с помощью различных типов реализаций фильтра Калмана. Эти новые схемы вычислений уже не требуют соблюдения невырожденности матриц и могут быть применены к различным видам фильтров. В прикладном аспекте особо следует подчеркнуть возможность применения полученных результатов при решении современных прикладных задач с использованием многопроцессорных вычислительных комплексов в качестве средства вычислений, поскольку все разработанные в диссертации алгоритмы допускают эффективное распараллеливание.
Диссертация объемом 131 страница состоит из введения, трех глав, заключения и списка литературы (114 наименований). Работа включает 29 таблиц и 13 рисунков.
Выводы по диссертационной работе состоят в следующем:
1. Последовательные алгоритмы фильтрации, построенные с использованием процедуры "скаляризации" измерений, как правило, являются наиболее устойчивыми по отношению к ошибкам округления реализациями дискретного фильтра Калмана и позволяют существенным образом сократить общее количество арифметических действий на организацию вычислений.
2. В случае систем с большой размерностью вектора наблюдений (тп » п) целесообразно применять "скаляризованные" реализации фильтра. Более того, чем больше размерность вектора наблюдений т, тем существеннее выигрыш во времени от применения "скаляризованных" алгоритмов вместо "векторных".
3. Рекуррентное вычисление логарифмической функции правдоподобия требует применения достаточно сложных (в вычислительном плане) процедур обращения матрицы и вычисления ее детерминанта. Предложенные эффективные алгоритмы вычисления ЛФП, сформулированные на основе последних достижений в области калмановской фильтрации, позволяют получать очередное значение ЛФП непосредственно в терминах величин, генерируемых этими фильтрами.
4. Разработанные в диссертационной работе новые алгоритмы для вычисления ЛФП являются более устойчивыми по отношению к ошибкам округления и позволяют существенным образом сократить общее количество арифметических действий на организацию вычислений.
5. Внесение незначительного объема дополнительных вычислений в рассматриваемые в диссертации квадратно-корневые алгоритмы фильтрации позволяет модифицировать их таким образом, что они наряду со своей основной задачей приобретают новую функциональность — позволяют вычислять ЛФП.
6. Предложенный в диссертации новый способ вычисления производной вырожденной блочной треугольной матрицы R уже не требует соблюдения невырожденности матриц и может быть применен к различным реализациям дискретного фильтра Калмана с целью разработки новых алгоритмов для нахождения ГЛФП.
7. Разработанные в диссертации алгоритмы для вычисления градиента логарифмической функции правдоподобия: ГЛФП-РКККФ, ГЛФП-РККИФ и ГЛФП-МККИФ, построенные на основе квадратно-корневых методов фильтрации РКККФ, РККИФ и МККИФ, соответственно, наследуют все их преимущества и, в частности, являются более устойчивыми к ошибкам округления, чем "дифференцированный" стандартный фильтр Калмана и "дифференцированный" стандартный информационный алгоритм. В связи с чем, алгоритмы ГЛФП-РКККФ, ГЛФП-РККИФ и ГЛФП-МККИФ более предпочтительны к использованию и внедрению на практике.
8. Предлагаемые методы и алгоритмы являются универсальными в том смысле, что могут использоваться в широком круге систем наблюдения и управления движением сложных динамических объектов, описываемых линейными дискретными уравнениями. Возможные приложения включают: проблемы навигации и управления движением в аэрокосмонавтике; дефектоскопия, сейсмология, геофизика; моделирование и обнаружение тенденций в социально-экономических, медико-биологических и т.п. процессах.
Научная и практическая значимость работы определяется тем, что в ней предложены новые численно эффективные алгоритмы рекуррентного оценивания вектора состояния линейных дискретных динамических систем, возмущаемых белым гауссовым шумом; построены последовательные алгоритмы вычисления логарифмической функции правдоподобия и методы вычисления ее градиента. Разработан новый способ вычисления производной матрицы по параметру, нетребующий соблюдения условия невырожденности матриц. Эти методы, формулируемые в виде теорем, получили строгое математическое обоснование. В прикладном аспекте особо следует подчеркнуть возможность применения полученных результатов при решении современных прикладных задач с использованием многопроцессорных вычислительных комплексов в качестве средства вычислений, поскольку все разработанные в диссертации алгоритмы допускают эффективное распараллеливание.
Вместе с тем работа не претендует на исчерпывающий охват всех аспектов проблемы. Ряд вопросов остался за рамкамирассмотрения в связи с ограниченностью объема работы. Поэтому дальнейшие исследования могут быть продолжены в следующих направлениях:
1) Построение эффективных алгоритмов рекуррентного вычисления градиента логарифмической функции правдоподобия на основе "скаляризованных" квадратно-корневых реализациях дискретного фильтра Калмана. .
2) Сравнительный анализ эффективности новых алгоритмов, включающий в себя анализ вычислительной сложности и устойчивости к ошибкам округления, по сравнению с разработанными в данной диссертации "векторными" методами вычисления градиента логарифмической функции правдоподобия, стандартным подходом и ранее развитыми алгоритмами.
Заключение
В диссертационной работе получены следующие результаты:
1) Построены численно эффективные модификации алгоритмов рекуррентного оценивания вектора состояния линейной дискретной динамической системы, возмущаемой белым гауссовым шумом, отличающиеся покомпонентной обработкой вектора измерений системы.
2) Математическое обоснование алгоритма вычисления логарифмической функции правдоподобия, построенного на основе "скаляризованной" стандартной реализации дискретного фильтра Калмана.
3) Построены численно эффективные алгоритмы рекуррентного вычисления логарифмической функции правдоподобия, разработанные на основе "скаляризованных" квадратно-корневых методах фильтрации и ориентированные на параллельные вычисления.
4) Разработана методика вычисления производной вырожденной блочной треугольной матрицы R, связанной ортогональным преобразованием Q с вырожденной матрицей А специального блочного вида. Новая схема вычислений уже не требует соблюдения невырожденности матриц и может быть применена к различным реализациям дискретного фильтра Калмана с целью разработки новых алгоритмов для нахождения ГЛФП.
5) Построены численно эффективные алгоритмы рекуррентного вычисления градиента логарифмической функции правдоподобия, основанные на квадратно-корневых реализациях дискретного фильтра Калмана, ориентированные на параллельные вычисления.
1. АНАСОВ O.JL, БУТКОВСКИЙ О.Я., ИСАКЕВИЧ В.В. Выявление нестационарности случайно-подобных сигналов динамической природы// Радиотехника и электроника. 1995. Т. 40. № 2. С. 255-260.
2. Бояринцев Ю.Е., Данилов В.А., Логинов А.А., Чистяков В.Ф. Численные методы решения сингулярных систем. Новосибирск: Наука. Сиб. отд-ние, 1989.
3. Ван-ДЕР-Вардер. Математическая статистика. Изд-во иностранной литературы, 1960.
4. Ван-Трис Г. Теория обнаружения оценок и модуляции. М.: Советское радио. Т. 1, 1972.
5. ГАНТМАХЕР Ф.Р. Теория матриц. М.: Наука, 1988.
6. ГЛУШКО А.З. Применение метода моментов в решении задачи параметрической идентификации// Приборостроение. 1990. Т. 33. № 1. С. 56-62.
7. ЛАЙНИОТИС Д. Разделение — единый метод построения адаптивных систем. I. Оценивание. И. Управление// ТИИЭР. 1976. Т. 64. № 8. С. 8-27; С. 74-93.20. льюинг л. Идентфикация систем. м.: Наука, 1991.
8. Семушин И.В., Цыганова Ю.В., Куликова М.В. О вычислении функции правдоподобия для гауссовских марковских последовательностей// Фундаментальные пробл. матем. и механ. Ульяновск: Изд-во УлГУ, 2000. Вып. 2(9). С. 93-100.
9. СРАГОНОВИЧ В.Г. Адаптивное управление. М.: Наука, 1981.
10. Фомин С.И., фрадков A.JL, Якубович В.А. Адаптивное управление динамическими объектами. М.: Наука, 1981.
11. Хазен Э.М. Методы оптимальных статистических решений и задачи оптимального управления. М.: изд-во "Советское радио", 1968.
12. ЦЫГАНОВА Ю.В. Алгоритмы адаптации и контроля активного типа в линейных стохастических системах управления. Диссертация на соискание ученой степени к.-та физ.-мат. наук. Ульяновск: Ульяновский Государственный Университет, 2000 г.
13. ЦЫГАНОВА Ю.В. Последовательные алгоритмы наименьших квадратов и статистического оценивания// Фундаментальные пробл. матем. и механ. Ульяновск: Изд-во УлГУ, 1996. Вып. 1. С. 79-83.
14. ЦЫПКИН Я.3. Адаптация и обучение в автоматических ситемах. М.: Наука, 1968.
15. ЦЫПКИН Я.З. Оптимальные алгоритмы оценивания параметров в задачах идентификации// АиТ. 1982. № 12. С. 9-23.
16. ЦЫПКИН Я.З., КЕЛЬМ АНС Г Л. Дискретные адаптивные системы управления. Сер. Итоги науки и техники: Техническая кибернетика. Т. 17. М.: ВИНИТИ. 1983. С. 3-73.
17. Цянь Сюэ-Сэнь. Техническая кибернетика. М.: ИЛ, 1956.
18. ШИРЯЕВ А.Н. Статистический последовательный анализ. М.: Наука, 1976.
19. Шульце К.-П., Реберг К.-Ю. Инженерный анализ адаптивных систем. М.: Мир, 1992.
20. ЭЙКХОФФ П. Основы идентификации систем управления. М.: Мир, 1975.
21. AGEE W.S., TURNER R.H. Triangular Decomposition of a Positive Defined Matrix Plus a Symmetric Dyad, with Applications to Kalman Filtering// White Sands Missile Range Tech. Rep. 38, 1972.
22. ANDERSON P. Adaptive joke getting in recursive identification through multiple models// Int. J. Contr. 1985. V. 42, У'- 5. P. 1175-1193.
23. ANDREWS A. A square root formulation of the Kalman covariance equations// AIAA Journal. 1968. V. 6. P. 1165-1166.
24. ASTROM K.J. Maximum likelihood and prediction error method// Automatica. 1980. V. 16. № 5. P. 551-574.
25. CARLSON N.A. Fast triangular formulation of the square root filter// AIAA Journal. 1973. V. 11. № 9. P. 1259-1265.
26. Chui C., Cheh G., Chui H. Modified extended Kalman filtering and realtime parallel algorithm error system parameter identification// IEEE Trans. Autom. Contr. 1991. V. 35. № 1. P. 100-104.
27. Dennis J.B. Data flow supercomputers// Computer. 1980. V. 13. JV« 48.
28. ENLIAN L. Estimation of stochastic parameters on nonlinear systems// Advances in Modelling and simulation. 1987. V. 9. X* 4. P. 23-29.
29. DYER P., McREYNOLDS S. Extension of square-root filtering to include process noise// Journal of Optimization Theory and Applications. 1969. V. 3. P. 444-458.iserman R. Parameter Adaptive Control Algorithms// Automatica. 1982. V. 18. JY» 5. P. 513-528.
30. KULIKOVA M.V. On Scalar Evaluation of the Logarithm of the Likelihood Ratio Function for Gaussian Signals// Book of abstracts of the Conference on Scientific Computing and Differential Equations (SciCADE 2003). Trondheim, Norway. 2003. P. 52-52.
31. I T.L. Sequential multiple hypothesis testing and efficient fault detection-isolation in stochastic systems// IEEE Trans, on Inform. Theory. 2000. V. IT-46. № 2. P. 595-608.
32. I T.L., Shan J.Z. Efficient recursive algorithms for detection of abrupt changes in signals and systems// IEEE Trans, on Autom. Contr. 1999. V.-AC-44. № 4. P. 952-966.
33. NDAU I.D. Model Reference Adaptive Controllers and Stochastic Selftuning Regulators. A Unified Approach// Journ. Dynamic Systems, Measurement and Control. 1981. V. 103. 6. P. 404-416.
34. WIS F.L. Optimal Estimation with an Introduction to Stochastic Control Theory. 1986. Jonh Wiley&Sons: New York, 1986.
35. Newbold P.M., Ho YU-Chi. Detection of Changes in the Characteristics of a Gauss-Markov Process// IEEE Trans, on Aerosp. and Electron. Systems. 1968. V. AES-4. * 5. P. 707-718.
36. NlKIFOROV I.V. A generalized change detection problem// IEEE Trans, on Inform. Theory. 1995. V. IT-41. .4' 1. P. 171-187.
37. NlKIFOROV I.V. A simple recursive algorithm for diagnosis of abrupt changes in random signals// IEEE Trans, on Inform. Theory. 2000. V. IT-46. № 7. P. 27402746.
38. NlKIFOROV I., VARAVA v., KlREICHIKOV v. Application of statistical fault detection algorithms for navigation systems monitoring// Proc. IFAC/IMACS Symp. SAFEPROCESS'91. Baden-Baden. 1991. v. 2. P. 351-356.
39. Rao S.K., Kailath T. VLSI arrays for digital signal processing. Part I: A model identification approach to digital filter realizations// IEEE Trans. Circuits Syst. 1985. V. CAS-32. № 1105.
40. Sangsuk-Iam S., Bullock Т.Е. Analysis of Discrete-Time Kalman Filtering Under Incorrect Noise Covariances// IEEE Trans, on Autom. Contr. 1990. V. 35. № 12. P. 1304-1308.
41. SCHWEPPE F.C. Evaluation of Likelihood Functions for Gaussian Signals// IEEE Trans, on Inform. Theory. 1965. V. IT-11. № 1. P. 61-70.
42. SEBORG D.E. A perspective on advanced strategies for process control (revisited)// In. Advances in control: highlights of ECC'99, London: Springer-Verlag London Limited, 1999. P. 103-134.
43. SEGAL M., WEINSTEIN E. A New Method for Evaluating the Log-Likelihood Gradient (Score) of Linear Dynamic Systems// IEEE Trans. Autom. Contr. 1988. V. 33. jYj 8. P. 763-766.
44. Yu-Chi Ho., agarawala A.K. On Pattern Classification Algorithms — Introduction and Survey// IEEE Trans, on Autom. Contr. 1968. V. AC-13. № 6. P. 676-690.
