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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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