Построить максимально точное уравнение прямой по точкам

Есть куча точек - набор пар (x,y), все координаты - double. Нужна готовая библиотека или алгоритм (с/c++), который может построить уравнение данной прямой так, чтобы оно максимально подходило заданным точкам.

Проблема в том, что в каждой точке маа-а-а-аленькая погрешность (6-7 знаки после запятой), т.е. каждая из них окружена некоторой окрестностью ошибки.

Re: Построить максимально точное уравнение прямой по точкам

мне кажется, что кучу точек никак не соединить прямой. по идее кучи не надо: хватит и 2-х

если же нужна не прямая, а что-либо другое, то одним уравнением не обойтись никак, т.е. соединить точки - не проблема, но между точками будет непорядок, ибо соединять их будешь полиномом. "красиво" соединить можно, но это уже будет сплайн - набор функций от а до б, от б до ц, от ц до.

Re: Построить максимально точное уравнение прямой по точкам

Как раз сейчас этим занимаюсь. Здесь нужно применить метод наименьших квадратов http://users.kpi.kharkov.ua/fmp/biblio/BOOK1/2-3.html Вопрос по теме, как применить формулу, зная, что график обязательно пройдёт через точку (0; 0)?

Re: Построить максимально точное уравнение прямой по точкам

По другому это называется линейная аппроксимация! ;-)

Re: Построить максимально точное уравнение прямой по точкам

что называется линейной аппроксимацией? сплайны? да они чаще всего кубические ;)

Re: Построить максимально точное уравнение прямой по точкам

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

Re: Построить максимально точное уравнение прямой по точкам

Линейная аппроксимация - это и есть метод наименьших квадратов. Или я не прав?

Re: Построить максимально точное уравнение прямой по точкам

> метод наименьших квадратов нужен, если данные с немалыми погрешностями Считаешь, что в данном случае он не применим? Другие варианты есть? Как на счёт моего вопроса о прохождении этой прямой через (0; 0)?

Re: Построить максимально точное уравнение прямой по точкам

понял. просто я про неё ни слова не говорил

Re: Построить максимально точное уравнение прямой по точкам

Линейный корелляционный и регрессионный анализ. Библиотеку на c/c++ не подскажу, но в R это делается в пол-строки.

Re: Построить максимально точное уравнение прямой по точкам

Боже, просто классический метод наименьших квадратов.

20 минут программирования (с отладкой) на любом языке -- зачем тебе готовая библтотека?

Re: Построить максимально точное уравнение прямой по точкам

В чём проблема-то? Ищешь прямую, для которой сумма квадратов отклонений минимальна, но не среди всех вообще прямых, а среди только тех, которые проходят через начало координат.

Re: Построить максимально точное уравнение прямой по точкам

А еще есть fit в gnuplotе, который этот самый метод наименьших квадратов реализует.

Re: Построить максимально точное уравнение прямой по точкам

За МНК идёт на форум.

Re: Построить максимально точное уравнение прямой по точкам

>Как на счёт моего вопроса о прохождении этой прямой через (0; 0)?

Как-то даже не смешно становится. У тебя совсем никаких мыслей на этот счет нет?

Обычная прямая имеет два параметра, их и находим с помощью МНК. Угадай с трех раз, сколько параметров у прямой, проходящей через О?

Re: Построить максимально точное уравнение прямой по точкам

> У тебя совсем никаких мыслей на этот счет нет? Неправильно задал вопрос! в МНК точку (0; 0) подставлять?

Re: Построить максимально точное уравнение прямой по точкам

Слушай, за эти несколько дней можно было и почитать про метод наименьших квадратов, и вообще заботать всё вариационное исчисление и половину статистики. Ты давай кончай тут на эту тему постить, сходи в библиотеку и не позорься.

Re: Построить максимально точное уравнение прямой по точкам

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

П.С. не надо мне говорить, что матрица здесь 2х2, я про более общий случай.

Re: Построить максимально точное уравнение прямой по точкам

> но надо ведь находить обратную матрицу, что уже требует серьерзных алгоритмов.

Дядько, нахождение обратной матрицы на double-ах - задачка для первокурсника (собственно, я лично это как раз тогда и делал) на одну лабораторную работу. Не говоря уже о том, что оно есть готовое в тысяче вариантов.

Re: Построить максимально точное уравнение прямой по точкам

Да, так раскажите каким методом вы делали ? Особенно как часто вам попадались illconditioned матрицы?

Numerically stable методы есть и хорошие методы, но они в библиотеках, от которых тут сильно отговаривают.

Re: Построить максимально точное уравнение прямой по точкам

"используй метод н.кв." - некорректное утверждение.

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

Наиболее рапрострaненные случаи "Построить максимально точное уравнение прямой по точкам"

1. Из электроники - имеется линейно-нарaстающий сигнал, (y = a*x + b), к нему добавляется гауссовский/"белый" шум, т.е. отклонения от прямой "вертикальные"(по оси y).

Применяя метод н.кв. получим:

a = (x_среднее*y_среднее - xy_среднее)/(x_среднее**2 - (x**2)_среднее) b = y_среднее - a*x_среднее

т.е. никаких матриц вращaть не надо.

2. Из жизни :) - проверка на трезвость. Необходимо пройти по-прямой в "пьяном" виде. Вероятность отклонения в лево, в право - одинаковая.

Домашнее задание - найти фомулы для вычисления коеффициентов прямой a и b.

Есть довольно интересные рекурсивные алгоритмы, особенно те, которые адаптивные (калмановская фильтрация), но это уже выходит за рамки вопроса.

📎📎📎📎📎📎📎📎📎📎