Сплайны тоже бывают аппроксимационные

[ksili]

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

Пока сам вспомнил:

Интерполяция:
1) построение интерполяционного многочлена (их там несколько, но многочлен один и тот же дают)
2) сплайны

Аппроксимация:
1) метод наименьших квадратов
2) сюда наверно можно ещё отнести разложение по базису Фурье, да и вообще по любому конечному базису.

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

Какие ещё методы есть?

Изменил заголовок при архивации, сохраняя интересное сообщение от worm2 (ниже)

[ИСН]

Интерполяционный многочлен Лагранжа (это который "один и тот же") служит исключительно для доказательства какой-то там теоремы в мат.анализе. А собственно для интерполяции он бесполезен чуть более чем полностью.

[worm2]

Сплайны тоже бывают аппроксимационные.
Например, кубический аппроксимационный сплайн для сеточной функции $y_i=f(x_i)$, $i=0,1,2,\dots,n$, $a=x_0<x_1<\dots<x_n=b$ --- это функция g(x), которая:
1) определена на [a, b];
2) на каждом отрезке $[x_i, x_{i+1}]$ является многочленом степени не выше 3-й;
3) непрерывна на [a, b] вместе со своей первой и второй производными;
4) доставляет минимум функционалу

$$\sum_{i=0}^n\rho_i\left(y_i-g(x_i)\right)^2 + \alpha\int\limits_a^b\left(g''(x)\right)^2dx$$

среди всех функций $g(x): [a, b] \to \mathbb R$, удовлетворяющих условиям 1), 2), 3).
Константа $\rho_i \geqslant 0$ --- это вес i-го значения сеточной функции (чем больше задать вес i-го значения по сравнению с другими весами, тем меньше сплайн будет отличаться от $y_i$ в точке $x_i$) а $\alpha \geqslant 0$ --- это вес "некривизны" функции: чем больше задать $\alpha$, тем более плавным будет сплайн (но тем менее он будет тяготеть к заданным точкам).
В пределе, когда $\rho_i \to \infty$, $\alpha > 0$, получается кубический интерполяционный сплайн.
В пределе, когда $\alpha \to \infty$, $\rho_i > 0$, получается линейная регрессия по МНК.

[ksili]

worm2, вопрос про аппроксимационный сплайн:
для n точек там сколько будет реально многочленов? один или больше?

если один, то я как-то не вижу особых отличий от МНК

[worm2]

ksili писал(а):

для n точек там сколько будет реально многочленов? один или больше?

Для n точек будет n-1 многочленов. Хотя в моём предыдущем посте я рассматриваю пример с (n+1)-й точкой, поэтому там будет n многочленов (так же, как и для интерполяционного сплайна --- свой многочлен для каждого отрезка разбиения, которые сшиваются, чтобы вся функция, производная и вторая производная были непрерывными).

[ewert]

ksili писал(а):

worm2, вопрос про аппроксимационный сплайн:
для n точек там сколько будет реально многочленов? один или больше?

если один, то я как-то не вижу особых отличий от МНК

реально -- грубо говоря, столько же многочленов, сколько и точек.

Это вроде и недостаток по сравнению с МНК, но есть и принципиальнейшее достоинство: этот метод локален, т.е. случайные выбросы на некотором участке слабо влияют на другие участки.

-------------------------------------------
Кстати, "аппроксимация" вовсе не является альтернативой "интерполяции". Аппроксимация в переводе на русский -- это просто приближение, и всё.

[ksili]

worm2 в сообщении #137464 писал(а):

Для n точек будет n-1 многочленов.

что-то как-то неэкономно. Даже для обычного же кубического сплайна - один полином на каждые 4 точки. А через каждые 4 точки сшиваются. Может вы ошиблись?

[ewert]

ksili писал(а):

Даже для обычного же сплайна - один полином на каждые 4 точки. А через каждые 4 точки сшиваются.

Это неверно. Для стандартного сплайна ровно 1 мн-н на каждый отрезок, т.е. на каждую пару точек.

[ksili]

ewert в сообщении #137465 писал(а):

Кстати, "аппроксимация" вовсе не является альтернативой "интерполяции"

С этим я согласен. И у того, и у другого - свои цели.

[worm2]

ksili писал(а):

что-то как-то неэкономно. Даже для обычного же кубического сплайна - один полином на каждые 4 точки. А через каждые 4 точки сшиваются. Может вы ошиблись?

Нет, это Вы напутали. То, что Вы написали --- это не про сплайн. Да и посудите сами: через 4 точки может проходить только один многочлен степени не выше 3-й. Два таких соседних многочлена сошьются так, как им хочется, а не так как нам надо (а нам надо гладко).

[ksili]

ewert в сообщении #137470 писал(а):

Для стандартного сплайна ровно 1 мн-н на каждый отрезок, т.е. на каждую пару точек.

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

Добавлено спустя 2 минуты 1 секунду:

worm2 в сообщении #137473 писал(а):

То, что Вы написали --- это не про сплайн

Точно, убедили. Это я напутал за давностью лет. Просто меня гладкость сама по себе не интересовала.

Добавлено спустя 2 минуты 53 секунды:

Со сплайнами разобрались. ewert, worm2, спасибо.

Как насчёт ещё каких-то методов?

[ewert]

ksili писал(а):

Точно, убедили. Это я напутал за давностью лет. Просто меня гладкость сама по себе не интересовала.

Тогда и сплайны не должны интересовать. Они только ради гладкости и нужны.