Качество аппроксимации.

у тебя не аппроксимация походу, а интерполяция.

интерполируй куюическим сплайном, а не полиномом.

Ну или если все таки аппроксимация, то все равно сплайном лучше наверное будет.

а вообще дай нормальное ТЗ.

А формулы (даже без коэффициентов) совсем нет?

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

Более сложные - минимизация функционала от отклонения на опорных точках и от первых/вторых производных на интервалах между точками, т.е. требования минимальной выпуклости и «осциляций». Тут уже нужно хорошо разбираться в мат. аппарате и уметь формализоаывать в таких терминах своё «лучше».

В общем, нужно кроме самих опорных точек задавать какие-то априорные свойства о поведении ф-ии между точками.

1. Даны точки от неизвестной функции
2. Даны две интерполяции этой функций
3. Найти более близкую к функции интерполяцию из данных

неизвестной функции
более близкую

любая.

Линейно интерполировать несколько дополнительных точек и сравнить среднее квадратическое отклонение от всех получившихся точек?

Найти более близкую к функции интерполяцию из данных

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

Определись, что ты хочешь получить на выходе. И дай больше информации о системе. А то знавал я молодцов, которые по одной точке зависимость строили.

Линейно интерполировать несколько дополнительных точкам и сравнить среднее квадратическое отклонение от всех получающихся точек?

Можно и так. Если хочется больше перфекционизма, то можно минимизировать функционал SUM{k, integrate{ (x(k), x(k+1)) ,(A(k) + B(k) * x - f(x, Uo,..., Um))**2} по {Uo,...,Um}, для некоторых классов f(x,...) он хорошо превращается в СЛАУ.

Найти более близкую к функции интерполяцию из данных

ну а критерий-то какой?

Если тебе надо создать критерий отвечающий твоим «ощущениям» от взгляда на график, то я думаю, что тебе подойдет понятие полной вариации. То есть та интерполяция лучше, у которой полная вариация меньше,

Я забыл, как теорема называется (Чебышева, что-ли). Она объясняет, почему когда точки расположены на примерно одинаковом расстоянии, интерполирование полиномом даёт такой результат, как синяя кривая. Погугли вычматы.

Я забыл, как теорема называется (Чебышева, что-ли)

Это называется явление Рунге (Runge's phenomenon). А интерполяция по Чебышевским узлам его давит.

О! Спасибо за напоминание. Давно знал, но основательно забыл.

Даны точки от неизвестной функции

Так может тебе сигнал реконструировать надо из сэмплов?...
http://en.wikipedia.org/wiki/Whittaker–Shannon_interpolation_formula

Если у тебя так осциллирует «синяя», то явно неправильный метод выбран! Кстати, чем аппроксимируешь? B-сплайны пробовал? Очень хороши!

P.S. Если тебе нужно сформулировать критерий отбора «нехороших» интерполяций по вот таким вот осцилляциям, можешь ее лапласианом гауссианы обработать и проанализировать результат — скажем, просто считать количество выбросов выше заданного порога. Еще вариант — сгладить скользящей медианой с достаточно длинной выборкой, а затем посчитать сумму абсолютных разностей или квадратов разностей.

Да и красная не айс. Плюсую бета-сплайны!

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

Как аналитически выделить более качественную аппроксимацию.

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

P.S. Странно, что никто не предложил «идеальную» кусочно-линейную аппроксимацию :)

Любую «аппроксимацию» надо делать не по «среднеквадратическим», а по кросс-валидации --- то есть по оценке способности предсказывать значение в точках не участвовавших в фите.

У тебя overfitting:

https://pbs.twimg.com/media/BuIq4vXIAAA04oM.jpg:large

P.S. Странно, что никто не предложил «идеальную» кусочно-линейную аппроксимацию :)

Я бы предложил кусочно-постоянную аппроксимацию :)

Топикстартеру:
1. критерий качества какой? (хотя бы словами)
2. класс аппроксимирующих функций какой? (непрерывные, многочлены, ряды экспонент...)

Обычно принято считать, что Чебышевская аппроксимация (минимаксная) лучше аппроксимации в среднем, поскольку норма Чебышева сильнее нормы в пространстве L_p. В твоем случае красная линия лучше.

Говорю как человек, который пару лет активно занимался чебышевскими приближениями.

Вообще, это открытый вопрос об обобщающей способности. В твоем случае, тебе подойдет регуляризация, где ты штрафуешь негладкость функции (l2 норма от градиента в каждой точке). Если не очень ограничен по времени, то используй методы локальной регрессии (loess в матлабе).

Если даны две кривые и надо определить ту, которая лучше, то вот некоторые критерии хорошести, а точнее, их гладкости:

sum( (df/dx)^2 ) — если нету резких углов

sum( abs(df/dx) ) — если есть резкие углы

sum( (d^2f/dx^2) ) — гладкая, но более гибкая. Энергия сгибания стержня. Большой плюс в том, что не штрафует прямые линии.

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

Я начинаю любить этот тред всё больше и больше. Реально, про 90 процентов этих вещей и не слышал.