Математические модели и вычислительно-эффективные методы оптимизации информационно-измерительных комплексов динамических систем

I.

Теория фильтрации случайных сигналов возникла, как прикладная область математики, из потребностей практики — в первую очередь радиолокации. Фундаментом для построения этой теория, явились успехи в теории вероятностей и математической статистике [173, 181]. Впервые проблема фильтрации была сформулирована в работе Колмогорова [47] в 1941 году для случайных последовательностей. В 1949 году появилась работа Винера [211], в которой сформулирована проблема фильтрации случайных процессов и получены результаты, имеющие большое практическое значение. Настоящий прорыв в теории фильтрации произошел в 60-е годы. Толчком к этому были пионерские работы Калмана [193] и Калмана и Быоси [194]. Вплотную к «открытию» нового подхода подошел Бэттин [21, 179]. Толчком к развитию нового направления могла послужить теория условных марковских процессов Стратоновича [103, 104], предложенная им в статье 1960 года, однако эта работа осталась незамеченной, хотя в ней был изложен более общий подход. Справедливости ради, теорию фильтра Калмана (ФК) следовало бы называть теорией фильтрации Калмана-Стратоновича.

После работ Калмана и Калмана и Быоси произошел настоящий информационный взрыв в теории фильтрации. К настоящему времени опубликованы тысячи работ в этой области теоретического и прикладного характера. За последние десятилетия теория фильтрации Калмана получила дальнейшее развитие применительно к нелинейным динамическим системам, к системам с распределенными параметрами, к системам с неопределенными параметрами, к системам со случайными измерениями и др. Расширился также диапазон практических применений.

Эта теория породила новые области исследований, как, например, оптимизация информационно-измерительных комплексов (ИИК) динамических объектов, оптимальное управление наблюдениями в динамических системах, многие новые задачи построения оптимальных измерительных комплексов, предназначенных для оценивания состояний. Несмотря на огромное число публикаций в области теории фильтрации и ее приложений, до сих пор существуют и появляются новые задачи, актуальные в теоретическом и практическом отношениях, которые требуют своего решения.

Теория фильтрации с момента зарождения [47, 211] и до наших дней достигла значительных результатов [5, 6, 8, 18, 30, 32, 51, 77, 91, 108]. Эти результаты находят применение практически во всех областях техники, где * возникает потребность в управлении теми или иными объектами и процессами (авиация и космонавтика [17, 40, 60], навигация [25, 34, 52, 54, 59, 93, 94, 109, 113], технологические процессы [4, 18], связь [97, 99] и т. д.).

Традиционным в теории фильтрации является вопрос: как наилучшим образом (при заданных условиях) оценивать состояние динамической системы? С развитием теории фильтрации и с расширением ее приложений все больше внимания исследователи и инженеры-практики стали уделять нетрадиционным ранее проблемам, а именно: какие измерительные средства следует использовать, в какие моменты времени целесообразно проводить наблюдения, в каких пространственных точках нужно устанавливать датчики и т. д., чтобы добиться наивысшей эффективности системы управления или оценивания [27,29,31,46, 62, 111, 174, 176, 192].

Технические системы управления и обработки измерений постоянно развиваются, становятся сложнее. Все чаще применяются комплексы взаимосвязанных динамических систем. Математические модели таких объектов имеют сложную структуру и высокие размерности. И такие объекты уже ееt тественно относить к «большим системам» или даже к «большим сложным системам». Казалось бы, если «большая система» описывается стандартным образом в пространстве состояний, то решение многих задач оптимизации управления, наблюдения и оценивания для таких систем определяется стандартными известными методами. Однако па деле все оказывается пе так просто. При практическом применении этих методов часто начинает напоминать о себе «проклятие размерности». Оно проявляется в двух моментах. Во-первых, резко увеличиваются вычислительные затраты, во-вторых, вычислительные погрешности могут принять разрушительный характер.

В связи с этим актуальными являются вытекающие отсюда проблемы:

1) методы синтеза оптимальных (или субоптимальных) алгоритмов управления и оценивания, а также методы проектирования систем управления, наблюдения и оценивания для динамических объектов должны быть «быстрыми» до практически приемлемой степени (должны позволять проводить расчеты за приемлемое время);

2) сами алгоритмы управления и оценивания должны удовлетворять требованиям по быстродействию, которые определяются характеристиками применяемых вычислительных средств;

3) структура алгоритмов должна быть устойчивой к вычислительным погрешностям, и алгоритмы не должны включать в себя плохо обусловленные операции.

В данной работе мы основное внимание будем уделять разработке методов решения первых двух указанных проблем. Вопросы устойчивости к вычислительным погрешностям относятся к отдельной большой и важной проблемездесь мы их касаемся только вскользь.

Одним из путей понижения вычислительной сложности алгоритмов является учет специфики решаемых задач, учет структуры моделей рассматриваемых динамических объектов, учет формата данных, которые должны быть сформированы на выходе системы обработки информации и’т.д.

При решении задач оптимизации больших систем управления и оценивания «узким местом» является вычисление показателя качества функционирования системы. Однократный расчет такого показателя может занимать очень много времени, а при решении оптимизационных задач количество вычислений показателя качества может быть очень большим. При решении проблемы понижения вычислительной сложности оптимизационных алгоритмов важно продвинуться сразу по нескольким направлениям:

1) минимизировать вычислительную сложность процедуры расчета показателя качества (целевой функции);

2) при разработке метода оптимизации стремиться минимизировать число обращений к процедуре вычисления целевой функции;

3) предусмотреть возможность решения оптимизационной задачи с заданной абсолютной или относительной точностью, причем алгоритм при меньшей заданной точности должен работать существенно быстрее.

Исследованием проблемы понижения вычислительной сложности алгоритмов оценивания состояний динамических систем занимались миогие ученые [36, 90, 101]. В. С. Пугачев с сотрудниками разработал метод синтеза фильтров заданной структуры, в соответствии с которым уравнения фильтрации ищутся в приемлемом с точки зрения вычислительных затрат классе. Близко к этому подходу в идейном плане примыкают работы по синтезу субоптимальных фильтров пониженного порядка [35, 36, 76, 208].

В тех случаях, когда оценка вектора состояния нужна лишь в некоторых дискретных достаточно редких точках, понижения вычислительной сложности (количества вычислений на единицу времени работы фильтра) можно добиться без понижения размерности, а используя предварительную обработку наблюдений (в простейшем случае интегрирование или суммирование наблюдений па заданных отрезках) [64, 145, 203, 210].

Данная диссертационная работа посвящена разработке методов построения эффективных в вычислительном отношении (быстрых) алгоритмов фильтрации состояний сложных динамических систем. А' также вычислительно-эффективных методов оптимизации информационно-измерительных комплексов (ИИК) и информационно-управляющих комплексов (ИУК) I сложных динамических систем.

Работа выполнялась в соответствии с тематическими планами научно-исследовательских работ Томского государственного университета, Координационными планами АН СССР на 1976;1985 г. г. по проблемам 1.10.3 (тема 1.10.3.2.2), 1.10.4 (темы 1.10.4.2а, б) (М" гос. регистрации 77 019 134, 1 830 062 805), планами научно-исследовательских работ факультета информатики, экономики и математики филиала Кемеровского государственного университета в г. Анжеро-Судженске.

Целыо настоящей работы является построение вычислительно-эффективных (быстрых) методов обработки наблюдений в больших сложных динамических системах, в которых критичным является скорость расчетов в силу ограниченности ресурсов используемых вычислительных средства также построение вычислительно-эффективных (в смысле объема вычислительных затрат) методов оптимизации состава средств ИИК, оптимизации графика переключения измерительных приборов (управления наблюдениями) и оптимизации пространственного расположения измерительных датчиков и управляющих приводов в больших динамических СРП.

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

Научная новизна. Научная новизна состоит в том, что.

— разработаны новые подходы и методы синтеза быстродействующих алгоритмов обработки наблюдений в динамических системах и быстрого расчета характеристик точности оценок векторов состояния динамических объектов;

— разработан новый подход к построению математической модели задачи оптимизации состава измерительных средств ИИК, оптимизации графика переключений измерительных средств и оптимального пространственного расположения измерительных датчиков и управляющих приводов в динамических СРП;

— разработан новый метод решения указанных проблем, основанный на применении вычислительно-эффективных алгоритмов выпуклого дискретного программирования;

— выявлены новые свойства (закономерности) поведения ковариационных матриц ошибок оптимальных оценок.

Достоверность и обоснованность основных положений диссертационной работы подтверждается строгим математическим выводом полученных формул и уравнений и доказательством утверждений. Косвенным подтверждением достоверности служат результаты численных расчетов и моделирования на ЭВМ.

Практическая ценность. Применение полученных вычислительно-эффективных методов и алгоритмов фильтрации состояний динамических систем и методов оптимизации систем управления и обработки наблюдений для динамических объектов при разработке навигационных комплексов, комплексов траекторных измерений и других технических систем позволяет существенно понизить требования к ресурсам используемых вычислительных средств и ускорить процессы проектирования.

Внедрение результатов работы. Результаты работы реализованы в рамках НИР «Розыск-МВО», «Репортер-РВО», «Рулевой-РВО» (выполненных в Сибирском физико-техническом институте (СФТИ)) в виде математических моделей функционирования сложных навигационных систем с модульной структурой и резервированием, алгоритмов и программ комплексной обработки навигационной информации, исследования и оптимизации состава средств навигационных комплексов и использованы в в/ч 62 728 при исследовании перспективных технических систем навигации и при разработке технических заданий на НИР и ОКР по созданию таких систем, что позволило повысить обоснованность и оперативность принимаемых решений. Результаты работы реализованы также в рамках НИР «Руан-МСП», «Ригведа-МСП» (выполненных в СФТИ) в виде математических моделей функционирования перспективных навигационных систем и алгоритмов обработки навигационной информации и использованы в ЦНИИ «Электроприбор» (г. I.

Санкт-Петербург). Научно-технический эффект от внедрения результатов диссертации состоит в повышении обоснованности и оперативности принимаемых решений при разработке перспективных систем навигации.

Кроме того, материалы исследований использовались в учебном процессе при чтении курса лекций «Теория фильтрации» и при выполнении курсовых и дипломных работ студентов в Томском государственном университете, при чтении спецкурса «Оценивание состояний динамических систем» и при выполнении курсовых и дипломных работ студентов в филиале Кемеровского государственного университета в г. Анжеро-Судженске.

На защиту выносятся следующие положения.

1) Вывод уравнений фильтрации состояний: а) дискретных и непрерывных линейных динамических систем (ЛДС) в прореженном ряде точек со сжатием наблюдений, в которых процедура сжатия наблюдений полностью определяется характеристиками динамической системыб) совокупности дискретных ЛДС с использованием разработанной в диссертационной работе двухэтапной процедуры в случае наблюдения рассогласований компонент векторов состояния разных объектовв) дискретных ЛДС с измерительными комплексами, состоящими из нескольких модулей, в случае, когда оценки на выходе отдельных модулей доступны для обработки в каждый дискретный момент времени или в прореженные моменты времени.

