In der numerischen Analyse ist polynomische Interpolation die Interpolation einer gegebenen Datei durch ein Polynom: In Anbetracht einiger Punkte, finden Sie ein Polynom, das genau durch diese Punkte geht.

Anwendungen

Polynome können verwendet werden, um mehr komplizierten Kurven, zum Beispiel, den Gestalten von Briefen in der Typografie in Anbetracht einiger Punkte näher zu kommen. Eine relevante Anwendung ist die Einschätzung des natürlichen Logarithmus und der trigonometrischen Funktionen: Picken Sie einige bekannte Datenpunkte auf, schaffen Sie eine Nachschlagetabelle, und interpolieren Sie zwischen jenen Datenpunkten. Das läuft auf bedeutsam schnellere Berechnung hinaus. Polynomische Interpolation bildet auch die Basis für Algorithmen in der numerischen Quadratur und den numerischen gewöhnlichen Differenzialgleichungen.

Polynomische Interpolation ist auch notwendig, um subquadratische Multiplikation und Quadrieren wie Multiplikation von Karatsuba und Toom-Koch-Multiplikation durchzuführen, wo eine Interpolation durch Punkte auf einem Polynom, das das Produkt definiert, das Produkt selbst nachgibt. Zum Beispiel gegeben = f (x) = Axt + Axt +... und b = g (x) = bx + bx +... dann ist das Produkt ab zu W (x) = f (x) g (x) gleichwertig. Die Entdeckung von Punkten entlang W (x) durch das Auswechseln x für kleine Werte in f (x) und g (x) Erträge weist auf der Kurve hin. Auf jenen Punkten gestützte Interpolation wird die Begriffe von W (x) und nachher dem Produkt ab nachgeben. Im Fall von der Karatsuba Multiplikation ist diese Technik wesentlich schneller als quadratische Multiplikation sogar für bescheiden-große Eingänge. Das, ist wenn durchgeführt, in der parallelen Hardware besonders wahr.

Definition

In Anbetracht einer Reihe von n + 1 Datenpunkte (x y), wo keine zwei x dasselbe sind, sucht man nach einem Polynom p vom Grad am grössten Teil von n mit dem Eigentum

:

Der unisolvence Lehrsatz stellt fest, dass solch ein Polynom p besteht und einzigartig ist, und durch die Matrix von Vandermonde, wie beschrieben, unten bewiesen werden kann.

Der Lehrsatz stellt fest, dass für n+1 Interpolationsknoten (x) polynomische Interpolation eine geradlinige Bijektion definiert

:

wo der Vektorraum von Polynomen (definiert auf jedem Zwischenraum ist, der die Knoten enthält) vom Grad am grössten Teil von n.

Das Konstruieren des Interpolationspolynoms

Nehmen Sie an, dass das Interpolationspolynom in der Form ist

:

Die Behauptung, dass p die Datenpunkte interpoliert, bedeutet das

:

Wenn wir Gleichung (1) in hier einsetzen, bekommen wir ein System von geradlinigen Gleichungen in den Koeffizienten. Das System in der Matrixvektor-Form liest

:

x_0^n & X_0^ {n-1} & X_0^ {n-2} & \ldots & x_0 & 1 \\

x_1^n & X_1^ {n-1} & X_1^ {n-2} & \ldots & x_1 & 1 \\

\vdots & \vdots & \vdots & & \vdots & \vdots \\

x_n^n & X_n^ {n-1} & X_n^ {n-2} & \ldots & x_n & 1

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

a_n \\

a_ {n-1} \\

\vdots \\

a_0

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

y_0 \\

y_1 \\

\vdots \\

y_n

\end {bmatrix}.</Mathematik>

Wir müssen dieses System lösen für, den interpolant zu bauen, Die Matrix wird links allgemein eine Matrix von Vandermonde genannt.

Die Bedingungszahl der Matrix von Vandermonde kann groß sein, große Fehler verursachend, wenn sie die Koeffizienten schätzt, wenn das Gleichungssystem mit der Beseitigung von Gaussian gelöst wird.

Mehrere Autoren haben deshalb Algorithmen vorgeschlagen, die die Struktur der Matrix von Vandermonde ausnutzen, um numerisch stabile Lösungen in Operationen statt des erforderlichen durch die Beseitigung von Gaussian zu schätzen. Diese Methoden verlassen sich auf das Konstruieren zuerst einer Interpolation von Newton des Polynoms und dann Umwandelns davon zur Monom-Form oben.

Einzigartigkeit des interpolierenden Polynoms

Beweis 1

