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

Question

[beavis]

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

Answer 1

[Koss1024]

Слишком мало данных для полного ответа.

Вообще вам подойдет сплайн первого порядка с нужным количеством узлов (это и есть ломаная)
Просто непрерывная кривая (недифференцируемая в точках излома)
Математику сего процесса можно найти в NURBS book или в интернетах

Например очень глубоко проработана теория NURBS сплайнов
Нагуглить работающий интерполятор несложно (с незафиксированными узлами)
Я давно не заглядывал но вроде NURBS++ работал гуд

Там параметризуется обычно количество узлов и границы

Узлы очевидно стоит размещать поближе к точкам с минимальным модулем производной
(перегибы, минимумы и максимумы)

Comments

[beavis]

Спасибо за ответ, похоже то что вы пишете это то что мне нужно, особенно книжка.

Почему мало данных? Вроде задача однозначно определена из описания. Попробую переформулировать: Пусть имеется набор данных {(Xi, Yi)}, i = 1, ..., M который нужно аппроксимировать наилучшим образом при помощи ломаной. Число узлов ломаной ограничено наперёд заданным числом N, расположение узлов ломаной произвольно. Под наилучшим приближением пониматеся минимизация величины суммы квадратов разностей Yi и cоответствующих точек ломаной.

Я правильно понимаю, учитывая то что вы написали в последнем абзаце, что точного решения этой задачи не существует, а можно только разлиными соображениями построить вероятно близкое к точному решение?

[Koss1024]

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

Есть шаги рунге-куты, есть адаптивные сплайны Безье, можно подумать над адаптацией де Кастельжо в экстремальных точках поскольку у вас набор и производные посчитать легко, то построить сплайн Безье вообще задача за log(n), а потом можно адаптивно искать приближенную ломаную.

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

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

Собственно почти все это есть в книге о которой я написал. (здесь есть решение в NURBS)
Еще на русском об интерполяции Бахвалов - Численные Методы (но эта книга не решает Вашу задачу напрямую)

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

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

Если же порядок выше, то точные методы строить смысла нет, поскольку погрешность их вычислений очень сильно превзойдет погрешность любого МНК подхода (например Ньютон-Гаусс он же Левенберг- Марквардт)