2) Подход к выводу быстрых алгоритмов решения дифференциальных и дискретных матричных уравнений Риккати и полученные на основе этого подхода новые алгоритмы решения уравнений Риккати, отличающиеся повышенным быстродействием.

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

4) Алгоритмы решения задач выпуклого дискретного программирования с трудоемкими для вычисления целевыми функциями (ЦФ) для случаев: а) квазивыпуклой и выпуклой целевой функции (ЦФ) и линейных ограниченийб) линейной ЦФ и выпуклых функций в ограничениях.

5) Подход к построению математических моделей задач оптимизации состава измерительных средств ИИК динамических объектов, задач оптимального переключения измерений в ЛДС и оптимальной локализации измерительных датчиков и управляющих приводов в СРП. А также метод решения этих задач на основе применения разработанных в диссертационной работе алгоритмов выпуклого дискретного программирования.

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на 49 Международных, Всесоюзных, Всероссийских, Республиканских и региональных научных форумах, в том числе: IV Всесоюзная конференция по проблемам теоретической кибернетики (Новосибирск, 1977) — VIII Всесоюзное совещание по проблемам управления (Таллин, 1980) — V Всесоюзное совещание по статистическим методам в процессах управления (Алма-Ата, 1981) — VII научная конференция ЗападноСибирского региона по математике и механике (Томск, 1981) — Всесоюзная конференция «Измерения и контроль при автоматизации производственных процессов» (Барнаул, 1982) — II Всесоюзное совещание-семинар «Методы синтеза и планирования развития структур крупномасштабных систем» (Саратов, 1986) — Всесоюзная НТК «Микропроцессорные системы автоматизации технологических процессов» (Новосибирск, 1987) — XV и XVII МНТК памяти Н. Н. Острякова (Ленинград, 1987; 1990) — III Всесоюзная конференция «Перспективные методы планирования и анализа экспериментов при исследовании случайных полей и процессов» (Гродно, 1988) — IFAC/IMACS Workshop «Computer-aided control systems design» (Alma-Ata, 1989) — VI Всесоюзное совещание «Управление многосвязными системами» (Суздаль, 1990) — II Всесоюзная НТК «Микропроцессорные системы автоматики» (Новосибирск, 1990) — Республиканская научная конференция «Математическое и программное обеспечение анализа данных» (Минск, 1990) — III Всесоюзный семинар по обнаружению изменений свойств случайных процессов (Воронеж, 1990) — Всесоюзная НТК «Идентификация, измерение характеристик и имитация случайных сигналов» (Новосибирск, 1991) — International Workshop «Control System Synthesis: Theory and Application» (Novosibirsk, 1991) — IMACS/IFAC International Workshop «Methods and Software for Automatic Control Systems» (Irkutsk, 1991) — I Всесибирская конференция по математическим проблемам экологии (Новосибирск, 1992) — X Белорусская зимняя школа-семинар по теории массового обслуживания (Минск, 1994) — The International Conference «Computer Data Analysis and Modelling» (Minsk, 1995) — III Международная НТК «Микропроцессорные системы автоматики» (Новосибирск, 1996) — Международная конференция «Всесибирские чтения по математике и механике» (Томск, 1997) — Сибирская научно-практическая конференция «Наука, образование, производство: Интеграция и новые технологии» (Анжеро-Судженск, 1997) — Научно-практическая конференция «Наука и образование: Пути интеграции» (Анжеро-Судженск, 1998) — III Сибирский конгресс по индустриальной и прикладной математике (Новосибирск, 1998) — Научно-методическая конференция «Качество образования и наука» (Анжеро-Судженск, 1999) — IV Сибирский конгресс по прикладной и индустриальной математике (Новосибирск, 2000) — Межрегиональная научно-методическая конференция «Повышение эффективности научных исследований и совершенствование учебного процесса» (Анжеро-Судженск, 2000) — Всероссийская научно-практическая конференция «Новые технологии и комплексные решения: наука, образование, производство» (Анжеро-Судженск, 2001) — Всероссийская научная конференция с международным участием «Новые информационные технологии в исследовании сложных систем» (Томск, 2002) — Всероссийская научно-практическая конференция «Информационные технологии и математическое моделирование» (Анжеро-Судженск, 2002).

Краткое содержание работы.

В главе 1 приводится вывод уравнений фильтрации вектора состояния дискретной ЛДС х (к +1) = А (к)х (к) + w{k) ' (1) в заданных точках ty t2,. ~tk > 1, tk eN, & = 1, 2,.). В уравнениях фильтрации вектор наблюдений z (k) = H (k)x (k) + v (k) ' (2) па отрезке между двумя соседними точками преобразуется («сжимается)» в два вспомогательных вектора % и к:

А+1) = - p ((M)Lk (ft+1)]ф (w*) + к* ('**)" = (3).

Для вычисления ковариационной матрицы ошибки фильтрации P (t), P{t2),. получаются рекуррентные уравнения:

P (tk*) = Г (/А+|)[/ + Lk (tk+l)Г (/,+1)]-Р (0) = Р0, (4).

Г ('*+1) = Л) Р"к + «ы)•.

Коэффициенты рекуррентных уравнений L, Ф, U зависят только от параметров динамической системы A, Q, Н, R (Q и R — ковариационные матрицы гауссовских белых шумов w и v) и не зависят от Р0, поэтому их можно рассчитать заранее и хранить в памяти используемой ЭВМ. В линейных рекуррентных уравнениях «сжатия наблюдений» коэффициенты не зависят от Р, поэтому уравнение для ковариационной матрицы ошибки фильтрации и уравнения «сжатия» наблюдений можно решать независимо.

Получен аналогичный алгоритм для непрерывной линейной динамической системы, в котором уравнения для расчета ковариационной матрицы ошибки фильтрации Р и оценок фильтрации в точках t, t2,. > О, е R, Л: = 1, 2,.) совпадают с уравнениями для дискретной системы, а матрицы L, Ф, U являются решениями системы матричных дифференциальных уравнений (ДУ), уравнения сжатия наблюдений являются линейными стохастическими ДУ.

С использованием уравнений фильтрации для дискретного и непрерывного случаев построен алгоритм фильтрации вектора состояния непрерывной ЛДС с непрерывными и дискретными наблюдениями в заданных точках t, t2,. Дискретные наблюдения могут находиться между заданными точками или совпадать с ними.

С учетом структуры полученных алгоритмов разработан подход к построению приближенных алгоритмов фильтрации в заданных точках, в которых наблюдения «сжимаются» в ряд вспомогательных векторов с помощью интеграторов кратности 1,2,.

Глава 2 посвящена решению задачи фильтрации состояний дискретной ЛДС специального вида. Специфика задачи состоит в том, что система включает в себя несколько однотипных динамических объектов, на каждом из которых имеется свой набор измерительных приборовкроме того, для каждой пары объектов наблюдаются рассогласования (разности) части (или всех) компонент векторов состояния отдельных объектов.

Для решения задачи предлагается двухэтапная процедура: на I этапе проводится обработка рассогласований, на II этапе показания совокупности всех приборов используются для оптимальной коррекции полученных оценок. Сформулировано достаточное условие оптимальности в среднеквадра-тическом смысле такой процедуры.

Приводится вывод общих уравнений фильтрации двухэтапной процедуры. Оценки фильтрации на I этапе компонент х' вектора состояния s' (i =, N), рассогласования которых наблюдаются, имеют очень простой вид-арифметического среднего рассогласований всех пар объектов, включающих 1-й объект. Для компонент векторов состояния объектов у', рассогласования которых не наблюдаются, получены рекуррентные уравнения фильтрации (N уравнений, каждый размерности nj = п — щ, где п, щ, п2 — размерности У, х' и У соответственно): у'{к) = А*уу{к-)ук-) +АуКк-)хк-) + А*уу{к-)Кц{к-) Ш).

