Быстрая (приблизительная) оценка полинома Чебышева

9

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

Следующие идеи пришли мне в голову:

  • Попробуйте адаптировать методы неоднородного БПФ (NFFT)
  • Используйте БПФ для вычисления производных в чебышевских узлах, потенциально после первого перехода к более тонкой (чебышевской) сетке. Затем используйте кусочно-кубическую интерполяцию для (приблизительной) оценки.
  • Используйте некоторую формулу, которая использует только значения функций (и, возможно, производные) в «соседних» чебышевских узлах (это связано с конкретной техникой NFFT).
Томас Климпел
источник
Посмотрите на chebfun ! Это целая библиотека, основанная на представлениях функций с помощью полиномов Чебышева. Это открытый исходный код, высоко оптимизированный и хорошо поддерживаемый, и я предполагаю, что если существует предпочтительный способ поточечной оценки полинома, то вы найдете его там.
Jan

Ответы:

11

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

На самом деле это точная оценка чебышевского интерполанта. Если вы оцениваете полином степениn в m узлы, стоимость в O(nm),

Обновить

Другой вариант, если у вас есть коэффициенты Чебышева вашего интерполяционного полинома, это использовать алгоритм Кленшоу . Если у вас есть только значения функций в узлах Чебышева, но вы должны оценивать полином несколько раз, вы можете вычислить коэффициенты с помощью БПФ.

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

Pedro
источник
В настоящее время я делаю это путем предварительного вычисления весов относительно значений функций в узлах Чебышева для конкретной точки оценки, а затем оцениваю эту точку для всех необходимых мне интерполяций (их много, все с одинаковыми узлами Чебышева и одинаковыми точками оценки) , а затем перейдите к следующей точке оценки.
Томас Климпел
@ThomasKlimpel: Как вы рассчитываете вес? Если вы используете чебышевские узлы на[1,1]они просто ±1, или ±1/2по краям. Если скорость действительно важна, я добавил в свой ответ алгоритм Кленшоу. По моему опыту, это примерно в четыре раза быстрее в скомпилированном коде.
Педро