?

Log in

No account? Create an account

Previous Entry | Next Entry

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

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

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

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

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

Comments

( 59 comments — Leave a comment )
Page 1 of 2
<<[1] [2] >>
ppl
Mar. 6th, 2008 10:53 pm (UTC)
Очень даже интересно! :)
ppl
Mar. 6th, 2008 11:28 pm (UTC)
Мне, кстати, что-то такое вспоминается, что с неустойчивостью можно бороться отбрасывая "старые" измерения. Тогда вроде бы точность (ковариационная матрица) и не будет уменьшаться.
(no subject) - scholar_vit - Mar. 7th, 2008 05:43 pm (UTC) - Expand
kdv2005
Mar. 6th, 2008 10:59 pm (UTC)
Мне тоже очень интересно.
А почему многим инженерам трудно объяснить теорему Аги-Тернера?
Они чего-то не знают?
scholar_vit
Mar. 7th, 2008 03:47 am (UTC)
Честно говоря, не знаю почему. Это эмпирическое наблюдение: если знания инженров в области анализа часто оставляют желать лучшего, то с линейной алгеброй совсем плохо. Даже когда какие-то вещи знают, её "не чувствуют", не видят за ней геометрических вещей, того же эллипсоида ошибок. Возможно, что-то с преподаванием.