— Лху (к-)ук-)] + 1/п (Ы)Дч+(*-1)СШ у (0)= у'0, (5) где ^к) = хк)-Ахх{к-)?{к-), y’j — разность (рассогласование) между х и У. Для вычисления А* {к), Кц{к.

Un{k), Яц (к) приведены формулы.

В случае, когда возмущающие воздействия в стохастических разностных уравнениях для компонент х' не коррелированы с возмущающими воздействиями в уравнениях для компонент у', в уравнениях фильтрации исчезает слагаемое, содержащее Un.

Выведены уравнения фильтрации измерений на II этапе: f (k) =A (k-l)Hk-1) + Жоо (*) ZHJT (k)MJi (k) + i=1 У=1 1Г0j{k)HjyT{k)Mjk) z’M (k)9 т = 0- И gl (k) =Ag{k-)gl{k-) + ?[Г10(к)^Н]Г{к)М^к) + i j=i ^{к)н1т{к)Мк)]Гм{к)у g'(0)=0, (6).

У=1 где, А — матрица динамики отдельно взятого объекта, И с индексами — матрицы измерений, невязки измерений z’M получаются из измерений z' и оценок фильтрации на I этапе. Для вычисления матриц Ag и MJ> (блоков матрицы М) приведены формулы. Для ковариационных матриц ошибок одношагового предсказания получены рекуррентные уравнения. Размерность уравнений фильтрации равна (и + N-n2), что в (N-n)f (n + N-n2) раз меньше, чем в ФК с псевдообращением для расширенной системы.

Итоговые оценки фильтрации в двухэтапной процедуре формируются, А. «V «о» .

— у'. + У.

У.

В случае, когда наблюдаются рассогласования всех компонент векторов состояния объектов, уравнения фильтрации (размерности п) II этапа принимают очень простой вид:

Нк) =А (к-)Нк~ 1) + £г00(*) iHJT (k)MJi (k)zUk), (7).

I /=1 где z, M{k)^zlM (k)-Hf{k)A{k-)Hk-);

Тт{к) = А{к-)Рт{к-)Ат{к-)+ Q{k-1);

Роо (к) = Г00(/с) — Г00(£) X X Я''Г (/с)Я j (к) Г00(к).

1У=1.

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

Уравнения фильтрации конкретизированы для случаев нескольких упрощающих предположений: 1) измерения не содержат компоненты У- 2) составы измерительных приборов всех объектов идентичны- 3) хотя бы часть измерений не содержит компонент у. Получающиеся при этом уравнения имеют более простой вид. Для часто встречающегося на практике случая 1) оценка фильтрации двухэтапной процедуры является оптимальной. Сами уравнения (размерности п) имеют-очень простую структуру: к) =A (kA)$(k-)+rUk)tl, Hjr (k)MJk)rM (k), f (0) = 0- и y=i gl (к) = 0- g*(0)= 0 (/=VV) — Гоо (*) = А{к-)Роо (к-1)Ат (к-1) + Q (k.

Poo (k)^r00(k)-r00(k)ZZHir (k)MiJ (k)HJk)r00(ky, Роо (0) = Р0. (8).

Для ковариационных матриц ошибок оценок g1 и для взаимных ковариационных матриц ошибок оценок s и g1 получены рекуррентные уравнения.

В случае 2) уравнения фильтрации в вычислительном отношении являются намного более простыми, чем для общего случая.

Двухэтапная процедура фильтрации применена для получения уравнений фильтрации в задаче оптимального оценивания вектора состояния динамической системы по данным многоканального измерительного комплекса с «цветными» шумами измерений.

Проведено моделирование двухэтапной процедуры фильтрации применительно к решению задачи навигации двух морских объектов (судов) в ситуации, когда объекты могут обмениваться измерительной информацией и, кроме того, наблюдаются рассогласования части компонент векторов состояния объектов. Результаты моделирования подтверждают работоспособность полученных алгоритмов и эффективность их применения для решения задач морской навигации.

Глава 3 посвящена исследованию проблемы фильтрации состояний дискретной ЛДС с измерительным комплексом модульной структуры. Модули представляют собой устройства, включающие в себя несколько измерительных приборов, показания которых обрабатываются оптимальным образом (в среднеквадратическом смысле). На выходе модулей формируются оптимальные оценки фильтрации. В измерительный комплекс входит несколько модулей, и для дальнейшей обработки доступны только частные оценки на выходе модулей.

В разделе 3.2.1 приведен вывод уравнений для оценки фильтрации выходов модулей в общем случае. Показано, что оптимальные оценки можно получить путем обработки наблюдений, формируемых из частных оценок:

Q (k) = /Г1 (*){*/(*) -UК,(к)Н,(к)]А (к — 1)*,(* - 1)}. (9).

Уравнения фильтрации имеют вид: х (к) = А (к)х (к -1) + К{к)[^{к) — Н (к)А (к -1)х (к — 1)], *(0) = О, К (к) s Г (к)Нг{к)[н (к)Г (к)Лг (к) + Я (/с)] Г (£) = А{к -1)Р (к -1)Ат{к -1) + Q (k -1),.

Р{к) = [/ - К{к)Н (к)] Г (к). (10).

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

В разделе 3.2.2 приведен вывод уравнений фильтрации для специального случая матриц измерений Я, полного ранга горизонтальной ориентации: х (/с) =.

N N.

A{k —)x (k — 1) + P{k)t.

1=1/=1 (*)]" ' ///(ВД-1 (Л): с) ЗД' iL/=i х — - Р1(к)Н{т (к)Ки-к)Н^к)л (к — 1)*,(* -1)}, х (0) = 0. (11) В случае наблюдений с независимыми ошибками в разных модулях уравнения упрощаются. Если при этом модули идентичны, уравнения имеют вид х (к) = [l-N P (k)J] {к)]А (к -1)х{к — 1) + N где Р{к)Тх (к)ХР{~](к){х-(к)-[/-/}{k)Jx (к)]А (к -)х,{к -1)}, /=1.

12).

Т (к) S Нхт (/с)[я, {k)Hl (к)] Н{(к). В разделе 3.3.2 приведен вывод уравнений фильтрации для случая коррелированных шумов измерений и возмущающих воздействий: х (к) = А (к -1)х{к -1) + К{к)[^(к) — Н (к)А (к -1)х (к -1)], Jc (0) = 0, К{к) = [г (к)Нт (к) + S (k)[H (k)r (k)Hr (k) + R (k) + H (k)S (k) + ST {k)HT{к)], Г (£) ~А{к-1)Р{к -)Ат (к -1) + Q (k — 1),.

Р (^) = Ц/:)-од[г (/:)Яг^) + эд]Г, Р (0) = Р0, (13) где компоненты вектора С, выражаются через частные оценки следующим образом: Ъ (к) = Xj (k) — [/ - ?,-(?)#Д?)]Л (/с — 1) хД 1с -1). • (14) В разделе 3.3.3 приведен вывод уравнений фильтрации для специального случая матриц С,{к) = /Г,. (?) + [/-/Г,-(?)#,.(А)]?/,•(?) полного ранга вертикальной ориентации: х (к) = х (к) + P (k)jr? tf, r — Яj (к)х (к)]- х (0) = 0, i >i i. х.

N N где ад = Ф (к — 1) х (к -1) + 2 (к) у j (/с),.

1=1 >1.

У J (*) * [с/ (k)Cj (к)У с/ (k)[xj (к) — Bj (k)xj (к -1)],.

15) (16).

Р{к) = Г {к).

N N ы]=.

Г (к) = Ф (к -1)Р{к — 1) Ф{к -1) + 0(к -1),.

— 1.

Ф (к -1) = -)Л (к -1),.

Ч'(к-1) = /-? jtSi&Wy (k)Hj (/с), 1=1 y=i е (Л: -1) = V (к -1)Q (k — Щт (к -1) — ХЕЗДХБ^ (*) V k) Mj,{k)SjT (к). (17).

1 у=1 <7=1/=1.

В разделе 3.4.3 получены уравнения фильтрации вектора состояния дискретной ЛДС с прореженными выходами модулей: х (кТ) = А*(кТ, кТ — Т) х (кГТ) + К (кТ)[^кТ) — Н{кТ)АкТ, кТ — Т) х (кТ — Т), jc (0) = О,.

