Schnelle (ungefähre) Auswertung des Chebyshev-Polynoms

9

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).
Thomas Klimpel
quelle
Schau dir chebfun an ! Es ist eine ganze Bibliothek, die auf Funktionsrepräsentationen mittels Chebyshev-Polynomen basiert. Es ist Open Source, hochoptimiert und gut gepflegt, und ich denke, wenn es einen bevorzugten Weg für die punktweise Bewertung eines Polynoms gibt, werden Sie ihn dort finden.
Januar

Antworten:

11

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.

nmO(nm)

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.

Pedro
quelle
Derzeit berechne ich die Gewichte relativ zu den Funktionswerten an den Chebyshev-Knoten für einen bestimmten Bewertungspunkt vor und bewerte diesen Punkt dann für alle Interpolationen, die ich durchführen muss (es gibt viele, alle mit identischen Chebyshev-Knoten und identischen Bewertungspunkten). und fahren Sie dann mit dem nächsten Bewertungspunkt fort.
Thomas Klimpel
[1,1]±1±1/2