Newton-Polynom

Im mathematischen Feld der numerischen Analyse ist ein Polynom von Newton, genannt nach seinem Erfinder Isaac Newton, das Interpolationspolynom für einen gegebenen Satz von Datenpunkten in der Form von Newton. Das Polynom von Newton wird manchmal das geteilte Unterschied-Interpolationspolynom von Newton genannt, weil die Koeffizienten des Polynoms mit geteilten Unterschieden berechnet werden.

Für jeden gegebenen Satz von Datenpunkten gibt es nur ein Polynom (des am wenigsten möglichen Grads), der sie alle durchführt. So ist es passender, von "der Form von Newton des Interpolationspolynoms" aber nicht "des Interpolationspolynoms von Newton" zu sprechen. Wie die Form von Lagrange ist es bloß eine andere Weise, dasselbe Polynom zu schreiben.

Definition

In Anbetracht einer Reihe von k + 1 Datenpunkte

:

wo keine zwei x dasselbe sind, ist das Interpolationspolynom in der Form von Newton eine geradlinige Kombination von Basispolynomen von Newton

:

mit den Basispolynomen von Newton definiert als

:

für und. Die Koeffizienten werden als definiert

:

wo

:

ist die Notation für geteilte Unterschiede.

So kann das Newton-Polynom als geschrieben werden

:

Das Newton-Polynom kann oben in einer vereinfachten Form ausgedrückt werden, wenn aufeinander folgend mit dem gleichen Raum eingeordnet werden. Die Notation für jeden und einführend, kann der Unterschied als geschrieben werden. So wird das Newton-Polynom oben:

::

wird das Newton Vorwärts Geteilte Unterschied-Formel genannt.

Wenn die Knoten als wiederbestellt werden, wird das Newton-Polynom:

:

Wenn mit x = und für, dann, ebenso unter Drogeneinfluss

sind::

wird das Newton Rückwärts Geteilte Unterschied-Formel genannt.

Bedeutung

Die Formel des Newtons ist von Interesse, weil es die aufrichtige Rate der Änderung seiner Rate der Änderung, usw. ist) an einem besonderem X-Wert. Die Formel des Newtons ist das Polynom von Taylor, das auf begrenzten Unterschieden statt sofortiger Raten der Änderung gestützt ist.

Hinzufügung neuer Punkte

Als mit anderen Unterschied-Formeln kann der Grad eines interpolierenden Polynoms von Newton durch das Hinzufügen von mehr Begriffen und Punkten vergrößert werden, ohne vorhandene zu verwerfen. Die Form von Newton hat die Einfachheit, dass die neuen Punkte immer an einem Ende hinzugefügt werden: Die Vorwärtsformel von Newton kann neue Punkte nach rechts, und Newton umgekehrt hinzufügen Formel kann neue Punkte nach links hinzufügen. Leider hängt die Genauigkeit der polynomischen Interpolation ab, wie nahe der interpolierte Punkt zur Mitte der x Werte des Satzes von verwendeten Punkten ist; da die Form von Newton immer neue Punkte an demselben Ende hinzufügt, kann eine Zunahme im Grad nicht verwendet werden, um die Genauigkeit überall, aber an diesem Ende zu vergrößern. Gauss, Stirling und Bessel alle entwickelten Formeln, um dieses Problem zu beheben.

Die Formel von Gauss fügt abwechselnd neue Punkte am verlassenen und richtige Enden hinzu, dadurch den Satz von Punkten in den Mittelpunkt gestellt in der Nähe von demselben Platz (in der Nähe vom bewerteten Punkt) haltend. Wenn so tuend es Begriffe von der Formel von Newton, mit Datenpunkten und X-Werten gebraucht, die in Übereinstimmung mit jemandes Wahl dessen umbenannt sind, welcher Datenpunkt als der Datenpunkt benannt wird.

Die Formel von Stirling bleibt in den Mittelpunkt gestellt über einen besonderen Datenpunkt für den Gebrauch, wenn der bewertete Punkt zu einem Datenpunkt näher ist als zu einer Mitte von zwei Datenpunkten. Die Formel von Bessel bleibt in den Mittelpunkt gestellt über eine besondere Mitte zwischen zwei Datenpunkten für den Gebrauch, wenn der bewertete Punkt zu einer Mitte näher ist als zu einem Datenpunkt. Sie erreichen das, indem sie manchmal den Durchschnitt von zwei Unterschieden verwenden, wo Newton oder Gauss gerade einen Unterschied verwenden würden. Stirling tut das in Begriffen des sonderbaren Grads; Bessels tut das in Begriffen des gleichen Grads. Das Rechnen und die Mittelwertbildung von zwei Unterschieden brauchen mit Extraarbeit nicht verbunden zu sein, da es durch die Formel im Voraus getan werden kann — ist der Ausdruck für den durchschnittlichen Unterschied nicht mehr kompliziert als dieser des einfachen Unterschieds.