К (кТ) = [г (кТ)Нт (кТ) + S (kT)[R (kT) +Н (кТ)Г (/сТ)Нг (кТ) + H{kT)S (kT) + ST (кТ)Нг (кТ)}, Г (кТ) = АкТ, кТ — Т) Р{кТ — Т) А*г (кТ, кТ-Т) + QkT — Т),.

Р (кТ) = Г (кТ) — К (кТ)[г (кТ)Нт (кТ) + S (kT)J, Р (0) = Р0. (18).

Здесь Р{кТ) — ковариационная матрица ошибки оптимальной комплексной оценки х (кТ) вектора состояния д: на основе выходов модулей х^, х2,., xN, которые входят в ?- Те N характеризует степень прореженности.

В разделе 3.4.4 получены уравнения для специального случая матриц.

Сj СкТ) ^ Кj (кТ) + [/ - Кj СкТ) Н * {kT)uj (кТ) (19) полного ранга вертикальной ориентации: х (кТ) = х (кТ) + Р (кТ)? (кТ)Ц-{кТ) х ы> 1 х^ГЬЯ'^ВДДТ)], х (0) = 0, х{кТ) = Ф (/сГ — Т) х{кТ — Т) +? ? 5— (АГ)Л/" (/сГ) ^ (*Г), му=1.

ДО) = Г (кТ)[1 + ?ХЯ^аГ^^^Я^/гПП^Г)]" 1, ДО) = Р0, 1=1 м.

Г (кТ) = Ф (кТТ)Р (кТ — Т) Фт (кТТ) + Q (kT — Т), (20) ъ | где ^ (кТ) = [с/(*Г)С, (AT)]" ' СjT (kT)[xj (кТ) — В, (W — 71)], (21) С' (кТ) 3 К, (AT) + [/ - К,-(?Г)Я/(?Г)][/, (AT), Б, (/сГ) s [/ - Kj (кТ)Н/ {кТ)ь{кТ — Т),.

К J СkT) s Pj (kT)H/r (kT)[Rj/(kT)Y'.

U J (кт) г 5/(*Г)[я/(*Г)5/(*Г) + Л/С/сГ)]" 1, Ф (кТТ) = х?(кТ — Т) А*(кТ — Т),.

— Г) = 1 — 2 Y^S*{кТ)Мij СкТ) Н/(кТ), i=lj= кТТ) = ЧкТ — T) QkT — туут{кт — Т) —? х /=1 х YLMiq (kT)Rql (кТ)М, (kT)Sj Т{кТ). (22).

H/=i.

Здесь Pj — ковариационная матрица ошибки оптимальной фильтрации вектора состояния в ум модуле, Р — ковариационная матрица ошибки фильтрации состояний после того, как осуществлена оптимальная в среднеквадратиче-ском смысле обработки выходов всех модулей.

В полученных уравнениях отсутствует операция псевдообращения матриц высокого порядка, поэтому с вычислительной точки зрения (понижения вычислительных затрат и уменьшения погрешности вычислений) они предпочтительнее уравнений для общего случая.

В разделе 3.5 получены уравнения фильтрации вектора состояния дискретной ЛДС с частично модульной структурой измерительного комплекса, когда кроме модулей имеются измерительные приборы, выходные сигналы которых должны обрабатываться наряду с выходами модулей.

В разделе 3.6 показано, как полученные уравнения фильтрации выходов модулей применяются для решения задачи оптимальной фильтрации состояний N динамических систем (объектов) на основе частных оценок векторов состояний отдельных динамических систем и наблюдений рассогласований компонент векторов состояния объектов.

В разделе 3.6.4 приведены результаты моделирования процесса комплексной обработки выходов двух навигационных комплексов (ЫК) в задаче морской навигации. Каждый НК рассматривается как отдельный измерительный модуль. Результаты моделирования подтверждают работоспособность I алгоритмов обработки информации в модульных измерительных комплексах и показывают возможность эффективного их применения в технических системах, в том числе в навигационных приложениях.

В главе 4 излагается единый подход к выводу быстрых алгоритмов решения матричных дифференциальных и дискретных уравнений Риккати. На основе этого подхода получепы уравнения 4 групп алгоритмов. Исходной базой для их вывода являются уравнения для расчета ковариационной матрицы ошибки фильтрации состояний непрерывных и дискретных ЛДС в заданных точках t, t2, приведенные в главе 1.

Получены алгоритмы расчета решения ДУ Риккати.

Р = АР + РАТ — РМР + Q, Р{0) = Р0 (23) в последовательных точках Д, 2Д, ЗД, ., а также в точках с удвоением шага 2Д, 2 А, 2 А,. Ниже сформулированы 4 группы алгоритмов с удвоением шага для случая постоянных или периодических (с периодом Д) матриц А, М, Q.

Алгоритм 4.2.3. Решение матричного ДУ Риккати (23) в моменты времени 2А, 22Д, 23 А,. получается по следующей быстрой рекуррентной схеме с удвоениемшага:

Р (2к+] А) = {ц 2 м А) + W (2k+l Д)[ро + 0(2м Д)]" ' Ч’г (2*+1 Д)}" ', (24) где L (2k+l A) = L (2kA) + Ч'(2* Д)[/ + L (2k Д)0(2* А)]" ' Ц 2кА) Ч, г (2к А), 0(2*+l А) = 0(2* А) + Ч^ (2* Д)0(2к Д)[/ + Ц2к А))0(2к А)]" ' Ч'(2к А),.

Ч/(2к+1 А) = Ш{2к Д)[/ + Ц2к Д)0(2* Д)]~' Ч,(2к А), {к = 0,1, (25) Начальные условия ЦД), Ф (А) и 0(A) являются решениями в момент времени, А соответствующих матричных ДУ. Матрица Р{Д) получается по формуле.

24), если в ней положить (&+1) = 0.

Алгоритм 4.2.4. Решение матричного ДУ Риккати (23) в моменты 2А,.

22Д, 23Д,. находится по рекуррентной схеме с удвоением шага:

Р (2м А) = {l (2* А) + Ч*(2к Д)[р (2к А) + 0(2* A)]-' (2к А)[', (26) где к= 0, 1, .- L{2кА), VF (2*A), 0(2* А) рассчитываются по рекуррентным соотношениям (24)-(25). Матрицы Р (А), ЦА), Ф (Д) и 0(A) определяется как в алгоритме 4.2.3.

Алгоритм 4.2.3(LV Ковариационная матрица ошибки фильтрации P (t), удовлетворяющая матричному ДУ Риккати (23), в моменты времени 2 ^.

2А, 2 А, 2 А,. (при t0 = 0) определяется по следующей быстрой формуле с удвоением шага:

Р{2*+1 А) = Z (2*+1 А) + А)[/ + Р0 0(2*+l Д)]~' />0ФГ (2м А) (27) где L{2k+X А) = L (2* А) + Ф (2* А)[/ + L (2* Д)0(2* A)]" ' L (2* Д) ФГ (2к А), 0(2*+1 А) = 0(2* А) + (2* Д)0(2* Д)[/ + L (2k Д)0(2* А)]" ' Ф (2* А), Ч'(2*+|А) = Ф (2*А)[/ + L (2kД)0(2*А)]" 1 Ф (2*A), (& = 0, 1,.), (28) Матрица Р{А) находится как в алгоритме 4.2.3 или любым другим способом. Начальные условия Z,(A), 0(A) и *Р (Д) являются решениями соответствующих матричных дифференциальных уравнений.

Алгоритм 4.2.4(b). Ковариационная матрица ошибки фильтрации P (t), удовлетворяющая матричному ДУ Риккати (23), в моменты времени 2 ^.

2А, 2 А, 2 А,. (при t0 = 0) определяется по следующей быстрой рекуррентной формуле с удвоением шага:

Р (2*+| А) = L (2k А) + Ч'(2* А)[/ + Р (2к Д)0(2* А)]" 1 Р (2к А) ФГ (2к А), (29) = 0,1,.

Алгоритм 4.2.3(D). Ковариационная матрица ошибки фильтрации P{t), удовлетворяющая матричному ДУ Риккати (23), в моменты времени.

А, 2А, 2 А,. (при to — 0) определяется по следующей быстрой. формуле с удвоением шага:

Р (2кА) = [и (2кА)Р0 +Л12(2*Д)][Л21(2*А)/>0 + Л22(2* А)]Л (30) где к = 1, 2,.- А,-, — (г, j = 1, 2) — блоки матрицы.

Л (2* А) = Л (2*-1 Д) Л (2*-1 А). (31).

А (А) является решением соответствующего матричного линейного ДУ.

Алгоритм 4.2.4(D). Ковариационная матрица ошибки фильтрации P (t), удовлетворяющая матричному ДУ Риккати (23), в моменты времени.

Л 1.

2А, 2 Д, 2 А,. (при to = 0) определяется по быстрой рекуррентной формуле с удвоением шага:

Р (2к+] А) = [А, (2к А) Р{2к А) + Л|2 (2* Д)]х.

X [л21 (2* Д) Р (2* А) + Л22(2* А)]-', (32) где к — 1,2, А, у (/, у = 1, 2) вычисляются как в алгоритме 4.2.3(D). Матрица Р (Д) может быть рассчитана любым способом.

