Простая реализация подгонки кривой в C++ (SVD Least Sqares Fit или аналогичный)

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

Я использую VС++ 2008.

Я сталкивался со многими библиотеками, такими как cminipack, cmpfit, lmfit и т. д., но ни одна из них не кажется интуитивно понятной, и мне было трудно реализовать код.

В конечном итоге у меня есть набор дискретных значений, помещенных в одномерный массив, и я пытаюсь найти «виртуальную максимальную точку» по кривой, соответствующей данным, а затем найти максимальную точку этих данных в нецелом значении (где целое число значение будет самой высокой точностью, просто глядя на массив).

В любом случае, если кто-то сделал что-то подобное и может указать мне на пакет, который они использовали, и, возможно, на простую реализацию пакета, это было бы здорово!

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

РЕДАКТИРОВАТЬ: Вот код, который я написал, который работает! http://pastebin.com/tUvKmGPn

изменить размер, чтобы изменить количество используемых входов

0 0 1 1 2 4 4 16 7 49

a: 1 b: 0 c: 0 Нажмите любую клавишу, чтобы продолжить. . .

Спасибо за помощь!


person Shawn Tabrizi    schedule 27.06.2012    source источник
comment
Подгонка параболы наименьших квадратов к 5 точкам данных? Требуется ли вам, чтобы он имел форму y = ax^2 + bx + c, или вам требуется возможность подогнать его к «свободным» точкам (т.е. вращение стандартной параболы??)   -  person mathematician1975    schedule 27.06.2012


Ответы (2)


Предполагая, что вы хотите соответствовать стандартной параболе формы

    y = ax^2 + bx + c 

к вашим 5 точкам данных, тогда все, что вам нужно, это решить матричное уравнение 3 x 3. Взгляните на этот пример http://www.personal.psu.edu/jhm/f90/lectures/lsq2.html - он работает с той же проблемой, которую вы, кажется, описываете (только с использованием большего количества точек данных). Если у вас есть базовые знания в области исчисления и вы можете инвертировать матрицу 3x3 (или что-то более красивое в числовом выражении — что, как я предполагаю, вы делаете, учитывая, что вы ссылаетесь конкретно на SVD в своем заголовке вопроса), то этот пример прояснит, что вам нужно сделать.

person mathematician1975    schedule 27.06.2012
comment
Спасибо, я видел этот метод раньше, и у меня есть общий опыт работы с Linear Alg, и я должен быть в состоянии сделать это, но мне кажется, что ему не хватает какой-то минимизации функции для наилучшего соответствия данным, из чего Я понимаю, что этот метод даст 1 результат для любого набора точек, но кто скажет, что этот результат подходит лучше всего? - person Shawn Tabrizi; 27.06.2012
comment
@user1396977 user1396977 Линейный метод наименьших квадратов УНИКАЛЬНЫЙ - шаг минимизации исходит из частных производных по вашим параметрам приближения (a, b, c) и устанавливает их равными нулю. Последний набор уравнений, который вы решаете, используется для получения параметров. Не волнуйтесь - это уравнение дает вам полином наименьших квадратов степени 2 для ваших данных. Это уникально. Метод завершится ошибкой только в том случае, если в ваших данных нет различных значений x. - person mathematician1975; 27.06.2012
comment
Еще один момент, который мне нужно решить с помощью этой подгонки, заключается в том, что мне нужен быстрый алгоритм, поскольку моя программа зависит от запуска этого количества десятков тысяч раз. Я определенно вижу, что это общий способ сделать это, но другие методы, такие как SVD или levmar, оптимизированы, не так ли? - person Shawn Tabrizi; 28.06.2012
comment
levmar предназначен для НЕЛИНЕЙНЫХ задач, а это не так. SVD не является тривиальным алгоритмом. Для чего-то такого маленького с полиномом только степени 2, подходящим для 5 баллов, я думаю, что подход закрытой формы, подобный этому, достаточен. Для более общих проблем (больше точек данных и полиномов более высокой степени) я бы рекомендовал найти метод факторизации QR. Если вы часто этим занимаетесь, вам лучше всего будет разобраться с соответствующей теорией — хорошей отправной точкой будет вводный текст по численному анализу. Если у вас уже есть линейная алгебра, это хорошее начало. - person mathematician1975; 28.06.2012
comment
Окей, большое спасибо. Я напишу код для использования этого метода, и, к счастью, в C++ есть несколько хороших библиотек линейной алгебры, если я правильно помню. - person Shawn Tabrizi; 28.06.2012
comment
Это неудобно делать численно, но вы можете вычислить обратное 3x3 вручную. Если вы можете достать ее, попробуйте эту книгу — это хорошее введение, и вы также узнаете о численной устойчивости www-maths.mcs.st-and.ac.uk/~gmp/gmptheo.html - person mathematician1975; 28.06.2012
comment
Большое спасибо, вот код, который я написал, и он отлично работает. Я сделал, как вы предложили, и решил обратное самостоятельно, и жестко закодировал его в своей программе. Затем несколько сложных циклов для выполнения матричного умножения, и теперь у меня есть аппроксимация методом наименьших квадратов для квадратичных функций! pastebin.com/tUvKmGPn 0 0 1 1 2 4 4 16 7 49 a: 1 b: 0 c: 0 Нажмите любую клавишу для продолжения . . . Спасибо! - person Shawn Tabrizi; 28.06.2012
comment
Вы можете использовать Maxima, чтобы выполнить алгебру символьных матриц за вас. Курсы робототехники, которые я прошел, были для меня настоящей находкой. - person Kuba hasn't forgotten Monica; 28.06.2012
comment
@ user1396977 Рад, что это работает. Просто последний совет - если вы можете найти некоторые общие библиотеки линейной алгебры, лучше использовать их, но если нет, безопаснее сопоставить ваши значения x с диапазоном [-1,1] или [0,1] для большая численная стабильность. Или, если вы чувствуете себя смелым, найдите полиномы Чебышева и используйте их в качестве полиномиальной основы. - person mathematician1975; 28.06.2012
comment
@ mathematician1975 Я не понимаю, что именно вы имеете в виду и как это будет более стабильно. Вы говорите, что мой код на данный момент может дать сбой с определенными параметрами для значений [x, y]? - person Shawn Tabrizi; 28.06.2012
comment
@user1396977 user1396977 нет, это не приведет к сбою, хотя вы должны проверять, чтобы матрица была единственной. Я имею в виду ЧИСЛЕННУЮ устойчивость - использование полиномиального базиса Чебышева более устойчиво численно, чем полиномиальный. Для вашего случая 3 x 3 все должно быть хорошо, но если вы увеличиваете количество баллов и более высокие степени, я бы предложил использовать библиотеку линейной алгебры. Обычно данные (абсцисса = значения x) сопоставляются с [0,1] или [-1,1] для улучшения числовой стабильности. Если процедура численно нестабильна, вы можете получить небольшие ошибки в параметрах аппроксимации. - person mathematician1975; 28.06.2012
comment
Это хороший пример плохой численной стабильности en.wikipedia.org/wiki/Hilbert_matrix. - person mathematician1975; 28.06.2012
comment
Хм, интересно. Что ж, я никогда не планирую превышать 5 баллов, поэтому я просто буду придерживаться этого, но я буду иметь это в виду на будущее. Спасибо, ваши знания мне очень помогли. - person Shawn Tabrizi; 28.06.2012

Посмотрите на эту страницу Википедии о полиномиальной регрессии.

person Doug Currie    schedule 27.06.2012