Линейная аппроксимация Polynomial is badly conditioned

stm2383383

Прошу помощи, Доброфорум.
Высшая математика у меня была давно на младших курсах, потом я ее нигде не использовал. Да и сдавал в основном на 4, поэтому сейчас возник вопрос, на который не могу сам ответить.
Итак, у меня есть GPS-трек, состоящий из набора точек с координатами X и Y. Таких точек порядка 40-50 (хотя это значение не так важно, то же самое и при многих тысячах). Координаты точек имеют вид типа: (569000, 629000).
Мне надо аппроксимировать этот кусок трека прямой линией. Я использую матлаб и функцию в нем polyfit, которая в моем случае аппроксимирует по методу наименьших квадратов.
Однако матлаб каждый раз выдает ошибку вида:
Warning: Polynomial is badly conditioned. Add points with distinct X values, reduce the degree of the polynomial, or try centering and scaling
.
Не могли бы вы на пальцах объяснить, почему это происходит? Разве алгоритму не пофиг на вид точек? Разве не через любой набор точек можно аппроксимировать МНК с той или иной погрешностью?

marina1206

Скорее всего это не аппроксимация, а интерполяция, причем методом Ньютона, то есть с требованием точного равенства интерполируемой функции в узлах. В результате получается полином такой же степени, сколько есть точек. Для большого числа точек это бесполезно.
Если нужна именно прямая, то нужно фиттировать именно прямой. То есть нужно найти правильную функцию, которая делает именно фит по МНК, а не интерполяцию. Если же нужна просто кривая, которая будет гладко проходить через нужные точки, то сплайны.

stm2383383

В матлабовском хелпе сказано:
p = polyfit(x,y,n) findsthe coefficients of a polynomial p(x) of degree n thatfits the data, p(x(i to y(iin a least squares sense.
Здесь я использую n = 1, т.е. фит до полинома первой степени (линейная функция).
Есть еще приписка в хелпе:
The polyfit MATLAB® file forms theVandermonde matrix, V, whose elements arepowers of x.
It then uses the backslash operator, \, tosolve the least squares problem Vp≅y.

BSCurt

Ну если точки образуют такое круглое-куруглое облако, то наклон прямой очевидно будет неустойчив относительно малых колебаний. Казалось бы в матлабе должна быть т чистая линейная регрессия где-нибудь, попробуй её.

BSCurt

И кстати, или я затупляю или линейная регрессия тут это не тоже самое что прямая такая что сумма квадратов расстояний от неё до точек минимальна.

demiurg

Скорее всего то же самое.
Проблема я думаю в том, что у него все координаты близки, а теоретический range значений — вся земля. Поэтому у него всё почти в одной точке.
Надо значения сдвинуть (чтобы среднее X и cреднее Y были равны нулю и нормировать на разность между максимальным и минимальным значением, потом уже делать регрессию.
Возможно, поможет.

griz_a

Не то же, там не расстояния берутся, а сумма квадрат разниц по оси ординат

demiurg

А в методе наименьших квадратов разве по-другому?

griz_a

Я и говорю, что в МНК расстояния по вертикали, что не то же самое, что настоящие расстояния от точек до прямой.

demiurg

Настоящие вроде никогда и не используются, слишком сложно

seregaohota

Надо значения сдвинуть (чтобы среднее X и cреднее Y были равны нулю и нормировать на разность между максимальным и минимальным значением, потом уже делать регрессию.Возможно, поможет.
наверно действительно в этом дело, скорми этой функции точки с координатами
(1,12,33,3)
а потом
(600001,500001600002,500003600003,500003)
и посмотри, если в первом случае не ругается, а во втором ругается, значит в этом дело
Может быть ещё x почти не меняется, данные такие, что искомая прямая почти параллельна оси y, тогда за независимую переменную может y взять?

seregaohota

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

stm2383383

Да, действительно, в этом дело. Первый вариант идет без ошибок, во втором выдает warning.
За предложение мехматовской программы спасибо, но это не нужно. Сдвинуть данные к 0 перед фитированием совершенно не проблема.
Что касается параллельности оси Y, сейчас попробовал ввести точки (0,1 (0,2 (0,3 матлаб выдал ту же ошибку (точнее warning но решил задачу: k = -inf, b = 2.5. Так что это не большая проблема.
А вообще, спасибо всем откликнувшимся. Помогло.

luherstag

Почему слишком сложно? Берёшь ковариационную матрицу, собственный вектор отвечающий наибольшему собственному значению. Он определяет направление прямой, минимизирующей сумму квадратов "настоящих" расстояний.

Niklz

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

BSCurt

Ну геометрически то и PCA понятно что делает. Для двухмерного случая, наверное, можно даже проще посчитать эту прямую.
Оставить комментарий
Имя или ник:
Комментарий: