Evaluasi polebom Chebyshev yang cepat (perkiraan)

9

Apakah ada cara yang disukai bagaimana menerapkan evaluasi cepat (perkiraan) dari polinomial interpolasi Chebyshev pada grid yang seragam (diberi nilai fungsi pada node Chebyshev)? Masalah saya adalah interpolasi menjadi lambat ketika tingkat polinomial interpolasi meningkat.

Ide-ide berikut muncul di benak saya:

  • Cobalah untuk menyesuaikan teknik FFT (NFFT) yang tidak seragam
  • Gunakan FFT untuk menghitung derivasi di node Chebyshev, berpotensi setelah pertama kali pergi ke grid yang lebih halus (Chebyshev). Kemudian gunakan interpolasi kubik piecewise untuk evaluasi (perkiraan).
  • Gunakan beberapa rumus yang hanya menggunakan nilai fungsi (dan berpotensi turunan) di node Chebyshev "terdekat" (ini terkait teknik NFFT tertentu).
interpolation fourier-analysis fftw Thomas Klimpel
sumber
Lihatlah chebfun ! Ini adalah seluruh perpustakaan yang mendasarkan pada representasi fungsi melalui polinomial Chebyshev. Ini adalah open source, sangat dioptimalkan, dan dipelihara dengan baik dan saya kira bahwa jika ada cara yang disukai untuk evaluasi polinomial, maka Anda akan menemukannya di sana.
Jan

Jawaban:

11

Pernahkah Anda berpikir untuk menggunakan Interpolasi Barycentric ? Penjelasan rinci tentang cara melakukannya secara efisien untuk node Chebyshev diberikan dalam Bagian 5 dari makalah ini .

nmHAI(nm)

Memperbarui

Alternatif lain, jika Anda memiliki koefisien Chebyshev dari polinomial interpolasi Anda, adalah dengan menggunakan algoritma Clenshaw . Jika Anda hanya memiliki nilai fungsi di node Chebyshev, tetapi harus mengevaluasi polinomial beberapa kali, Anda bisa menghitung koefisien dengan FFT.

Algoritma Clenshaw agak lebih cepat daripada interpolasi Barycentric karena hanya membutuhkan penambahan dan perkalian, dan juga vektorisasi dengan cukup baik.

Pedro
sumber
Saat ini, saya melakukannya dengan menghitung bobot relatif terhadap nilai-nilai fungsi di node Chebyshev untuk titik evaluasi tertentu, kemudian mengevaluasi titik ini untuk semua interpolasi yang harus saya lakukan (ada banyak, semua dengan node Chebyshev identik dan poin evaluasi yang identik) , dan kemudian beralih ke titik evaluasi selanjutnya.
Thomas Klimpel
[-1,1]±1±1/2