Максимальное линейное приближение данных

[jetyb]

Доброго времени суток!

Есть какая-то функция, для которой известны все ее значения допустим во всех натуральных числах от 0 до 100.
Эту функцию надо как-то приблизить, причем не абы как, а кусочно-линейной непрерывной функцией, которая имеет, например, 10 узлов(точек излома).
Два узла должны быть расположены в концах отрезка [0;100].
Надо найти минимальную кусочно-линейную приближающую функцию(или ее узлы), такую, чтобы сумма квадратов отклонений приближающей функции от нашей по всем известным точкам была минимальной.

Я ищу численное решение. Количество точек известной функции как и количество узлов искомой могут меняться.

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

Может у вас есть какие-то мысли?

[Circiter]

Ваша задача случаем не имеет чего-нибудь общего с задачей из темы параметризация поверхности?

[oveka]

Очень давно что-то похожее делал для укладки трубы по геодезическим точкам.
Писал программу расчёта. Теория - статья какого-то итальянца на итальянском в Биометрике. Статью находили в Ленинке. Вот и всё.

[мат-ламер]

jetyb. Запишите Вашу задачу как задачу линейной регрессии и примените метод наименьших квадратов.

[Maslov]

jetyb,
я думаю, можно попробовать порешать нелинейную задачу МНК для нахождения координат $x_2, ..., x_9, y_1, ..., y_{10}$ точек излома аппроксимирующей ломаной с линейными ограничениями $x_1 < x_2 < ... < x_9 < x_{10}$.

мат-ламер в сообщении #449734 писал(а):

Запишите Вашу задачу как задачу линейной регрессии и примените метод наименьших квадратов.

Стесняюсь спросить: а как Вы предлагаете записать задачу линейной регрессии при неизвестных абсциссах точек излома?

[мат-ламер]

Цитата:

Стесняюсь спросить: а как Вы предлагаете записать задачу линейной регрессии при неизвестных абсциссах точек излома?

В условии не говорится насчёт того, что они неизвестны и мы их можем двигать.

-- Вт май 24, 2011 22:13:37 --

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

-- Вт май 24, 2011 22:15:19 --

Книга называется, типа, сплайны в инженерной геометрии. Но точно не помню.

-- Вт май 24, 2011 22:24:42 --

jetyb в сообщении #449537 писал(а):

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

Но ведь это можно записать в удоваримой форме, пригодной для программирования.

[Евгений Машеров]

Как вариант решения - регрессия на функции вида

$$ f_i(x)=\begin{cases} 0,&\text{если $x \lt<i$;}\\ x-i,&\text{если $x>i$.} \end{cases} $$

используя какой-либо алгоритм пошаговой регрессии.

[mserg]

Напрашивается генетический алгоритм, у которого переменные $x_i$, а целевая функция – минимальная сумма квадратов разностей.
Данные есть? Можно попробовать.

[jetyb]

Генетический алгоритм? Интересно.
Правда если считать, что следующее поколение получилось из предыдущего сдвигом некоторых узлов на шаг влево - вправо, то могут возникнуть проблемы с огромным размером нового поколения (в задаче я ищу в среднем около 100 узлов для 500 точек). Но если сперва искать не 100, а 10 узлов, а в получившихся отрезках снова искать по 10 узлов, то что-то может и получиться. Подумаю.

мат-ламер в сообщении #449805 писал(а):

Но ведь это можно записать в удоваримой форме, пригодной для программирования.

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

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

[Евгений Машеров]

Вот опыт применения описанного выше подхода. Для расчёта использовалась пошаговая регрессия с добавлением переменных (Forward) пакета Statistica, F на включение 4, на исключение 3. Получено 8 узлов. Подстройку их числа можно делать, меняя F (конечно, если писать свою программу, то проще задавать число добавляемых).

[Sender]

Это как же кусочную функцию задать без условий? Разве что через модули.
$y(x)=a_1(x-x_1)+\sum_{i=2}^{n}a_i|x-x_i|$.

[jetyb]

Евгений Машеров
Класс! Осталось разобраться в приведенном алгоритме.
Спасибо.

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

[Евгений Машеров]

Алгоритм, по сути, сводится к поочередному включению в модель базисных функций и проверке, не стали ли в результате ранее включённые незначимы. Описание пошаговой регрессии можно найти в разных источниках, например, в книге Себера "Линейный регрессионный анализ"
http://depositfiles.com/ru/files/6619118

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