Впрочем справедливости ради надо сказать, что теорема А-Т далеко не проста.
(no subject) - dumendil - Mar. 7th, 2008 07:11 am (UTC) - Expand
(no subject) - scholar_vit - Mar. 7th, 2008 06:06 pm (UTC) - Expand
filin
Mar. 6th, 2008 11:02 pm (UTC)
Гм. Казалось бы, без каких-то априорных представлений о динамике движения цели ничего разумного не получится - какой кривой апроксимировать траекторию? Фильтруются, очевидно, данные по положению цели в разные моменты времени - но что получается на выходе?
Ну то есть если цель летит по прямой с постоянной скоростью, то метод наименьших квадратов понятно как применить :-) А если она маневрирует или хотя бы нелинейно теряет скорость?
scholar_vit
Mar. 7th, 2008 03:54 am (UTC)
Ну да, нужна хорошая модель динамики (пропагатор на языке этой науки). Модель постоянной скорости действительно распространена. Когда речь идет о спутниках, то работает Кеплерова орбита. Я не занимался межконтинентальными баллистическими ракетами, но подозреваю, что для них Кеплер плюс атмосферное сопротивление должны давать хороший результат. Если отслеживать дружественную цель, то она может что-нибудь сама рассказать о динамике: например, что включила бустерные двигатели на данную мощность.
ex_juan_gan
Mar. 6th, 2008 11:05 pm (UTC)
Мило! Я ничего такого не знал. А Калмана-Бьюси, сколько мне его ни впаривали для расчётов параметров долота на забое (при бурении), так и не признал; основная причина была, правда, в том, что при бурении никакой корреляции нету: что мы наблюдали в более верхних слоях, никак не связано с тем, что мы набурим дальше.
palmas1
Mar. 6th, 2008 11:09 pm (UTC)
Спасибо, очень интересно. А можно ещё вкратце пояснить, где от такого фильтра может зависеть безопасность людей?
scholar_vit
Mar. 7th, 2008 03:59 am (UTC)
Если совсем вкратце, то морским и воздушным судам очень не вредно уметь предсказывать, где в каждый момент окажутся соседние суда. И безопасности совсем не помогает, если эта предсказалка время от времени вынуждена перегружаться.
__rico
Mar. 6th, 2008 11:52 pm (UTC)
Очень интересно. В эконометрике это типичная проблема - очень часто состоятельные оценки "в лоб" ковариационных матриц не гарантируют положительной определенности. Но правда это уже давно успешно побороли :)
mrshurik
Mar. 6th, 2008 11:54 pm (UTC)
вот вы пишите, инженеры не знают устойчивые алгоритмы. всё обычно хуже, средние инженеры не знают схемы Горнера.
femme_amoureuse
Mar. 7th, 2008 02:13 am (UTC)
А зачем им? Есть компутер. Пусто он знает. :(
Мои студенты-инженеры Пи не знали.

Интересно, почему продолжают учить Калману, а не улучшениям?
(no subject) - vitus_wagner - Mar. 7th, 2008 09:38 am (UTC) - Expand
(no subject) - scholar_vit - Mar. 7th, 2008 05:54 pm (UTC) - Expand
(no subject) - vitus_wagner - Mar. 7th, 2008 09:40 am (UTC) - Expand
(no subject) - femme_amoureuse - Mar. 7th, 2008 01:50 pm (UTC) - Expand
(no subject) - vitus_wagner - Mar. 7th, 2008 02:10 pm (UTC) - Expand
(no subject) - femme_amoureuse - Mar. 7th, 2008 02:43 pm (UTC) - Expand
(Deleted comment)
(no subject) - ny_quant - Mar. 8th, 2008 12:57 am (UTC) - Expand
(no subject) - scholar_vit - Mar. 7th, 2008 05:53 pm (UTC) - Expand
(no subject) - danillo - Mar. 7th, 2008 02:31 am (UTC) - Expand
(no subject) - vitus_wagner - Mar. 7th, 2008 02:12 pm (UTC) - Expand
_glav_
Mar. 7th, 2008 12:25 am (UTC)
не может ли случиться так, что достигнув min значения, следующий шаг будет "достаточным" для "прыжка" в отрицательную область, что приведёт к комплексным значениям b. Что, в свою очередь приведёт к нехорошим осциляциям или тому же разносу?

(я не уточняю механизма этого "прыжка" ввиду иллюстраивности примера и незнания деталей, но мой вопрос не праздный: недавно сам столкнулся с случаем, когда, несмотря на ограничение, вылазит "комплесность". В терминах примера это выглядит так: мы исследуем эвоюцию b, но внешние операции всё-равно производятся с b2; в результате чего из b2 может быть вычтено большее по абсолютному значению число, и "новое" b2 станет отрицательным).
scholar_vit
Mar. 7th, 2008 05:46 pm (UTC)
Так в том и идея, что отрицательные значения b никак не выделены: квадрат-то всегда положителен. Разумеется, надо проверить, чтобы уравнения для b давали всегда действительные решения.
(no subject) - _glav_ - Mar. 7th, 2008 10:15 pm (UTC) - Expand
(no subject) - scholar_vit - Mar. 7th, 2008 10:40 pm (UTC) - Expand
dyak
Mar. 7th, 2008 02:12 am (UTC)
Вообще это smart как общий подход -- вместо слежения/анализа шарахающейся около нуля положительной по важным причинам величины, следить за ее корнем.
angerona
Mar. 7th, 2008 02:27 am (UTC)
я далеко не специалист, но мне кажется, что эта проблема (с ошибкой) по английски называется "zero crossing" -- так? И если так, то разве нет разных распространенных методов ее решения?
Во всяком случае я знаю парочку алгоритмов (то есть я знаю о их существовании :)).
scholar_vit
Mar. 7th, 2008 05:58 pm (UTC)
Я полагаю, что большинство этих алгоритмов было придумано тогда же, когда и этот. К тому же в данном случае через нуль переходит не просто число, а собственное значение матрицы, что сильно меняет ситуацию (нужно иметь дело со всей матрицей, у которой есть и другие собственные значения).
danillo
Mar. 7th, 2008 02:32 am (UTC)
спасибо, хорошее объяснение
roma
Mar. 7th, 2008 03:54 am (UTC)
a 4to za teorema-to? Mozhet est' kakaja-to online ssylka?
rioman
Mar. 7th, 2008 04:38 am (UTC)
О!
Спасибо.
Попробую с фильтром Бирмана ;)
sutasu
Mar. 7th, 2008 04:40 am (UTC)
интересно, спасибо!
freedom_of_sea
Mar. 7th, 2008 08:18 am (UTC)
отрицательная
а почему настоящая траектория не может быть отрицательной?
scholar_vit
Mar. 7th, 2008 06:13 pm (UTC)
Re: отрицательная
Отрицательной становится не траектория, а квадрат ошибки. Траектория при этом начинает вести себя как пьяный матрос в ночном переулке.
Page 1 of 2
<<[1] [2] >>
( 59 comments — Leave a comment )

Profile

knot
scholar_vit
scholar_vit

Latest Month

August 2018
S M T W T F S
   1234
567891011
12131415161718
19202122232425
262728293031 

Tags

Powered by LiveJournal.com
Designed by Paulina Bozek