Nehmen Sie an, dass wir durch n + 1 Datenpunkte mit höchstens n Grad-Polynom p (x) interpolieren (wir brauchen mindestens n + 1 datapoints, oder das Polynom für nicht völlig gelöst werden kann). Nehmen Sie an, dass auch ein anderes Polynom auch des Grads am grössten Teil von n besteht, der auch den n + 1 Punkte interpoliert; nennen Sie es q (x).

In Betracht ziehen. Wir, wissen

1. r (x) ist ein Polynom
2. r (x) hat Grad am grössten Teil von n seitdem und sind nicht höher als das, und wir ziehen sie gerade ab.
3. Am n + 1 Datenpunkte. Deshalb r (x) hat n + 1 Wurzeln.

Aber r (x) ist ein n Grad-Polynom (oder weniger)! Es hat eine Wurzel zu viele.

Formell, wenn ein Nichtnullpolynom ist, muss es writable als sein.

Durch distributivity der n + multipliziert 1 x's zusammen, um, d. h. ein Grad höher zu machen, als das Maximum, das wir setzen.

So kann der einzige Weg r (x) bestehen, ist wenn r (x) = 0.

:

So (der jedes Polynom sein konnte, so lange es die Punkte interpoliert) ist damit identisch und ist einzigartig.

Beweis 2

In Anbetracht der Matrix von Vandermonde, die oben verwendet ist, um den interpolant zu bauen, können wir das System aufstellen

:

Wir wollen beweisen, dass V nichtsingulär ist. Gegebener

:

seit dem n + sind 1 Punkte verschieden, die Determinante kann nicht Null sein, wie nie Null ist, deshalb V ist nichtsingulär, und das System hat eine einzigartige Lösung.

Auf jede Weise bedeutet das das, egal was Methode wir verwenden, um unsere Interpolation zu tun: Direkt, Fugenbrett, lagrange usw., (das Annehmen können wir alle unsere Berechnungen vollkommen tun), werden wir immer dasselbe Polynom bekommen.

Non-Vandermonde Lösungen

Wir versuchen, unser einzigartiges Interpolationspolynom im Vektorraum von Polynomen des Grads n zu bauen. Wenn man eine Monom-Basis verwendet, weil wir die Matrix von Vandermonde lösen müssen, um die Koeffizienten für das Interpolationspolynom zu bauen. Das kann eine sehr kostspielige Operation (wie aufgezählt, in Uhr-Zyklen eines Computers sein, der versucht, den Job zu tun). Durch die Auswahl einer anderen Basis, weil wir die Berechnung der Koeffizienten vereinfachen können, aber dann müssen wir zusätzliche Berechnungen tun, wenn wir das Interpolationspolynom in Bezug auf eine Monom-Basis ausdrücken wollen.

Eine Methode ist zu schreiben, dass das Interpolationspolynom im Newton bildet und die Methode von geteilten Unterschieden verwendet, die Koeffizienten, z.B der Algorithmus von Neville zu bauen. Die Kosten sind O Operationen, während Beseitigung von Gaussian O Operationen kostet. Außerdem müssen Sie nur O Extraarbeit tun, wenn ein Extrapunkt zur Datei hinzugefügt wird, während für die anderen Methoden Sie die ganze Berechnung nochmals tun müssen.

Eine andere Methode ist, die Form von Lagrange des Interpolationspolynoms zu verwenden. Die resultierende Formel zeigt sofort, dass das Interpolationspolynom unter den Bedingungen besteht, hat im obengenannten Lehrsatz festgesetzt. Formel von Lagrange soll der Formel von Vandermorde bevorzugt werden, wenn wir uns für die Computerwissenschaft der Koeffizienten des Polynoms, aber in der Computerwissenschaft des Werts in einem gegebenen x nicht in der ursprünglichen Datei nicht interessieren. In diesem Fall können wir Kompliziertheit auf O reduzieren.

Die Form von Bernstein wurde in einem konstruktiven Beweis des Annäherungslehrsatzes von Weierstrass von Bernstein verwendet und hat heutzutage große Wichtigkeit in der Computergrafik in der Form von Kurven von Bézier gewonnen.

Interpolationsfehler

Wenn

wir eine gegebene Funktion f durch ein Polynom des Grads n an den Knoten x..., x interpolieren, bekommen wir den Fehler

:wo:

ist die Notation für geteilte Unterschiede. Wenn f n + 1mal unaufhörlich differentiable auf dem kleinsten Zwischenraum I ist, der die Knoten x und x dann enthält, können wir den Fehler in der Form von Lagrange als schreiben

:

für einige in mir, gemäß dem Mittelwertlehrsatz für geteilte Unterschiede. So ist der Rest-Begriff in der Form von Lagrange des Lehrsatzes von Taylor ein spezieller Fall des Interpolationsfehlers, wenn alle Interpolationsknoten x identisch sind.