Алгоритм 4.2.3(Y). Ковариационная матрица ошибки фильтрации P (t), удовлетворяющая матричному ДУ Риккати (23), в моменты времени.

2 3.

Д, 2Д, 2 Д, 2 Д,. определяется по быстрой формуле с удвоением шага:

Р{2* Д) = D (2k А) -Ст (2к Д)[я (2к А) + /^J" 1 С (2к Д), (к = 0, 1,.), (33) где матрицы С, В, D находятся из уравнений.

С (2*+1 А) = С (2к A)[D (2к Д) + В{2к А)]" ' С (2* А),.

В (2к+] А) = С (2* А) — С (2к A)[D (2к Д) + В{2к Д)]~' Сг (2к А), 2Л+| Д) = D (2А Д) — Сг {2к A)[D (2к А) + В (2к Д)]~' С (2к Д). (34).

• I.

Начальные условия С (Д), В (Д), D (A) являются решениями соответствующих дифференциальных уравнений.

Алгоритм 4.2.4(Y). Ковариационная матрица ошибки фильтрации P (t), удовлетворяющая матричному ДУ Риккати (23), в моменты времени л ->

2Д, 2 Д, 2 А,. определяется по рекуррентной формуле с удвоением шага:

Р{2м А) = D (2k А) — Ст{2к A)[z?(2* Д) + Р (2к А)]" ' С (2к А), (35) к = 0, 1,.

Алгоритмы нахождения решения уравнений Риккати в последовательных точках А, 2Д,. можно получить из алгоритмов с удвоением шага, если в них заменить Р{ 2*+|Д) на Р[(Ж)Д], Р{2кА) — на Р{кА), а в коэффициентах 2кА заменить на Д.

Для решения дискретного матричного уравнения получаются в точности такие же алгоритмы. В них Д имеет смысл натурального числа, большего 1, и вместо нее используется буква N. Отличие состоит лишь в том, что расчет начальных условий для коэффициентов осуществляется, но соответствующим рекуррентным уравнениям.

Установлена связь между коэффициентами разных групп алгоритмов. Полученные формулы позволяют переходить при проведении расчетов от одного алгоритма к другому.

Проведено сравнение быстрых алгоритмов по затратам. Установлено, что быстрые алгоритмы 4 группы (Y) обеспечивают вычислительный выигрыш по сравнению с другими алгоритмами до 2 раз.

Алгоритмы обобщены на случай ДУ Риккати с разрывными решениями (разрывы I рода) в точках т, 2 т,. В интерпретации статистической теории оценивания это соответствует случаю проведения и обработки дискретных наблюдений в этих точках.

Проведено численное исследование полученных алгоритмоврезультаты подтверждают работоспособность алгоритмов и их вычислительную эффективность.

В главе 5 исследуются свойства ковариационной матрицы ошибки фильтрации случайного процесса и случайной последовательности в зависимости от ковариационной матрицы ошибки измерения, а в случае, когда процесс или последовательность является вектором состояния стохастической ЛДС (непрерывной или дискретной), также в зависимости от ковариационной матрицы начального состояния и ковариационной матрицы возмущающих воздействия на входе системы.

В разделе 5.2 исследуются свойства ковариационной матрицы ошибки оценивания в задаче винеровской фильтрации. При этом предполагается, что корреляционная матрица шума измерения имеет вид.

Rvv{t, 0=R{t)b (t-n, где матрица R (t) является дважды непрерывно дифференцируемой функцией от некоторой векторной переменной Ь.

Доказаны следующие утверждения.

Теорема 5.2.1. Если 5ВД > О V те[Г0, /], то V / > t0 ЬР{Т, Т) > 0.

Теорема 5.2.2. Если 52Я (т) < 0 V те[/0, /], то V / > /() 52Р{Т, Т) < 0.

Теорема 5.2.3. Если 52/Г'(т)<0 Vie[/0, /], то Ъ2Р (Т, Т)>0 VT>t0.

В разделе 5.3 проводится исследование свойств ковариационной матрицы ошибки оценивания в задаче оптимальной линейной фильтрации случайных последовательностей (фильтр Колмогорова). Предполагается, что ошибка измерений есть гауссовский дискретный белый шум с ковариационной матрицей R. Доказаны следующие утверждения.

Теорема 5.3.4. Если 5У?(т) > О V т = 1,/, то 5Р (Т, Г) > О V / >/0. Теорема 5.3.5. Если 52Л (т) < О V т = 17, то 5 2Р (Т, Т) < О W > /0. Теорема 5.3.6. Если 82R4(t) < 0 Vt= li, то Ъ2Р{Т, Г)>0 УГ>/0.

В разделе 5.4 исследуются свойства ковариационной матрицы ошибки фильтрации векторного поля. Случайное поле s (t, со) имеет нулевое математическое ожидание и корреляционную функцию (матрицу).

Rss (t, соt ю1) = ?{*(/, co) s7'(/ со')} (36).

Наблюдается векторное случайное поле z{т, со) = Н (т, co) j (t, со) + v (t, со) (/0 < т < со е W с Q), (37) где z — ш-вектор-столбец измерений, Нтхп-матрица измерений, v — случайная ошибка измерений с нулевым математическим ожиданием и корреляционной матрицей ^(z, со-со') = ?{v (/, co) vr (/', со')}, (38) Показано, что в случае, когда.

•) = Л (/, ю)5(/ - /')§((c) — со'), (39) где 5(со-ш,) = б (со1-со,')5(со2-со2') ••• §(сог-сог'), (40) ковариационная матрица ошибки фильтрации имеет следующие свойства.

Теорема 5.4.1 .Если bR (x, u)>0 V xe[t0,t] и ueW, то 5/>(7со-7со)> 0 V / >/0 и cogQ.

Теорема 5.4.2. Если 52Л (т, и)< 0 V те[/0,/] и и elf, то 52Р (Г, со-7"<0 V/>^0 и cogQ.

Теорема 5.4.3. Если 62/Г'(т, м) < 0 V те[/0, t] п и е1¥-, то.

52Р (7>-7">0 V/>/0 и coeQ.

В случае, когда Луу (Г, со-/', со') = Я (Г, со, оУ)5(/-/'), доказаны утверждения: Теорема 5.4.4. Если вариация 5Я (т, и, м') такова, что.

WW.

Vtg[/0,/] и любых вещественных матричных функций С (и, и') размеров их т, определенных на множестве WxW, то.

5Р (Г, со-Г, со)>0 VT>/0 и cog П.

Теорема 5.3.5. Если вариация S2R (t, u, u') такова, что J C (u, u')b2R (i, u, u')CT{u, u*)diidu'< О.

WW.

Vie[/0,t и любых вещественных матричных функций С (и, и') размеров п х т, определенных на множестве W х W, то.

52Р (Г, со-Г, со)<0 Vr>/0 и coeQ.

Теорема 5.4.6. Если вариация такова, что.

J C (ii, u%)b2R-i, u, u*)CT{u, ul) dudiC<0.

WW.

V т g [7о, t] и любых вещественных матричных функций С (м, м') размеров пхт, определенных на множестве JVxfV, то.

52Р (Г, со-Г, со) > 0 Vr>/0 и соеП.

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

В разделе 5.5 исследуются свойства ковариационной матрицы ошибки фильтрации в ФК, которая удовлетворяет уравнению Риккати.

P (t) = A{t)P{t) + P{t)T A (t) + ДО — P (t)M (t)P (t), P (tQ) = PQ, (41) где L (t)^G (t)Q (t)GT (t), (42).

M{t) = HT{t)R~t)H{t). (43) <

Теорема 5.5.1. Если вариации 5J0, bQ~](x), 57Г'(т) (/0<т<0 являются неположительно (неотрицательно) определенными матрицами, то &-/(/)<О (5У (/)>0) V/>/0.

Теорема 5.5.2. Если вариации 5J0, 6? Г'(т:), 87?,(т) (/0<т</) являются неположительно (неотрицательно) определенными матрицами, то bP (t)>0 (bP (t) < 0) V t>tQ.

Теорема 5.5.3. Если вариации 8Р0, bQ (j), bR (x) (t0<0 (3P (t)>0) V t>t0.

Теорема 5.5.4. Если вариации ЬР0, bQ (x), bR (z) (/0 < т < t) являются неположительно (неотрицательно) определенными матрицами, то 5.7(0 > 0 < 0) t>t0.

Теорема 5.5.5. Если вторые вариации 52J0, 82Q 1(т), 52R '(т) (/0 <т </) являются неположительно определенными матрицами, то.

82J (t) < 0, 82P{t)>0 V / > /0.

Теорема 5.5.6. Если вторые вариации 82Р0, 82Q (t), 82R (x) (t0 < т < t) являются неположительно определенными матрицами, то 52Р (0<0, 82J (t)>0 Vt>t0.

В разделе 5.5.2 исследуются свойства решений дискретных матричных уравнений Риккати теории фильтрации.

P (i) = Г (0 — r (i)HT (i)[H (i)r (i)HT (i) + Л (/)ГЯ (/)Г (0, Р (0) = Р0, (44) Y{i +) = A (i)P (i)AT (i)G (i)Q (i)GT {i), Теорема 5.5.8. Если вариации 8Р0, 8Q (i), 8R (i + 1) (/ = 0, 1,., ?-1) являются неположительно (неотрицательно) определенными матрицами, то 8Р (к)<0 (8Р (к)>0) V к> 0.

Теорема 5.5.9. Если вариации 8Р0, 8Q (i), 8R{i + 1) (/ = 0,1,к — 1) являются неположительно (неотрицательно) определенными матрицами, то 5/(/с)>0 (8J (k)<0) Vk>0.

Теорема 5.4.10. Если вариации б/ц-1 = 8J0,8Q~i), 8R~i + l) (/ = 0,1,., к — 1) являются неположительно (неотрицательно) определенными матрицами, то 8J {к) < 0 (6J {к) > 0), а ЪР{к) > 0 (5 Р (к) < 0) V к > 0.

Теорема 5.5.11. Если вторые вариации 8 Р0, 8 Q (i), 8 R (i +) (i = 0,1,., /с -1) являются неположительно определенными матрицами, то.

8 2Р (к) < 0, а 52 J {к) > 0 V к > 0.

Теорема 5.5.12. Если вторые вариации 52J0, 82Q~i), 82R~i +) (/ = 0,1,., к- 1) являются неположительно определенными матрицами, то.

82J{k) < 0, а Ъ2Р{к) > 0 V к > 0.

В разделе 5.5.3 установлены свойства ковариационной матрицы ошибки фильтрации в случае непрерывных и дискретных динамических систем с корректирующими измерениями.

В разделе 5.5.4 исследуются вариационные свойства спектральных характеристик ковариационной матрицы ошибки фильтрации. Доказаны утверждения:

Теорема 5.5.17. Если вариации 5Р0,5?(т), 5Л (т) (/0<т</) являются неположительно (неотрицательно) определенными матрицами, то 5^[Р (0]<0 (5^[Р (Г)]>0) Vf>f0, i = l, 2.и.

Теорема 5.5.18, Если вариации 5У0, 5<2~'(т), б/?-1 (т) (/0<т</) являются неположительно (неотрицательно) определенными матрицами, то 5^. J (0]<0 (5^. J (0]>0) У t>tQ, / = 1,2,., я.

Теорема 5.5.19. Если вторые вариации 52J0,52gI (x), 52jR" «'(t) (t0 <т<t) являются неположительно определенными матрицами, то.

5%nill[j (0]<0,a52^max[P (0]^0 Vt>t0.

Теорема 5.5.20. Если вторые вариации д2Р0, S2Q (x), д2Я (х) {tQ < т < t) являются неположительно определенными матрицами, то 52A, min[P (/)]< 0, а.

V/>/0.

В главе 6 строятся алгоритмы решения задач выпуклого дискретного программирования. Для решения задачи нелинейного дискретного программирования min f{x), (45) где G — многогранное множество, D — конечное дискретное множество (например, булево: {0,1}"), /- квазивыпуклая дифференцируемая в G функция векторной переменной л, построен Алгоритм 6.2.1.

1) Положим / = 0.

2) Построим касательную гиперплоскость к/(х) в точке д, yi=f{xi) + VTf{xi){x-xi). (46).

3) Сформируем допустимую область.

G^{x:xeG, у0(*)#0/(х0), Yi (*)#//(*/)}• (47).

Поясним здесь сразу смысл значка # с нижним индексом. Пусть для некоторого целого к > 0 f (xk) = min (f (x0),., /(*,)). (48).

Тогда в (47) #k нужно взять в виде <, а все остальные значки ttj (j Ф к).

— в виде <. Если же f{x, s),., f (x{) {q > 1) одновременно удовлетворяют условию (48), то только один из значков #/(выбирается в виде <, например, тот, у которого индекс имеет наименьшее значение. Остальные значки имеют вид <.

4) Найдем решение задачи дискретного программирования с линейной целевой функцией у, — и допустимой областью G-. minу,(х). (49).

В результате решения этой задачи придем в точку лг/+1.

5) Если /(.х/+|) = /(*,.), то принимаем xf за решение задачи (45), иначе полагаем i = i + и возвращаемся к пункту 2.

Для выпуклой ЦФ/получен.

Алгоритм 6.3.1.

1) Положим / = 1.

2) Построим касательную гиперплоскость.

У/ (*) = fix,) + V ГД*(-)(х — х,.).

3) Сформируем допустимую область.

Gf G, у0(х) <т,., уДх) < т), где т = min (/(*"),., /(*,)).

4) Найдем хм — решение задачи линейного дискретного программирования min у,(х). xeG. fiD «.

5) Если f{xM) = f (Xj), то принимаем х (за решение (45) с выпуклой целевой функцией, иначе полагаем / = i +1 и возвращаемся к пункту 2.

В разделе 6.4 алгоритм решения задачи выпуклого дискретного программирования модифицирован таким образом, чтобы с его помощью можно было получать не только точное решение задачи, но, при желании, и приближенное решение с любой наперед заданной точностью (абсолютной или относительной):

Алгоритм 6.4.1.

1) Положим i- -1.

2) Положим / = / + 1 и построим касательную гиперплоскость.

У i (x) = f{xi) + VTf (xi)(x-xi).

3) Найдем такое число к, что = min (/(x0),., f{x,)).

