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

Question

[koliane]

Необходимо построить ф-ию по точкам и затем ее анализировать. Точек может быть до нескольких миллионов. Какую интерполяцию лучше выбрать с точки зрения эффективности и скорости нахождения значения функции по определенной точке в программе? Интерполяция Лагранжа не подходит, т.к. там степень ф-ии увеличивается с увеличением кол-ва точек.
Пока рассматриваю интерполяцию, используя разложение Фурье.
Может есть еще какие-нибудь типы интерполяций, более подходящих для моей задачи?

Comments

[youngmysteriouslight]

Уточните вид анализа полученных функций (одну из задач Вы привели ниже в комментариях) и как Вы их проводили бы в случае полиномиальной интерполяции Лагранжа для ста точек.

Answer 1

[MechanicZelenyy]

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

Comments

[koliane]

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

[MechanicZelenyy]

А как конкретно анализировать? Я не очень понимаю как вам мешает ломаность линейной функции или кусочность сплайнов. Вы потом будете получать от интерполятора просто значения в точка --- он будет как черный ящик.

[koliane]

В задаче необходимо построить несколько функций и затем решить систему уравнений.
Пример:
По точкам получили две функции. Необходимо найти такие точки, чтобы 2 * |F2(x1) - F1(x2)| = |F1(x2) - F2(x3)|

[MechanicZelenyy]

Здесь ломанность вам никак не мешает

[MechanicZelenyy]

И нужны ли тут вообще полная интерполяция? Берем и ищем тройку точек наилучшем образом удовлетворяющим вашем условию. А затем ищете дихотомией уже вблизи этих точек.

[koliane]

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

[MechanicZelenyy]

Опишите ваше решения, поскольку я в упор не понимаю как кусочность может препятствовать.

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

[koliane]

Решение пока представляю такое (объясню на примере выше):
Необходимо составить систему уравнений. У нас всего 3 неизвестных, соответственно должно быть 3 уравнения. Одно уравнение уже есть - это 2 * |F2(x1) - F1(x2)| = |F1(x2) - F2(x3)|. Для того чтобы система была полной, нужно добавить еще 2 уравнения. Их буду итерационно подбирать. Т.е. для нашего примера, А должно быть в 2 раза меньше Б. Соответственно, в одной системе ур-ий А=1, Б=2. Далее подбираю значиния, где А=2, Б=4; А=3, Б=6 и т.д.
Если есть более оптимальный способ решения, буду рад услышать

[MechanicZelenyy]

koliane, Это не система уравнений, это одно уравнение с тремя неизвестными. Оно может иметь несколько (и даже бесконечно много решений).

Я бы перешел к функции F(x1,x2,x3) = 2 * |F2(x1) - F1(x2)| - |F1(x2) - F2(x3)|, и решал бы уравнение F(x1,x2,x3)=0, каким либо методом для решения уравнений. Например бы считал градиент, разбивал бы пространство (x1,x2,x3) на области с постоянным направлением градиента, и проверял бы область на наличие корня.

Ну или воспользовался какой-либо дополнительной информацией о функциях.

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

[koliane]

MechanicZelenyy, т.е. кусочная функция не подходит, да?

[MechanicZelenyy]

koliane, Да, нет, почему? Тут наоборот коэффициента наклона это градиент функции - его можно как-либо использовать для оптимизации поиска

[koliane]

MechanicZelenyy, а как называются эти методы(используя градиенты или гладкость)? Хотелось бы про них почитать

[MechanicZelenyy]

koliane, Я работаю в смжных областях, поэтому конкртную литературу не назову.

Но зато у меня дооформилось решение - путем не сложных преобразований сводим задачу к поиску нулей этой функции:
$$
F(x1,x2,x3) = (4 * (F2(x1) - F1(x2))^2 - (F1(x2) - F2(x3))^2)^2
$$
Но эта функция не отрицательна, а значит можно просто найти её минимумы - а это стандартная задача. Я для этого использую scipy.optimize

Answer 2

[xmoonlight]

Кубическими сплайнами - думаю оптимально будет.
Там поиск линейно делается:

//*************************************************************************/
//Подсчет значения интерполянты в заданной точке
//*************************************************************************/
double Interpolate(double x)
{
	//double result;
	int i=0;

	while (KnotArray[i].x < x)
		i++;
	i--;
	return Coef[i][0] + Coef[i][1]*(x-KnotArray[i].x) + Coef[i][2]*powf((x-KnotArray[i].x),2) + Coef[i][3]*powf((x-KnotArray[i].x),3); 

}

Comments

[koliane]

Сплайны тоже не совсем подходят, т.к. мы получаем множество кусочных функций. А мне в задаче, после получения ф-ии, необходимо ее анализировать, а осуществить необходимый анализ можно только используя 1у "целую" функцию