Kräfte und Schwächen von verschiedenen Formeln

Die Eignung von Stirling, die Formeln von Bessel und Gauss hängen 1) von der Wichtigkeit vom kleinen durch durchschnittliche Unterschiede gegebenen Genauigkeitsgewinn ab; und 2) wenn größere Genauigkeit notwendig ist, ob der interpolierte Punkt an einem Datenpunkt oder an einer Mitte zwischen zwei Datenpunkten näher ist.

Im Allgemeinen können die Unterschied-Methoden eine gute Wahl sein, wenn man nicht weiß, wie viele Punkte, was Grad, Polynom zu interpolieren, für die gewünschte Genauigkeit erforderlich sein werden, und wenn man erst auf die geradlinige und andere Interpolation des niedrigen Grads aussehen will, nacheinander Genauigkeit durch den Unterschied in den Ergebnissen von zwei aufeinander folgenden polynomischen Graden beurteilend. Die Formel von Lagrange (nicht eine Unterschied-Formel) erlaubt, dass auch, aber zum folgenden höheren Grad gehend, ohne Arbeit nochmals zu tun, verlangt, dass der Wert jedes Begriffes — nicht ein Problem mit einem Computer, aber vielleicht ungeschickt mit einer Rechenmaschine registriert wird.

Anders als das ist Lagrange leichter zu rechnen als die Unterschied-Methoden, und ist (wahrscheinlich richtig) betrachtet von vielen als die beste Wahl, wenn man bereits das weiß, welcher polynomischer Grad erforderlich sein wird. Und wenn die ganze Interpolation an einem X-Wert mit nur den Datenpunkt-Y-Werten getan wird, die sich von einem Problem bis einen anderen ändern, wird die Formel von Lagrange so viel günstiger, den es beginnt, die einzige Wahl zu sein, zu denken.

Die Bequemlichkeit der Formel von Lagrange der Berechnung wird am besten durch sein "barycentric Formen" erreicht. Seine 2. Barycentric-Form könnte von allen am effizientesten sein, als sie einen Computer verwendet hat, aber seine 1. Barycentric-Form könnte günstiger sein, als sie eine Rechenmaschine verwendet hat.

Genauigkeit

Wenn ein besonderer Datenpunkt als dann benannt wird, weil sich der bewertete Punkt diesem Datenpunkt, die Unterschied-Formel-Begriffe nähert, nachdem der unveränderliche Begriff zur Null neigt. Deshalb ist die Formel von Stirling an seinem besten im Gebiet, wo es weniger erforderlich ist. Bessel ist an seinem besten, wenn der bewertete Punkt in der Nähe von der Mitte zwischen zwei Datenpunkten ist, und deshalb Bessel an seinem besten ist, wenn die zusätzliche Genauigkeit am meisten erforderlich ist. Also, wie man sagen konnte, war die Formel von Bessel die am meisten durchweg genaue Unterschied-Formel, und, im Allgemeinen, am meisten durchweg genau der vertrauten polynomischen Interpolationsformeln.

Es sollte hinzugefügt werden, dass, wenn Bessel oder Stirling gewinnen über Gauss und Lagrange ein bisschen Genauigkeit, es für diese Extragenauigkeit ungewöhnlich sein würde, erforderlich zu sein. Keiner sollte verlassen, Lagrange oder Gauss wegen seiner zu verwenden.

Wenn, mit Stirling oder Bessel, der letzte gebrauchte Begriff den Durchschnitt von zwei Unterschieden einschließt, dann wird ein mehr Punkt verwendet, als die oder anderen polynomischen Interpolationen von Newton für denselben polynomischen Grad verwenden würden. Also, in diesem Beispiel, Stirling oder Bessel stellt kein n-1 Grad-Polynom durch N-Punkte, aber, ist statt dessen Handelsgleichwertigkeit mit Newton für das bessere Zentrieren und die Genauigkeit, jenen Methoden manchmal potenziell größere Genauigkeit für einen gegebenen polynomischen Grad gebend als andere polynomische Interpolationen.

