Finden Sie das Lagrange-Interpolationspolynom. Lagrange-Interpolationsformel. Approximation der in einer Tabelle angegebenen Funktionen

n ist die Anzahl der Knoten.

Die Aufgabe der Interpolation besteht darin, eine Funktion zu finden, die an den Punkten die gleichen Werte annimmt.

Es wird davon ausgegangen, dass keiner der Werte gleich ist. Die Punkte werden Interpolationsknoten genannt. Die Interpolationsknoten müssen nicht gleichmäßig auf dem Segment [ verteilt sein.

Die Funktion wird als Funktionsinterpolant bezeichnet.

Wenn der Wert im Intervall [ gesucht wird, wird diese Aufgabe normalerweise als Interpolationsaufgabe bezeichnet, und wenn er außerhalb dieses Intervalls liegt, ist dies die Extrapolationsaufgabe.

Das Problem hat viele Lösungen, denn Durch die gegebenen Punkte i=0, 1,..., n können unendlich viele Kurven gezeichnet werden, von denen jede der Graph einer Funktion ist, für die alle Bedingungen (1.2) erfüllt sind.

Je nach Zweck der Näherung kommt entweder Interpolation (Punktnäherung) oder Näherung zum Einsatz. Approximation ist das Ersetzen einer Tabellenfunktion durch eine Funktion, die eine begrenzte Abweichung von der Funktion im betrachteten Segment aufweist.

Interpolationsbedingung:

(1.2)

Wobei a der Vektor unbekannter Koeffizienten ist.

Normalerweise ist die Art im Voraus bekannt. Um das Interpolationsproblem zu lösen, wird ein Koeffizient benötigt.

Das Lösen des Interpolationsproblems bedeutet, für gegebene und zu finden.

IN Gesamtansicht Das System repräsentiert das System nichtlineare Gleichungen und hat oft keine Lösungen für große n.

Die erste Methode zur Lösung des Interpolationsproblems ist die Lagrange-Methode.

Die einfachste und am häufigsten verwendete Funktion ist das Polynom:

(1.3)

wobei , , , …, der Polynomkoeffizient ist,

m ist der Grad des approximierenden Polynoms.

Interpolation besteht im ungefähren Ersetzen einer in einer Tabelle angegebenen Funktion durch eine Funktion, die dieselben Werte wie die Funktion annimmt.

Alle Interpolationsmethoden können in lokale und globale unterteilt werden. Bei der globalen Interpolation wird ein einziges Polynom über das gesamte Intervall [ gefunden. Globale Interpolationsmethoden werden normalerweise für Funktionen verwendet, die durch eine kleine Anzahl von Punkten definiert sind, da mit zunehmender Anzahl von Punkten die Ordnung des Interpolationspolynoms zunimmt, was sich negativ auf die Glätte der resultierenden Funktion auswirkt. Eine polynomische Näherung, die alle Knoten der Tabelle gleichzeitig verwendet (globale Interpolation), hat einen erheblichen Nachteil – die Möglichkeit, dass in den Intervallen zwischen den Knoten des Gitters große Extrema auftreten. Diese. Das Interpolationspolynom kann Schwankungen aufweisen, die für die Originaldaten nicht charakteristisch sind. Darüber hinaus kommt es mit zunehmendem Grad des Polynoms zu einer schnellen Anhäufung von Rundungsfehlern. Um diese unerwünschten Effekte zu vermeiden, wird in der Praxis die lokale Interpolation eingesetzt. . Bei der lokalen Interpolation wird für jedes Intervall ein eigenes Polynom gebildet. Bei lokaler Interpolation die Anzahl der Knoten von großer Wichtigkeit hat nicht.

Betrachten wir einige Arten der lokalen und globalen Interpolation.

Lokale Interpolation:

1. Stückweise lineare Interpolation

2. Interpolation durch Splines

Globale Interpolation:

1. Lagrange-Polynom

2. Newtons Polynom

GLOBALE INTERPOLATION

Interpolation durch Lagrange-Polynom

Bei der globalen Interpolation wird über das gesamte Intervall ein einzelnes Polynom gebildet. Eine der Formen, das Interpolationspolynom für die globale Interpolation zu schreiben, ist das Lagrange-Polynom:

Das Lagrange-Interpolationspolynom n-ten Grades ist eine Linearkombination der grundlegenden Lagrange-Polynome:

Das heißt, das Lagrange-Polynom:

(2.3)

Das Polynom erfüllt die Bedingung

Diese Bedingung bedeutet, dass das Polynom für alle gleich Null ist, außer , d. h. , , … , sind die Wurzeln dieses Polynoms. Somit ist der Grad des Polynoms gleich n, und bei verschwinden alle Terme in der Summe, mit Ausnahme des Termes mit der Zahl i=j, gleich .

Am Punkt nimmt er den Wert 1 und an den anderen Stützpunkten den Wert 0 an. Daher nimmt das ursprüngliche Polynom an diesem Punkt den Wert an

(2.4)

Ausdruck (2.1) gilt sowohl für Knoten mit gleichem Abstand als auch für Knoten mit unterschiedlichem Abstand.

Das Lagrange-Polynom enthält explizit die Funktionswerte an den Interpolationsknoten und ist daher nützlich, wenn sich die Funktionswerte ändern, die Interpolationsknoten jedoch unverändert bleiben. Die Anzahl der arithmetischen Operationen, die zur Konstruktion eines Lagrange-Polynoms erforderlich sind, ist proportional und für alle Notationsformen am kleinsten. Zu den Nachteilen dieser Notationsform gehört, dass bei einer Änderung der Anzahl der Knoten die gesamte Berechnung erneut durchgeführt werden muss.

2.2. Newton-Polynom

Die Funktion g(x) sei mit einer beliebigen Schrittweite gegeben und die Punkte der Wertetabelle seien in beliebiger Reihenfolge nummeriert.

Newtons Polynom basiert stark auf dem Konzept der geteilten Differenzen.

Die geteilten Differenzen nullter Ordnung stimmen mit den Werten der Funktion an den Knoten überein. Die geteilten Differenzen erster Ordnung werden anhand der geteilten Differenzen nullter Ordnung definiert:

Die geteilten Differenzen der k-ten Ordnung werden anhand der geteilten Differenz der Ordnung definiert:

Um die Genauigkeit der Interpolation zu verbessern, können der Summe neue Mitglieder hinzugefügt werden, was die Verbindung zusätzlicher Knoten erfordert. Gleichzeitig spielt es für die Newton-Formel keine Rolle, in welcher Reihenfolge neue Knoten verbunden werden, während für das Lagrange-Polynom alle Berechnungen erneut durchgeführt werden müssen, wenn neue Knoten hinzugefügt werden.

Nehmen wir an, dass der Grad des Polynoms um eins erhöht werden muss, indem der Tabelle ein weiterer Knoten hinzugefügt wird. Zur Berechnung genügt die Addition zu nur einem Term

LOKALE INTERPOLATION

3.1. Stückweise lineare Interpolation.

Eine der am häufigsten verwendeten und einfachsten Arten der lokalen Interpolation ist die stückweise lineare Interpolation, bei der jeweils zwei Punkte und eine Tabellenfunktion durch gerade Liniensegmente verbunden werden (d. h. es wird ein Polynom ersten Grades gezeichnet).

	(3.3)
	(3.4)

Die stückweise lineare Interpolation ist die einfachste und wird daher häufig zur Berechnung von Werten zwischen Interpolationsknoten verwendet. Um eine Interpolationsbeziehung zu konstruieren, die in weiteren wissenschaftlichen und technischen Berechnungen verwendet wird, werden normalerweise komplexere Interpolationsmethoden verwendet.

3.2. Spline-Interpolation

Manchmal ist es erforderlich, die Kontinuität nicht nur der Interpolationsfunktion, sondern auch der erforderlichen Anzahl ihrer Ableitungen sicherzustellen; hierfür greift man auf die Spline-Interpolation zurück.

Spline ist eine Funktion, deren Definitionsbereich in eine endliche Anzahl von Segmenten unterteilt ist, auf denen der Spline jeweils mit einem algebraischen Polynom übereinstimmt. Der maximale Grad der verwendeten Polynome wird als Grad des Splines bezeichnet.

Die Vorteile der Spline-Interpolation gegenüber herkömmlichen Interpolationsverfahren liegen in der Konvergenz und Stabilität des Berechnungsprozesses. In der Praxis werden am häufigsten kubische Splines verwendet – Splines dritten Grades mit einer stetigen, zumindest ersten Ableitung. In diesem Fall wird der Wert als Steigung des Splines am Punkt (Knoten) bezeichnet.

Teilen wir das Segment in N gleiche Segmente [ , ], wobei , i=0,1,…,N-1.

Wenn die Knoten , , auf die Werte gesetzt werden, die der kubische Spline annimmt, dann hat er auf dem Teilsegment [ , ] die Form:

(3.3)

Tatsächlich lässt sich dies leicht durch Berechnung und an den Punkten überprüfen:

Es kann bewiesen werden, dass, wenn ein Polynom dritten Grades an den Punkten die Werte annimmt bzw. an diesen Punkten Ableitungen hat, es mit dem Polynom (3.3) übereinstimmt.

Um also einen kubischen Spline auf einem Segment festzulegen, müssen am Knoten die Werte i=0,1…,N in N+1 festgelegt werden.

INTERPOLATIONSFEHLER

Bei der Interpolation erhalten Funktionen immer einen Fehler, der aus dem Fehler der Methode selbst und Rundungsfehlern besteht.

Fehler bei der Approximation einer Funktion durch ein Interpolationspolynom n. Grad am Punkt x wird durch die Differenz bestimmt.

Hier ist die Ableitung (n+1) der Ordnung der Funktion an einem bestimmten Punkt, und die Funktion ist definiert als

dann folgt eine Schätzung für den Interpolationsfehler.

(4.4)

Der spezifische Wert des Fehlers am Punkt x hängt offensichtlich vom Wert der Funktion an diesem Punkt ab. Die qualitative Natur der Abhängigkeit ist in Abbildung 2 dargestellt.

Aus der Abbildung ist ersichtlich, dass der Interpolationsfehler umso höher ist, je näher der Punkt x an den Enden des Segments liegt. Außerhalb des Interpolationssegments (d. h.

bei Extrapolation) steigt schnell an, sodass der Fehler deutlich zunimmt.

Figur 2

Aufgrund des beschriebenen Fehlerverhaltens kann die globale Interpolation in manchen Fällen zu einem völlig unbefriedigenden Ergebnis führen.

5. BEISPIEL FÜR FUNKTIONSINTERPOLATION DURCH LAGRANGE- UND NEWTON-POLYNOMIALE

Um ein Polynom zu finden, das an bestimmten Punkten die gewünschten Werte annimmt, kann das Mathcad-Paket verwendet werden. Betrachten Sie als Beispiel das Problem, ein Lagrange-Polynom zu finden, das die gegebenen Anfangsdaten erfüllt.

Lassen Sie uns das Lagrange-Polynom im Mathcad-Paket erstellen:

Ausgangsdaten:

In der Rechenpraxis muss man sich oft mit Funktionen befassen, die durch Tabellen ihrer Werte für eine endliche Menge von Werten definiert sind X : .

Bei der Lösung des Problems ist es notwendig, die Werte zu verwenden
für Zwischenwerte des Arguments. In diesem Fall wird eine Funktion Ф(x) erstellt, die für Berechnungen an bestimmten Punkten einfach genug ist X 0 , X 1 ,...,X N , sogenannte Interpolationsknoten, nimmt Werte an und an anderen Punkten des Segments (x 0 ,x n), die zum Definitionsbereich gehören
, stellt ungefähr die Funktion dar
mit einer gewissen Genauigkeit.

Bei der Lösung des Problems handelt es sich in diesem Fall um eine Funktion
operieren mit der Funktion Ф(x). Die Aufgabe, eine solche Funktion Ф(x) zu konstruieren, wird als Interpolationsproblem bezeichnet. Am häufigsten liegt die Interpolationsfunktion Ф(x) in Form eines algebraischen Polynoms vor.

1. Interpolationspolynom

Für jede Funktion
definiert am [ a,b] und eine beliebige Menge von Knoten X 0 , X 1 ,...,X N (X ich
[a,b], X ich X J für mich j) unter algebraischen Polynomen mit einem Grad von höchstens n gibt es ein eindeutiges Interpolationspolynom Ф(x), das in der Form geschrieben werden kann:

, (3.1)

Wo
ist ein Polynom n-ten Grades, das folgende Eigenschaft hat:

Für ein Interpolationspolynom das Polynom
sieht aus wie:

Dieses Polynom (3.1) löst das Interpolationsproblem und wird Lagrange-Interpolationspolynom genannt.

Betrachten Sie als Beispiel eine Funktion des Formulars
auf dem Intervall
tabellarisch dargestellt.

Es ist notwendig, den Wert der Funktion am Punkt x-2,5 zu bestimmen. Wir verwenden hierfür das Lagrange-Polynom. Basierend auf den Formeln (3.1 und 3.3) schreiben wir dieses Polynom explizit:

(3.4).

Wenn wir dann die Anfangswerte aus unserer Tabelle in die Formel (3.4) einsetzen, erhalten wir

Das erhaltene Ergebnis entspricht der Theorie, d.h. .

1. Lagrange-Interpolationsformel

Das Lagrange-Interpolationspolynom kann in einer anderen Form geschrieben werden:

(3.5)

Das Schreiben eines Polynoms in der Form (3.5) ist für die Programmierung bequemer.

Bei der Lösung des Interpolationsproblems wird der Wert N heißt die Ordnung des interpolierenden Polynoms. In diesem Fall ist, wie aus den Formeln (3.1) und (3.5) hervorgeht, die Anzahl der Interpolationsknoten immer gleich n+1 und Bedeutung X, für den der Wert ermittelt wird
, muss im Bereich der Interpolationsknoten liegen diese.

. (3.6)

In einigen praktischen Fällen die gesamte bekannte Anzahl von Interpolationsknoten M kann größer sein als die Ordnung des Interpolationspolynoms N.

In diesem Fall ist es vor der Durchführung des Interpolationsverfahrens gemäß Formel (3.5) erforderlich, diejenigen Interpolationsknoten zu bestimmen, für die die Bedingung (3.6) gilt. Es ist zu beachten, dass bei der Ermittlung des Wertes der kleinste Fehler erzielt wird X in der Mitte des Interpolationsgebiets. Um dies sicherzustellen, wird folgende Vorgehensweise vorgeschlagen:

Der Hauptzweck der Interpolation besteht darin, tabellarische Funktionswerte für nicht-knotenförmige (Zwischen-)Argumentwerte zu berechnen, weshalb Interpolation oft als „die Kunst, Tabellen zwischen Zeilen zu lesen“ bezeichnet wird.

Die Probe experimenteller Daten ist eine Reihe von Daten, die den Prozess der Änderung des gemessenen Signals während einer bestimmten Zeit (oder relativ zu einer anderen Variablen) charakterisieren. Um eine theoretische Analyse des gemessenen Signals durchzuführen, muss eine Näherungsfunktion gefunden werden, die einen diskreten Satz experimenteller Daten mit einer kontinuierlichen Funktion verbindet – einem Interpolationspolynom N -Grad. Eine Möglichkeit, ein gegebenes Interpolationspolynom n-Grades darzustellen, besteht darin, ein Polynom in der Lagrange-Form zu verwenden.

Interpolationspolynom in Form vonLagrangeist eine mathematische Funktion, mit der Sie ein Polynom schreiben können N -Grad, der alle gegebenen Punkte aus einer Reihe von empirisch oder methodisch ermittelten Werten verbindet zufällige Probe zu verschiedenen Zeitpunkten mit einem nicht konstanten Zeitschritt der Messungen.

1. Interpolationsformel von Lagrange

Im Allgemeinen ist das Interpolationspolynomin der Lagrange-Form wird wie folgt geschrieben:

Wo ˗ Polynomgrad;

˗ der Wert des Wertes der Interpolationsfunktion am Punkt ;

˗ Grundpolynome (Lagrange-Multiplikator), die durch die Formel bestimmt werden:

Zum Beispiel das Interpolationspolynomin der Lagrange-Form durch drei gegebene Punkte, wird in folgender Form geschrieben:

Das Lagrange-Polynom enthält explizit die Funktionswerte an den Interpolationsknoten und ist daher nützlich, wenn sich die Funktionswerte ändern, die Interpolationsknoten jedoch unverändert bleiben. Die Anzahl der arithmetischen Operationen, die zur Konstruktion des Lagrange-Polynoms erforderlich sind, ist proportional zuund ist für alle Notationsformen die kleinste. Zu den Nachteilen dieser Schreibweise gehört die Tatsache, dass bei der Konstruktion eines Polynoms vom Grad n + 1 die Information über das vorherige Polynom vom Grad n vollständig verloren geht, d.h. Bei einer Änderung der Anzahl der Knoten muss die gesamte Berechnung erneut durchgeführt werden.

2. Fehler des Interpolationspolynoms in der Lagrange-Form

Betrachten Sie die Funktion f(x ), die auf dem betrachteten Segment stetig und differenzierbar ist. Interpolationspolynom L (x) in der Lagrange-Form nimmt Punkte anFunktionssollwerte. An anderen Stellen das Interpolationspolynom L(x) vom Funktionswert verschieden f(x) um den Betrag Restmitglied , der den absoluten Fehler der Lagrange-Interpolationsformel bestimmt:

A Der absolute Fehler der Lagrange-Interpolationsformel wird wie folgt bestimmt:

wo n ˗ Polynomgrad

Variable stellt die Obergrenze des Modulwerts dar (n+1)te Ableitung der Funktion f(x) auf einem gegebenen Intervall

Der Interpolationsfehler der Lagrange-Methode hängt von den Eigenschaften der Funktion ab f(x) und auch aus der Lage der Interpolationsknoten und dem Punkt X. Wenn der Fehler nicht die erforderliche Genauigkeit erreicht, müssen Sie das Segment in Teile aufteilen und jeden Teil separat interpolieren – stückweise Interpolation.

Auswahl der Interpolationsknoten

Mit Hilfe einer richtigen Wahl der Knoten kann man den Wert minimierenbei der Fehlerschätzung, wodurch die Interpolationsgenauigkeit verbessert wird. Dieses Problem kann mit dem Tschebyscheff-Polynom gelöst werden:

Als Knoten nehmen Sie die Wurzeln dieses Polynoms, also die Punkte:

3. Technik zur Berechnung eines Polynoms in der Lagrange-Form

Der Algorithmus zur Berechnung eines Polynoms in der Lagrange-Form ermöglicht es uns, die Aufgaben der Bestimmung der Koeffizienten und der Berechnung der Werte des Polynoms für zu trennen verschiedene Werte Streit:

1. Eine Probe von N -Punkte, einschließlich der Werte der Funktion und der Werte des Funktionsarguments.

2. Ein Polynom n-Grades wird in der Lagrange-Form mit der folgenden Formel berechnet:

Algorithmus zur Berechnung eines Polynoms in der Form Lagrange in Abbildung 1 dargestellt.

Technik zur Berechnung eines Polynoms in der Form Lagrange

Angenommen, eine Funktion sei auf einem Segment in einer Folge von Knoten mit ihren Werten angegeben, wobei. Das Problem der algebraischen Interpolation besteht darin, ein Gradpolynom zu konstruieren, das die Interpolationsbedingung erfüllt:.

Es ist bekannt, dass es ein eindeutiges Polynom mit einem Grad von nicht höherem Grad gibt, das an den Anfangspunkten die angegebenen Werte annimmt. Die Polynomkoeffizienten lassen sich aus dem Gleichungssystem ermitteln:

Die Determinante dieses Systems ist die Vandermonde-Determinante, und daher hat das System eine einzigartige Lösung.

Beispiel. Konstruieren Sie ein Interpolationspolynom, das mit der Funktion übereinstimmt an Punkten.

Lösung. Lassen , also haben wir

Deshalb bei.

Lagrange-Polynom

Wir suchen nach einem Polynom in Form einer Linearkombination von Gradmengen :.

In diesem Fall benötigen wir, dass jedes Polynom an allen Interpolationsknoten außer einem ist, wo es gleich 1 ist. Es ist leicht zu überprüfen, ob diese Bedingungen von einem Polynom der Form erfüllt werden

.

Wirklich, . Der Akkumulator des Ausdrucks ist 0. Analog erhalten wir:

,

Wenn wir diese Formeln in das ursprüngliche Polynom einsetzen, erhalten wir:

Diese Formel wird als Lagrange-Interpolationspolynom bezeichnet.

Beispiel. Konstruieren Sie das Lagrange-Interpolationspolynom, das mit der Funktion an den Punkten übereinstimmt

.

Lösung. Machen wir einen Tisch

Wenn wir diese Werte in die Lagrange-Formel einsetzen, erhalten wir:

Wenn die Funktion bis einschließlich der dritten Ordnung stetig differenzierbar ist, dann hat der Restterm des Interpolationspolynoms in der Lagrange-Form die Form

Dabei handelt es sich um einen inneren Punkt des minimalen Segments, das Interpolationsknoten und einen Punkt enthält.

Newton-Polynom mit endlichen Differenzen

Betrachten Sie den Fall äquidistanter Interpolationsknoten, d. h. einen Schritt.

Lassen Sie uns das Konzept der endlichen Differenzen einführen. Lassen Sie die Werte der Funktion an den Knoten bekannt sein. Bilden Sie die Differenz zwischen den Werten der Funktion:

Diese Unterschiede werden als Unterschiede erster Ordnung bezeichnet.

Wir können Differenzen zweiter Ordnung machen:

Unterschiede der k-ten Ordnung werden analog zusammengestellt:

Wir drücken die endlichen Differenzen direkt durch den Funktionswert aus:

Somit können wir für jedes k schreiben:

Schreiben wir diese Formel für die Differenzwerte am Knoten:

Mithilfe endlicher Differenzen kann man bestimmen

Fahren wir mit der Konstruktion des Newtonschen Interpolationspolynoms fort. Wir werden dieses Polynom in der Form suchen

Der Polynomgraph muss durch die angegebenen Knoten verlaufen, d. h. . Wir verwenden diese Bedingungen, um die Koeffizienten des Polynoms zu ermitteln:

Lassen Sie uns die Koeffizienten hier ermitteln:

Somit hat die Formel für jeden -ten Koeffizienten die Form

.

Wenn wir diese Formeln in den Newton-Polynomausdruck einsetzen, erhalten wir die folgende Form:

Die resultierende Formel kann in einer anderen Form geschrieben werden. Dazu führen wir eine Variable ein.

In diesem Fall

Unter Berücksichtigung dieser Beziehungen kann die Newton-Polynomformel geschrieben werden als

Der resultierende Ausdruck kann die gegebene Funktion über das gesamte Segment der Argumentänderung annähern. Es ist jedoch sinnvoller (im Hinblick auf die Erhöhung der Berechnungsgenauigkeit und die Reduzierung der Anzahl der Terme in der resultierenden Formel), sich auf den Fall zu beschränken, also diese Formel für alle zu verwenden. In anderen Fällen anstelle von Accept if at. In diesem Fall kann das Interpolationspolynom geschrieben werden als

Die resultierende Formel wird Newtons erstes Interpolationspolynom für die Vorwärtsinterpolation genannt. Diese Interpolationsformel wird normalerweise verwendet, um die Werte der Funktion an den Punkten der linken Hälfte des betrachteten Segments zu berechnen. Dies wird wie folgt erklärt: Die Differenzen werden außerdem über die Werte der Funktion berechnet. Aus diesem Grund können wir für große x-Werte keine höheren Ordnungen berechnen.

Für die rechte Hälfte des betrachteten Segments ist es besser, die Unterschiede von rechts nach links zu berechnen. In diesem Fall kann das Newtonsche Interpolationspolynom in der Form erhalten werden:

Die resultierende Formel wird als zweites Rückwärtsinterpolationspolynom bezeichnet.

Beispiel. Berechnen Sie mithilfe des Newton-Interpolationspolynoms, wobei die Funktion in der Tabelle angegeben ist

Lösung. Erstellen Sie eine Tabelle mit endlichen Differenzen.

Zur Berechnung setzen wir dann und das Newtonsche Interpolationspolynom ein

Beispiel. Die Tabelle ist gegeben. Finden .

Bei der Berechnung setzen wir

.

Bei der Berechnung setzen wir

.

Schätzen wir die Fehler von Newtons Formeln vorwärts und rückwärts ab:

Näherungsformeln zur Differentiation basieren auf Newtons erster Interpolationsformel. Newtons Interpolationspolynom hat die Form

Durch Multiplikation der Binome erhalten wir

als , Das

Ebenso können Ableitungen von Funktionen beliebiger Ordnung berechnet werden.

In einigen Fällen ist es erforderlich, Ableitungen von Funktionen an den Haupttabellenpunkten zu finden. Da der Tabellenwert als Anfangswert betrachtet werden kann, gilt Folgendes:

Für die Ableitung des Newton-Polynoms erster Ordnung kann der Fehler nach der Formel berechnet werden ,

Wo ist die Anzahl der endlichen Differenzen im Newton-Polynom?

Beispiel. Finden Sie eine in einer Tabelle angegebene Funktion.

Lösung.

Wenn wir den Fehler berechnen, erhalten wir:

.

Wirklich, .

Somit stimmen die Ergebnisse bis zur vierten Ziffer überein.

Wir werden ein Interpolationspolynom in der Form konstruieren

Wo gibt es höchstens Gradpolynome? P, mit der folgenden Eigenschaft:

Tatsächlich ist in diesem Fall das Polynom (4.9) an jedem Knoten x j, j=0,1,…n, ist gleich dem entsprechenden Wert der Funktion y j, d.h. ist eine Interpolation.

Konstruieren wir solche Polynome. Da für x=x 0 ,x 1 ,…x i -1 ,x i +1 ,…x n , kann wie folgt faktorisiert werden

wobei c eine Konstante ist. Aus der Bedingung ergibt sich das

Interpolationspolynom (4.1) in der Form geschrieben

wird das Lagrange-Interpolationspolynom genannt.

Ungefährer Wert einer Funktion an einem Punkt X *, berechnet mit dem Lagrange-Polynom, weist einen Restfehler (4.8) auf. Wenn die Funktionswerte y i an Interpolationsknoten x i werden ungefähr mit dem gleichen absoluten Fehler angegeben, dann statt genauer Wert ein ungefährer Wert wird berechnet, und

Dabei ist der rechnerische absolute Fehler des Lagrange-Interpolationspolynoms. Schließlich haben wir die folgende Schätzung des Gesamtfehlers des Näherungswertes.

Insbesondere die Lagrange-Polynome ersten und zweiten Grades haben die Form

und ihre Gesamtfehler am Punkt x *

Es gibt andere Formen, dasselbe Interpolationspolynom (4.1) zu schreiben, zum Beispiel die unten betrachtete Newton-Interpolationsformel mit geteilter Differenz und ihre Varianten. Mit genauen Berechnungen können die Werte ermittelt werden Pn(x *), die durch verschiedene Interpolationsformeln erhalten wurden, die aus denselben Knoten erstellt wurden, stimmen überein. Das Vorliegen eines Rechenfehlers führt zu einem Unterschied in den mit diesen Formeln erhaltenen Werten. Das Schreiben eines Polynoms in der Lagrange-Form führt in der Regel zu einem kleineren Rechenfehler.

Die Verwendung von Formeln zur Abschätzung der bei der Interpolation auftretenden Fehler hängt von der Problemstellung ab. Wenn beispielsweise die Anzahl der Knoten bekannt ist und die Funktion mit einer ausreichend großen Anzahl gültiger Vorzeichen angegeben ist, können wir die Aufgabe der Berechnung stellen f(x*) mit höchstmöglicher Genauigkeit. Wenn dagegen die Anzahl der richtigen Vorzeichen klein und die Anzahl der Knoten groß ist, können wir das Problem der Berechnung stellen f(x*) mit der Genauigkeit, die der Tabellenwert der Funktion zulässt, und um dieses Problem zu lösen, können sowohl eine Verdünnung als auch eine Verdichtung der Tabelle erforderlich sein.

§4.3. Getrennte Unterschiede und ihre Eigenschaften.

Der Begriff einer geteilten Differenz ist ein verallgemeinerter Begriff einer Ableitung. An den Punkten seien x 0 , x 1 ,…x n die Werte der Funktionen f(x 0), f(x 1),…,f(x n). Geteilte Differenzen erster Ordnung werden durch die Gleichheiten definiert

geteilte Unterschiede zweiter Ordnung - Gleichheiten,

und die geteilten Unterschiede k Ordnung werden durch die folgende rekursive Formel bestimmt:

Die geteilten Differenzen werden normalerweise in einer Tabelle wie dieser platziert:

x i	f(xi)	Geteilte Unterschiede
1. Ordnung	II. Ordnung	III. Ordnung	IV-Bestellung
x 0	y 0
		F
x 1	Jahr 1		F
		F		F
x 2	y2		F		F
		F		F
x 3	Jahr 3		F
		F
x 4	Jahr 4

Betrachten Sie die folgenden Eigenschaften geteilter Differenzen.

1. Geteilte Differenzen aller Ordnungen sind lineare Kombinationen von Werten f(xi), d.h. es gilt folgende Formel:

Beweisen wir die Gültigkeit dieser Formel durch Induktion über die Ordnung der Differenzen. Für Unterschiede erster Ordnung

Formel (4.12) ist gültig. Nehmen wir nun an, dass es für alle Ordnungsunterschiede gilt.

Dann nach (4.11) und (4.12) für Ordnungsunterschiede k=n+1 wir haben

Begriffe enthalten f(x0) Und f(x n +1), über das erforderliche Formular verfügen. Betrachten Sie die Begriffe, die enthalten f(xi), i=1, 2, …,n. Es gibt zwei solcher Terme – aus der ersten und zweiten Summe:

diese. Formel (4.12) gilt für die Ordnungsdifferenz k=n+1, der Beweis ist vollständig.

2. Die geteilte Differenz ist eine symmetrische Funktion ihrer Argumente x 0 , x 1 ,…x n (d. h. sie ändert sich bei keiner Permutation):

Diese Eigenschaft folgt direkt aus Gleichheit (4.12).

3. Einfache Verbindung der geteilten Differenz F und Ableitung f(n)(x) gibt den folgenden Satz.

Die Knoten x 0 , x 1 ,…x n gehören zum Segment und Funktion f(x) hat eine stetige Ableitung der Ordnung P. Dann gibt es so einen Punkt xО, Was

Beweisen wir zunächst die Gültigkeit der Beziehung

Nach (4.12) lautet der Ausdruck in eckigen Klammern

F.

Aus Vergleich (4.14) mit Ausdruck (4.7) für den Restterm R n (x)=f(x)-L n (x) erhalten wir (4.13), ist der Satz bewiesen.

Aus diesem Satz folgt eine einfache Folgerung. Für Polynom P Abschluss

f(x) = a 0 x n +a 1 x n -1 +…a n

Auftragsableitung P offensichtlich gibt es das

und Beziehung (4.13) gibt den Wert für die geteilte Differenz an

Also für jedes Polynom mit Grad P geteilte Auftragsunterschiede P sind gleich einem konstanten Wert – dem Koeffizienten am höchsten Grad des Polynoms. Getrennte Differenzen höherer Ordnung
(mehr P) sind offensichtlich gleich Null. Diese Schlussfolgerung ist jedoch nur dann gültig, wenn für die geteilten Differenzen kein Rechenfehler vorliegt.

§4.4. Newtons Interpolationspolynom mit geteilten Differenzen

Wir schreiben das Lagrange-Interpolationspolynom in der folgenden Form:

Wo L 0 (x) \u003d f (x 0) \u003d y 0, A L k (x) ist das Lagrange-Interpolationspolynom vom Grad k, durch Knoten aufgebaut x 0 , x 1 , …, x k. Dann gibt es ein Polynom vom Grad k, deren Wurzeln Punkte sind x 0 , x 1 , …, x k -1. Daher kann es faktorisiert werden

wobei Ak eine Konstante ist.

Gemäß (4.14) erhalten wir

Durch den Vergleich von (4.16) und (4.17) erhalten wir, dass auch (4.15) die Form annimmt

das sogenannte Newtonsche Interpolationspolynom mit geteilten Differenzen.

Diese Art der Aufzeichnung des Interpolationspolynoms ist visueller (das Hinzufügen eines Knotens entspricht dem Auftreten eines Termes) und ermöglicht es Ihnen, die Analogie der durchgeführten Konstruktionen mit den Hauptkonstruktionen der mathematischen Analyse besser zu verfolgen.

Der Restfehler des Newton-Interpolationspolynoms wird durch die Formel (4.8) ausgedrückt, kann aber unter Berücksichtigung von (4.13) auch in einer anderen Form geschrieben werden

diese. Der Restfehler kann anhand des Moduls des ersten verworfenen Termes im Polynom geschätzt werden N n (x *).

Rechenfehler Nn(x*) bestimmt durch die Fehler der geteilten Differenzen. Interpolationsknoten, die dem interpolierten Wert am nächsten liegen X *, hat einen größeren Einfluss auf das Interpolationspolynom, das weiter liegt - weniger. Daher empfiehlt es sich, wenn möglich, z x0 Und x 1 nimm es, zu kommen X * Interpolationsknoten und führen Sie zunächst eine lineare Interpolation über diese Knoten durch. Ziehen Sie dann nach und nach die folgenden Knoten an, sodass sie relativ dazu möglichst symmetrisch sind X *, bis der nächste Modulo-Term kleiner als der absolute Fehler der darin enthaltenen geteilten Differenz ist.