scholar_vit (scholar_vit) wrote,
scholar_vit
scholar_vit

Categories:

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

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

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

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

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

Одна из стандартных задач навигации: известны наблюдения за целью в некоторые моменты времени. Надо предсказать, где эта цель (это можете быть Вы, а может быть ракета супостата) будет в заданное время. Полвека для этого применяют так называемый фильтр Калмана: по сути, специальный вариант метода наименьших квадратов. И с семидесятых годов известно, что этот фильтр неустойчив: в нём как раз и происходит катастрофическая потеря точности. Примерно тогда же были разработаны несколько вариантов улучшенного фильтра, где этой потери точности нет. Подробнее это описано в классической книжке
@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=b2, и будем исследовать эволюцию не a, а b. Даже когда b упадет до уровня ошибки вычислений ±bmin, a будет оставаться на минимальном уровне |bmin|2. Это чем-то напоминает уравнение Шредингера, где тоже работают не с плотностью вероятности, а с корнем из неё: волновой функцией.

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

Tags: science
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 59 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →