Szybka (przybliżona) ocena wielomianu Czebyszewa

9

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

Odpowiedzi:

11

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 stopnian w m węzły, koszt jest w 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]są po prostu ±1lub ±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