Содержание к диссертации
Введение
1. Модифицированные алгоритмы рекуррентного оценивания 18
1.1. Постановка задачи 18
1.2. Инновации в теории калмановской фильтрации 19
1.2.1. Расширенный квадратно-корневой ковариационный алгоритм 19
1.2.2. Расширенный квадратно-корневой информационный алгоритм 21
1.2.3. Модифицированные алгоритмы, построенные на основе РКККФ и РККИФ 23
1.3. Последовательные алгоритмы рекуррентного оценивания 25
1.3.1. Формулировка последовательных алгоритмов 26
1.3.2. Теоретическое обоснование 29
1.4. Сравнительный анализ эффективности 31
1.4.1. Исследование вычислительной сложности 31
1.4.2. Устойчивость к ошибкам округления 38
1.5. Вычислительные эксперименты 44
1.5.1. Работоспособность 44
1.5.2. Сравнение вычислительной сложности 48
1.5.3. Устойчивость к ошибкам округления 51
2. Последовательные методы вычисления ЛФП 55
2.1. Постановка задачи 55
2.2. Вычисление ЛФП на основе стандартного алгоритма Калмана . 57
2.2.1. Формулировка алгоритма 57
2.2.2. Теоретическое обоснование алгоритма 58
2.3. Вычисление ЛФП на основе последовательных квадратно-корневых фильтров 63
2.4. Сравнительный анализ эффективности 68
2.5. Вычислительные эксперименты 73
2.5.1. Работоспособность 73
2.5.2. Сравнение вычислительной сложности 76
2.5.3. Устойчивость к ошибкам округления 81
3. Квадратно-корневые алгоритмы вычисления ГЛФП 85
3.1. Постановка задачи и формулы для вычисления ГЛФП 85
3.2. Метод вычисления ГЛФП, построенный на основе РКККФ 88
3.2.1. Формулировка алгоритма 88
3.2.2. Теоретическое обоснование алгоритма 90
3.3. Метод вычисления ГЛФП, построенный на основе РККИФ 94
3.3.1. Формулировка алгоритма 95
3.3.2. Теоретическое обоснование алгоритма 97
3.4. Метод вычисления ГЛФП, построенный на основе МККИФ 101
3.4.1. Формулировка алгоритма 101
3.4.2. Теоретическое обоснование алгоритма 102
3.5. Сравнительный анализ эффективности 104
3.5.1. Исследование вычислительной сложности 104
3.5.2. Устойчивость к ошибкам округления 108
3.6. Вычислительные эксперименты 111
3.6.1. Работоспособность 111
3.6.2. Устойчивость к ошибкам округления 116
Заключение 120
Литература 123
- Расширенный квадратно-корневой ковариационный алгоритм
- Модифицированные алгоритмы, построенные на основе РКККФ и РККИФ
- Вычисление ЛФП на основе стандартного алгоритма Калмана .
- Метод вычисления ГЛФП, построенный на основе РККИФ
Введение к работе
При изучении явлений окружающего мира мы часто сталкиваемся с процессами, течение которых заранее предсказать невозможно. Эта неопределенность (непредсказуемость) вызвана влиянием случайных факторов, воздействующих на ход процесса. Подобные неопределенности (помехи) присущи большинству процессов, протекающих в технических, экономических, биологических и др. системах. В связи с чем многие математические модели в биологии, медицине, электротехнике и т.д. представляют собой стохастические системы, т.е. системы стохастических дифференциальных уравнений.
Одной из важнейших задач математической кибернетики является задача адаптации, а одним из основных объектов исследования — адаптивные или, другими словами, "самонастраивающиеся" системы. Впервые понятие адаптации было использовано Цянь Сюз-Сэнем [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,...iV, влечет за собой применение р параллельных "дифференцированных" фильтров (по отношению к неизвестному параметру системы в Є Rp). В иностранной литературе: "filter sensitivity equations" (см., например, [49], [55], [59], [83], [84], [102], [103] и др.).
Возникающая, в связи с необходимостью применения дискретного фильтра Калмана, проблема хорошо известна — его стандартная реализация является неустойчивой по отношению к ошибкам округления, что очевидным образом влечет за собой некорректное вычисление ЛФП и ее градиента. В сложившихся обстоятельствах остро встает задача разработки новых численно эффективных алгоритмов нахождения указанных выше величин. Последнее обуславливает практическую ценность и подчеркивает актуальность поставленной в диссертационной работе задачи.
В связи со сказанным выше, коротко остановимся на истории развития теории калмановской фильтрации и ее современном состоянии. В начале 40-х годов двадцатого века, решая поставленную перед ним задачу разработки системы защиты от возникновения пожара на борту самолета, Norbert Wiener впервые применил теорию случайных процессов к проблемам управления и системам передачи данных [113].
Широко известное уравнение Винера-Хопфа (Wiener-Hopf equation [69]) г h(t, s)+ f h(t, t)K{t, s)dr = K(t, s), t0 В случае гауссовских величин линейная оценка x(t) совпадает с оптимальной в средне-квадратичном смысле. В уравнении (0.1), K(t,s) = E{x(t)x(s)T + x(t)v(s)T + v(t)x(s)T} — функция вектора состояния системы x(t) и вектора шумов v(t), Е{-} — операция математического ожидания. В I960 г. венгерский ученый Калман Р. впервые показал, что понятие наблюдаемости для динамических систем в теории оценивания имеет алгебраическую двойственность с понятием управляемости систем в теории управления. В том же году Richard S. Busy предположил, что уравнение Винера-Хопфа в случае конечномерных ВВЕДЕНИЕ систем эквивалентно матричному уравнению Риккати (Riccati equation [85]): Pt = FtPtFj - FtPtHj{HtPtHj + Rt)-lHtPtF? + 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], [9% [110], [111], [112] и многие др.). Прекрасный обзор предложенных к 1971 г. различных типов фильтров, иллюстрация их работы при решении плохо обусловленных задач и сравнительный анализ их эффективности были даны Kaminski P.G. и соавт. в [73]. В связи с обозначенной выше целью диссертационной работы, остановимся более подробно на истории развития существующих в настоящее время различных типов реализаций фильтра Калмана, их сравнительном анализе и современном состоянии данного направления исследований. Дискретный фильтр Калмана описывается следующими уравнениями (см., например, [85]): Этап экстраполяции: оценки: xj+1 = Ftxf + Btut, (0.4) ковариации ошибки: Р4+г = FtP* Fj -f GtQtGjj (0-5) Этап обработки измерений и фильтрации: Kt+i - ^t+i#t+i(#mA+i#t+i + Rt+i)'1, (0.6) оценки: f+1 = хї+1 + Kt+i(zt+1 - Ht+ixJ+1), (0.7) ковариации ошибки: РД^ = P^ — Kt+iHt+iP^, (0-8) где Ft, Gt, Bt, Ht, Qt, Rt — известные матрицы-параметры линейной дискретной динамической системы, щ — вектор управления, zt — доступный вектор наблюдений и xt — вектор состояния системы, где х0 ~ ЛҐ(х0,П0). Хорошо известно, что при отсутствии наблюдений за состоянием системы наилучшей в средне-квадратичном смысле оценкой вектора состояния является его математическое ожидание. При этом матрица ковариации ошибки оценивания х/ = it — Xt совпадает с матрицей ковариации самого вектора состояния динамической системы. Таким образом, в момент времени t = 0, когда измерения о состоянии системы еще не поступили, наилучшими оценками являются априорные знания, т.е. х0 и П0. ВВЕДЕНИЕ 10 Если в алгоритме фильтрации (0.4) — (0.8) соединить два этапа воедино, то мы получим еще одну известную формулировку данного алгоритма: x;+l = Ftx~ + FtPt~Hj{HtPt-Hj + Rt)-\zt - tftx"), хе = x0, (0.9) P^ = FtPrFj-Ftp-Hj{HtPt-Hj + Rt)-lHtPrFj^GtQtG^ P0~ = П0. (0.10) Легко видеть, что уравнение (0.10) есть ни что иное как уравнение Риккати (0.3). Одной из проблем, возникающей при реализации алгоритма (0.4) — (0.8) или (0.9) — (0.10) с помощью ЭВМ, является потеря положительной определенности матрицы Pf из-за ошибок округления, что в свою очередь, приводит к неустойчивости самого алгоритма оценивания. В связи с чем были разработаны новые типы реализации фильтра, которые алгебраически эквивалентны начальной версии алгоритма, однако, позволяют решать возникающие на практике проблемы, связанные с ошибками округления при использовании ЭВМ в качестве средства вычислений. Исторически, первыми возникли, так называемые, квадратно-корневые алгоритмы фильтрации. Ключевая идея, лежащая в основе всех таких методов, принадлежит Cholesky и Banachiewicz [73]. Ими были получены два независимых, но эквивалентных доказательства алгоритма представления любой положительно-определенной матрицы, скажем А, в виде A = LLT. Однако метод факторизации таких матриц был развит ими с целью разработки численного устойчивого алгоритма для нахождения решения системы уравнений, вида Ах = Ь, где А — положительно-определенная матрица. Первые квадратно-корневые алгоритмы фильтрации появились только в 1963 г. Родоначальниками данного подхода являются Potter J.E. и Stern R.G. [97], кто впервые применил идею факторизации положительно-определенных матриц к алгоритмам калмановской фильтрации. Ими была развита основная идея таких методов, заключающаяся в представлении матрицы ковариации ошибки оценивания Р* в виде Pt = Sf (5,±)t , где Sf — так называемый, квадратный корень матрицы Pt . Данная "структурная" переформуливка алгоритма позволяет убрать один существенный недостаток, упомянутый ранее, — потерю положительной определенности матрицы ковариации ошибки оценивания Р*. В случае работы с ее факторами Sf, этот недостаток и связанная с ним численная неустойчивость фильтра Калмана устраняются, поскольку теперь Р* = Sf (St) — всегда положительно-определенная. Кроме того, исследование чисел обусловленности указанных выше матриц показало, что алгоритмы, созданные для работы не с самой матрицей Pt , а с ее квадратными корнями Sf, обеспечивают вычисления с двойной точностью (см., например, [73]). Таким образом, квадратно-корневые алгоритмы фильтрации существенно превосходят стандартный алгоритм Калмана. В связи с чем именно эти типы реализаций фильтра были успешно применены в космической навигации, в программе исследования Луны (Apollo, см. [52]). В 1963 г. Potter J.E. в своей работе [97] показал, что этап обработки измерений стандартного фильтра Калмана может быть выражен в терминах множителей ВВЕДЕНИЕ Холецкого (Cholesky), т.е. уравнение (0.8) представимо в следующем виде: Р+ = S+{St? = Pf - KtHtPt~ = St(I - affT)Sj, (0.11) где I — единичная матрица соответствующего размера и j = SjHj, и l/a^ff + Rt, где fit Є Я1. (0.12) Он также доказал, что величина (/ — otffT) в уравнении (0.11) может быть далее факторизована с помощью специального выбора некой константы 7 и представлена в следующем виде: (/ - aff) = (1- а7//Г)(/ - а7//Т), 7 = 1/(1 ± ^/ =» Kt = aStft, St = St-cx1StffT. (0.13) Таким образом, этап обработки измерений стандартного фильтра Калмана, т.е. уравнения (0.6) - (0.8) могут быть заменены на алгебраически эквивалентные (0.12), (0.13), но дающие существенные преимущества, перечисленные ранее, по сравнению со стандартным алгоритмом. Следует отметить, что при разработке нового подхода к алгоритмам фильтрации Potter J.E. рассматривал определенный класс задач, а именно: он развил свои идеи только для случая одномерного выходного сигнала системы zt и при условии, что матрица ковариации шумов в объекте Qt = 0. Очевидно, что подобные ограничения существенно сокращают потенциал самой методики. Дальнейшие исследования были направлены на преодоление этих ограничений. Обобщение идеи Potter J.E. и Stern R.G. на случай мульти-выходных систем, т.е. систем, где выходной сигнал Zt есть вектор, скажем zt Є Rm, было развито и опубликовано Andrews А. в 1968 г. (см. [48]). Он показал, что в случае, если матрица ковариации шумов в измерителе Rt является диагональной, то для обработки т-мерного вектора измерений zt динамической системы на этапе II алгоритма может быть использована процедура Potter J.E., примененная, соответственно, т раз. Однако новые открытия также не решили всех проблем, возникающих на практике. Действительно, при реализации предложенных квадратно-корневых алгоритмов фильтрации с помощью ЭВМ, зачастую, возникает ситуация, когда из-за ошибок округления матрицы 5"* теряют свой специальный вид (согласно представлению Р* = St(Sf)T матрицы St имеют верхний или нижний треугольный вид). Устранить данный недостаток можно с помощью, так называемой, процедуры триангуля-ризации, т.е. процедуры приведения матрицы 5t к требуемому треугольному виду. Эта идея впервые была предложена и развита Schmidt S.F. [107] в 1970 г. В частности, он показал, что уравнение (0.5) для предсказания матрицы ковариации ошибки оценивания на этапе экстраполяции может быть заменено на эквивалентное: ВВЕДЕНИЕ где Pt+1 = St+1(St+l)T, Pt+ - St(St)T, Qt = QtQj и St+1, Sf, Qt — нижний треугольные матрицы. Он также разработал алгоритм для нахождения ортогонального преобразования Т, приводящего к требуемому треугольному виду матрицу, стоящую в правой части формулы (0.14). Эта процедура известна как процедура ортогонализации Грама-Шмидта. Еще одним важным типом реализации фильтра Калмана, гарантирующим положительную определенность Pf+, является, так называемый, стабилизированный алгоритм Джозефа (Joseph stabilized version [85]), впервые предложенный в 1968 г. авторами Bucy R.S. и Joseph P.D. В данной версии алгоритма уравнение (0.8) стандартного фильтра Калмана заменяется на алгебраически эквивалентное [58]: Р+ = (/ - KtHt)Pt~{I - KtHt)T + KtKj, но уже гарантирующее положительную определенность матрицы Pt+ (которая могла бы быть утеряна из-за ошибок округления). Все рассмотренные выше алгоритмы калмановской фильтрации относятся к, так называемым, ковариационным типам фильтров, поскольку с основе их работы лежит идея предсказания и фильтрации матрицы ковариации ошибки оценивания Pt или ее квадратных корней St . Однако существует другой важный класс методов, который также заслуживает особого внимания- Это, так называемые, информационные типы алгоритмов. В основе их работы лежит идея предсказания и фильтрации матрицы обратной к матрице ковариации ошибки, т.е. Af = (Р/1)-1 (а также ее факторов). Матрицу Af называют информационной матрицей, что и дало название данному классу методов. Их появление обусловлено тем, что зачастую на практике приходится решать задачи в условиях очень скудной априорной информации или, вообще говоря, в ее отсутствии, что математически может быть записано следующим образом: Xq = х0 = 0 и Pq — П0 = оо. В этих условиях применение ковариационных алгоритмов фильтрации не способно решить поставленную задачу, тогда как информационные типы методов справляются с этим легко: в качестве начальных условий достаточно положить Xq = xq = 0 и Aq = 0. Именно на решение таких задач и нацелен, прежде всего, данный класс методов. Информационные алгоритмы фильтрации впервые были разработаны и опубликованы в конце 60-х авторами Dyer Р. и McReynolds S. [66]. Таким образом, к началу семидесятых годов двадцатого века были разработаны все основные типы реализаций фильтра Калмана. Дальнейшие исследования в теории фильтрации были обусловлены все повышающимися требованиями к эффективности разрабатываемых алгоритмов, т.е. к их способности быстро и эффективно обрабатывать данные наблюдений, существенно повысив тем самым точность и надежность систем обработки информации и управления. По этой причине усилия ученых в дальнейшем были направлены, прежде всего, на разработку новых, численно устойчивых и более эффективных с точки зрения вычислительных затрат алгоритмов. Итак, семидесятые годы двадцатого века были ознаменованы целым рядом открытий, последовавших друг за другом. В 1971 г. Kaminski P.G. предложил новые ВВЕДЕНИЕ модификации ковариационных и информационных типов квадратно-корневых методов фильтрации, обладающие рядом преимуществ перед ранее известными алгоритмами [72]. Остановимся более подробно лишь на одном из них, который потребуется в дальнейшем. Исходя из хорошо известной дуальности ковариационных и информационных алгоритмов, Kaminski P.G. разработал новую схему для осуществления этапа обработки измерений и фильтрации [72]: В}'2 О HtST (0.15) где Re't — квадратный корень матрицы ковариации невязки измерений Rej, где et — zt — НхТ, Kt — Pf HjR~t , 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Р^ = Р^.1 — Pt вместо Pt , что позволило значительно улучшить численные характеристики квадратно-корневых алгоритмов для подобных систем, т.е. сократить общее количество арифметических действий на вычисления и, следовательно, время работы [91]. Кроме того, ими была предложена идея слияния воедино алгоритмов, разработанных Schmidt S.F. для этапа экстраполяции фильтра Калмана (0.14) и Kaminski P.G. для этапа обработки измерений (0.15), с целью получения новой, более эффективной реализации фильтра: (РГ+1)1/2 о (0.16) (РГУ'2Н? (РГ)1/2^Г0 Q]/2GJ где Г — любое ортогональное преобразование, приводящее к верхнему треугольному виду матрицу, стоящую в правой части формулы (0.16) и Kp Еще один важный тип реализаций — это, так называемые, U — D алгоритмы для калмановской фильтрации. Они впервые были предложены в 1974 г. Bier-man G.J. [54] и затем дополнены и улучшены Thornton C.L. [111] в 1976 г. Основная ВВЕДЕНИЕ идея данных типов методов заключается в представлении матриц Pt~, Rt, Qt& виде: р± = (p(±)T/2Dt±(pt±)1/2) Rt = ЯрЯ*_ДЇ'2, ^ = 0Г/2Ад;/2, где Д±, Д* D? - '*, диагональные матрицы, (Р^1)1^2, Rt , Qt —верхний треугольные с единичной диа- гональю. Аналогично, можно сформулировать алгоритм, где матрицы (Р^)1^2,* Rt > Qt — нижний треугольные с единичной диагональю. Если в уравнении (0.16) для выше указанных матриц использовать U—D разложение, то оно может быть заменено на алгебраически эквивалентные: обозначим матрицы, стоящие в левой и правой части формулы (0.16) через W и U, соответственно. Тогда с помощью взвешенного алгоритма ортогонализации Грама-Шмидта, разработанного Bierman G.J., можно построить матрицу V такую, что ее строки взаимно ортогональны и выполняются условия: W = UV, и D = VDVT =* WDWT = UVDVTUT = UDUT, где матрица D — блочно диагональная с блоками Df, Df и D{, соответственно. В зарубежной литературе данные типы методов называют "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 — ортогональное преобразование, А — прямоугольная матрица. Отметим, что подобная задача, но только для случая невырожденных матриц R и А, была решена в 1991 г. Bierman G.J. и соавт [55]. Очевидно, что данное ограничение — невырожденность матриц — существенно снижает потенциал самой методики. Здесь удалось усилить этот результат, существенно расширив, тем самым, область его применимости. В конечном итоге, это позволило решить задачу вычисления ГЛФП с помощью различных типов реализаций фильтра Калмана. Эти новые схемы вычислений уже не требуют соблюдения невырожденности матриц и могут быть применены к различным видам фильтров. В прикладном аспекте особо следует подчеркнуть возможность применения полученных результатов при решении современных прикладных задач с использованием многопроцессорных вычислительных комплексов в качестве средства вычислений, поскольку все разработанные в диссертации алгоритмы допускают эффективное распараллеливание. Диссертация объемом 131 страница состоит из введения, трех глав, заключения и списка литературы (114 наименований). Работа включает 29 таблиц и 13 рисунков. В Главе 1, состоящей из пяти параграфов, предложены новые эффективные алгоритмы рекуррентного оценивания, разработанные на основе последних достижений в области калмановской фильтрации. Раздел 1.2 носит вводный характер. В нем представлен краткий обзор инноваций в данной области исследований. Раздел 1.3 посвящен построению и строгому математическому обоснованию новых последовательных алгоритмов фильтрации. Сравнительный анализ их эффективности, включающий в себя анализ вычислительной сложности и устойчивости к ВВЕДЕНИЕ ошибкам округления, представлен в Разделе 1.4. Все теоретические выводы, сделанные в данной главе, о работоспособности, надежности и эффективности новых алгоритмов перед ранее известными реализациями дискретного фильтра Калма-на подтверждены практически и проиллюстрированы на многочисленных вычислительных примерах, результаты которых изложены в Разделе 1.5. В Главе 2, состоящей из пяти параграфов, предложены новые численно эффективные алгоритмы вычисления логарифмической функции правдоподобия (ЛФП). Алгоритм для нахождения ЛФП, построенный на основе стандартного "скаляри-зованного" фильтра Калмана, и его строгое математическое обоснование представлены в Разделе 2.2. Разработанные в первой главе диссертации новые "скаляри-зованные" квадратно-корневые фильтры послужили базисом для построения на их основе алгоритмов для вычисления ЛФП и изложены в Разделе 2:3 диссертации. Сравнительный анализ эффективности новых алгоритмов, включающий в себя анализ вычислительной сложности и устойчивости к ошибкам округления, проведен в Разделе 2.4, а результаты проведенных экспериментов, педставленные в Разделе 2.5. В Главе 3, состоящей из шести параграфов, разработаны новые численно эффективные алгоритмы вычисления градиента логарифмической функции правдоподобия (ГЛФП). В Разделах 3.2, 3.3, 3.4 сформулированы и строго математически обоснована справедливость новых методов вычисления ГЛФП, построенных на основе последних достижений в области калмановской фильтрации, т.е. алгоритмов РКККФ, РККИФ и МККИФ, соответственно. Сравнительный анализ их эффективности, включающий в себя анализ вычислительной сложности и устойчивости к ошибкам округления, представлен в Разделе 3.5. Результаты вычислительных экспериментов изложены в Разделе 3.6. Они подтверждают работоспособность разработанных алгоритмов и их преимущества перед стандартным подходом, т.е. с использованием "дифференцированного" фильтра Калмана. Сравнительный анализ эффективности проиллюстрирован при решении плохо обусловленных задач, т.е. в случае когда "дифференцированный" фильтр Калмана терпит поражение. Основные теоретические результаты сформулированы в виде лемм и теорем. В диссертации принята двойная нумерация формул, теорем, рисунков и т.п.: первая цифра означает номер главы, вторая — номер формулы, теоремы, рисунка и т.п. Положения диссертационной работы, выносимые на защиту: Численно эффективные модификации квадратно-корневых реализаций дискретного фильтра Калмана, разработанные на основе покомпонентной обработки вектора измерений системы. Математическое обоснование алгоритма вычисления логарифмической функции правдоподобия, построенного на основе "скаляризованной" стандартной реализации дискретного фильтра Калмана. Численно эффективные алгоритмы рекуррентного вычисления логарифмической функции правдоподобия, разработанные на основе "скаляризованных" квадратно-корневых методах фильтрации и ориентированные на параллельные вычисления. ВВЕДЕНИЕ Способ вычисления матрицы R'$ специального блочного треугольного вида, связанной ортогональным преобразованием Q с прямоугольной матрицей А. Численно эффективные алгоритмы рекуррентного вычисления градиента логарифмической функции правдоподобия по отношению к неизвестному параметру системы в Є Rp, основанные на квадратно-корневых реализациях дискретного фильтра Калмана и ориентированные на параллельные вычисления. Результаты, изложенные выше, получены при финансовой поддержке Министерства общего и профессионального образования России (грант Министерства Образования Российской Федерации, № Т02-03.2-3427, 2002-2003). Основные результаты диссертации докладывались: на IV международной научно-технической конференции "Математическое моделирование физических, экономических, технических, социальных системи процессов" (Ульяновск, 2001), на XXIV конференции молодых ученых механико-математического факультета МГУ им. М.В. Ломоносова (Москва, 2002), на V международной научно-технической конференции "Математическое моделирование физических, экономических, технических, социальных систем и процессов" (Ульяновск, 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). По теме диссертации опубликованы 11 работ, в том числе: [14], [15], [16], [17], [18], [33], [74], [75], [76], [77], [106]. Автор считает приятным долгом выразить искреннюю благодарность научному руководителю профессору Семушину И.В. за помощь и постоянное внимание, оказываемое при работе над диссертацией. Как отмечалось ранее, в наши дни при разработке новых типов реализаций фильтра Калмана акцент ставится на создание эффективных алгоритмов, ориентированных на возможность дальнейшего применения многопроцессорных вычислительных комплексов в качестве средства вычислений. Алгоритмы данного типа были предложены в 1995 г. (см. [96]). В параграфе 1.2 остановимся детально на последних разработках в теории калмановской фильтрации и исследуем их преимущества перед ранее известными методами. Для удобства дальнейшего изложения введем следующие обозначения: пусть матрица А 0, будем рассматривать разложение Холецкого вида: А = АТ 2А1 2, где А1/2 — верхняя треугольная матрица, являющаяся квадратным корнем А. Тогда лг/2 = (Ai/2jrj л-і/2 = (А1/2)"1 и А т12 = {А-1 2)т. Для величин, вычисляемых в фильтре Калмана, примем обозначения: KPit = $tPtHjЩ}, Kp,t = tPHj R t , et — нормализованные невязки фильтра Калмана, т.е. et = Щ,І е, гДе е = zt — HxJ — невязка измерений фильтра в момент времени , характеризующаяся ковариационной матрицей E{eteJ} = ReM Re,t = HtPtHf -f Rt. Кроме того, xt , xf — предсказанная и отфильтрованная оценки вектора состояния системы (1.1), (1.2), соответственно; Pt, Pt — предсказанная и отфильтрованная оценки матрицы ковариации ошибки. Исходя из цели, обозначенной в данном разделе, рассмотрим, так называемый, расширенный квадратно-корневой ковариационный алгоритм фильтрации (РКККФ), впервые предложенный в [96]. Теоретическое обоснование изложенного выше алгоритма можно найти [96]. В частности, отметим, что уравнения (0.9), (0.10) стандартного фильтра Калмана (СКФ) алгебраически эквивалентны формуле (1.3). Очевидно, что представленный выше РКККФ, есть ни что иное как "расширение" стандартного квадратно-коневого ковариационного алгоритма фильтрации (см. что и дало название данному типу фильтра. Однако, несмотря на свою простоту, подобная модификация алгоритма обладает рядом преимуществ перед ранее известными ковариационными реализациями дискретного фильтра Калмана [96]: 1 С целью нахождения предсказанной оценки вектора состояния системы xj +i с помощью стандартного квадратно-корневого ковариационного алгоритма фильтрации (СКККФ) (см. формулу (0.16)) существует необходимость организовывать дополнительные вычисления, а именно: по доступным из (0.16) Kp t, R\\t найти х +1 = Фі&7 + Kp,t \R\,t ) (zt HtXf). Последнее, в свою очередь, требует обращения верхней треугольной матрицы Rei размера m х т. Однако при использовании РКККФ эта необходимость исчезает. По найденным из (1.3) величинам P /i и /f+i/ xt+i сразу находим xt+1 — rt+l \rt+l xt+l} 2 Поскольку теперь х +1 определяется непосредственно из алгоритма, нетребуя дополнительных вычислений, а также все необходимые для продолжения работы фильтра данные могут быть найдены одновременно и независимо друг от друга, то это свойство РКККФ (1.3) делает его более приспособленным к параллельным вычислениям, чем, например, ранее известные методы. 3 Для каждого момента времени t единственной матрицей, для которой требуется вычисление обратной, является верхняя треугольная матрица Rt . (В случае если По ф 1п, где 1п — единичная матрица размера пхп, также необходимо вычислить По ). Таким образом, в случае П0 = 1п работоспособность РКККФ в каждый момент времени t существенным образом зависит от свойств матрицы Rt . Пояснение данного свойства РКККФ и наглядная иллюстрация такого рода ситуации с помощью вычислительных экспериментов будет представлена в Главе 2 диссертационной работы (см. пп. 2.5.3). Очевидно, что если следовать методике, предложенной в [96], то РКККФ (1.3) может быть разбит на два этапа следующим образом: Этап обработки измерений и фильтрации: где Ot,i — ортогональное преобразование, приводящее к блочному верхнему треугольному виду первых два (блочных) столбца матрицы, стоящей в левой части формулы (1.5а). Легко видеть, что формула (1.5а) есть ни что иное как "расширенное" уравнение (0.15), разработанное Kaminski P.G. Этап экстраполяции: где Ot,2 — ортогональное преобразование, приводящее к верхнему треугольному виду первый (блочный) столбец матрицы, стоящей в левой части формулы (1.56). Также очевидно, что формула (1.56) есть ни что иное как "расширенное" уравнение (0.14), разработанное Schmidt S.F. Как отмечалось ранее, информационные алгоритмы применяются для решения задач в условиях очень скудной априорной информации или в ее отсутствии, т.е. в тех ситуациях, когда применение ковариационных фильтров не способно решить проблему, что еще раз подчеркивает важность разработки информационных типов методов. Рассмотрим расширенный квадратно-корневой информационный алгоритм фильтрации (РККИФ), впервые предложенный в [96]. Алгоритм РККИФ в(?е 0( — то же самое ортогональное преобразование, что и в СКККФ (0.16), или любое иное, приводящее к нижнему треугольному виду первых три (блочных) столбца матрицы, стоящей в левой части формулы (1.6), и Iq — единичная матрица размера qx q. Теоретическое обоснование изложенного выше алгоритма можно найти [96]. В частности отметим, что РККИФ получен аналогичным образом, что и РКККФ, т.е. путем добавления столбца данных (1.4) к квадратно-корневому информационному алгоритму фильтрации: Подобная модификация обладает рядом преимуществ перед ранее известными информационными типами реализаций фильтра Калмана [96]: 1 Поскольку теперь величины Pt+i и f Д+1 t+i) доступны непосредственно из алгоритма (см. РККИФ, формула (1.6)), то предсказанная оценка вектора состояния х +1 может быть найдена с помощью решения линейной треугольной системы, вида: (Pt+i/2) ( Г+і) = [Pt +i й-і)- 2 Поскольку все необходимые для продолжения работы фильтра данные могут быть найдены одновременно и независимо друг от друга, то это свойство РККИФ (1.6) делает его более приспособленным к параллельным вычислениям, чем, например, ранее известные методы. Таким образом, в случае систем с большой размерностью вектора наблюдений (т п) целесообразно применять разработанные в диссертации последовательные алгоритмы фильтрации (т.е. П-РКККФ (1.12), П-РККИФ (1.13), П-МККИФ (1.14), П-КККФ (1.15)) вместо соответствующих "векторных" аналогов. Наглядно показано, что использование последних в указанном случае (т.е. при т » п) не эффективно с точки зрения общего количества арифметических действий и, соответственно, затрат машинного времени на организацию вычислений. Более того, из сказанного выше следует, что чем больше размерность вектора наблюдений т, тем существеннее выигрыш во времени от применения "скаляризованных" реализаций фильтра. Итак, теоретически подтверждено, что построенные последовательные алгоритмы П-РКККФ (1.12), П-РККИФ (1.13), П-МККИФ (1.14), П-КККФ (1.15) обладают преимуществами 1, 3, 4 (см. с. 25), которые присущи всем "скаляризованные" типам методов, и, кроме того, по построению наследуют достижения "базовых" алгоритмов (в частности, ориентированность на параллельные вычисления). Все сделанные в данном разделе теоретические выводы об эффективности новых методов будут подтверждены практически в пп. 1.5.2. Далее, оценим вычислительные затраты новых последовательных методов фильтрации и сравним их с вычислительными характеристиками ранее существовавших алгоритмов. Другими словами, постараемся ответить на вопрос: какое место по своим вычислительным затратам занимают разработанные в диссертационной работе новые последовательные реализации дискретного фильтра Калмана среди ранее существовавших методов. Для сравнительного анализа были выбраны: стандартный и "скаляризованный" алгоритмы Калмана (см. формулы (0.4) - (0.5), (1.16) - (1.17)), U — D алгоритм Бирмана, квадратно-корневые методы Поттера и Карлсона. С целью, обозначенной выше, проведем подсчет общего числа арифметических действий, затрачиваемых на вычисления согласно указанным выше реализациям на одном шаге их работы, т.е. на этапах экстраполяции и обработки измерений. При этом не будем учитывать затраты на вычисление вектора наблюдений zt, так как данная величина одинакова для всех реализаций фильтра, а, следовательно, не представляет для дальнейшего исследования интереса. По результатам подсчета сформируем табл. 1.5, 1.6 и проведем сравнительный анализ вычислительных затрат. Прежде всего отметим, что "скаляризованная" реализация стандартного фильтра Калмана требует приблизительно на два порядка меньше операций относительно параметра т, чем его "векторный" аналог (см. табл. 1.6). Таким образом, еще раз подтверждается тот факт, что переход от векторной обработки вектора наблюдений zt к покомпонентной ("скалярной") обеспечивает снижение объема вычислений на два порядка относительно т, где т — размерность вектора zt в измерителе (1.2). Анализируя данные табл. 1.5, 1.6, можно сделать ряд выводов. В случае когда параметры системы (1.1), (1-2) m,q « п, т.е. размерность вектора наблюдений zt и вектора шумов в объекте wt много меньше размерности вектора состояния системы xt, то справедливо следующее: П-РКККФ, П-РККИФ и алгоритм Карлсона требуют наименьшего количества арифметических действий на организацию вычислений; П-РКККФ и П-РККИФ затрачивают приблизительно одинаковый объем вычислений, но в т + 1 раз больше, чем квадратно-корневой алгоритм Карлсона; Алгоритм Поттера требует в 1,5 раза больше арифметических действий, чем П-РКККФ, П-РККИФ и фильтр Карлсона; аналогично П-РКККФ и П-РККИФ, модификации П-КККФ, П-МККИФ затрачивают приблизительно одинаковое количество арифметических операций, но в т + 1 раз больше, чем последовательная реализация стандартного алгоритма Калмана. Когда т и q приближаются к п, то П-РККИФ требует приблизительно в q раз больше арифметических действий, чем П-РКККФ, ивд2 раз больше, чем квадратно-корневой алгоритм Карлсона. Затраты алгоритмов Поттера и Карлсона в этом случае приблизительно одинаковы и немногим меньше, чем затраты последовательного стандартного фильтра Калмана. Аналогично, П-КККФ требует приблизительно в q раз больше арифметических действий, чем П-МККИФ, и в q2 раз больше, чем "скаляризованная" реализация стандартного фильтра Калмана. В случае когда параметры системы (1.1), (1.2) п,д « т, т.е. размерность вектора наблюдений zt много больше размерности вектора шумов в объекте wt и вектора состояния системы Xf, то справедливо следующее: сложность стандартного алгоритма Калмана есть 0(т3), т.е. данная реализация требует наибольшего количества арифметических действий; все остальные алгоритмы являются "скалярными" реализациями, так как обрабатывают вектор наблюдений покомпонентно, и тем самым их зависимость вычислительных затрат от размерности вектора zt носит линейный характер. Ситуация, изложенная ниже, очень редко встречается при решении практических задач и, тем самым, представляет интерес только с теоретической точки зрения. Пусть ге,т д, т.е. размерность вектора шумов в объекте Wt много больше размерности наблюдений zt и вектора состояния системы xt, тогда справедливо, что вычислительные затраты алгоритмов П-РККИФ и П-КККФ в этом случае приблизительно одинаковы; кроме того, П-РККИФ и П-КККФ требуют наибольших объемов вычислений; ранее известные раелизации дискретного фильтра Калмана, а именно: алгоритмы Поттера, Карлсона, Бирмана и последовательный стандартный алгоритм Калмана требуют наименьшего количества арифметических действий и зависимость их вычислительных затрат от размерности вектора wt носит линейный характер. Дальнейшая работа направлена на исследование вычислительной точности новых "скаляризованных" методов обработки данных. Основной задачей данного раздела является иллюстрация надежности (т.е. устойчивости к ошибкам округления) "векторных" (см. п. 1.2) и разработанных "скаляризованных" (см. п. 1.3) типов фильтров по сравнению со стандартным алгоритмом Калмана и некоторыми ранее развитыми его реализациями. Одной из причин потери вычислительной точности при работе алгоритма является машинное округление. Так как число двоичных разрядов, отводимых под мантису числа, в ЭВМ ограничено, то при выполнении арифметических действий неизбежно возникают погрешности машинного округления. Чтобы показать их влияние на результаты работы различных алгоритмов, рассмотрим два простых примера плохо обусловленных задач, наиболее часто встречающихся в литературе (см., например, [64], [73], [85]). Один и тот же метод нахождения ЛФП может вычислять их с разной точностью, в зависимости от свойств той или иной реализации дискретного фильтра Калмана, которая была использована в качестве "базового" метода для построения алгоритма ЛФП. В связи с чем, исследуем устойчивость к ошибкам округления при вычислении указанных выше величин в отдельности. Итак, чтобы показать влияние ошибок округления на результаты работы предложенных в диссертационной работе алгоритмов вычисления ЛФП, рассмотрим задачу 1.4.3 (см. пп. 1.4.2, Глава 1). В условиях примера 2.5.3 вычислим значения det(i?e i) и ef іС,їеі после обработки одного измерения при d — 0 и сравним полученные результаты с точным решением задачи. Эксперимент спланирован следующим образом: пусть число а таково, что 0 т 1 и выполняются условия: с + 1 ф 1, но в результате округления имеем — + 1 = 1. Тогда, очевидно, что при d а точное решение задачи будет отличаться от решения, полученного с использованием ЭВМ, из-за неизбежности процесса округления. Для компьютерной системы матричных вычислений MatLab, с помощью которой был написан код программы, число 0 а « 1, удовлетворяющее условиям: a -f 1 ф 1, но — + 1 = 1, есть величина 2.2204 10 16, хранящееся в переменной EPS. Напомним, что при Q\ = 1 пример 2.5.3 иллюстрирует особенности задачи с плохой обусловленностью начального этапа обработки и схемы измерений. Как было показано ранее, в данной ситуации из-за ошибок округления матрица ReX близка к вырожденной. Попытки ее обращения приводят к расхождению всего алгоритма фильтрации. В связи с чем, при d EPS относительная погрешность вычислений резко возрастает, что в конечном счете приводит к неспособности того или иного алгоритма решить поставленную задачу. Основной целью данного эксперимента является иллюстрация устойчивости к ошибкам округления разработанных в диссертации новых последовательных алгоритмов вычисления ЛФП. Для сравнительного анализа были выбраны: стандартный "векторный" алгоритм Калмана для вычисления ЛФП, "скалярный" ЛФП-ПКФ, алгоритм, сформулированный на основе метода Поттера [37], и разработанные в диссертационной работе методы: ЛФП-ПРКККФ, ЛФП-ПРККИФ, ЛФП-ПМККИФ, ЛФП-ПКККФ. Заметим, что два последних алгоритма являются модификациями первых двух и получены путем добавления в них новой иформации. Очевидно, что они производят тот же результат для величин det(Reit), ejR let, что и "базовые" методы, т.е. ЛФП-ПРКККФ, ЛФП-ПРККИФ. В связи с чем, отдельное исследование алгоритмов ЛФП-ПМККИФ, ЛФП-ПКККФ не представляет собой дальнейшего интереса. Итак, вычислим значение двух слагаемых ЛФП: det(/2e,i) и ejR {ei, после обработки одного измерения указанными выше методами и сравним полученные данные с точным решением задачи. Затем, найдем относительную погрешность вычислений, используя норму loo, и представим полученные данные в виде графиков рис. 2.3 и 2.4. Обратимся, прежде всего, к рис. 2.3, где представлена зависимость относительной погрешности вычислений det(i?e,i) (в норме /оо) от параметра d для 10_9EPS2/3 d 109EPS2/3 или, другими словами, при Ю-20 d Ю-2. Легко видеть, что в условиях примера 2.5.3 алгоритмы: Поттера, ЛФП-РКККФ и ЛФП-ПРКККФ обеспечивают одинаковую точность при вычислении det(i?e,i) и ведут себя наилучшим образом — им удается как можно дольше сохранять приемлемую точность. Алгоритм ЛФП-ПКФ, построенный на основе "скаляризованной" реализации стандартного фильтра Калмана, чуть хуже справляется с поставленной задачей. Действительно, из рис. 2.3 наглядно видно, что при Ю-7 d Ю-2 все пять алгоритмов, т.е. "векторный" Калмана, ЛФП-РКККФ, ЛФП-ПРКККФ, ЛФП-ПКФ и алгоритм Поттера работают одинаково. Затем, ЛФП-ПКФ немного теряет точность вычислений, тогда как квадратно-корневые методы обеспечивают практически точное решение. Кроме того, из рис. 2.3 наглядно видно, что стандартный алгоритм Калмана справляется с поставленной задачей наихудшим образом. Таким образом, результаты проведенного эксперимента ясно показывают, что в условиях примера 2.5.3 исследуемые алгоритмы: ЛФП-Поттера, ЛФП-РКККФ и ЛФП-ПРКККФ менее чувствительны к ошибкам округления при вычислении det(Ke,i), чем остальные методы фильтрации. Обратимся к рис. 2.4. Здесь представлена зависимость относительной погрешности вычислений ejR \ei (в норме /оо) от параметра d для 10 9EPS2/3 d 109EPS2/3 или, другими словами, при Ю-20 d Ю-2. Из рис. 2.4 легко видеть, что в условиях примера 2.5.3 алгоритм Поттера для вычисления ЛФП ведет себя наилучшим образом. Действительно, даже при Ю-16 d Ю-10, т.е. в случае, когда остальные исследуемые методы полностью неработоспособны, алгоритм Поттера обеспечивает вычисления с приемлемой точностью — относительная погрешность вычислений в данном эксперименте составила около 20%. Алгоритм ЛФП-ПКФ, построенный на основе "скаляризованной" реализации стандартного фильтра Калмана, чуть хуже справляется с поставленной задачей. Действительно, при Ю-7 d Ю-2 все пять алгоритмов, т.е. "векторный" Калмана, ЛФП-РКККФ, ЛФП-ПРКККФ, ЛФП-ПКФ и алгоритм Иоттера работают одинаково, обеспечивая практически точное вычисление ejR \ei в данном эксперименте. Затем, ЛФП-ПКФ немного теряет точность, а предложенный в диссертационной работе алгоритм ЛФП-ПРКККФ, так же как и его "векторный" аналог ЛФП-РКККФ и стандартный алгоритм Калмана, не способны решить поставленную задачу. Уже при d = Ю-8 и далее их относительная погрешность вычислений составила 100%, что говорит об их полной неработоспособности. Может показаться, что результаты проведенного эксперимента говорят о неработоспособности новых методов вычисления ЛФП, разработанных в диссертации. Однако, неторопясь с выводами, более внимательно рассмотрим и исследуем сложившуюся ситуацию. Так, авторы РКККФ, РККИФ, МККИФ и КККФ фильтров в своей работе [96, с. 897] отмечают: "Поскольку в каждый момент времени t единственной матрицей, для которой требуется вычисление обратной, является верхняя треугольная матрица Rt , то работоспособность алгоритма РКККФ в каждый мої/2 мент времени существенным образом зависит от свойств матрицы Rt ". Таким образом, легко видеть, что условия примера 2.5.3 являются тем единственным предельным случаем, когда алгоритм ЛФП-РКККФ и, соответственно, разработанный в диссертации его "скаляризованный" аналог ЛФП-ПРКККФ, не способны решить поставленную задачу. Действительно, в условиях примера 2.5.3 при /-)-0 матри- 1/2 о ца Rt является плохо обуставленной, что и сказывается на работоспособности методов. Таким образом, поведение алгоритмов ЛФП-РКККФ и ЛФП-ПРКККФ, проиллюстрированное с помощью рис. 2.4, закономерно и наглядно подтверждает свойства данных методов. Являясь одним из наиболее общих и часто используемых, метод максимума правдоподобия может быть применен к задаче оценивания неизвестных параметров линейных динамических систем. Со статистической точки зрения, оценка максимума правдоподобия обладает рядом полезных свойств, а именно: она является несмещенной, состоятельной и эффективной при N — со, где N — размер выборки (см., например, [4], [85]), что подчеркивает потенциал данного метода. Однако задача нахождения глобального максимума ЛФП сама по себе является достаточно сложной проблемой. Многие алгоритмы поиска экстремума функции, применяемые для ее решения, требуют вычисления градиента ЛФП. Таким образом, на практике приходится решать близкую, оказывающую огромное влияние на сам конечный результат задачу эффективного вычисления ГЛФП. Третья глава диссертационной работы, состоящая из шести параграфов, посвящена разработке новых алгоритмов для нахождения данной величины и исследованию их эффективности. Возникающая, в связи с необходимостью применения дискретного фильтра Калмана, проблема хорошо известна — его стандартная реализация является неустойчивой по отношению к ошибкам округления, что очевидным образом влечет за собой некорректное вычисление ЛФП и ее градиента. В сложившихся обстоятельствах остро встает задача разработки новых численно эффективных алгоритмов нахождения указанных выше величин. Последнее обуславливает практическую ценность и подчеркивает актуальность поставленной в диссертационной работе задачи. В связи со сказанным выше, коротко остановимся на истории развития теории калмановской фильтрации и ее современном состоянии. В начале 40-х годов двадцатого века, решая поставленную перед ним задачу разработки системы защиты от возникновения пожара на борту самолета, Norbert Wiener впервые применил теорию случайных процессов к проблемам управления и системам передачи данных [113]. Широко известное уравнение Винера-Хопфа (Wiener-Hopf equation [69]) позволяет получить импульсную переходную характеристику формирующего фильтра h(t,s) с целью нахождения линейной оптимальной в средне-квадратичном смысле оценки неизвестного вектора состояния x(t) динамической системы, подверженной влиянию шумов v(t), и имеющей следующий вид: В случае гауссовских величин линейная оценка x(t) совпадает с оптимальной в средне-квадратичном смысле. В уравнении (0.1), K(t,s) = E{x(t)x(s)T + x(t)v(s)T + v(t)x(s)T} — функция вектора состояния системы x(t) и вектора шумов v(t), Е{-} — операция математического ожидания. В I960 г. венгерский ученый Калман Р. впервые показал, что понятие наблюдаемости для динамических систем в теории оценивания имеет алгебраическую двойственность с понятием управляемости систем в теории управления. В том же году Richard S. Busy предположил, что уравнение Винера-Хопфа в случае конечномерных Работая совместно над данной проблемой, им удалось показать, что уравнение (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], [9% [110], [111], [112] и многие др.). Прекрасный обзор предложенных к 1971 г. различных типов фильтров, иллюстрация их работы при решении плохо обусловленных задач и сравнительный анализ их эффективности были даны Kaminski P.G. и соавт. в [73]. В связи с обозначенной выше целью диссертационной работы, остановимся более подробно на истории развития существующих в настоящее время различных типов реализаций фильтра Калмана, их сравнительном анализе и современном состоянии данного направления исследований. Дискретный фильтр Калмана описывается следующими уравнениями (см., например, [85])Расширенный квадратно-корневой ковариационный алгоритм
Модифицированные алгоритмы, построенные на основе РКККФ и РККИФ
Вычисление ЛФП на основе стандартного алгоритма Калмана .
Метод вычисления ГЛФП, построенный на основе РККИФ
Похожие диссертации на Методы вычисления логарифмической функции правдоподобия и ее градиента в алгоритмах калмановской фильтрации
