Evaluación rápida (aproximada) del polinomio de Chebyshev

¿Existe una forma preferida de cómo implementar una evaluación rápida (aproximada) del polinomio de interpolación de Chebyshev en una cuadrícula uniforme (dados los valores de función en los nodos de Chebyshev)? Mi problema es que la interpolación se vuelve lenta cuando aumenta el grado del polinomio de interpolación.

Las siguientes ideas me vinieron a la mente:

Intente adaptar las técnicas de FFT no uniforme (NFFT)
Use FFT para calcular los derivados en los nodos de Chebyshev, posiblemente después de ir primero a una cuadrícula más fina (Chebyshev). Luego use una interpolación cúbica por partes para la evaluación (aproximada).
Use alguna fórmula que solo use valores de función (y potencialmente derivados) en nodos de Chebyshev "cercanos" (esto está relacionado con una técnica NFFT específica).

interpolation fourier-analysis fftw Thomas Klimpel
fuente

¡Echa un vistazo a chebfun ! Es una biblioteca completa que se basa en representaciones de funciones por medio de polinomios de Chebyshev. Es de código abierto, altamente optimizado y bien mantenido y supongo que si existe una forma preferida para la evaluación puntual de un polinomio, entonces lo encontrará allí.

Jan

Respuestas:

¿Has pensado en usar la interpolación baricéntrica ? Una descripción detallada sobre cómo hacerlo eficientemente para los nodos de Chebyshev se da en la Sección 5 de este documento.

Esta es en realidad una evaluación exacta del interpolante de Chebyshev. Si está evaluando un polinomio de grado en nodos, el costo está en . $n$ $m$ $\mathcal O(nm)$

Actualizar

Otra alternativa, si tiene los coeficientes de Chebyshev de su polinomio interpolador, es utilizar el algoritmo de Clenshaw . Si solo tiene los valores de función en los nodos de Chebyshev, pero tiene que evaluar el polinomio varias veces, podría calcular los coeficientes con una FFT.

El algoritmo de Clenshaw es algo más rápido que la interpolación barcéntrica, ya que solo requiere adiciones y multiplicaciones, y que también se vectoriza bastante bien.

Pedro
fuente

Actualmente, lo hago precalculando los pesos relativos a los valores de función en los nodos de Chebyshev para un punto de evaluación específico, luego evalúo este punto para todas las interpolaciones que tengo que hacer (hay muchas, todas con nodos de Chebyshev idénticos y puntos de evaluación idénticos) , y luego pasar al siguiente punto de evaluación.

Thomas Klimpel

@ThomasKlimpel: ¿Cómo estás calculando los pesos? Si está utilizando nodos Chebyshev en , son solo o en los bordes. Si la velocidad es realmente esencial, he agregado el algoritmo Clenshaw a mi respuesta. En mi experiencia, es aproximadamente cuatro veces más rápido en código compilado.

[- 1, 1]

$[-1,1]$

\pm 1

$\pm 1$

\pm 1 / 2

$\pm 1/2$

Pedro