Im Fall von Interpolationsknoten ebenso unter Drogeneinfluss, hieraus folgt dass der Interpolationsfehler O ist. Jedoch gibt das keine Information darüber nach, was wenn geschieht. Diese Frage wird in den Abteilungskonvergenz-Eigenschaften behandelt.

Der obengenannte gebundene Fehler deutet an, die Interpolationspunkte x solch dass das Produkt | Π zu wählen (x &minus; x) | ist so klein wie möglich. Die Knoten von Tschebyscheff erreichen das.

Konstanten von Lebesgue

:See der Hauptartikel: Unveränderlicher Lebesgue.

Wir befestigen die Interpolationsknoten x..., x und einen Zwischenraum [a, b], alle Interpolationsknoten enthaltend. Der Prozess der Interpolation stellt die Funktion f zu einem Polynom p kartografisch dar. Das definiert X vom Raum C ([a, b]) aller dauernden Funktionen auf [a, b] zu sich kartografisch darzustellen. Die Karte X ist geradlinig, und es ist ein Vorsprung auf dem Subraum Π Polynome des Grads n oder weniger.

Der Lebesgue unveränderliche L wird als die Maschinenbediener-Norm X definiert. Man hat (ein spezieller Fall des Lemmas von Lebesgue):

:

Mit anderen Worten ist das Interpolationspolynom höchstens ein Faktor (L + 1) schlechter als die bestmögliche Annäherung. Das weist darauf hin, dass wir nach einer Reihe von Interpolationsknoten das L klein suchen. Insbesondere wir haben für Knoten von Tschebyscheff:

:

Wir beschließen wieder, dass Knoten von Tschebyscheff eine sehr gute Wahl für die polynomische Interpolation sind, weil das Wachstum in n für gleich weit entfernte Knoten Exponential-ist. Jedoch sind jene Knoten nicht optimal.

Konvergenz-Eigenschaften

Es ist natürlich zu fragen, für welche Klassen von Funktionen und für welche Interpolationsknoten die Folge, Polynome zu interpolieren, zur interpolierten Funktion zusammenläuft, als der Grad n zur Unendlichkeit geht? Konvergenz kann unterschiedlich, z.B pointwise, Uniform oder in einer integrierten Norm verstanden werden.

Die Situation ist für gleich weit entfernte Knoten ziemlich schlecht, in dieser gleichförmigen Konvergenz wird für ungeheuer differentiable Funktionen nicht sogar versichert. Ein klassisches Beispiel, wegen Carl Runges, ist die Funktion f (x) = 1 / (1 + x) auf dem Zwischenraum [&minus;5, 5]. Der Interpolationsfehler || f &minus; p wächst ohne bestimmten als. Ein anderes Beispiel ist die Funktion f (x) = |x auf dem Zwischenraum [&minus;1, 1], für den die interpolierenden Polynome pointwise außer an den drei Punkten x = &minus;1, 0, und 1 nicht sogar zusammenlaufen.

Man könnte denken, dass bessere Konvergenz-Eigenschaften durch die Auswahl verschiedener Interpolationsknoten erhalten werden können. Der folgende Lehrsatz scheint, eine ziemlich ermutigende Antwort zu sein:

:For jede Funktion f (x) dauernd auf einem Zwischenraum [a, b] dort besteht ein Tisch von Knoten, für die die Folge, Polynome zu interpolieren, zu f (x) gleichförmig auf [a, b] zusammenläuft.

Beweis. Es ist klar, dass die Folge von Polynomen der besten Annäherung zu f (x) gleichförmig (wegen des Annäherungslehrsatzes von Weierstrass) zusammenläuft. Jetzt müssen wir nur zeigen, dass jeder mittels der Interpolation auf bestimmten Knoten erhalten werden kann. Aber das ist wegen eines speziellen Eigentums von Polynomen der besten vom Alternantensatz von Tschebyscheff bekannten Annäherung wahr. Spezifisch wissen wir, dass solche Polynome f (x) mindestens n+1 Zeiten durchschneiden sollten. Wenn wir die Punkte der Kreuzung als Interpolationsknoten wählen, erhalten wir das interpolierende Polynom, das mit dem besten Annäherungspolynom zusammenfällt.

Der Defekt dieser Methode besteht jedoch darin, dass Interpolationsknoten von neuem für jede neue Funktion f (x) berechnet werden sollten, aber der Algorithmus ist hart, numerisch durchgeführt zu werden. Dort besteht ein einzelner Tisch von Knoten, für welche die Folge, Polynome zu interpolieren, zu dauernder Funktion f (x) zusammenlaufen? Die Antwort ist leider negativ, wie sie durch den folgenden Lehrsatz festgestellt wird:

:For jeder Tisch von Knoten dort ist eine dauernde Funktion f (x) auf einem Zwischenraum [a, b], für den die Folge, Polynome zu interpolieren, auf [a, b] abweicht.

