Szybka (przybliżona) ocena wielomianu Czebyszewa

Czy istnieje preferowany sposób realizacji szybkiej (przybliżonej) oceny wielomianu interpolacji Czebyszewa na jednolitej siatce (biorąc pod uwagę wartości funkcji w węzłach Czebyszewa)? Moim problemem jest to, że interpolacja staje się wolna, gdy wzrasta stopień interpolacji wielomianu.

Przyszło mi do głowy następujące pomysły:

Spróbuj dostosować niejednolite techniki FFT (NFFT)
Użyj FFT, aby obliczyć pochodne w węzłach Czebeszewa, potencjalnie po pierwszym przejściu do dokładniejszej (Chebyshev) siatki. Następnie użyj częściowej interpolacji sześciennej do (przybliżonej) oceny.
Użyj formuły, która używa tylko wartości funkcji (i potencjalnie pochodnych) w „pobliskich” węzłach Czebyszewa (jest to związane z konkretną techniką NFFT).

interpolation fourier-analysis fftw

— Thomas Klimpel
źródło

Zobacz chebfun ! Jest to cała biblioteka oparta na reprezentacjach funkcji za pomocą wielomianów Czebyszewa. Jest to oprogramowanie typu open source, wysoce zoptymalizowane i dobrze utrzymane, i sądzę, że jeśli istnieje preferowany sposób punktowej oceny wielomianu, to tam go znajdziesz.

— stycznia

Czy myślałeś o zastosowaniu interpolacji barycentrycznej ? Szczegółowy opis tego, jak zrobić to skutecznie dla węzłów Czebyszewa, znajduje się w rozdziale 5 niniejszego dokumentu.

Jest to właściwie dokładna ocena interpolantu Czebyszewa. Jeśli oceniasz wielomian stopnia $n$ w $m$ węzły, koszt jest w $\mathcal O(nm)$ .

Aktualizacja

Inną alternatywą, jeśli masz współczynniki Czebyszewa wielomianu interpolacyjnego, jest użycie algorytmu Clenshaw . Jeśli masz tylko wartości funkcji w węzłach Czebyszewa, ale musisz kilkakrotnie ocenić wielomian, możesz obliczyć współczynniki za pomocą FFT.

Algorytm Clenshaw jest nieco szybszy niż interpolacja barycentryczna, ponieważ wymaga tylko dodawania i mnożenia oraz że całkiem ładnie wektoryzuje.

— Pedro
źródło

Obecnie robię to poprzez wstępne obliczenie wag w stosunku do wartości funkcji w węzłach Czebyszewa dla konkretnego punktu oceny, a następnie oceniam ten punkt dla wszystkich interpolacji, które muszę wykonać (jest ich wiele, wszystkie z identycznymi węzłami Czebyszewa i identycznymi punktami oceny) , a następnie przejdź do następnego punktu oceny.

— Thomas Klimpel

@ThomasKlimpel: Jak obliczasz wagi? Jeśli korzystasz z węzłów Czebyszewa na

[- 1, 1]

$[-1,1]$ są po prostu

\pm 1

$\pm 1$ lub

\pm 1 / 2

$\pm 1/2$ na krawędziach. Jeśli naprawdę najważniejsza jest szybkość, do odpowiedzi dodałem algorytm Clenshaw. Z mojego doświadczenia wynika, że w skompilowanym kodzie jest około cztery razy szybszy.

— Pedro