Gibt es eine bevorzugte Methode zur Implementierung einer schnellen (ungefähren) Auswertung des Chebyshev-Interpolationspolynoms auf einem einheitlichen Gitter (angesichts der Funktionswerte an den Chebyshev-Knoten)? Mein Problem ist, dass die Interpolation langsam wird, wenn der Grad des Interpolationspolynoms zunimmt.
Die folgenden Ideen kamen mir in den Sinn:
- Versuchen Sie, ungleichmäßige FFT-Techniken (NFFT) anzupassen
- Verwenden Sie FFT, um die Ableitungen an den Chebyshev-Knoten zu berechnen, möglicherweise nachdem Sie zuerst zu einem feineren (Chebyshev) Gitter gegangen sind. Verwenden Sie dann eine stückweise kubische Interpolation für die (ungefähre) Auswertung.
- Verwenden Sie eine Formel, die nur Funktionswerte (und möglicherweise Ableitungen) an "nahe gelegenen" Chebyshev-Knoten verwendet (dies hängt mit einer bestimmten NFFT-Technik zusammen).
interpolation
fourier-analysis
fftw
Thomas Klimpel
quelle
quelle
Antworten:
Haben Sie daran gedacht, die baryzentrische Interpolation zu verwenden ? Eine ausführliche Beschreibung, wie dies für Chebyshev-Knoten effizient durchgeführt werden kann, finden Sie in Abschnitt 5 dieses Dokuments.
Aktualisieren
Eine andere Alternative, wenn Sie die Chebyshev-Koeffizienten Ihres interpolatorischen Polynoms haben, ist die Verwendung des Clenshaw-Algorithmus . Wenn Sie nur die Funktionswerte an den Chebyshev-Knoten haben, das Polynom jedoch mehrmals auswerten müssen, können Sie die Koeffizienten mit einer FFT berechnen.
Der Clenshaw-Algorithmus ist etwas schneller als die Barycentric-Interpolation, da er nur Additionen und Multiplikationen erfordert und auch sehr gut vektorisiert.
quelle