Der Beweis verwendet im Wesentlichen die tiefer bestimmte Bewertung von unveränderlichem Lebesgue, den wir oben definiert haben, um die Maschinenbediener-Norm X zu sein (wo X der Vorsprung-Maschinenbediener auf Π ist). Jetzt suchen wir einen Tisch von Knoten für der

:

Wegen des Banach-Steinhaus Lehrsatzes ist das nur möglich, wenn Normen X gleichförmig begrenzt werden, der nicht wahr sein kann, da wir das wissen

Zum Beispiel, wenn gleich weit entfernte Punkte als Interpolationsknoten gewählt werden, demonstriert die Funktion vom Phänomen von Runge Abschweifung solcher Interpolation. Bemerken Sie, dass diese Funktion nicht nur dauernd ist, aber sogar ungeheuer Zeiten differentiable auf [&minus;1, 1]. Für bessere Knoten von Tschebyscheff, jedoch, ist solch ein Beispiel viel härter, wegen des Lehrsatzes zu finden:

:For jede absolut dauernde Funktion auf [&minus;1, 1] die Folge, auf Knoten von Tschebyscheff gebaute Polynome zu interpolieren, läuft zu f (x) gleichförmig zusammen.

Zusammenhängende Konzepte

Das Phänomen von Runge zeigt, dass für hohe Werte von n das Interpolationspolynom wild zwischen den Datenpunkten schwingen kann. Dieses Problem wird durch den Gebrauch der Fugenbrett-Interpolation allgemein aufgelöst. Hier ist der interpolant nicht ein Polynom, aber ein Fugenbrett: eine Kette von mehreren Polynomen eines niedrigeren Grads.

Die Interpolation von periodischen Funktionen nach harmonischen Funktionen wird von Fourier vollbracht verwandeln sich. Das kann als eine Form der polynomischen Interpolation mit harmonischen Grundfunktionen gesehen werden, trigonometrische Interpolation und trigonometrisches Polynom zu sehen.

Interpolationsprobleme von Hermite sind diejenigen, wo nicht nur die Werte des Polynoms p an den Knoten gegeben werden, sondern auch alle Ableitungen bis zu einer gegebenen Ordnung. Das erweist sich, zu einem System von gleichzeitigen polynomischen Kongruenzen gleichwertig zu sein, und kann mittels des chinesischen Rest-Lehrsatzes für Polynome gelöst werden. Interpolation von Birkhoff ist eine weitere Generalisation, wo nur Ableitungen von einigen Ordnungen, nicht notwendigerweise alle Ordnungen von 0 bis einen k vorgeschrieben werden.

Kollokationsmethoden für die Lösung von unterschiedlichen und Integralgleichungen basieren auf der polynomischen Interpolation.

Die Technik des vernünftigen Funktionsmodellierens ist eine Generalisation, die Verhältnisse von polynomischen Funktionen denkt.

Schließlich, multivariate Interpolation für höhere Dimensionen.

Referenzen

• Kendell A. Atkinson (1988). Eine Einführung in die Numerische Analyse (2. Hrsg.), Kapitel 3. John Wiley and Sons. Internationale Standardbuchnummer 0-471-50023-2.
• Sergei N. Bernstein (1912) Annäherung von Sur l'ordre de la meilleure setzt des fonctions par les polynômes de degré donné fort. Mem. Acad. Roy. Belg. 4, 1-104.
• L. Brutman (1997), Lebesgue fungiert für die polynomische Interpolation — ein Überblick, Ann. Numer. Mathematik. 4, 111-127.
• Georg Faber (1912), Über sterben interpolatorische Darstellung stetiger Funktionen, Deutsche Mathematik. Jahr. 23, 192-210.
• M.J.D. Powell (1981). Annäherungstheorie und Methoden, Kapitel 4. Universität von Cambridge Presse. Internationale Standardbuchnummer 0-521-29514-9.
• Michelle Schatzman (2002). Numerische Analyse: Eine Mathematische Einführung, Kapitel 4. Clarendon Press, Oxford. Internationale Standardbuchnummer 0-19-850279-6.
• Endre Süli und David Mayers (2003). Eine Einführung in die Numerische Analyse, Kapitel 6. Universität von Cambridge Presse. Internationale Standardbuchnummer 0-521-00794-1.
• G. Alistair Watson (1980). Annäherungstheorie und Numerische Methoden. John Wiley. Internationale Standardbuchnummer 0-471-27706-1.

Außenverbindungen

• ALGLIB hat Durchführungen in C ++ / C# / VBA / Pascal.
• GSL hat einen polynomischen Interpolationscode in C
• Polynom durch Stephen Wolfram, das Demonstrationsprojekt von Wolfram interpolierend.