Экспериментальная запись

Время от времени я вижу в ЖЖ записи с пометкой "Интересно только для программистов". Часто там бурное обсуждение. Иногда зависть берёт: вон сколько программистов собралось в сети!

В качестве эксперимента попробую написать о техническом предмете, не являющемся программированием. Хочется посмотреть, будет ли это интересно кому-то, кроме того анонима из Австралии, на чей вопрос я отвечаю.

Я недавно написал:

Катастрофическая потеря точности, говорите? Тогда я расскажу ещё одну историю про навигацию.

Одна из стандартных задач навигации: известны наблюдения за целью в некоторые моменты времени. Надо предсказать, где эта цель (это можете быть Вы, а может быть ракета супостата) будет в заданное время. Полвека для этого применяют так называемый фильтр Калмана: по сути, специальный вариант метода наименьших квадратов. И с семидесятых годов известно, что этот фильтр неустойчив: в нём как раз и происходит катастрофическая потеря точности. Примерно тогда же были разработаны несколько вариантов улучшенного фильтра, где этой потери точности нет. Подробнее это описано в классической книжке
@Book{Bierman77,
author = {Gerald J. Bierman},
title = {Factorization Methods for Discrete Sequential Estimation},
publisher = {Academic Press},
year = 1977,
volume = 128,
series = {Mathematics in Science and Enineering},
address = {New York; San Francisco; London}}
В улучшенном фильтре потери точности нет. Больше того, он быстрее "обычного" Калмана и удобнее программируется. Недостаток у него один: его сложнее объяснить и понять: там довольно хитрая матричная алгебра. Тот факт, что Бирман категорически не умел писать, делу не помогает.

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

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

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

Меня спросили, откуда берется неустойчивость. У меня секретов нет - рассказываю. Разумеется, это объяснение "на пальцах" и с кучей упрощений; подробности см. в книжке выше.

В обычном методе наименьших квадратов неустойчивости, понятно, нет. Но там мы заранее знаем, сколько у нас наблюдений, и учитываем каждое с нужным весом. В задачах навигации и слежения ситуация другая: в каждый момент я не знаю, будет ли данное наблюдение последним, и мне нужно получить траекторию с учетом того, что я намерил до настоящего момента. Поэтому там делают так: хранят текущие параметры траектории и предполагаемый квадрат ошибки (на самом деле ковариационную матрицу). Каждому наблюдению тоже приписывают некоторую ошибку. Получив наблюдение, сравнивают ошибку предсказания и ошибку наблюдения, подправляют траекторию и изменяют ковариационную матрицу. Если все хорошо, то эта матрица потихоньку уменьшается (по норме). И вот тут-то лежит засада. Потому что может случиться, что в итоге норма матрицы окажется одного порядка с ошибкой в её определении ("ошибкой в оценке ошибки"). Что само по себе не так плохо, но в рамках метода катастрофично. Дело в том, что ковариационная матрица обязана быть симметрична и положительно определена. Стандартные уравнения Калмана гарантируют первое свойство, но увы, не гарантируют второго. Поэтому в результате накопления ошибок в ковариационной матрице она может поменять сигнатуру - и тут-то система идет вразнос. Уравнения плохо реагируют, когда предполагаемый квадрат ошибки оказывается отрицателен.

Понятно, почему ранние заказчики - всякие зенитчики-ракетчики - не особо беспокоились по этому поводу. Нестабильность проявляется не сразу. А пока там ковариационная матрица уменьшится настолько, чтобы выйти в минус, - либо мы супостата собьём, либо он сам резко изменит траекторию, чтоб от нас уйти. Эффект заметили позже, когда стали следить за спутниками. Кстати, сам Бирман работал в JPL, и первые публикации о неустойчивости фильтра Калмана появились именно там.

Идея улучшения фильтра основана на простом соображении. Пусть я слежу за эволюцией некоторой величины a, причем я знаю, что она непременно неотрицательна. Но из-за приблизительности в уравнениях и накоплении погрешностей она у меня может выйти и отрицательной. Чтобы этого избежать, запишем a=b², и будем исследовать эволюцию не a, а b. Даже когда b упадет до уровня ошибки вычислений ±b_min, a будет оставаться на минимальном уровне |b_min|². Это чем-то напоминает уравнение Шредингера, где тоже работают не с плотностью вероятности, а с корнем из неё: волновой функцией.

Поскольку мы работаем с матрицами, и корни можно определять по-разному, есть несколько вариаций этой темы. В моем любимом варианте ковариационная матрица записывается как UDU^T, где D диагональна, а U - верхняя треугольная матрица. Затем уравнения Калмана переписываются так, чтобы матрица D в явном виде сохраняла сигнатуру (есть такая теорема Аги-Тернера, которая позволяет это сделать). Тогда ковариационная матрица остается всегда положительной, и неустойчивости не возникает. Проблема у этого метода, как я уже сказал, одна: многим инженерам сложно объяснить теорему Аги-Тернера.