Метод ι1-аппроксимации в навигационных задачах оценивания

Оглавление
Введение 4
1 Уровни неоптимальности для итерационных алгоритмов
в методе наименьших модулей б
1.1 Введение к первой главе................................................. 6
1.2 Метод наименьших модулей................................................. 7
1.2.1 Постановка задачи................................................ 7
1.2.2 Метод Вейсфельда................................................. 8
1.3 Анализ вариационных задач............................................... 9
1.3.1 Формулировки основных экстремальных задач......................... 9
1.3.2 Двойственные задачи............................................. 10
1.3.3 Решение задач гладкой оптимизации............................... 13
1.4 Оценки сверху для уровня неоптимальности............................... 17
1.4.1 Подход, основанный на задаче
взвешенного метода наименьших квадратов.......................... 17
1.4.2 Подход, основанный на свойствах задачи
метода наименьших модулей........................................ 18
1.5 Метод наименьших модулей в спутниковой навигации........................ 21
1.5.1 Донлеровские измерения спутниковой навигационной системы ... 21
1.5.2 Численное решение задачи метода наименьших модулей.............. 23
1.6 Заключение к первой главе.............................................. 26
2 Задача оценивания смещений в погрешностях БИНС 27
2.1 Введение ко второй главе............................................... 27
2.2 Математическая модель ВИНС ........................................... 28
2.2.1 Уравнения ошибок БИНС .......................................... 28
2.2.2 Особенности уравнений ошибок при стендовых испытаниях........... 31
2.2.3 Модели погрешностей чувствительных элементов.................... 33
2.2.4 Особенности начальной выставки.................................. 35
2.2.5 Уравнения формирующего фильтра.................................. 38
2.2.6 Динамическая система в непрерывном времени...................... 40
2.3 Структура задачи оценивания............................................ 40
2.3.1 Дискретизация динамической системы.............................. 40
2
‘2.3.2 Структура измерений и задаче оценивания........................ 42
2.3.3 Эксперимент с угловой и азимутальной информацией.
Декомпозиция динамической системы ............................ 49
2.3.4 Моделирование массива измерений................................ 51
2.3.5 Анализ точности приближенных моделей .......................... 55
2.3.6 Эксперимент с полной угловой информацией.
Второй вариант декомпозиции системы............................. 59
2.3.7 Масштабирование и переход к безразмерным переменным............ 62
2.4 Вариационные проблемы................................................. 66
2.4.1 Оценивание состояний динамической системы...................... 66
2.4.2 Сведение к проблеме линейного программирования.................. 69
2.4.3 Переход к проблеме безусловной минимизации...................... 75
2.5 Заключение ко второй главе............................................ 80
3 Решение и численный анализ задач оценивания 81
3.1 Введение к третьей главе.............................................. 81
3.2 Структурные элементы программной реализации........................... 81
3.3 Оценивание скачков в инерциальных датчиках
при наличии скоростной и азимутальной информации...................... 83
3.3.1 Входные параметры вычислительной процедуры..................... 83
3.3.2 Оценивание скачков в показаниях акселерометров................. 86
3.3.3 Варьирование весовых коэффициентов............................. 92
3.3.4 Сравнение с методом наименьших квадратов....................... 95
3.3.5 Оценивание скачков в показаниях гироскопов.....................100
3.4 Оценивание скачков в инерциальных датчиках
при наличии полной угловой информации............................... 105
3.4.1 Особенности вариационных проблем и их решений..................105
3.4.2 Границы применимости метода /1-аппроксимации...................108
3.5 Алгоритмические особенности ^-аппроксимации ..........................111
3.5.1 Методы, основанные па линейном программировании................111
3.5.2 Уровни неоптималыюсти в проблемах /1-аппроксимации
для динамических систем.........................................114
3.5.3 Оконное /х-сглаживание для больших массивов измерений .........121
3.6 Заключение к третьей главе............................................128
Основные результаты диссертации 129
Список литературы 130
3
ВВЕДЕНИЕ
В задачах прикладной математики и механики часто появляется необходимость оценить значения некоторых неизвестных параметров по произведенным измерениям. Так возникают проблемы оценивания. Среди методов их решения помимо статистических и частотных подходов можно выделить методы, в которых оценки неизвестных параметров ищутся как решения вариационных проблем; таков, например, широко известный метод наименьших квадратов. В данной работе речь пойдет о методе /х-аппроксимации, также называемом методом наименьших модулей (МНМ). В качестве его приложений будут рассматриваться задачи обработки навигационной информации, в частности, задача выявления сбоев в показаниях инерциальных датчиков [14].
Известно [13, 31, 46, 47, 50], что по сравнению со многими другими методами оценивания /х-аппроксимация обладает большей устойчивостью по отношению к аномально большим ошибкам в измерениях. Поэтому метод наименьших модулей оказывается полезным при обработке реальных данных, которые, как показывает практика, могут содержать погрешности, существенно превосходящие средний уровень шумов.
Идея использования метода наименьших модулей в прикладных задачах не нова. У истоков данного направления стояли П.С. Лаплас |53| и Р. Боскович [49]. Среди современных исследований в этой области необходимо упомянуть работы И.Б. Челпаиова [13], В.И. Мудрова и В.Л. Кушко [31|, П. Блумфилда [46]. Важное место ^-аппроксимация занимает и в работах С. Бойда [47, 52) и Б.Т. Поляка [35], посвященных теории оптимизационных задач. Однако этот метод непрост с вычислительной точки зрения, что затрудняет его использование в случае большого количества измерений и неизвестных параметров. Поэтому, как правило, он находил свое применение в статических задачах оценивания, где необходимые объемы вычислений были сравнительно невелики. В данной работе представлен новый взгляд на использование 1\-аппроксимации: ее предлагается применить в том числе и в динамических задачах оценивания, возникающих в навигации. Это влечет за собой необходимость обработки больших массивов данных, поэтому значительный интерес вызывают алгоритмы численного решения, позволяющие выполнять такую обработку за ограниченное время и с приемлемой точностью. Примером такого алгоритма может служить метод вариационно-взвешенных квадратических приближений (алгоритм Всйсфельда) [55, 56, 31], дающий возможность найти приближенное решение задачи МНМ. В первой главе данной работы предлагается усовершенствование этого алгоритма: на основе теории двойственности выпуклых вариационных задач |7| получены оценки уровней неоптимальности, позволяющие контролировать качество приближенных решений указанной оптимизационной проблемы. Ранее оценки уровней неоптимальности строились для приближенных решений задач гарантирующего оценивания и линейного программирования [9, 25, 26, 54, 47], а применительно к методу Всйсфельда этот результат является новым. Кроме того, в первой главе показано, как гипоритм Вейсфельда может быть использован в важной с прикладной точки
зрения задаче обработки сигналов спутниковых навигационных систем.
Значительное внимание в диссертации уделено применению 1\-аппроксимации для обработки результатов стендовых испытаний бесплатформенных ннерциальных навигационных систем. Решается задача, состоящая в определении моментов и величин скачков в показаниях чувствительных элементов БИНС. Особый интерес к данному направлению исследований возник в рамках сотрудничества лаборатории управления и навигации МГУ с Московским институтом электромеханики и автоматики, имеющим полувековой опыт разработки ннерциальных навигационных систем.
Основы современной теории навигационных задач оценивания заложены в работах АЛО. Ишлинского [21, 22|, В.Д. Андреева [8|, Г.О. Фридлендера [38), Е.А. Девяпина [1G, 17| и H.A. Парусникова [34]. Большой практический опыт в этой области накоплен в лаборатории управления и навигации МГУ им. М.В. Ломоносова [14, 15, 18]. Так, эффективные алгоритмы численного решения навигационных задач оценивания разработаны Ю.В. Болотиным, Н.Б. Вавиловой, A.A. Голованом и В.В. Тихомировым [37).
Отметим, что часть современных исследований посвящена в том числе и обработке информации с аномально большими ошибками. Так, большое распространение получили робастные статистические методы, детально изученные, например, в монографии Дж. П. Хьюбера [41]. Также необходимо отметить диссертацию А.Ю. Невидомского [32], в которой применительно к навигации и гравиметрии рассмотрено использование робастных методов оценивания, в том числе и метода наименьших модулей. Еще один способ оценивания в случае скачков в обрабатываемых сигналах основан на так называемом банке фильтров Калмана. Одним из первых методику использования данного подхода описал Д.Г. Лайниотис [24]. Существенное развитие его результатов предложено в работах С.П. Дмитриева, O.A. Степанова и Д.А. Кошаева [19, 23], посвященных методу мпотальтернативной фильтрации в навигационных задачах оценивания.
Как правило, подходы к обработке навигационной информации основаны на кал-мановской теории оценивания (см., например, [6, 51]). В этом смысле, предлагаемый в данной работе метод /i-аппроксимации принципиально отличается от них как с точки зрения свойств получаемых решений, так и с точки зрения алгоритмической реализации. Основным математическим моделям навигационных задач оценивании и формулировкам соответствующих вариационных проблем посвящена вторая глава диссертации. В третьей главе исследуются численные особенности ^-аппроксимации в динамических задачах оценивания. Для анализа точности приближенных решений используются оценки уровней неоптимальности, полученные в первой главе.
Таким образом, главная цель данной работы состоит в том, чтобы на основе теории выпуклых вариационных задач разработать методику применения ^-аппроксимации для решения навигационных проблем оценивания (в том числе, динамических).
5
Глава 1
Уровни неоптимальности для итерационных алгоритмов в методе наименьших модулей
1.1 Введение к первой главе
На практике часто возникают задачи обработки измерительной информации с аномально большими ошибками (сбоями). В этом случае эффективным подходом к решению проблемы оценивания является метод наименьших модулей (МІІМ) [47, 30].
В [46| указано, что метод наименьших модулей появился примерно на полстолетия раньше метода наименьших квадратов (МІІК). Первые упоминания о нем связываются с работой Босковича [49], написанной между 1755 и 1757 гг. Позже Лаплас исследовал метод наименьших модулей в 1789 г. При этом Лежандр издал свой труд о методе наименьших квадратов в 1806 г., а Гаусс использовал этот метод еще в 1795 г., опубликовав свои результаты в 1809 г.
Численные реализации МНМ, как правило, носят итерационный характер и вопрос о скорости их сходимости не всегда ясен. Данная глава посвящена построению оценок уровней неоптимальности текущей итерации, которые позволяют контролировать точность вычислений, и тем самым дают надежный критерий ос тановки итерационного процесса. Предлагаемая методика проиллюстрирована на примерах, моделирующих некоторые способы обработки первичных измерений спутниковых навигационных систем.
6
1.2 Метод наименьших модулей
1.2.1 Постановка задачи
Пусть по произведенным измерениям необходимо оценить значения неизвестных параметров, которые связаны с измерениями соотношением:
2 = Hтq + г,
где 2 €■ — вектор измерений, г € — вектор ошибок измерений, 7 е Пп — неиз-
вестный векторный параметр, Н — (Их,, Н,у) — заданная матрица размерности п х N № > п).
Метод наименьших модулей состоит в решении вариационной задачи:
Ич) = 13 I* ~ н*т«1 УЗ/.- (1Л)
1=1 4
т. е. в минимизации ^-нормы вектора невязки.
Данный метод позволяет снизить влияние измерений со сбоями при получении искомой оценки параметров. В этом состоит отличие МНМ от МНК, обладающего хорошими свойствами осреднения, но не обладающего помехоустойчивостью по отношению к аномально большим ошибкам измерений.
Отметим также, что на практике различные измерения 2,- могут иметь разный "вес". Иными словами иногда необходимо, чтобы различные измерения по-разному учитывались в целевом функционале:
N
= Хдф* - Н'[я\ — (1-2)
Рг > 0 - заданные весовые коэффициенты. Обычно они выбираются тисходя из представлений о масштабах измеряемых величин. Легко заметить, что проблемы (1.1) и (1.2) очень похожи: достаточно домножить 2*, //, из второй задачи на у^, чтобы считать все весовые коэффициенты равными единице. Однако с вычислительной точки зрения так не всегда удобно делать, что будет пояснено в следующем подразделе.
Существует несколько способов решения вариационной проблемы (1.1). Среди них можно указать подход, основанный на сведении данной проблемы к задаче линейного программирования [12, 47), которая может быть решена как при помощи широко известного симплекс-метода [12], так и при помощи более современного метода внутренней точки [47]. Однако решение задач большой размерности с помощью этих алгоритмов не совсем тривиально. Например, использование программ из пакета МаЫаЬ при количестве измерений N ~ 104 проблематично, так как требует чрезмерно большого выделения памяти. Для решения задачи (1.1) используется и метод вариационно-взвешенных квадратических приближений (называемый также алгоритмом Вейсфельда), который будет описан далее. Все эти три алгоритма являются итерационными, поэтому возникает необходимость получения критериев их остановки, особенно при обработке большого количества измерений.
7
1.2.2 Метод Вейсфельда
Одним из алгоритмов решения задачи (1.1) является метод вариационно-взвешенных квадратических приближений [31], идея которого была предложена Вейсфельдом в 1937 г. [55, 56]. Эта идея заключается в следующем. Вместо минимизации негладкой функции Ц(/) производится последовательность итераций, на каждой из которых ищется вектор, минимизирующий специальную квадратичную по д форму
вегствующий г-й компоненте вектора невязки на предыдущем шаге, г/*-1* — вектор, полученный на предыдущей итерации. В качестве начального вектора (при к = 0), берется некоторое априорное (возможно, грубое) значение неизвестного иараметра. которое требуется уточнить. Иными словами, строится последовательность векторов }, такая что
Отметим, что задача нахождения минимума функции ф(д5 представляет со-
бой проблему взвешенного МНК, ддя которой существуют очень простые и хорошо известные алгоритмы решения. Этим объясняется популярность алгоритма Вейсфельда в инженерной практике. Если на каком-либо шаге выполнится условие: (2(д,д^) > (^(д^К д^) для всех ду то можно доказать, что q^ — точное решение проблемы (1.1) [31]. Если на каждом шаге приведенное выше условие не выполняется, то последовательность будет бесконечной.
Указанный способ получения квадратичной формы Q(q,q('k^) наталкивается на вычислительные сложности при малых значениях компонент вектора невязки г —
А если одна из его компонент становится равной нулю, то вычислить весовой коэфн-циент №}к) = (л - Д7У«)-1 на данном шаге невозможно. Для решения этой проблемы используется прием регуляризации. Пусть а > 0 — достаточно малое число, тогда г-е слагаемое в задается так [311:
і=і
где к — номер итерации, И'/*'1* = (|^ — Я^*”1*]) 1 — весовой коэффициент, соот-
= а^тіп С)(д,д(к 1)).
Или в терминах весовых коэффициентов:
8
Тогда функция (2(<7, <?^) является квадратичной но q формой, весовые коэффициенты которой могут зависеть как от q'k|, гак и от а. При этом всегда выполняется неравенство \у№ < \/а, что обеспечивает необходимую ограниченность весовых коэффициентов.
Вопрос о сходимости алгоритма вариационно-взвешснных-квадратических приближений остается открытым, особенно в случае регуляризации. Поэтому представляется важным оценить, насколько неоптимальным является полученный на каком-либо шаге вектор qlk\ т. с. насколько I(q^) больше неизвестного оптимального значения /0 — где q° — решение задачи (1.1).
Уровнем неоптимальности к— й итерации метода вариационно-взвешенных квадратических приближений назовём величину [54|
Оценки неоптимальности такого типа первоначально появились в гарантирующем оценивании [9. 25, 26, 54]. Точное значение уровня неоптимальности неизвестно, так как неизвестно оптимальное значение целевого функционала /о- В данной главе предлагаются два способа построения оценки Д0 уровня неоптимальности Д, один из которых может быть использован и для других итерационных алгоритмов решения задачи (1.1).
Эти оценки могут оказаться полезными при решении прикладных задач. Если на данном шаге Д < Д0 и Д0 достаточно близко к единице, то /(<?^) и /0 тоже мало отличаются. Тогда q^ можно взять в качестве удачного приближенного решения задачи (1.1). Таким образом, получение оценки сверху уровня неоптимальности для текущей итерации дает надежный критерий остановки вычислительного процесса.
1.3 Анализ вариационных задач
1.3.1 Формулировки основных экстремальных задач
Сформулируем вариационные задачи в том виде, в котором они понадобятся в дальнейшем. Введем обозначения для компонент неизвестного вектора невязки:
д<М /(q<fc>) = /(qPO) ^
/(7°) /о
где
q(k) = argmin .7(7), J(q) = Wf l)(zi - Hjqf.
Xi = Zi- Hfq, i = 1,..., N, x = (xu ..., xN)r.
В этих обозначениях исходная задача метода наименьших модулей примет вид
N
(1.3)
при ограничениях
Zi — Xi- Hjq = 0, г = 1,..., N.
9
Задача МИК, решаемая на каждой итерации алгоритма вариационно-взвешенных квадратических приближений, может быть записана следующим образом (номер итерации опущен):
./о = inf (xrWx)2 (1.4)
xeR”, gCR"
при ограничениях
Zi — Xi — Hj <7 = 0, i = 1,... ,iV,
где W—положительно определенная диагональная матрица W = diag{lVb..., W^}. Введем обозначение для нормы, фигурирующей в задаче (1.4):
\\x\\w = (xTWx)b.
Кроме того через (г/0,т°) обозначим решение задачи МНМ (1.3), а че|>ез (<7*,.т") — решение задачи взвешенного метода наименьших квадратов (1.4).
Замечание 1.1. Рассмотрим функции Лагранжа для вариационных проблем (1.3) и (1.4):
Li (я, q, Л) = ||х|| ! + XT(z -X- Hrq),
L2{x, q, A) = \\x\\w + \T(z -X- H1 q),
где Л Є Rv—вектор множителей Лагранжа. Тогда указанные задачи (1.3) и (1.4) могут быть переформулированы в виде проблем безусловной минимизации
/0= inf sup L\(х, q. X),
Agr*
Jo = inf sup L<2(x,q,\).
XfcRW.qeRn AGRN
Действительно, если Zi — Xi — HJ q > 0 для некоторого і, то Li{x, q, Л) —* +oo при А,- —> +ос. В случае Zi — Xi — Hjq < 0 аналогично: іц(х, <7, А) —* +оо при А, —» —оо. Поэтому
[ЦхІІ! при z-x-HTq = 0,
SUP Li(x, q, A) = <
AgR‘v l+oo в противном случае.
Тогда supÀ Li(x, <7, A) -* infx>(/ — другая запись задачи (1.3). Для задачи (1.4) все рассуждения те же самые.
1.3.2 Двойственные задачи
Для получения оценки сверху уровня неотималыюети А понадобится переход к так называемым двойственным проблемам. Напомним основные факты из теории двойстве и посій выпуклых вариационных задач.
10
Утверждение 1.1. Задача, двойственная к проблеме. (1.3), имеет вид:
/° = sup zTX (1.5)
А6 Rn
при ограничениях
Н\ = 0, |Лг-1 <1, i= 1,..., /V.
Кроме того выполняется соотношение двойственности: /0 — ^°-
Доказательство. Общее правило для получения двойственной задачи изложено в [7]. Рассмотрим функцию Лагранжа для задачи (1.3):
N N
q,X) = YJ Ы + ^ “ х* ~ нТя) = \\x\U + Хтг - ХтНтд - Хтх =
»=1 »=1
N
= $^(N1 “ ” XrHTq' + zTX.
t=i
Двойственной к задаче (1.3) называется проблема вида
/°= sup inf Li(x,qt А).
AcRw *eR",geRn
Найдем явное выражение для inf*^ L\(x, q, Л). Возможны три случая.
1. Если ЯА ф 0, то положим х = 0, тогда функция Лагранжа Li(0,g,A) станет линейной по q. Поэтому она неограничена по q и infXi9 Li(x, q, X) = —оо.
2. Если |А*| > 1 для некоторого г, то Li(x.q,X) содержит слагаемое |т*| — XtXi = |a?i|(l—AiSigno:»). Пусть А* > 0, тогда, устремив Xi —> +эо, получим |х,-| (1—AjSignx,) —► —оо (при Aj < 0 устремим —» —оо и получим тот же результат).
3. Если |Aj| <1, г = 1,..., Я и НХ — 0, то 2i=i(lxil - Ai®<) > 0. Следовательно Li(x,q, А) > zTX для всех x,q и L|(0,0, А) = zTX, поэтому infx>/7 L\(x, q, А) = zTX.
Таким образом, имеет место равенство
. ( т . . /гг\ при ЯА = 0. ЦАЦоо < 15
inf n L\(x,q, А) = <
x€R ,<?eR 1—00 В ПрОТИВНОМ Случае.
Отсюда получим, что вариационная проблема (1.5) является двойственной к задаче (1.4).
Соотношение двойственности имеет вид [7, 20]:
sup inf L\(x,q,X) = inf sup Li(x,q,X).
AgR" xeR*\g€Rn *eR*,<76Rn A(ERn
Левая часть этого равенства соответствует решению задачи (1.5) и была обозначена 1°. В силу замечания 1.1, правая часть соотношения двойственности равна /0. Итак, получено второе утверждение: /о = /°. П
11