4) Положим т = f (xk)-€.

5) Сформируем допустимую, область.

G, = {х:хе <7, у0(*) < т, у,(х) < т},.

6) Если множество G, П D пусто, то за решение задачи (45) с гарантированной абсолютной точностью с принимаем хк и прекращаем поиск.

7) Если множество С/, П D не пусто, то находим в нем допустимую точку хм и возвращаемся к пункту 2.

Алгоритм 6.4.1 дает приближенное решение задачи (45) с выпуклой целевой функцией и требуемой относительной точностью 5, если в нем в формуле т = f{xk)-z вместо г подставить выражение f (xk)b/(l + 5), где функция /предполагается положительной.

В разделе 6.5 построен алгоритм квазимонотонного дискретного программирования.

В разделе 6.6 построен алгоритм решения задачи дискретного математического программирования с линейной ЦФ и выпуклыми функциями в ограничениях: min L{x), gi (x).

Алгоритм 6.6.1.

1) Находим начальную точку х0 е G П D. Полагаем i = 0, Q = Rn.

2) Строим касательные к функциям gt в точке xt: ,.

Уi (*) = ёк (*,) + Vgft{х,)(х-*,)(/ = Ът). Определяем область Q = Q П {л: У f (лг) ^ ^^, к~, т}. Полагаем / = / +1.

3) Решаем задачу линейного дискретного программирования т’тЦх), xeDflGflQ. Полученное решение обозначим x-t.

4) Если Xj &Q, то возвращаемся к пункту 2. В противном случае за решение задачи (50) принимаем х, — и прекращаем поиск.

В алгоритме использовано обозначение т.

Q = jQi* Qi^{^gi{x).

В разделе 6.7 приведен алгоритм минимизации вогнутых функций на дискретных множествах.

В главе 7 разработан подход к решению задачи оптимизации состава средств ИИК для динамических объектов на основе результатов, полученных в предыдущих главах. Основная идея подхода заключается в том, что задача определения оптимального состава средств ИИК сводится путем введения в ЦФ булева вектора присутствия-отсутствия в составе ИИК средств из заданного списка к задаче выпуклого булева программирования, для решения которой применяется один из разработанных выше эффективных вычислительных алгоритмов. При расчете ЦФ или функций в ограничивающих условиях для ускорения расчетов целесообразно использовать быстрые методы решения уравнений Риккати.

Измерительные средства в списке могут быть неинерционными и/или инерционными, с «цветным» или без «цветного» шума. В списке могут присутствовать измерительные средства эпизодической коррекции.

Если в списке N средств непрерывного действия и Nэ средств эпизодической коррекции, причем ошибки 'разных измерительных средств некоррели-рованы между собой, то булев вектор присутствия-отсутствия вводится через ковариационные матрицы ошибок измерения следующим образом: где R' - невырожденная ковариационная матрица шума 1-го измерительного средства непрерывного действия (i =, N), Rj — невырожденная ковариационная матрица ошибки j-го измерительного средства корректирующего типа (j =, N3), ф — некоторая непрерывная на (0, 1] функция, выбираемая так, что ковариационная матрица ошибки фильтрации P (t) выпукла по д, в частности, можно взять ф (6) = Mb.

Рассматривается 2 класса оптимизационных задач. й jv.

1-й класс задач: minD, ^Sy&y.

51).

52).

Здесь D — выпуклая по b функция (если b рассматривать как непрерывную переменную в [О,). n.

2-й класс задач: mine b, -so-> D ^ A) > be{0,}N. (54) b J=i.

Задача (54) является задачей выпуклого булева программирования с линейной целевой функцией и выпуклыми функциями в ограничениях. Для ее решения можно использовать алгоритм 4.6.1.

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

