Wie kann ich eine ungleichmäßig abgetastete Funktion numerisch unterscheiden?

21

Standardformeln für endliche Differenzen können verwendet werden, um eine Ableitung unter der Annahme numerisch zu berechnen, dass Sie Funktionswerte an gleichmäßig beabstandeten Punkten haben, so dass h ≡ x k + 1 - x k eine Konstante ist. Was ist, wenn ich ungleichmäßig verteilte Punkte habe, sodass h jetzt von einem Paar benachbarter Punkte zum nächsten variiert? Offensichtlich kann ich noch eine erste Ableitung als f ′ ( x ) ≈ 1 berechnenf(xk)h≡xk+1−xkh, aber gibt es numerische Differenzierungsformeln bei höheren Ordnungen und Genauigkeiten, die sich an Variationen in der Gittergröße anpassen können?f′(x)≈1hk[f(xk+1)-f(xk)]

finite-difference discretization David Z
quelle
7
Sie können immer einen (stückweisen) Polynominterpolanten konstruieren, der durch Ihre Punkte geht, und diesen dann differenzieren.
JM
Oder Sie können die Finite-Differenzen-Formeln ohne die Vereinfachung rekonstruieren . Oft muss dies für die Integration getan werden, aber es ist wahrscheinlich, dass der Vorschlag von JM stabiler ist. h=xk+1-xk
rcollyer
Was ist das für eine Funktion?
mbq
Das Beispiel, das zu dieser Frage geführt hat, ist eine Funktion, die mit logarithmisch beabstandeten Werten abgetastet wurde. Die Berechnung der zweiten Ableitung der logarithmisch transformierten Daten liefert jedoch lustige Ergebnisse, und ich wollte, dass dies überprüft wird. Außerdem dachte ich, ich würde so allgemein wie möglich eine Frage stellen. xk=x0δk
David Z
1
Für mich wäre etwas, das nur für die erste und zweite Ableitung funktioniert, eine perfekte Antwort auf die Frage. Ich habe die Frage so geschrieben, wie ich es getan habe, um eine allgemeine Antwort zu ermöglichen, wenn jemand eine hatte, aber in der Praxis sind natürlich die ersten und zweiten Ableitungen am nützlichsten.
David Z

Antworten:

21

JMs Kommentar ist richtig: Sie können ein interpolierendes Polynom finden und es differenzieren. Es gibt andere Möglichkeiten, solche Formeln abzuleiten. In der Regel führen sie alle dazu, dass ein Van-der-Monde-System für die Koeffizienten gelöst wird. Dieser Ansatz ist problematisch, wenn die Finite-Differenz-Schablone eine große Anzahl von Punkten enthält, da die Vandermonde-Matrizen schlecht konditioniert werden. Ein numerisch stabilerer Ansatz wurde von Fornberg entwickelt und wird in einem zweiten Aufsatz von Fornberg klarer und allgemeiner erläutert .

Hier ist ein einfaches MATLAB-Skript , das die Fornberg-Methode zur Berechnung der Koeffizienten einer endlichen Differenznäherung für eine beliebige Ordnungsableitung mit einer beliebigen Menge von Punkten implementiert. Eine nette Erklärung finden Sie in Kapitel 1 von LeVeques Text über Methoden mit endlichen Differenzen .

Ein bisschen mehr zu FD-Formeln: Angenommen, Sie haben ein 1D-Raster. Wenn Sie den gesamten Satz von Gitterpunkten verwenden, um einen Satz von FD-Formeln zu bestimmen, entspricht die resultierende Methode dem Auffinden eines Interpolationspolynoms durch das gesamte Gitter und dem Differenzieren dieses Polynoms. Dieser Ansatz wird als spektrale Kollokation bezeichnet. Alternativ können Sie für jeden Gitterpunkt eine FD-Formel mit nur wenigen benachbarten Punkten bestimmen. Dies wird bei traditionellen Finite-Differenzen-Methoden durchgeführt.

Wie in den Kommentaren unten erwähnt, kann die Verwendung endlicher Differenzen sehr hoher Ordnung zu Schwingungen führen (das Runge-Phänomen), wenn die Punkte nicht sorgfältig ausgewählt werden.

David Ketcheson
quelle
3
Wenn Sie dagegen interpolierende Polynome verwenden, müssen Sie sich immer an Dinge wie das Runge-Phänomen erinnern, das möglicherweise mit Ihren Daten auftritt, wenn Ihre Daten pervers genug konfiguriert sind. Ich würde sagen, stückweise Polynome sind dafür weniger anfällig ...
JM
1
Ich frage mich, ob Koevs Werk und Fornbergs Technik in Beziehung stehen könnten.
David Ketcheson
1
Interessanterweise scheint es eine Ähnlichkeit zwischen Fornbergs Formeln und früheren Formeln zu geben, die von Lyness und Moler auf der Grundlage der klassischen Neville-Methode zur Erzeugung des Interpolationspolynoms entwickelt wurden. Es könnten tatsächlich die gleichen Formeln in unterschiedlicher Notation sein, aber ich habe nicht gründlich nachgesehen.
JM
2
Für die Polynominterpolation mit vielen Punkten müssen spezielle Punktverteilungen gut konditioniert werden. Im Allgemeinen wird für ungleichmäßige Punktverteilungen nicht empfohlen, das Interpolationspolynom zu interpolieren und dann zu differenzieren, da es stark schwingfähig sein kann (denken Sie an das von JM erwähnte "Runge-Phänomen"). Je nach Ihren Anforderungen ist es möglicherweise besser, nur kubische Splines zu verwenden, die für viele praktische Zwecke eine gute Antwort auf das Approximationsproblem der Approximation von Derivaten liefern können.
Allan P. Engsig-Karup
1
Gute Antwort. Nur zur Information wird in diesem Artikel ein alternativer Ansatz zu Fornbergs vorgestellt. Es folgt demselben Prinzip, gibt jedoch einen anderen Algorithmus an.
Davidhigh
2

