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

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

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

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

interpolation fourier-analysis fftw Томас Климпел
источник

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

Jan

Ответы:

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

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

Обновить

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

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

Pedro
источник

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

Томас Климпел

@ThomasKlimpel: Как вы рассчитываете вес? Если вы используете чебышевские узлы на

[- 1, 1]

$[-1,1]$ они просто

\pm 1

$\pm 1$ , или

\pm 1 / 2

$\pm 1/2$ по краям. Если скорость действительно важна, я добавил в свой ответ алгоритм Кленшоу. По моему опыту, это примерно в четыре раза быстрее в скомпилированном коде.

Педро