В разделе 7.4 в случае, когда в список измерительных средств входит несколько однотипных измерительных приборов, из которых нужно выбрать не более одного, предложен способ, который при вычислении градиента ЦФ методом малых приращений обеспечивает существенный вычислительный выигрыш.

В разделе 7.5 описывается быстрый способ расчета градиента ЦФ в случае, когда существует установившееся решение соответствующего уравнения Риккати:' = -tr{[HPJJP"HT[R.

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

D = trKPmKr], нужно рассчитать матрицу HPJJP^H1 (можно даже соответствующие ее диагональные блоки), а затем воспользоваться простой формулой (55) для / = ], N.

В случае дискретных динамических систем частные производные D находятся также по формуле (55). U в этом случае является решением матричного алгебраического уравнения Ляпунова (для дискретной системы).

Схемы вычисления градиента целевой функции вида аналогичны в случае непрерывных и дискретных динамических систем: определив матрицу HPJUP^H, компоненты градиента находим по простой формуле (55) для i =, N.

В разделе 7.6 описывается схема оптимизации состава средств ИИК в случае, когда для оценки вектора состояния применяется не ФК, а другие фильтры, в том числе адаптивные к неизвестным параметрам.

В разделе 7.7 описывается схема решения задачи оптимизации состава средств ИИК для случая, когда для всех или части приборов измерения можно проводить только в случайные отрезки времени, определяемые внешними факторами. Процедура построения оптимизационной задачи в этом случае такая же, что и в случае, когда моменты измерений детерминированные. Отличие состоит в том, что вместо P (t) используется усредненная по всем возможным реализациям случайных отрезков времени наблюдений матрица P (t), которая обозначается (Р (0) — Эта матрица обладает такими же свойствами, что и P{t). Поэтому процедура построения модели оптимизационной задачи здесь та же, что и в случае детерминированных моментов измерений.

В разделе 7.8 разработанный подход применен для решения задачи оптимизации состава измерительных средств навигационного комплекса (НК) морского судна на основе ИНС полуаналитического типа. Построена модель оптимизационной задачи. Оптимизационная задача решена для конкретного списка измерительных средств с помощью алгоритма выпуклого булева программирования. Для контроля решение проверялось путем перебора вариантов. Проверка подтвердила оптимальность найденного решения. При этом оказалось, что решение с помощью алгоритма выпуклого булева программи1 рования получилась в 45 раз быстрее.

В разделе 7.9 рассматривается задача оптимизации состава измерительных средств, предназначенных для контроля состояния тепловой системы (бойлера). Список средств включает 12 приборов. В качестве ЦФ использовалась мера наблюдаемости системы где F{t, 0) — фундаментальная матрица для Ab, (i =, NN = 12) — булевы переменные, характеризующие присутствие или отсутствие соответствующих измерительных средств в комплексе. Значение параметра Т взято равным 10,24. о.

Показано, что ЦФ f (b) = ln[detM (7 0)] вогнута по b > 0.

Решалась оптимизационная задача maх/(6) — ?&, с'<�сбе {0,1}* ь /=1.

Эта задача решалась при различных начальных значениях вектора b с помощью алгоритма 6.3.1, который сходился за 6−8 итераций.

В разделе 7.10 разработанный подход применяется для решения задачи оптимального управления наблюдениями в динамических системах. В этой задаче в заданные моменты времени Го, (nизмерительные приборы могут переводиться в 2 положения: включенное или выключенное. В каждый момент времени включенным должен быть только один прибор.

Математически задача формулируется как задача оптимального управления траекториями решений матричного ДУ Риккати: minD[P], ибП (/0.и g {0,1}L, (56) и i",(0 = i (tQ.

Р = АР + РА — РМР + GQG, P (t0) = P0, l г .-i где м (1/, 0 = ягл-, я = я-(0л-,(0^(0 + 2и/(0я^(0к (0] Hlx{i). (57) Запись и еП (*0,., tN) обозначает, что изменение вектора и происходит только в моменты /0,., tNx, а внутри отрезков tk, (к = 0, N -1) управление остается неизменным.

С помощью разработанного подхода строится другая модель оптимизационной задачи: minD[P], b е {0,l}ix/v, (58) ь.

Р = АР + РАТ-PM{b)P + GQGT, P (t0) = P0, b"= U = IN),.

У /=l l.

Rl н7. где для tH.

Здесь (58) является задачей выпуклого булева программирования. Если переключения допустимы в любые моменты времени на отрезке [/0, 7], то с помощью (58) можно получить приближенное решение задачи, которое затем можно уточнить с помощью метода последовательных приближений Крылова-Черноусько.

В случае дискретных систем задача оптимального управления наблюдениями решается аналогичным образом. Математически задача определения оптимальной последовательности переключений с уровня на уровень может быть сформулирована так: minZ>[/>, иеП (к{,., kN), we {0,1}L, (59) и и,{к)=1 о.

Р (к +1) = [г-1 (к +1) + М (и, к + 1)]" ', Р (0) = Р0, T (k +) = A (k)P (k)AT (k) + Q (k), где М{и, k)^HTy{Wyk)Hy{k) + {к)к[{к) Н[{к). (60) 1.

Запись и е П (Аг, ., kN) означает, что переключения допустимы только в моменты времени к, ., к^. Задача (59) является задачей оптимального управления матричной нелинейной детерминированной дискретной динамической системой.

Строится новая математическая модель задачи: minZ>[/>, ие{0,1}7-, (61) и.

Р (к + 1) = [г-1 (к + 1) + М (Ь, к +1)]~', Р (0) = Р0, Г (к +1) = A (k)P (k)Ar (k) + G (k)Q (k)Gr (к), 1 где для kj < к <

61) является задачей выпуклого булева программирования.

Если переключения допустимы в любые моменты времени, то решение задачи (61) можно взять в качестве приближенного, которое затем может быть уточнено с помощью метода последовательных приближений.

В качестве примера рассматривается задача определения оптимальных моментов наблюдения за ориентирами в задаче навигации, которая была сформулирована как задача выпуклого булева программирования и решена с помощью алгоритма 6.3.1.

В разделе 7.10.6 рассматривается задача оптимального управления наблюдениями в динамических системах со случайными моментами измерений. Такие задачи характеризуются очень высокой трудоемкостью расчета ЦФ. Для определения стратегии переключения приборов предложен приближенный метод, приводящий к задаче нелинейного математического программирования.

В главе 8 развитый в главе 7 подход к оптимизации состава средств ИИК применяется для решения задачи оптимизации пространственного расположения (локализации) измерительных датчиков и управляющих приводов в системах с распределенными параметрами (СРП).

В задаче оптимальной локализации измерительных датчиков наблюдается случайное векторное поле x{t, со) с нулевым математическим ожиданием и корреляционной матрицей Rxx (t, соt', со'). В пространственной области Q-задана «сетка» из N узловых точек, в которых можно размещать измерительные датчики. Требуется в этих точках расположить L < N измерительных приборов так, чтобы обеспечить наименьшее возможное значение ЦФ задачи, которая зависит от ковариационной матрицы ошибки фильтрации P{t, соt', со'). Измерения в /-м узле описываются уравнением dz{t, со') = H (t, (o')x (t, сo')dt + dvb (t, со'), (62) где vb (t, (o')sv (t, co'')/7?~,.

E{dvb (t, <�"y) =.

Rh (t, со'>Л (/, оз')/6/.

Предполагается, что матрица R (t, ш') — невырожденная.

На основе разработанного в главе 7 подхода задача сводится к задаче выпуклого булева программирования с одним линейным ограничением: mmD[P], f>, = L, бе{0,1}". (63).

Ь -=1.

В случае, когда со) является вектором состояния динамической СРП, описываемой ДУ в частных производных с самосопряженным оператором Аш, показано, как с помощью метода Фурье рассматриваемую задачу свести к задаче выпуклого булева программирования с ЦФ, зависящей от решения обыкновенного матричного ДУ Риккати, с ограничениями вида.

1=1.

В качестве примера рассматривается задача оптимальной локализации силовых приводов на гибком конусообразном стержне, которая является упрощенной моделью задачи размещения приводов в больших гибких космических конструкциях. В 50 «посадочных» точках нужно расположить 4 привода. Задача решалась с помощью алгоритма 6.4.1 при различных значениях допуска на точность решения. Точное решение получилось за 48 итераций, решение с относительным допуском 5 = 5% - за 7 итераций, с относительным допуском 5 = 10% - за 2 итерации. При этом реальная точность оказалась значительно выше: значение показателя качества отличалось от оптимального при 5 = 5% на 0,1%, а при 5 = 10% на 1%.

В разделе 8.6 рассматривается задача оптимального расположения управляющих приводов в гибких зеркалах. Суть задачи заключается в том, что для управления конфигурацией поверхности зеркала на некоторой сетке узловых точек размещается заданное число управляющих приводов так, чтобы наилучшим образом (с точки зрения выбранного критерия) — настроить (адаптировать) поверхность зеркала к искажениям волнового фронта.

Задача с помощью разработанного в главе 7 подхода сводится к задаче выпуклого булева программирования. Решена конкретная задача, в которой число узловых точек N= 31, число размещаемых приводов L = 4. Задача решалась с помощью алгоритма 6.4.1 при различных значениях относительного допуска на точность. Точное решение получилось за 65 итераций, решение с относительным допуском 5 = 5% - за 22 итерации, с относительным допуском 5 = 10% - за 8 итераций, с относительным допуском 5 = 20% - за 5 итераций. При этом реально значения ЦФ отличались от оптимального соответст I венно на 2%, 5% и 7% .

РОССИЙСКАЯ ГОСУДАРСТВЕННАЯ БИБЛИОТЕКА.

В Приложении приведены лемма об обратной матрице, вывод формул для обращения блочной матрицы, доказательство двух вспомогательных теорем о фильтрации состояний дискретных динамических систем, математическое описание (математическая модель) ПК на базе ИНС полуаналитического типа, акты об использовании результатов диссертационной работы.

Основные результаты работы.

1. Получены уравнения фильтрации состояний дискретных и непрерывных ЛДС в прореженных точках со сжатием наблюдений, в которых процедура сжатия наблюдений полностью определяется характеристиками динамической системы. Переходные матрицы фильтра и, если необходимо, ковариационную матрицу ошибки фильтрации можно рассчитать заранее и хранить в памяти используемой ЭВМ, что позволяет существенно понизить вычислительные затраты при обработке наблюдений.

2. Разработан двухэтапный метод фильтрации состояний нескольких взаимосвязанных дискретных динамических объектов, которые характеризуются тем, что кроме измерений на каждом из объектов имеются наблюдения (связывающие в информационном отношении все объекты), в виде разностей заданных компонент (возможно, всех) векторов состояния для каждой пары объектов.

3. Разработан метод фильтрации вектора состояния дискретного динамического объекта с измерительным комплексом, состоящим из нескольких модулей, на выходе каждого из которых формируются частные оценки фильтрации, при условии, что для обработки доступны только эти оценки. Получены уравнения фильтрации в двух вариантах (в зависимости от того, имеют матрицы измерений в модулях полный ранг или нет) для случаев, а) когда частные оценки на выходе модулей доступны в каждый дискретный момент времени, б) когда частные оценки формируются на выходе модулей в прореженные моменты времени.

4. Разработан единый подход к выводу быстрых алгоритмов решения матричных дифференциальных и дискретных уравнений Риккати, основанный на применении полученных в главе 1 уравнений для ковариационной матрицы ошибки фильтрации вектора состояния ЛДС в прореженном ряде точек.

5. На основе этого подхода получены 4 группы алгоритмов решения матричных и дискретных уравнений Риккати в заданных точках. В случае уравнения Риккати с постоянными или периодически изменяющимися параметрами из них выведены быстрые алгоритмы получения решения уравнения Риккати в последовательных точках N, 2N, 3 N,. или Т, 2 Т, ЗГ,. ив точках с удвоением шага 2°N, 2lN, 22N,. или 2°Tt 2ХТ, 22 Г,. Структурно алгоритмы разбиваются на 4 группы. В 1-ю группу входят алгоритмы, полученные Лай-ниотисом [197, 198], 2-я группа алгоритмов логически вытекает из 1-й, поэтому алгоритмы этой группы также можно назвать алгоритмами типа Лай-ниотиса, в 3-ю группу входят алгоритмы, выведенные автором [134, 150] на основе метода решения дифференциального уравнения Риккати, предложенного Дависоном и Маки [184], 4-ю группу входят новые алгоритмы, отличающиеся от других наименьшими вычислительными затратами.

6. Выведены соотношения, связывающие друг с другом начальные условия и коэффициенты разных алгоритмов на каждом шаге, которые позволяют переходить на любом этапе решения уравнения Риккати от использования одного алгоритма к другому, то есть позволяют использовать суперпозицию алгоритмов.

7. Все разработанные алгоритмы обобщены на случай ДУ с разрывами решений в заданные фиксированные моменты времени, в которых разрывы определяются так же, как и коррекция ковариационной матрицы ошибки фильтрации в фильтре Калмана-Быоси в моменты эпизодических коррекций. Аналогичные алгоритмы получаются в случае дискретных уравнений Риккати, когда их решения корректируются в заданные моменты времени.

8. Установлены свойства выпуклости и монотонности (в зависимости от корреляционной матрицы ошибки измерений) ковариационной матрицы ошибки оптимального линейного оценивания для:

— случайных векторных процессов,.

— случайных векторных последовательностей,.

— случайных векторных полей.

9. Установлены свойства выпуклости и монотонности решений матричных дифференциальных и дискретных уравнений Риккати теории фильтрации состояний динамических систем, а также их характеристических чисел в зависимости от ковариационной матрицы ошибки наблюдений, ковариационной матрицы возмущающих воздействий и ковариационной матрицы ошибки начального состояния.

10. Разработан подход к построению алгоритмов решения задач дискретного выпуклого программирования, эффективных в вычислительном отношении в ситуациях, когда расчет ЦФ на ЭВМ занимает много времени. Суть подхода состоит в том, чтобы минимизировать число обращений к вычислению ЦФ, а большую часть расчетов проводить на множестве менее трудоемких линейных задач дискретного программирования.

11. Разработаны сходящиеся за конечное число шагов алгоритмы ре.

• I шения задач выпуклого дискретного программирования с заданной абсолютной и относительной точностью.

12. Разработаны сходящиеся за конечное число шагов алгоритмы решения задач выпуклого дискретного программирования:

— с квазивыпуклой ЦФ и линейными ограничениями;

— с линейной ЦФ и выпуклыми функциями в ограничениях.

Эти алгоритмы ориентированы, в первую очередь, на решение задач с трудоемкими для вычисления ЦФ. 1.

13. Разработан метод решения задачи оптимизации состава измерительных средств ИИК для непрерывных и дискретных динамических систем. Оптимизация осуществляется на траекториях решений дифференциальных и дискретных матричных уравнений Риккати по переменным, характеризующим присутствие-отсутствие в комплексе средств из заданного списка. Сущность метода состоит в том, что эти переменные вводятся так, что получается задача выпуклого дискретного (булева) программирования, для решения которой разработаны вычислительно-эффективные методы.

14. Получены экономичные в вычислительном отношении формулы для определения градиента ЦФ в случае существования установившегося решения уравнения Риккати.

15. Показано, что задачи оптимального управления наблюдениями, в которых управление заключается во включении или выключении приборов, могут быть решены точно или приближенно с помощью разработанного метода оптимизации состава средств ИИК.

16. Показано, что разработанный в главе 7 метод может быть применен для решения задачи оптимальной пространственной локализации измерительных датчиков и управляющих приводов в системах с распределенными параметрами (СРП). Эффективность метода продемонстрирована на примере оптимальной локализации силовых приводов на гибком конусообразном стержне и на примере решения задачи оптимального расположения управляющих приводов в гибких зеркалах.

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

Основные результаты диссертации опубликованы в монографии [156]:

Якупов Р. Т. Оптимизация систем измерения, управления и обработки наблюдений для динамических объектов. — Томск: Изд-во Том. ун-та, 1995.

В статьях в научных журналах [71, 72, 74, 83, 128, 129, 134, 151, 152, 153, 155, 157].

В статьях, депонированных в ВИНИТИ редколлегией журнала «Известия вузов. Техническая кибернетика» [131, 132, 137, 139, 145, 150].

В статьях в сборниках научных трудов (издательство Томского государственного университета) [66, 70, 73, 82, 84, 85, 120, 121, 122, 123, 124, 125, 164, 165, 167, 168].

В материалах научных конференций [24, 75, 158, 166, 169, 170, 171, 172, 214]. А также в других работах автора, перечисленных в списке литературы (всего в 76 работах).

В работах, опубликованных в соавторстве с Поддубным В. В., исследование и решение задач проведено Якуповым Р. Т., а постановка задач и обсуждение результатов — совместно с Поддубным В. В. В работе, опубликованной в соавторстве с Потоловым А. Б., Потоловым А. Б. проведены расчеты на ЭВМ. В работах, опубликованных в соавторстве с Гарайшиной И. Р. и Моисеевой С. П., постановки задач принадлежат Якупову Р. Т., а решение этих задач и обсуждение результатов проведено совместно, разделить новые научные результаты невозможно.

8.7. Основные результаты и выводы.

1. Показано, что разработанный в главе 7 метод можно применить для решения задачи оптимальной пространственной локализации измерительных датчиков и управляющих приводов в системах с распределенными параметрами (СРП).

2. Эффективность метода, применительно к СРП, продемонстрирована на примере оптимальной локализации силовых приводов на гибком конусообразном стержне и на примере решения задачи оптимального расположения управляющих приводов в гибких зеркалах.

3. Метод оптимизации состава средств ИИК или ИУК для СРП может найти применение в самых разных областях. В том числе при конструировании систем управления конфигурацией больших гибких космических конструкций, при решении задачи размещении датчиков и управляющих элементов в системах контроля за технологическими процессами (химическими, тепловыми и др.), в экологическом мониторинге, в сейсмодиагностике и т. д.