Die obigen Antworten sind großartig, um Ihnen einen Code zur Verfügung zu stellen, aber theoretisch nicht so gut. Wenn Sie sich eingehender mit interpolierenden Polynomen befassen möchten, sehen Sie sich diese theoretische Behandlung anhand einiger konkreter Beispiele an:

Singh, Ashok K. und BS Bhadauria. "Finite Differenzformeln für ungleiche Teilintervalle unter Verwendung der Interpolationsformel von Lagrange." Internationale Zeitschrift für Mathematik und Analysis 3.17 (2009): 815-827. ( Link zum PDF )

Die Autoren verwenden die Lagrange-Interpolation (siehe Wikipedia- Artikel), um interpolierende 3-Punkt-, 4-Punkt- und 5-Punkt-Polynome sowie deren erste, zweite und dritte Ableitung zu berechnen. Sie haben auch Ausdrücke für den Kürzungsfehler, was wichtig ist, wenn ein endliches Differenzschema verwendet wird. Sie haben auch die generische Formel zum Berechnen von Interpolationspolynomen unter Verwendung von N Punkten.

Lagrange-Interpolationspolynome sind nützlich, da sie und ihre Ableitungen in dem Bereich, den Sie interpolieren, sehr genau sein können und keinen gleichmäßigen Gitterabstand annehmen. Aufgrund der Natur von Lagrange-Interpolationspolynomen können Sie niemals mehr Ordnungen von Ableitungen haben, als Sie Gitterpunkte haben.

Ich denke, dies beantwortet Ihre Frage gut, da das von mir zitierte Papier Formeln für beliebig hochrangige Finite-Differenzen-Schemata enthält, die von Natur aus für ungerade Gitter gelten und nur durch die Anzahl der Gitterpunkte begrenzt sind, die Sie in Ihre Schablone einfügen. Das Papier enthält auch eine allgemeine Formel für den Kürzungsfehler, anhand derer Sie das Lagrange-Interpolationspolynomschema mit anderen von Ihnen in Betracht gezogenen Schemata vergleichen können. Die Arbeit des Autors sollte die gleichen Ergebnisse liefern wie Fornbergs Methode. Ihr Beitrag besteht eigentlich nur darin, einige Beispiele zusammenzufassen und eine Schätzung des Fehlers zu geben, die Sie vielleicht nützlich finden.

Ich fand sowohl das Papier , das ich zitierte und Fornberg Arbeit für meine eigene Forschung nützlich zu sein.

jvriesem
quelle
1
Es tut mir leid, dass ich es angeben muss, aber Ihre zitierte Referenz sieht komisch aus - sie verwenden schreckliche Formeln und lösen nur einige Sonderfälle. Im Gegensatz dazu hat Fornberg das allgemeine Problem mit einem einfachen Algorithmus gelöst , und das bereits in den 80er Jahren. Siehe hier
davidhigh
Ein weiteres
Dokument zur
2
und ein letzter Kommentar zur Missachtung dieses Papiers. In einer "exzellenten theoretischen Behandlung" können Sie nicht 9 Referenzen haben, wobei sich 7 auf Ihre eigene Arbeit und eine auf ein allgemeines numerisches Analysebuch beziehen. Zumindest nicht, wenn Sie das Thema nicht selbst erfunden haben, was diese Autoren nicht haben.
Davidhigh
Du hast absolut recht. Ich würde nicht sagen, dass die Formeln schrecklich sind, obwohl sie verbessert werden könnten. Die Sonderfälle sind eigentlich als Tests / Vergleiche recht nett, und sie geben eine allgemeine Formel an, die mit der von Fornberg identisch sein muss.
Jvriesem
1
@jvriesem Bitte beachten Sie, dass die zitierte Arbeit im dritten Term in Gl. (15b)
Tarek,
-4

Die einfachste Methode ist die Verwendung endlicher Differenzenapproximationen.

Eine einfache Zweipunktschätzung besteht darin, die Steigung einer nahe gelegenen Sekantenlinie durch die Punkte (x, f (x)) und (x + h, f (x + h)) zu berechnen. [1] Wenn Sie eine kleine Zahl h wählen, stellt h eine kleine Änderung in x dar und kann entweder positiv oder negativ sein. Die Steigung dieser Linie beträgt

f(x+h)−f(x)h

Dieser Ausdruck ist Newtons Differenzquotient.

Die Steigung dieser Sekantenlinie unterscheidet sich von der Steigung der Tangentenlinie um einen Betrag, der ungefähr proportional zu h ist. Wenn sich h Null nähert, nähert sich die Steigung der Sekantenlinie der Steigung der Tangentenlinie. Daher ist die wahre Ableitung von f bei x die Grenze des Wertes des Differenzquotienten, wenn die Sekantenlinien immer näher an eine Tangentenlinie heranrücken

evion2011
quelle
1
Ich denke, Sie werden abgelehnt, weil David Zaslavsky die Differenzquotientenformel ausdrücklich erwähnt hat und die Frage lautet, ob es bessere Annäherungen gibt.
Dan
7
Auch, weil es sich um ein direktes Kopieren und Einfügen aus Wikipedia handelt , mit Ausnahme des Spam-Links, der ursprünglich Teil der Antwort war.
David Z