интерполяция функции

[zayc]

Есть 500.000 (полмиллиона ) точек, нужно построить функцию. Интерполировать функцию использовав полином Лагранжа не проблема, однако представте себе какой большой полином полчится. Естественно ищу другой способ/метод интерполировать функцию. Заранее спасибо.

[vlad_light]

Ridge regression, LOWESS

[dsge]

Kernel regression

[Brukvalub]

zayc в сообщении #1122627 писал(а):

Интерполировать функцию использовав полином Лагранжа не проблема

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

[svv]

Brukvalub в сообщении #1122646 писал(а):

попробовать угадать общий характер зависимости

Brukvalub, это, наверное, история курсов валют со всеми микроколебаниями за несколько лет наблюдений. Чую.

[Pphantom]

zayc в сообщении #1122627 писал(а):

Есть 500.000 (полмиллиона ) точек, нужно построить функцию. Интерполировать функцию использовав полином Лагранжа не проблема, однако представте себе какой большой полином полчится. Естественно ищу другой способ/метод интерполировать функцию. Заранее спасибо.

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

[Aritaborian]

zayc, чем вас не устраивают готовые решения, имеющиеся в матпакетах?

[zayc]

данная задача расматривается как часть криптографической задачи.

vlad_light в сообщении #1122633 писал(а):

Ridge regression, LOWESS

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

dsge в сообщении #1122645 писал(а):

Kernel regression

Kernel regression - если првильно понял это один из вариантов Ridge regression, что как было написанно ранее может вызвать колизии при большом отклонении от точек.

@Brukvalub
Да строить полином лагранжа по 0,5 милиона точек безумие, что в общем то и вызвал данный вопрос. Однако, угадывание функции по графику как в небо пальцем тыкать.

@svv нет вы не правы зача по криптографии

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

@Aritaborian что за готовые решения? и если мат пакеты могу составить функцию по 0,5 милионам точек то что за математический способ за этим стоит.

[Pphantom]

zayc в сообщении #1122799 писал(а):

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

Так. Давайте-ка сначала: что Вам нужно получить? Интерполяция - это когда функция проходит через точки (и отклонение, соответственно, нулевое - меньше некуда). Или речь идет об ограничениях на производные?

[Aritaborian]

zayc в сообщении #1122799 писал(а):

что за готовые решения?

Интерполяция данных в Wolfram Language.

[dsge]

zayc в сообщении #1122799 писал(а):

Kernel regression - если првильно понял это один из вариантов Ridge regression, что как было написанно ранее может вызвать колизии при большом отклонении от точек.

Нет, это совсем разные регрессии (подходы к регрессионному анализу).

[zayc]

Цитата:

Так. Давайте-ка сначала: что Вам нужно получить? Интерполяция - это когда функция проходит через точки (и отклонение, соответственно, нулевое - меньше некуда). Или речь идет об ограничениях на производные?

Ок, есть N-ое количество точек (x,y). нужно получить функцию этих точек. Интерполяция - это нахождение промежуточных точек функции, мне болше точек не нужно, мне нужна сама функция. Отлонения - это не к этому случаю относится, оговорился. Обычно в таких случаях я использовал полином Лагранжа, но при N = 0.5 миллиона, это безумие. Так что нужны еще способы составления функции по набору точек.

Цитата:

Интерполяция данных в Wolfram Language.

Насчет готовых решений. Использование мат пакетов не подходит так как у них есть свои ограничения, к примеру MathcaD на отрез отказывается работать с 32-ух разрядными чслами, т.е. он их переводит в вещественный тип, где потом округляет их.

[Aritaborian]

zayc в сообщении #1123232 писал(а):

к примеру MathcaD

Ясно. Я с вами больше не разговариваю.

[Pphantom]

zayc в сообщении #1123232 писал(а):

Ок, есть N-ое количество точек (x,y). нужно получить функцию этих точек.

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

zayc в сообщении #1123232 писал(а):

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

Пример неудачен - это самый дохлый матпакет из более-менее распространенных.

[Brukvalub]

Pphantom в сообщении #1123247 писал(а):

В каком смысле функцию?

Как я понял из последних реплик ТС, ему просто нужно нечто вроде формулы, которая позволяет хранить таблицу значений функции в заданных точках в относительно компактном виде. При этом, искомая "какбэ" формула должна точно восстанавливать все известные из таблицы значения по их аргументам.