Die anderen Unterschied-Formeln, wie diejenigen von Stirling, Bessel und Gauss, können aus Newton abgeleitet werden, die Begriffe von Newton, mit Datenpunkten und X-Werten gebrauchend, die in Übereinstimmung mit der Wahl der x Null umbenannt sind, und haben auf der Tatsache gestützt, dass sie sich auf denselben Summe-Wert wie Newton belaufen müssen (Mit Stirling, der so ist, wenn polynomischer Grad gleich ist. Mit Bessel, der so ist, wenn polynomischer Grad seltsam ist).

Allgemeiner Fall

Für den speziellen Fall dessen, dort ist nah Satz von Polynomen, auch genannt die Polynome von Newton verbunden, die einfach die binomischen Koeffizienten für das allgemeine Argument sind. D. h. man ließ auch die Polynome von Newton durch geben

:

In dieser Form erzeugen die Polynome von Newton die Reihe von Newton. Das ist der Reihe nach ein spezieller Fall der allgemeinen Unterschied-Polynome, die die Darstellung von analytischen Funktionen durch verallgemeinerte Unterschied-Gleichungen erlauben.

Hauptidee

Das Beheben eines Interpolationsproblems führt zu einem Problem in der geradlinigen Algebra, wo wir ein System von geradlinigen Gleichungen lösen müssen. Mit einer Standardmonom-Basis für unser Interpolationspolynom bekommen wir die sehr komplizierte Matrix von Vandermonde. Indem wir eine andere Basis, die Basis von Newton wählen, bekommen wir ein System von geradlinigen Gleichungen mit einem viel einfacheren tiefer Dreiecksmatrix, die schneller gelöst werden kann.

Für k + 1 Datenpunkte bauen wir die Basis von Newton als

:

Das Verwenden dieser Polynome als eine Basis, weil wir lösen

müssen:

\begin {bmatrix }\

1 & & \ldots & & 0 \\

1 & x_1-x_0 & & & \\

1 & x_2-x_0 & (x_2-x_0) (x_2-x_1) & & \vdots \\

\vdots & \vdots & & \ddots & \\

1 & x_k-x_0 & \ldots & \ldots & \prod_ {j=0} ^ {k-1} (x_k - x_j)

\end {bmatrix }\

\begin {bmatrix }\

a_0 \\

\vdots \\

a_ {k }\

\end {bmatrix }\\begin {bmatrix }\

y_0 \\

\vdots \\

y_ {k }\

\end {bmatrix }\

</Mathematik>

das polynomische Interpolationsproblem zu beheben.

Dieses Gleichungssystem kann rekursiv durch das Lösen gelöst werden

:

Polynom von Taylor

Die Grenze des Polynoms von Newton, wenn alle Knoten zusammenfallen, ist ein Polynom von Taylor,

weil die geteilten Unterschiede Ableitungen werden.

:

\lim_ {(x_0, \dots, x_n) \to (z, \dots, z) }\

f [x_0] + f [x_0, x_1] \cdot (\xi-x_0) + \dots + f [x_0, \dots, x_n] \cdot (\xi-x_0) \cdot\dots\cdot (\xi-x_ {n-1})

</Mathematik>

::

= f (z) + f' (z) \cdot (\xi-z) + \dots + \frac {f^ {(n)} (z)} {n! }\\cdot (\xi-z) ^n

</Mathematik>

Anwendung

Wie aus der Definition der geteilten Unterschiede gesehen werden kann, können neue Datenpunkte zur Datei hinzugefügt werden, um ein neues Interpolationspolynom zu schaffen, ohne die alten Koeffizienten wiederzuberechnen. Und wenn Daten Änderungen anspitzen, müssen wir nicht gewöhnlich alle Koeffizienten wiederberechnen. Außerdem, wenn die x gleich weit entfernt verteilt werden, wird die Berechnung der geteilten Unterschiede bedeutsam leichter. Deshalb wird die Newton-Form des Interpolationspolynoms gewöhnlich über die Form von Lagrange zu praktischen Zwecken bevorzugt, obwohl, in der wirklichen Tatsache (und gegen weit verbreitete Ansprüche), Lagrange auch Berechnung der folgenden höheren Grad-Interpolation erlaubt, ohne vorherige Berechnungen nochmals zu tun — und beträchtlich leichter ist zu bewerten.

Beispiel

Die geteilten Unterschiede können in der Form eines Tisches geschrieben werden. Zum Beispiel, für eine Funktion soll auf Punkten interpoliert werden. Schreiben Sie

:

x_0 & f (x_0) & & \\

& & {f (x_1)-f (x_0) \over x_1 - x_0} & \\

x_1 & f (x_1) & &


Zwang / Bulbophyllum beccarii
Impressum & Datenschutz